원문 내용입니다. http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf 의 10페이지. normal case operation 이하에서 확인하실 수 있습니다.
A backup i accepts the PRE-PREPARE message provided (in addition to the
conditions above) it has not accepted a PRE-PREPARE for view v and sequence
number n containing a different digest. If a backup i accepts the PRE-PREPARE
and it has request m in its log, it enters the prepare phase by multicasting a
h<PREPARE, v, n, D(m)>, iiαi message with m’s digest to all other replicas;
in addition, it adds both the PRE-PREPARE and PREPARE messages to its log. Otherwise,
it does nothing.
The PREPARE message signals that the backup agreed to assign
sequence number n to m in view v. We say that a request is pre-prepared at a
particular replica if the replica sent a PRE-PREPARE or PREPARE message for the
request.
Pre-prepare 메세지를 확인한 backup 노드 i는 메세지에 문제가 없으면 prepare 메세지를 생성해 네트워크의 모든 노드에게 전송합니다. Pre-prepare 메세지를 검증한 결과 옳지 않으면 prepare 메세지 자체가 발생하지 않습니다.
Then each replica collects messages until it has a quorum certificate with the
PRE-PREPARE and 2 f matching PREPARE messages for sequence number n, view
v, and request m. We call this certificate the prepared certificate and we say
that the replica prepared the request.
quorum certificate에서 quorum은 정족수를 말합니다. 논문 서두에 The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability라고 말했으므로, 비잔틴 노드의 개수가 f개라면 합의를 이루기 위한 정족수는 2f+1이 되겠죠.
Prepare가 2f인 이유는 검증하는 자기 자신을 제외했기 때문에 2f+1의 정족수에서 1을 뺀 것입니다. 애초에 Pre-prepare 메세지가 검증되지 않으면 Prepare 메세지를 보내지도 않기 때문에, 사실상 Prepare 메세지만 제대로 받았다면 prepare certificate상태가 되겠죠. 하지만 논문에서는 quorum certificate with the pre-prepare와 2f matching prepare message를 동시에 언급했기에 글에서도 두 가지를 동시에 적어 두었습니다. 논문에서 pre-prepare와 prepare 검증이 순차적으로 진행되는지는 확인할 수 없었기에 [4]에서처럼 "수집한 Pre-prepare 메시지 개수가 2f+1개이고 Prepare 메시지가 2f개 이상인 경우 "prepared certificate"라고 부르며" 라고 이해했습니다.
원문을 직접 확인하셨다고 했는데, 어떤 원문인지 알 수 있을까요? PBFT를 설명하는 다른 논문이거나, 같은 논문에서도 다른 설명을 보았을 수 있을 것 같습니다.
답변 감사합니다. 그러한 이유로 위 내용과 같이 서술하셨던 것이군요. 결론을 먼저 말씀드리자면 완전히 잘못 이해하셨습니다.
일단 제가 언급한 '직접 확인한 원문'은 작성자께서 참고하신 그 논문과 'CASTRO, M.AND LISKOV, B. 1999b. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), USENIX, New Orleans'을 말씀드린 것입니다. 후자는 PBFT가 최초로 제시된 논문이며 작성자께서 참고하신 논문의 레퍼에서도 해당 원문을 확인하실 수 있습니다.
본론으로 돌아가, 제가 문제 삼은 부분이 명백히 틀렸고 작성자께서 잘못 이해하셨다는 근거를 말씀드립니다.
애초에 Pre-prepare 메시지를 2f+1개 수집한다는 것이 말이 안 됩니다. Pre-prepare 메시지를 발생시켜 멀티캐스트하는 것은 프라이머리 노드 하나입니다. 모든 노드가 Pre-prepare 메시지를 멀티캐스트한다면 가능하겠지만, 프라이머리 노드 하나가 멀티캐스트 하는 이상 다른 백업 노드 중에서는 Pre-prepare 메시지를 2f+1개 수집할 수 없습니다.
'quorum certificate'에 대한 이해를 잘못 하셨을뿐만 아니라, 'quorum certificate with the PRE-PREPARE and 2f matching PREPARE messages for ~' 구문에 대해서도 잘못 해석하셨습니다.
우선 quorum이 정족수를 말하는 것은 맞습니다. 그러나 'quorum certificate'는 그저 어떤 상태를 이야기 하는 것이지 그것이 2f+1개의 특정 갯수를 의미하지 않습니다. 논문 중 이어서 나오는 내용도 읽어 보시면 아실겁니다.
또한 'quorum certificate with the PRE-PREPARE'와 '2f matching prepare message'로 잘못 끊어서 해석하셨습니다. 'quorum certificate'와 'with the PRE-PREPARE and 2f matching PREPARE message'로 끊으셨어야 합니다. 해석하자면 PRE-PREPARE' 메시지를 2f개의 PREPARE 메시지에 대조시킨다는 의미입니다. 해당 구문에 이어서 나오는 'for sequence number n, view v, and request m.' 구문을 참고하면 의미는 더 명확해질 것입니다. 백업 노드 본인이 받았던 PRE-PREPARE 메시지의 n, v, m 필드와 자신을 제외한 나머지 백업 노드로부터 받은 PREPARE 메시지들의 n, v, m 필드가 일치하는지 확인합니다. 조건을 만족하는 PREPARE 메시지가 2f개가 될 때까지 메시지를 수집합니다. 그러한 상황이 될 때 'quorum certificate'라는 상태가 되며, 이를 'prepared certificate'라고 부르겠다라는 의미입니다.
혹시나 작성자께서 원문에서 논란의 내용을 찾지 못하실까하여 원문의 내용도 복붙해놓겠습니다. 확인하시면 훨씬 이해가 잘 되실 겁니다.
제가 설명드린 내용이 옳다면 잘못 설명되었다고 본문에 명시하시는 것이 좋을 것 같습니다. 또 다른 누군가가 PBFT에 대해 공부할 때 혼란스러워하지 않기를 바라기 때문입니다.
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit
아아 맞네요. 제가 오해했습니다. 지적해주신 대로, Pre-prepare 상태를 모든 노드가 멀티캐스팅 하는 것은 불가능합니다. Pre-prepare 메세지는 최초에 요청받은 노드 - Primary Node - 하나가 네트워크에 발송하는 것이고, 그 노드가 보낸 메세지가 옳다고 검증될 경우 다른 노드가 prepare 메세지를 네트워크에 멀티캐스팅 하는 절차로 진행되는 것이 맞습니다. 마찬가지로 certificate 구문도 지적해주신 내용이 옳습니다.
내용 오류를 바로잡아 주셔서 감사드립니다. 안타깝게도 스팀잇에 게시한 지 일주일이 이미 지나서, 본문 수정은 현재 불가능한 상태입니다. 올바른 내용을 적어 주신 댓글이 PBFT 알고리즘을 공부할 때 혼란을 방지할 수 있었으면 좋겠습니다. 잘못된 내용전달을 바로잡아 주셔서 다시 한 번 감사드립니다.
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit