PBFT

많은 코인들이 합의 알고리즘으로 채택하고 있는 PBFT 합의 알고리즘 내용에 대해서 공부하고 정리해보려고 한다.

비잔틴 장군 문제

PBFT는 비잔틴 장군 문제로부터 나왔다. 비잔틴 군대는 여러 장군들이 같은 의사결정을 내려야 전쟁에서 이길 수 있다. 하지만 장군들은 서로 떨어져 있기 때문에 전령을 보내 의견을 통일해야 한다. 이 과정에서 적국의 첩자가 잘못된 메시지를 보낼 수도 있다. 이렇게 악의적인 방법으로 방해가 있을 수도 있는 상황에서 합의를 이끌어내는 방법을 비잔틴 장군 문제라고 한다.

이러한 문제를 처음 도입한 것은 항공기의 항법 장치 분야이다. 항공기 곳곳에 설치된 센서들이 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하므로 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다.

비잔틴 장애 허용 (BFT)

비잔틴 장애 허용에서는 일부 노드(장군)의 결과가 달라도 어느 정도 이상의 결과가 동일하면 합의된 것으로 본다. 즉, 다수결의 원칙을 따르는 합의 알고리즘이라고 할 수 있다. BFT에는 여러 방법이 있지만 PBFT를 가장 많이 사용한다.

비잔틴 장애 허용의 가장 기본적인 전제 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점이다. 항법장치의 센서가 세 개일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.

프랙티컬 비잔틴 장애 허용 (PBFT)

PBFT (Practical Byzantine Fault Tolerance)는 1999년에 Miguel Castro와 Barbara Liskov가 논문을 통해 발표했다.

PBFT는 PoW와 PoS의 단점인 finality의 불확실성과 성능 문제를 해결했다. BFT는 동기식 시스템에서만 설계됐지만 PBFT는 비동기식 시스템에서 작동하므로 실제 사용할 수 있을만큼의 성능을 구현했다.

네오, 질리카, 하이퍼레저, R2, ITC, 텐더민트 등에서 PBFT 합의 알고리즘을 이용하고 있다.

합의 과정

Client가 모든 노드에 현재 상태에 대한 Confirm을 요청한다.
모든 노드들 중 선정된 Primary Node는 Client로부터 받은 트랜잭션을 전부 모은다.
Primary Node는 트랜잭션을 모아 만든 블록을 다른 노드(Replica)들에게 전부 전파한다.
모든 노드가 Primary Node로부터 블록을 받는다.
블록을 받은 노드들은 자신이 블록을 블록을 받았다는 사실을 다른 모든 노드들에게 전파한다.
각 노드는 다른 노드들이 블록을 받았는지 여부를 취합하며 이 수가 2/3 이상일 경우, 해당 블록을 검증한다.
블록의 유효성을 검증한 결과값을 다른 노드들에게 전부 전파한다.
각 노드는 다른 노드들이 보내준 블록 유효성 검증 결과값을 취합하여 전체의 2/3를 초과한 동일한 결과값을 보냈을 경우 해당 결과값을 참으로 인식하고 이에 맞는 행동을 진행한다.
1. 2/3를 초과한 노드가 블록이 유효하다는 결과값을 보냈을 때, 블록을 자신의 블록체인에 추가한다.
2. 1/3 이상의 노드가 블록이 유효하지 않다는 결과값을 보냈을 때, 블록을 블록체인에 추가하지 않는다.
현재 상태(State) 값을 Client에 보내준다.

부정한 노드 수를 n개라고 하면 노드수는 3n+1개여야 하며, 확정에는 n+1개 이상의 노드가 필요하다. PBFT는 비동기 네트워크에서 배신자 노드 f개 있을 때, 총 노드 갯수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘이다.