[Blockchain] PBFT(Practical Byzantine Fault Tolerance) 합의 알고리즘이란?

비트코인이 세상에 등장한지 13년의 시간이 지났습니다. 비트코인이 나오기 이전에도 분산원장기술은 존재했었고, 중앙 분산 원장 시스템에서 각 노드간 합의 알고리즘은 존재했었습니다. 하지만 비트코인이 보여준 합의 알고리즘인 PoW(작업증명)는 Safety와 liveness를 동시에 만족시키면서 합의를 이뤄 가는 혁신적인 방법으로 주목을 받게 됩니다. 특별하게 비트코인에서 사용된 합의 알고리즘은 Nakamoto Consensus라고 불립니다. 이전에는 존재하지 않던 방식으로 분산 원장 시스템의 합의 알고리즘을 구현해냅니다. 

비트코인이 출현하기 전 분산 원장 시스템에서 쓰이던 합의 알고리즘은 비잔틴 장군 문제를 해결하는 방식으로 고안되었습니다. 즉, 분산 네트워크에서 악의적인 사용자가 존재하는 상황에서 각 노드가 합의에 이르러 네트워크를 유지하기 위해서 필요한 방법이 바로 Byzantine Fault Tolerance, BFT입니다. 하지만 비동기 방법을 채택하는 블록체인에서는 또 다른 방법이 필요합니다. 그래서 고안된 방법이 비잔틴 장군문제가 발생하는 비동기식 네트워크에서 합의에 이를 수 있는 방법인 Practical Byzantine Falut Tolerance, PBFT 알고리즘 입니다.

 

 

합의 알고리즘은 먼저 2가지 속성을 가져야 합니다. 바로 Safety와 Liveness 속성입니다. 

 

 

Safety는 문제없는 노드들이 모여있다면 절대로 잘못된 합의에 이르지 않는다는 개념입니다. 모든 정상적인 참여자들은 합의에 동의해야 하고, 정상적인 상태를 유지할 수 있어야 합니다.

Liveness는 문제 없는 정상적인 노드들은 반드시 합의에 도달해야 한다는 개념입니다. 항상 시스템이 살아있어야 하고, 결국 모든 참여자는 특정 합의에 동의해야만 합니다. 

 

 

FLP Impossibility

 

정상적인 노드들은 잘못된 합의에 도달해서는 안됩니다. 또한 정상적인 노드들은 반드시 합의에 도달할 수 있어야 합니다. 정상적인 노드들이 서로 다른 합의에 이르렀다는 것은 블록체인에서 새로운 분기가 생겼다는 말이 됩니다. 합의의 Safety가 보장이 안된 상태입니다. 또한 합의는 언젠가는 이뤄져야 하는데, 분산 원장 시스템에서는 노드들이 메세지를 주고 받으면서 자신의 상태를 변경시키게 됩니다. 각 노드들은 무한루프에 빠지지 않으면서 상태 변경이 종료되어야 합니다. 합의의 Liveness가 보장된다고 할 수 있습니다.  

 

 

기존 합의 알고리즘은 Safety를 Liveness보다 우선시 해서 개발하는 방향으로 진행되었습니다. 분산 원장 시스템에서 노드들이 모두 합의에 이르지는 못하더라도 일단 합의가 이뤄진다면 모든 노드가 동일한 데이터를 가지고 있어야 했습니다. Liveness를 희생하더라도 Safety를 보장하는 방식으로 말입니다. 

여기서 비트코인이 주목받은 이유가 등장합니다. 비트코인은 모든 거래를 수용하여 합의에 이르도록 하면서 Liveness를 보장했고, 확률적으로 Safety를 보장하는 방식으로 합의 알고리즘을 설계하였습니다. 모든 트랜잭션들은 체인에 연결되면서 길이가 가장 긴 체인이 가장 많은 해시 파워를 증명하면서 최종적으로 선택되는 방식으로 Safety를 보완합니다. 이미 연결된 블록의 트랜잭션들은 머클트리를 사용해 수정/변조가 안되게 제한합니다. 이를 Finality를 확보했다고 표현합니다. 예외적으로 51% Attack을 받을 수 있지만 기존 합의 알고리즘을 혁신적으로 개선한 모델로 주목을 받습니다.

문제는 동기 네트워크가 아닌 비동기 네트워크에서의 합의 알고리즘입니다. 동기 네트워크란 노드간 메시지를 송수신하는 시간의 상한이 정해져있습니다. 즉 네트워크 사이 노드들이 반드시 통신이 이뤄져야 한다는 것을 보장할 수 있습니다. 예를 들어 우주선에서의 통신은 반드시 송수신이 보장되어야 하기때문에 동기식 네트워크를 사용합니다. 

비동기 네트워크란 노드간 메시지를 송수신하는 시간의 상한이 존재하지 않습니다. 따라서 노드가 메시지를 수신했는지, 송신은 정상적으로 되었는지 보장할 수 없습니다. 이 때문에 비잔틴 노드가 거짓 전송을 할 수도 있고, 수신을 부인하는 등 배신행위가 가능해집니다. 블록체인이 비동기 네트워크에 속합니다. 이 경우 비잔틴 장애 허용이 반드시 필요해집니다. 

 

 

부분 동기 네트워크는 노드간 메시지를 송수신하는 시간의 상한은 존재하지만 그 상한선이 얼마정도 인지는 알 수 없습니다. 즉, 노드간 메시지가 도달하게 된다는 사실은 모증하지만 실제로 해당 메시지가 언제 도달하는지는 보장하지 않습니다. 

문제는 블록체인 네트워크가 비동기 네트워크라는 점입니다. 만약 비잔틴 노드가 네트워크에 존재한다면 블록체인의 노드들은 합의에 이르지 못하게 될 위험이 존재합니다. FLP Impossibility는 비동기 네트워크에서 Safety와 Liveness를 둘다 충족시키는 합의 알고리즘 설계는 불가능함을 증명한 이론입니다. 즉 블록체인에서 합의 알고리즘을 채택한다면 Safety와 Liveness 둘 중 하나는 희생을 해야 한다는 결론이 나게 됩니다.

Liveness over Safety

사토시 나카모토가 제시한 합의 알고리즘은 Liveness를 보장하면서 Safety를 추가적으로 보장하는 방식으로 발전합니다. 더 많은 해시 파워를 제공했다는 증명을 통해 하나의 체인에 노드들이 합의를 하게 되고, 51% Attack이 존재하지 않는한 노드들은 올바른 체인에 합의를 하게 됩니다. Liveness를 우선적으로 확보하고 확률적으로 Safety를 보장하는 방식입니다. Nakamoto Consensus에서 발전한 이더리움 Casper, the Finality Gadget은 PoW 방식으로 Liveness를 보장하면서 50블록 마다 투표를 진행하면서 Safety를 추가적으로 보장합니다. 

Safety over Liveness

전통적인 분산 시스템들은 Safety를 중시하는 방향으로 설계되었습니다. PBFT에 기반한 BFT 종류의 합의 알고리즘들은 Safety를 중시합니다. 실례로는 Cosmos에서 사용되는 Tendermint가 Safety를 보장하는 BFT 알고리즘을 사용하고 있습니다. FLP Impossibility가 증명하듯, Safety가 보장되는 비동기 환경에서는 Liveness를 동시에 보장할 수 없습니다. 따라서 BFT 계열 합의 알고리즘들은 다른 네트워크 모델에서 Liveness 보장을 설명하고 있습니다. 

비동기 네트워크에서 Liveness가 보장되지 않는 이유는 메시지가 언제 도착하는지에 대한 보장이 되지 않기 때문입니다. 메시지가 도착하지 않으면 송신 노드가 무한루프에 빠진 건지, 실제 메세지가 오고 있는데 시간이 오래 걸리는지 알 방법이 없기 때문입니다. 따라서 Tendermint는 정해진 시간안에 메시지는 도달하지만 그 시간은 구체적으로 알 수 없는 부분 동기 네트워크(Partially Synchronous Network Model)을 사용합니다.

부분 비동기 네트워크에서는 Omission Failure가 발생하지 않는 한 언젠가는 메시지가 도달되는 것을 보장하고 있습니다. BFT 계열 합의 알고리즘은 블록생성을 위해 2번의 투표를 진행합니다. 부분 동기 환경에서 언젠가 메시지가 도달하게 되지만 수차례 라운드에서 새로운 블록이 생성되지 않을 수도 있습니다.

 

PBFT 합의 알고리즘이란?

 

비동기 네트워크 환경에서 Safety를 확보하면서 Liveness를 부분적으로 충족하는 합의 알고리즘입니다. 기본적으로 비동기 환경에서 작동하는 블록체인에 BFT 합의 알고리즘을 사용했다고 하면 PBFT를 기본으로 발전했다고 할 수 이있습니다. 이더리움 Casper는 PoW에 PoS+PBFT를 접목한 알고리즘이며 Cosmos의 Tendermint는 DPoS+PBFT를 접목한 합의 알고리즘입니다. 또한 하이퍼레져 패브릭, R3, Ripple, EOS 등 Public/Private 블록체인 모두에서 PBFT가 사용되고 있습니다.

 

 

PBFT는 f개의 비잔틴 노드가 존재할 때 3f+1개의 총 노드가 존재하는 네트워의 경우 신뢰할 수 있는 합의에 도달 할 수 있다는 것을 증명한 알고리즘입니다. 노드들은 prepared certificate와 commit certificate 2 단계에 걸쳐 투표를 진행하고 합의에 도달합니다.

 

 

① Request 

상태 변환을 요청하는 노드는 Primary Node에게 request를 전송합니다. Primary Node는 가장 먼저 상태 변환 요청을 받은 노드이며, 나머지 노드들은 Backup으로 통칭됩니다. 

② Pre-prepare

Primary Node가 request를 받으면 해당 요청에 상응하는 Sequential Number(N)을 생성하고 backup들에게 pre-prepare 메시지 <Pre-prepare, V, N, D>를 전송합니다. 

• V : 메지기가 전송되는 View
• N : Sequential Number
• D : 요청 메시지 요약본

③ prepare

pre-prepare 메시지를 전달받은 backup 노드 i는 D와 V,N이 대응되는 값인지 검증을 진행합니다. 만약 검증에 실패하면 pre-prepare 메시지 <prepare, V, N, D, i>를 거부하고, 참이라면 prepare 메시지를 생성해 나머지 노드들에게 전송합니다. 

• i : pre-prepare 메시지를 검증했던 backup 노드 번호

④ Prepared certificate

각 노드들은 Pre-prepare 메시지와 Prepare 메시지를 수집합니다. 수집된 Pre-prepare 메시지가 2f+1개고 Prepare 메시지가 2f개 이상인 상태를 prepare certificate가 되고 이 노드는 prepared the request 상태로 변경됩니다.

⑤ Commit

prepared certificate 상태가 된 노드는 나머지 노드들에게 Commit 메시지 <Commit, V, N, i>를 전송합니다.

⑥ Commit certificate

각 노드는 commit 메시지를 수집하고 commit 메시지가 2f+1개 이상 수집되면 commit certificate로 상태가 변경됩니다. 

 

만약 한개의 노드가 prepared certificate와 commit certificate 2가지 상태를 가진 경우 commit certificate가 됩니다. 상태가 변경된다는 것은 Request가 수용되어 모든 노드들이 합의에 도달했다고 할 수 있습니다. 하지만 2f+1개의 이상의 노드가 상태변경을 하지 않으면 합의에 도달하지 못하게 되고 새로운 블록은 생성되지 않습니다. 

PBFT에서는 2번의 절차를 거치는 이유는 한번의 절차만 거치는 경우 비잔틴 노드가 네트워크의 safety를 위협하고 결과적으로는 합의 알고리즘을 부서버릴 수 있기 때문입니다. 따라서 PBFT에서는 prepare certificate와 commit certificate 두번의 절차를 거쳐 비잔틴 노드가 존재함에도 불구하고 safety를 보장하면서 합의에 도달할 수 있게 됩니다. 

 

PBFT 정리

 

합의 알고리즘은 safety와 liveness 2가지 속성을 충족해야 합니다. 기존 분산 시스템에서의 합의 알고리즘은 safety를 중시하면서 liveness를 확보하는 형식으로 발전했습니다. safety는 쉽게 말해 문제 없는 노드는 비정상적인 합의에 이르지 않는다는 것이고, liveness는 정상적인 노드들은 반드시 어떤 합의에 도달한다는 개념입니다.

비트코인에 적용된 Nakamoto Consensus는 Liveness를 보장하면서 확률적으로 Safety를 충족시키는 방향으로 발전했습니다. 블록체인 네트워크는 비동기 네트워크에서 작동합니다. 동기에서는 노드간 메시지가 특정 시간 안에 도착한다는 보장이 되지만 비동기 네트워크에서는 이런 보장이 없습니다. 비동기 네트워크에서 Safety와 Liveness를 동시에 충족하지 못한다는 이론이 FLP Impossibility 입니다. 

 

 

비동기식 네트워크에서 Safety와 Liveness를 보장할 수 있는 합의 알고리즘으로 PBFT가 제안됩니다. BFT에서는 2f+1개의 노드가 있으면 비잔틴 장군 문제를 해결할 수 있지만, PBFT에서는 3f+1개의 노드가 필요하고 2번의 상태변경을 통해 비잔틴 장군 문제를 비동기 네트워크에서 해결할 수 있습니다. 이더리움 Casper, Cosmos의 Tendermint가 PBFT 합의 알고리즘을 차용하고 있습니다.

 

 

Reference

• An Introduction to PBFT consensus Algorithm
• PBFT 합의 알고리즘 이해하기
• PBFT(Practical Byzantine Fault Tolerance) 논문
• PBFT 슬라이드 설명

 

 

 

[Blockchain] 루나 테라 사태 총정리

 

[Blockchain] 비잔틴 장군 문제 딜레마(BFT, PBFT, tendermint)란?

 

[Blockchain] 블록체인 트릴레마 해결 방법?