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

비잔틴 장군 딜레마는 분산 네트워크 분야에서 가장 오래된 문제이면서 반드시 풀어야할 대표적인 문제입니다. 1982년 인공위성, 비행기에서 사용되는 분산 컴퓨터 시스템을 연구하던 레슬리 램포트, 쇼스탁, 피스가 공저한 논문에서 최초로 언급되었습니다. 비잔틴 장군 문제는 여러 노드들 중 악의적인 노드가 있을 때 네트워크를 정상적으로 운영하기 위한 방법을 연구하는 방법론입니다. 

예를 들어 두 나라가 전쟁 중이라고 가정합니다. 아군은 적군의 진지를 함락시켜야 승리할 수 있습니다. 문제는 아군이 N개의 부대로 나뉘어져 있다는 것입니다. 각 군대는 지리적으로 분리되어 있어 동기적인 의사합의가 진행될 수 없습니다. 

 

 

적군의 진지는 방어체계가 잘 잡혀있어 모든 아군부대가 힘을 합쳐야만 승리할 수 있다고 가정합니다. 합동작전을 펼치기 위해 공격시간, 방법 등에 대한 논의가 필요할 것입니다. 하지만 아군의 부대중 배신자(악의적인 노드)가 있다고 가정했을 때 어떻게 하면 승리를 이끌어낼 수 있을까요? 이 상황에서 서로 다른 노드들이 악의적인 노드의 방해를 극복하고 합의에 도달할 수 있는 방법을 연구하는 것이 비잔틴 장군의 문제입니다.

 

 

기존 합의 알고리즘

 

블록체인은 서로 다른 노드들이 합의 과정을 통해 하나의 체인을 채택하면서 데이터를 관리해 나가는 분산 원장 기술입니다. 합의가 완성되기 위해서는 트랜잭션을 검증하고 새로운 블록을 체인에 연결하는 해시파워를 필요로 합니다. 즉, 블록체인을 운영하기 위해서는 네트워크 운영에 기여한 대가를 지불해야 합니다. 기존 합의 알고리즘에는 보상 체계가 없습니다.

CFT(Crash Fault Tolerance)는 분산 네트워크에서 한개의 노드가 비정상적인 충돌에 노출되어도 나머지 시스템을 통해 네트워크를 정상적으로 유지할 수 있게 됩니다. BFT(Byzantine Falut Tolerance)는 더 복잡한 가정을 통해 악의적인 유저에 대처할 수 있는 시스템을 제안했습니다.

 

 

하지만 블록체인에서는 블록을 검증하고 생성하는 과정에서 수준 높은 합의 알고리즘을 필요로 합니다. 비잔틴 장군 문제 논문에서도 해결책을 제안하고 있지만 CFT, BFT 보다 수준 높은 합의 알고리즘은 작업증명방식(PoW)으로 실제 시스템을 구현한 것은 비트코인이 최초 입니다. 

퍼블릭 블록체인이 아닌 컨소시엄형 블록체인인 하이퍼레져 패브릭의 경우 이미 기존에 참여한 노드들이 신뢰할 수 있다고 가정하기 때문에 BFT나 PoW 방식의 합의 알고리즘 대신 CFT 기반 오더링 알고리즘을 사용하고 있습니다. 

 

비잔틴 제국?

 

비잔틴 장군 문제에서 비잔틴움 제국은 통일 로마의 마지막 황제 테오도시우스 1세가 사망한 직후 동쪽 로마 제국을 의미합니다. 395년 경 최종적으로 로마 제국은 동서로 분리되게 되고 콘스탄티노폴리스(비잔티움)을 중심으로 발전한 로마 제국 동부 지역이 바로 비잔티움 제국이 됩니다. 반대로 로마 제국 서부지역의 중심지는 로마였습니다. 

 

 

논문에 배신자가 등장하기 때문에 특정 국가를 언급하는 것이 부담스러웠다고 합니다. 따라서 인구가 작은 알바니아 제국 문제라고 명칭했었는데, 잭 골드버그가 논문을 읽고 알바니아계 이민자들이 많다고 지적하면서 과거에 존재했었던 유럽 동부지역의 비잔티움 장군 문제로 명명되었습니다.

 

비잔틴 장군 문제 (BFT 방식)

 

적을 함락시키기 위해서는 4개의 군부대중 3개의 부대가 힘을 합쳐야 한다고 가정합니다. 공격 시간을 알리기 위해 A 부대에서 B 부대로 3시에 공격하자는 전령을 보내고 악의적인 노드인 B는 C에게 6시에 공격하자는 전령을 보냅니다. , C는 D에게 전령을 보냈습니다. 결과적으로는 3시에 공격하는 군부대는 A만 남게 되고 공격에 실패하게 됩니다. 

 

A 부대 => B 부대	3시에 공격합시다~!
B 부대 => C 부대	6시에 공격합시다~!
C 부대 => D 부대	6시에 공격합니사~!

 

 

이렇게 악의적인 노드가 전령을 전달하는 과정에 존재하니 문제가 해결되지 않습니다. 전령을 보내다가 죽을 수도 있고, 악의적인 노드가 전령의 내용을 수정해버리면 전체 부대가 성공할 수 없게 됩니다. 따라서 전령을 보내는 방법을 1:1 통신이 아닌 브로드캐스트 방식으로 변경합니다.

 

A 부대 => B,C,D 부대	3시에 공격합시다~!
B 부대 => A,C,D 부대	6시에 공격합시다~!
C 부대 => A,B,D 부대	3시에 공격합시다~!
D 부대 => A,B,C 부대	3시에 공격합시다~!

 

 

 

전령을 브로드캐스트 방식으로 보내고 다수결에 따라 3시 공격으로 모든 부대들은 합의를 볼 수 있습니다. 최종적으로 3개 부대 이상 뭉쳐서 적의 진지를 함락시킬 수 있게 됩니다. 여기서 중요한 해결책을 찾을 수 있습니다. 비잔틴 장군 문제를 해결하기 위해서는 배신자(악의적인 노드)의 수보다 신뢰할 수 있는 노드의 수가 많아야 한다는 점과 전체 2/3 다수결이 충족되어야 한다는 점입니다.

예를 들어 악의적인 노드가 N개 있으면 총 노드의 수는 3N+1개가 필요합니다. 악의적인 노드 N개를 제외한 나머지 노드들은 모두 신뢰할 수 있어야 합니다. 3N+1개의 노드만 있으면 악의적인 노드가 N개 존재하더라도 2/3 다수결합의에 이를 수 있고 네트워크를 정상적으로 유지할 수 있게 됩니다.

이 방식이 BFT(Byzantine Fault Tolerance)입니다. 모든 노드가 다른 노드들에게 데이터를 전송하면서 합의를 하는 방식입니다. PoW나 PoS와 달리 다수결로 합의를 진행하면서 완료되면 블록이 생성되기 때문에 완결성을 확보할 수 있습니다. 즉 블록의 분기가 생길 여지가 없습니다. 또한 다수결로 합의만 되면 블록이 생성되므로 무의미한 해시파워가 필요하지 않아 상당히 고속으로 작동합니다.

하지만 BFT에도 한계점은 존재합니다. 위 예시처럼 노드가 4개면 상과없지만 수천개의 노드가 있다고 가정할 때 모든 노드에게 브로드캐스트 방식으로 메세지를 전달하면 통신량이 기하급수적으로 늘어나고 처리량이 떨어지기 때문입니다. PoW나 PoS 합의 알고리즘은 수천개의 노드가 참여할 수 있지만 BFT는 수십개의 노드가 한계입니다. 따라서 퍼블릭 블록체인에서 BFT는 적합한 해결책이 되지 못합니다. 

 

비잔틴 장군 문제 (PBFT 방식)

 

PBFT는 BFT 합의 알고리즘이 동기식 네트워크에만 적용 가능했던 문제를 해결합니다. 즉, 악의적인 노드가 존재하는 비동기 네트워크에서 합의를 가능하게 합니다. PBFT에는 Primary Node 혹은 Leader라 불리는 특수한 노드가 존재합니다. 이 노드는 다른 노드들의 요청 순서를 정렬하고 최초로 다른 노드들에게 전파하는 역할을 담당합니다. 

먼저 Primary Node는 다른 노드들의 요청을 수집해 정렬하고 실행 결과와 함께 다른 노드들에게 전파합니다. 리더의 메시지를 받은 다른 노드들은 다시 한번 다른 노드들에게 메시지를 전파합니다. 이제 모든 노드들은 가장 많이 전달받은 메시지를 판별해서 다른 노드들에게 전파합니다. 이 과정이 끝나면 일정수 이상이 합의한 데이터를 공동으로 가지게 됩니다. 

 

 

PBFT에서는 다음 블록에 대한 합의가 완료되면 제안된 블록 합의 내용이 확정됩니다. 한번만 확인하면 거래가 완료되기 때문에 거래 확정시기가 단축됩니다. 또한 PBFT는 PoW이 아닌 PoS방식을 사용해 에너지 사용량이 적습니다. 따라서 거래비용이 상대적으로 저렴해집니다. 

PBFT에서는 두번의 브로드캐스트를 통해 악의적인 노드의 방해를 걸러내고 합의에 도달할 수 있게 됩니다. PBFT는 IBM Fabric, Orderer, R3 Corda, Notary 등의 프라이빗 블록체인에서 사용되고 있습니다.

 

Tendermin

Tendermint는 Cosmos에 사용되는 합의 알고리즘으로 DPoS와 PBFT를 조합해 비공개 블록체인에서 사용할 수 있도록 개량되었습니다. PBFT가 하나의 노드가 하나의 투표를 한다면 Terdermint는 노드가 가진 지분을 기반으로 투표를 진행합니다. 또한 Locking 메커니즘으로 투표에 참여한 노드의 지분을 네트워크에 동결시켜 이중 투표 문제를 방지합니다. 

Tendermint에서는 Propose, Prevote, Precommit 3단계를 거칩니다. 우선 Primary Node가 Propose 하면 validator들은 블록을 검증하고 Prevote(투표)를 합니다. 전체 2/3 이상의 validator가 투표를 하면 다음 단계인 Precommit이 진행됩니다. 이 단계에서도 2/3이상의 validator들이 참여해야 최종적으로 해당블록이 Commit됩니다.

Prevote와 Precommit 단계에서 2/3+1 이상의 노드 합의 필요합니다. 따라서 두개의 블록이 동시에 생성되는 경우는 없습니다. 하지만 메시지를 보내고 제시간에 도달하지 못하는 비동기 네트워크에서 합의가 이뤄지지 않아 블록이 생성되지 않을 수 있습니다. 

 

 

PBFT 한계점

결국 브로드캐스트 방식에서 발목이 잡힙니다. 합의에 참여하는 노드 수가 증가함에 따라 합의 속도가 저하됩니다. Cosmos의 경우 100개의 노드가 합의에 도달하기 위해서는 6초 가량의 시간이 소요됩니다. 이 때 합의를 위해 16,434번의 통신이 필요하게 됩니다. 노드가 더 추가된다면 노드수 제곱만큼의 통신량이 추가로 필요하게 됩니다. 

 

 

그외 PBT 솔루션들

 

DBFT(Delegated Byzantine Fault Tolerance)

다른 노드들에게 위임받은 대리인들이 합의에 참여합니다. 대리인의 2/3 이상이 합의를 해야 블록이 확정됩니다. 처리 속도가 빠르고 완결성을 확보할 수 있습니다. 하지만 특정 대리인들에게 권력이 집중되고, 대리인들간 담합에 대한 위험을 배제할 수 없습니다. 

IBFT(Istanbul BFT)

PoA(권한증명) 방식을 차용합니다. validator들은 최초 블록 생성시 트랜잭션과 블록을 검증하고 실제 체인에 연결되기 전 2/3 이상의 validator들이 최초 서명을 하면서 체인에 연결됩니다. 프라이빗 블록체인에 사용됩니다. 

RBFT(Redundant BFT)

PBFT 방식이 Primary Node에 지나치게 의존하기 때문에 성능 저하되는 문제를 개선한 합의 알고리즘입니다. 

Mir-BFT

블록체인에서 합의 과정에서 광역 네트워크(WAN)의 처리량을 극대화하는 것을 목표로 한 브로드캐스트 프로토콜입니다. 

NCCU BFT

Tendermin에 기반한 프로젝트로 이더리움 합의 과정을 BFT를 통해 허가형으로 변경한 방식입니다.

 

 

 

[Blockchain] 온체인(On-Chain) vs 오프체인(Off-Chain) 차이점

 

[Blockchain] 블록체인 트릴레마 3요소?

 

[Blockchain] 블록체인 트릴레마란?