[논문 리뷰] PBFT: Practical Byzantine Fault Tolerance

Authors : Miguel Castro, Barbara Liskov

Source : OSDI 1999

 

[Background]

• 네트워크 환경 구분 3가지
   : 메세지 송수신 간의 딜레이를 기준으로 (1) Synchronous, (2) Partially synchronous, (3) Asynchronous 로 구분함.
• Byzantine Fault Problem 을 해결하기 위해서는 Safety 와 Liveness 를 만족시켜야함. 
   : Safety - replicated state machines 들이 linearizability를 만족하는 것. 동일한 인풋이 주어지면 모든 노드들이 같은 결과에 도달하는 것. 마치 하나의 머신이 요청을 atomic 하게 처리하는 것과 같은 효과를 내야함. 
   : Liveness - 최종적으로 아웃풋을 내야함.
• FLP impossibility 
   : Asynchronous 한 네트워크 환경에서 Safety, Liveness 를 동시에 만족하는 deterministic 한 알고리즘은 존재하지 않는다는 사실이 증명됨 (Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382.)
• Quorum For Asynchronous Consensus
  : malicious 한 노드 개수를 f 개라고 했을 때, 정상적인 노드가 2f + 1 개 이상 있어야 합의에 도달할 수 있음. (fail-stop node가 f개라고 하면 f+1개 이상 있어야 합의 도달 가능) (Bracha, Gabriel, and Sam Toueg. "Asynchronous consensus and broadcast protocols." Journal of the ACM (JACM) 32.4 (1985): 824-840.)

 

[Purpose]

• 이전의 연구에서는 synchrony 를 가정하거나, asynchonous 하더라도 실제 사용하기에 속도가 너무 느렸음.따라서 asynchronous 한 네트워크 환경에서 적용 가능한 방안을 제시.
• Safety는 asynchrony 상황을 가정, Liveness는 weak synchronous assumption (partial synchrony) 가정함. (둘다 asynchronous 라고 가정하면 FLP impossibility 에 의해 해결이 불가능하기 때문.)

[Algorithm]

(필요조건)

- 각 노드들은 deterministic 해야함. (같은 인풋 -> 동일한 결과)

- 각 노드들의 start state 가 동일해야 함.

(알고리즘 간단버전)

1. 클라이언트가 primary 노드에게 요청 \(m\) 을 보냄.
2. primary 노드가 나머지 backup 노드들에게 request를 전파함 (pre-prepare)
3. 각 노드들은 요청을 실행하고, 클라이언트들에게 응답
4. 클라이어트는 f+1 개 이상의 동일한 응답을 받으면, 정상적인 응답이라고 판단.

(정상상황)

1. primary 노드가 \(<<PRE-PREPARE, n, v, H(m)>_{\sigma_p}, m>\) 을 만들어서 전파. (v 는 view no, n은 sequence no, \(\sigma\)는 서명, \(H\)는 해시함수)
2. pre-prepare 메세지를 받은 backup 노드들은 해당 메세지의 서명이 올바른지, 같은 view 인지, sequence 번호가 올바른지 등을 검증한 후 문제가 없으면 \(<PREPARE, n, v, H(m), i)>_{\sigma_i}\) 를 전파.
3. 2f+1 개의 prepare 메세지를 받으면, pre-prepare 메세지와 검증 후에 log로 기록한다. 이 후 \(<COMMIT, n, v, H(m), i>_{\sigma_i}\) 메세지를 전파한다.
4. 2f+1 개의 commit 메세지를 받으면, 요청을 실행시키고 클라이언트에게 최종적으로 응답한다. (단, 하나의 요청에 한 번만 응답하는 것을 보장하기 위해, 현재 실행시키려는 요청이 가장 최근 응답보다 과거에 발생한 경우에는 경우에는 실행시키지 않고 버린다.) 

(비정상상황)

1. primary 노드가 제대로 동작하지 않는 경우를 대비. 
2. 노드마다 순서대로 번호가 정해져 있는데, primary 노드 역할은 view 가 변하면서 순서대로 돌아감.
3. 각 노드마다 timeout 이 발생하면 멈추고 합의를 진행하지 않음(pre-prepare, prepare, commit 메세지를 받지 않음.) View-change 단계에 진입하여, \(<VIEW-CHANGE, v+1, n, C, P, i>_{\sigma_i}\) 메세지를 전파. (n은 lastest stable checkpoint s에 해당하는 seq 번호, C는 s에 대한 2f+1개의 valid messages, P는 s 이후의 사용자 요청에 대한 valid한 pre-prepare 메세지들(2f+1개의 prepare 응답을 받은 것만 해당)), timeout이 발생하지 않더라도 f+1개의 view-change 메세지를 받으면 view-change 단계에 진입함.
4. 새로운 primary 노드가 2f+1 개의 view-change 메세지를 받으면, \(<NEW-VIEW, v+1, V, O>_{\sigma_p}\) 메세지를 전파함. (V는 다른 노드들로부터 받은 view-change 메세지, O는 P들을 다 종합해서 가장 낮은 stable checkpoint 번호와 가장 높은 번호 사이에 있는 pre-prepare 메세지들. 다른 노드들과 sync를 맞추기 위함.)
5. new-view 메세지를 받으면 v+1 번째 view로 진입
6. new-view 메세지를 받은 노드들은 pre-prepare 메세지를 확인하고 prepare 메세지를 전파함. 사용자 요청을 중복 실행하는 것을 방지하기 위해, log를 확인하여 실행 결과를 가져오거나, 다른 노드들에게 요청함.

 

 

(리뷰)

- 1/3 이상의 노드를 비정상적으로 조작하지 않는한, safety와 liveness 가 깨지지 않는다는 것을 증명한 논문.

- 요청 처리 시간이 길어지면, exactly-once semantics 전략 때문에 추가 요청들을 실행시키지 않고 계속 버려야한다. 즉 순차처리를 강요하고 있는데, 앞선 요청이 끝나지 않은 상태에서는 메세지 합의가 더 빨리 진행되더라도 실행시키지 않는다. (linearizability) DoS 에 취약함! 이 부분을 optimistic하게 더 개선할 수 있지 않을까? 언제 도착할 지 모르기 때문에 힘들듯..

- primary 노드가 악의적으로 사용자 요청을 조작하여 전파하는 경우 -> 클라이언트가 자신의 요청에 대한 서명이나 MAC 등을 사용해야함.

- 새로운 노드가 참가하면, view-change 를 위해 모든 노드에게 그 사실을 전파해야함. Dynamic 하게 노드들이 참가하고 빠지는 환경에서는 추가적인 작업이 필요함.