Practical Byzantine Fault Tolerance

이전시간에 우리는 비잔틴 장군 문제(Byzantine General Problems)를 해결하기 위해 고안된 BFT에 대해서 다뤘다.

짧게 이야기 하자면, BFT는 다음과 같다.

 

1. 부대안에 첩자가 있을 것으로 예상하고 있으나 누구인지 모르는 상태에서 부대를 신뢰할 수 있도록 하는 합의과정.

2. 실제 비잔티움 제국에서 일어난 사건을 바탕으로 만들어진 용어로, 분산 데이터를 다루는 네트워크에서 활용 가능하다

3. 어떠한 합의에 있어서, 전체 인원의 2/3 이상이 동의를 할 경우 수렴을 하는 원리로 동작한다.

4. 비동기 네트워크에서는 그대로 활용하기에 여러 한계점이 있다.(실질적이지 못하다)

 

이렇게 비동기 네트워크에서 BFT를 활용하기 위해, PBFT, ABFT 등 다양한 방법이 제안되었다.

그 중 많은 블록체인 네트워크에서 사용중인 PBFT를 이번시간에 다뤄본다.

 

(대부분 블로그에서는 논문을 읽지도 않고, 글을 쓰는 경우가 많이 보입니다. 그래서 '어떠한 조건만 맞추면 합의에 도달한다' 라고 서술 되어있는 곳이 많은데, 조건이 정확히 무엇인지, 각 메세지가 어떤 의미를 담고 있는지를 확실하게 알아야 할 필요가 있다고 생각됩니다. 그래서 조금 더 '동작 원리' 측면에서 상세하게 알아보도록 하겠습니다)

Practical Byzantine Fault Tolerance(실질적 비잔틴 장애 허용)?

- 비동기 네트워크(Asynchronous Network)에서 합의(Consensus)에 도출하기 위해 제안됨

- 블록체인 네트워크에서 BFT 기반은 대부분 pBFT[1]를 활용하고 있음

- 쿼리 결과를 요청하는 Client, 쿼리 메세지를 전파하는 Primary Node(0번 노드), 각 쿼리를 실행하고 결과를 반환하는 Replica(1, 2, 3번 노드)로 구성되어 있음

- 3 step으로 나뉘어져서 동작함

Figure 1. Byzantine Generals Problem Image 

 

 

pBFT 동작 원리

비동기 네트워크(Asynchronous Network)에서, 각 단계별 조건을 만족할 경우 합의 완료(개인적 수렴)

 

1. Request - Client가 Primary Node에게 쿼리 결과를 요청하는 메세지를 전송함. <Request, o, t, c>s

o : operation(동작), t : time stamp(쿼리 요청 시간 - Client 기준),  c : client(클라이언트 이름), s : signature(서명, 자신임을 인증 즉, authentication)

 

2. Pre-prepare - Primary Node가 각 Replica에게 전송받은 메세지를 Broadcast함. <<Pre-prepare, v, n, d>, m>

v : view(메세지 전송), n : sequence number(메세지 번호, 메세지가 여러개로 오는 경우 이들의 순서를 정하기 위함), d : digest(메세지 해시, 메세지의 값 변조 방지), m : message(클라이언트가 요청한 메세지)

 

3. Prepare - Replica가 받은 메세지를 서로 교환함. 네트워크의 지연이나 예기치 못한 오류를 방지하고, 모두가 같은 메세지를 가지고 있음을 알기 위한 단계. <Prepare, v, n, d, i>s

i : replica number(자신의 이름, Primary Node에게 전파받은 Client의 메세지가 다른 Replica가 받은 메세지와 동일한지 확인하기 위함)

 

Primary Node와 Replica가 2f 개의 동일한 Prepare를 가지고 있으면(pre-prepare 메세지를 포함하여 2f + 1개) 각 Node는 prepared 상태(Prepared Certificate)가 된다.

동일한 Prepare 및 Pre-prepare란 2f+1개의 메시지의 (v, n, d)이 같다는 것을 의미한다. 

자신의 Prepared Certificate가 true일 때, Commit Phase로 들어간다.

 

4. Commit - 모든 Node가 동일한 메세지에 대해 Prepared 되었는지 검증. <Commit, v, n, D(m), i,>s

D(m) : 메세지 Digest [논문 상으로는 d와 D(m)이 같이 서술되어 있습니다]

Commit은 Committed와 Committed Local로 구분된다.

Committed는 f+1의 non-faulty node가 Prepared 상태임을 만족할 때 True이다.

Committed Local은 2f+1의 commit을 받았을 때 True이다.

결론적으로, Committed local은 Committed 이후에 발생하며 최종적인 상태라고 볼 수 있다.

 

5. Reply - 각 Node가 요청 받은 쿼리를 실행하고 그 결과를 Client에게 반환. <Reply, v, t, c, i, r>s

r : result of execution(실행 결과)

 

Committed-Local을 만족한 Node는 해당 쿼리를 실행하고 이를 Client에게 반환한다.

Client는 f+1개의 동일한 응답을 받으면, 올바르게 동작한 것으로 확신 할 수 있다.

 

 

정리하면서

pBFT는 현재 많은 블록체인 네트워크에서 활용중인 합의 알고리즘이다. 빠른 합의 속도와 Liveness를 궁극적인 목적으로 가지고 있지만, pBFT도 그 만의 한계점이 존재한다.

우선, Replica가 무수히 많이 늘어나면, 합의 속도가 비약적으로 증가한다는 것이고, 또한 Liveness를 목적으로 했기에, Safety Attack인 Double Spending, Censorship과 같은 문제가 일어날 수 있다. 뿐만 아니라, 2f+1 이상의 Node가 카르텔(Cartel)을 형성하여 네트워크를 조작하는 경우도 발생 가능하다는 한계점이 존재한다.

DPoS는 이러한 pBFT의 한계점을 해결 가능한 합의 알고리즘으로, 뛰어난 트랜잭션 처리 속도 및 블록 생성 속도로 많은 사람들의 주목을 받고 있다.

 

 

다음 시간에는 BFT 기반 DPoS에 대해서 서술하도록 하겠다. 

 

 

[1] PBFT : pmg.csail.mit.edu/papers/osdi99.pdf