비잔티움 장군 문제(Byzantine Generals Problem)가 발생할 수 있는 상황에서도 네트워크의 합의를 보장하는 알고리즘
- 비잔티움 장군 문제(Byzantine Generals Problem)란 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 장군들이 전령을 통해 교신하면서 공격 계획을 세울 때, 장군들 중에배신자가 있더라도 합의를 이끌어 내기 위해서 어떤 것이 보장 되어야 하는지에 관한 문제이다.
보장해야 하는 것은 아래와 같다.
모든 충직한 장군들은, 같은 정보를 획득해야 한다. (누가 배신자인지 모르기 때문에, x번째 장군이 직접 보낸 메시지를 받았다 하더라도, 바로 사용할 수 없다.)
만약 n번째 장군이 충직하다면, n번째 장군이 보낸 값은 충직한 장군들한테 같게 보내져야 한다.
이를 블록체인에 적용한다면 블록체인 네트워크 내에 악의적인 노드가 있을 때, 합의의 신뢰성을 보장하기 위해서는 어떤 조건을 만족해야 되는가에 관한 문제가 된다. PBFT는 기존의 BFT 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 악의적인 노드가 있는 비동기 네트워크에서도 합의를 이룰 수 있게 하였다.
PBFT는 비동기 네트워크에서 악의적인 노드가 f개 있더라도, 전체 노드 수가 3f+1개 이상이면 해당 네트워크에서의 합의의 신뢰성은 수학적으로 보장된다는 것을 이용한 알고리즘이다.
자세한 동작방식은 다음과 같다.
client가 request 메세지 m을 broadcast 한다.
- 처음 request 메세지 m을 받은 node가 primary node가 된다.(나머지 - Backup node)
primary node가 Backup node에게 Pre-prepare 메세지를 다음과 같은 양식으로 전송한다.
- <Pre-prepare, V, N, D(m)>
- V: 메세지가 전송되는 view
- N:Sequential Number
- D(m): request 메세지 m의 요약본
각 Backup node i가 Pre-prepare 메세지를 받고 V, N, D(m)을 검증한다.
- 검증 결과 서로 대응대지 않는 값이면 Pre-prepare 메세지를 수용하지 않는다.
- 검증 결과가 참이면 Prepare 메세지를 생성하여 다른 node에게 전송.
- <Prepare, V, N, D(m), i>
각 node는 Prepare 메세지를 수집한다.
- 수집한 Prepare 메세지가 2f개 이상이면 "prepared certificate"라고 부르고 해당 node는 "prepared the request" 상태가 된다.
"prepared certificate"를 만족한 노드는 모든 노드에게 commit 메세지를 전송한다.
- <Commit, V, N, i>
각 node는 Commit 메세지를 수집한다.
- Commit 메세지가 2f+1개 모이면 해당 node는 "commit certificate"가 된다.
- "commit certificate"가 되면 client가 요청한 request 메세지 m을 수용해 상태 변화 함수를 실행한다.(합의 도출)
- request 수용시 어느 node에서도 상태 변화를 수용한 것으로 본다. (Safety 충족)
- request 메세지 m이 아무 문제가 없더라도 2f+1개 이상의 node가 인정하지 않으면 체인에 올라갈 수 없다.(Liveness의 희생)
Liveness - 문제가 없으면 합의가 이루어 진다.
Safety - 합의가 발생하면 그 값은 어디에서나 같다.
요약하면,
Pre-prepare - 트랜잭션 브로드캐스트,
Prepare - 트랜잭션에 대한 검증
Commit - 합의가 된다.
PBFT는 두번의 broadcast를 통해 primary node나 backup node가 이상한 메세지를 보내도 네트워크의 모든 node는 같은 메세지를 가질 수 있게 하였다.
PBFT는 Hyperledger Fabric이나 R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있다.
Tendermint는 Cosmos에서 사용하는 합의 알고리즘으로 DPoS(Delegated Proof-of-Stake)와 PBFT를 섞어 개량한 합의 알고리즘이다.
이더리움 Casper는 PoW 방식의 채굴 위에 PoS + PBFT 형태의 합의 알고리즘을 사용한다.
출처
위키백과 - 비잔티움 장애 허용
https://ko.wikipedia.org/wiki/%EB%B9%84%EC%9E%94%ED%8B%B0%EC%9B%80_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9steemit - 합의 알고리즘 이해하기 - PBFT Consensus Algorithm
https://steemit.com/consensus/@kblock/48-pbft-consensus-algorithmICONLOOP - BFT 기반 합의 알고리즘
https://blog.theloop.co.kr/2017/06/21/bft-%EA%B8%B0%EB%B0%98-%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/Practical Byzantine Fault Tolerance and Proactive Recovery - MIGUEL CASTRO,BARBARA LISKOV
http://delivery.acm.org/10.1145/580000/571640/p398-castro.pdf?ip=163.239.195.124&id=571640&acc=ACTIVE%20SERVICE&key=0EC22F8658578FE1%2ECDFC9FE77EAE1A4F%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35&__