[POSTECH 블록체인 입문] BFT & PBFT

Safety와 Liveness

• 어떤 합의 알고리즘이 네트워크에서 통용되기 위해선 Safety와 Liveness라는 특성을 가지고 있어야 함
• Safety의 의미는 ‘노드 간 합의가 발생했다면, 어느 노드가 접근하든 그 값은 동일해야 한다’ 임
• 블록체인의 finality와 동일한 개념
• Liveness는 “합의 대상에 문제가 없다면, 네트워크 내에서 반드시 합의가 이루어진다” 라는 의미
• 그런데, 비동기 네트워크 내에서는 Safety와 Liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능하다는 것이 증명됨
• 이 증명을 “FLP Impossibility”라고 하며 비동기 네트워크에서는 합의 문제를 완벽히 해결할 수 있는 분산 알고리즘이 없다는 것을 증명함
• 비잔틴 장군 문제

[참고]https://youtu.be/SrE47EeRl-Y?list=PL9j05Awmso8XI3pLmX4Yw1Uy5NwHXFvhH&t=1112

위 김승주 교수님의 강의 18:33초에서 비잔틴 장군 문제에 대한 설명이 나옴

 

• 비잔틴 장군 문제는 1982년 제시된 논리적 딜레마로 비잔티움의 장군들이 차후의 행동을 합의하려 할 때 발생할 수 있는 의사소통의 문제에 관한 것임
• 장군들은 공격하거나 후퇴하기 위해서 동의를 얻어야 함
• 모든 장군이 합의에 도달하는 한, 즉, 공격을 하든 후퇴를 하든, 이를 협력적으로 실천하기 위한 결정에 동의한다면 아무런 문제가 없음

 

1. 각 장군들은 공격, 혹은 후퇴(동의 혹은 거부)를 결정함
2. 결정은 번복할 수 없음
3. 모든 장군이 같은 결정을 해야 하며, 이를 동시에 시행해야 함

• 결과적으로, 비잔티움 장군의 문제는 어떤 이유에서든 메시지가 늦게 전달되거나, 훼손되거나, 소실될 수 있다는 사실이 관건임
• 메시지가 성공적으로 전달된다 하더라도, 한 명 혹은 그 이상의 장군들이 어떤 이유에서든 악의적으로 행동하기로 선택할 수 있으며, 다른 장군들을 혼란스럽게 하기 위해 가짜 메시지를 보내 총체적인 실패로 이어질 수도 있음
• 분산화된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 ⅔ 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것임

 

• 작업 증명 알고리즘이 비잔티움 실패를 100% 막아내는 것은 아니지만, 비용 집약적인 마이닝 과정과 암호화 기술로 인해, 블록체인 네트워크에서 작동하는 가장 안전하고 신뢰할 수 있는 것으로 증명됨
• 이러한 점에서, 사토시 나카모토에 의해 설계된 작업 증명 합의 알고리즘은 비잔티움 실패에 대한 가장 똑똑한 해결책으로 여겨지고 있음

PBFT

• Safety를 확보하고 Liveness를 일부 희생하면서, 비동기 네트워크에서도 합의를 이룰 수 있는 알고리즘이 바로 Practical Byzantine Fault Tolerance(PBFT)임

• 즉, 네트워크에 배신자 노드가 어느 정도 있다고 해도 네트워크 내에서 이루어지는 합의의 신뢰를 보장하는 알고리즘임
• 현재까지 블록체인 합의 알고리즘 중 BFT 방식을 채택했다고 하는 경우 대부분 PBFT 합의 알고리즘을 바탕으로 조금씩 변형을 가했다고 볼 수 있음
• 대표적으로 Tendermint는 PBFT에 DPoS 합의 알고리즘을 결합했으며, 이더리움 Casper는 PoW 방식의 채굴 위에 PoS + PBFT 형태의 블록 검증 시스템을 제안함
• 이외에도 PBFT는 Hyperledger Fabric, R3, Ripple, EOS에 이르기까지 Public과 Private을 가리지 않고 다양한 블록체인에서 사용되고 있음

PBFT 요약

• 비동기 네트워크에서 배신자 노드가 f개 있을 때, 총 노드 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘
• 네트워크의 모든 노드는 거래와 같은 합의 대상의 상태를 변화할 것인지 prepared certificate와 commit certificate라는 두 번의 절차를 거쳐 결정함

 

• PBFT 알고리즘을 블록의 합의에 적용한 대표적인 사례로는 Tendermint가 있음
• 각 라운드마다 블록을 제안하며, 매 라운드에서 합의를 거쳐 블록을 생성함