블록체인 : BFT & PBFT : 배경, 출현, 원리, 필요성

비잔틴 장군 문제 배경

비잔틴 장군 문제에 대해 소개 드리고, 이를 해결하기 위한 BFT와 PBFT 알고리즘에 대해 소개하겠습니다. 어떤 합의 알고리즘이 네트워크에서 통용되기 위해선 Safety와 Liveness라는 특성을 가지고 있어야 합니다. Safety의 의미는 ‘노드 간 합의가 발생했다면, 어느 노드가 접근하든 그 값은 동일해야 한다’ 입니다.

블록체인의 finality와 동일한 개념으로 이해하셔도 됩니다. Liveness는 “합의 대상에 문제가 없다면, 네트워크 내에서 반드시 합의가 이루어진다” 라는 의미입니다. 그런데, 비동기 네트워크 내에서는 Safety와 Liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능하다는 것이 증명되었습니다.

이 증명을 “FLP Impossibility”라고 합니다. 비동기 네트워크에서는 합의 문제를 완벽히 해결할 수 있는 분산 알고리즘이 없다는 것을 증명했습니다

 

 

합의 알고리즘의 출현

이전 모듈에서 PoW, PoS, DPoS를 다루었습니다. 이 합의 알고리즘들은 모두 블록체인이라는 분산원장 시스템에서 노드 간 합의를 이루는 새로운 방법입니다. 특히 비트코인이 제시한 합의 알고리즘은 ‘Nakamoto Consensus’라고도 불릴 만큼, 이전 컴퓨터 과학의 합의 알고리즘에서는 시도한 적 없던 방법이었습니다.

하지만 블록체인 기술이 나타나기 전에도 분산컴퓨팅 기술은 있었고, 분산 환경에서 쓰이는 합의 알고리즘이 있습니다. 네트워크 내에 배신자가 있더라도 합의 내용에 문제가 없으려면 어떻게 해야 하는가에 대한 비잔틴 장군 문제(Byzantine Generals Problem) 를 해결하는 방안으로 제시된 비잔틴 장애 허용과, 비잔틴 장군 문제가 발생할 수 있는 상황에서도 네트워크의 합의를 보장하는 PBFT(Practical Byzantine Fault Tolerance) 알고리즘을 소개하고자 합니다

 

 

비잔틴 장군 문제 개요

간단히 말해, 비잔티움 장군 문제는 1982년 제시된 논리적 딜레마로 비잔티움의 장군들이 차후의 행동을 합의하려 할 때 발생할 수 있는 의사소통의 문제에 관한 것입니다. 이 딜레마는 각 장군이 자신의 군대를 가지고 있고, 각 장군이 공격하려는 도시가 아닌 다른 장소에 있다고 가정하고 있습니다. 장군들은 공격하거나 후퇴하기 위해서 동의를 얻어야 합니다.

모든 장군이 합의에 도달하는 한, 즉, 공격을 하든 후퇴를 하든, 이를 협력적으로 실천하기 위한 결정에 동의한다면 아무런 문제가 없습니다. 그러므로, 다음과 같은 내용을 간주해볼 수 있습니다:

1) 각 장군들은 공격, 혹은 후퇴(동의 혹은 거부)를 결정합니다

2) 결정은 번복할 수 없습니다

3) 모든 장군이 같은 결정을 해야 하며, 이를 동시에 시행해야 합니다

 

앞서 언급한 의사소통 문제는 각 장군이 전달자에 의해 전달되는 메시지를 통해서만 서로 소통할 수 있다는 사실과 관련이 있습니다. 결과적으로, 비잔티움 장군의 문제는 어떤 이유에서든 메시지가 늦게 전달되거나, 훼손되거나, 소실될 수 있다는 사실이 관건입니다. 게다가 메시지가 성공적으로 전달된다 하더라도, 한 명 혹은 그 이상의 장군들이 어떤 이유에서든 악의적으로 행동하기로 선택할 수 있으며, 다른 장군들을 혼란스럽게 하기 위해 가짜 메시지를 보내 총체적인 실패로 이어질 수도 있습니다

 

 

비잔틴 장애 허용 (Byzantine Fault Tolerance)

이러한 딜레마를 블록체인에 적용해 본다면, 각 장군들은 하나의 노드가 되며, 노드들은 현 시스템 상태에 합의를 달성해야 하는 상황이 됩니다. 달리 말하자면, 분산화된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 합니다. 그러므로, 분산화된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 ⅔ 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것입니다.

이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정할 경우, 시스템이 실패하거나 공격당할 수 있음을 의미합니다. 간단히 말해, 비잔티움 장애 허용은 비잔티움 장군 문제의 딜레마에서 파생되는 실패들을 막기 위한 시스템입니다.

비잔티움 장애 허용 시스템은 일부 노드가 고장나거나 악의적으로 행동하더라도 계속 작동할 수 있습니다. 비잔티움 장군 문제를 해결하는 방법은 하나 이상일 수 있으며, 따라서 비잔티움 장애 허용 시스템을 구축하는 다양한 방식이 있습니다.

 

블록체인 : BFT & PBFT : 배경, 출현, 원리, 필요성 1

 

마찬가지로, 블록체인에서도 비잔티움 장애 허용을 보통 합의 알고리즘이라 불립니다. 합의 알고리즘은 블록체인 네트워크에서 합의를 달성하는 매커니즘으로 정의할 수 있습니다. 가장 일반적인 예로 작업 증명과 지분 증명을 들 수 있습니다.

 

블록체인 : BFT & PBFT : 배경, 출현, 원리, 필요성 2

 

비트코인의 경우를 예로 들어 살펴보겠습니다. 비트코인 프로토콜은 시스템의 주요 규칙들을 규정하지만, 작업 증명 합의 알고리즘은 합의를 달성하기 위해 이러한 규칙들이 지켜져야 하는지를 정의합니다. 작업 증명은 암호 화폐보다 오래된 것이지만, 사토시 나카모토는 이를 수정해 비잔티움 장애 허용 시스템으로서 비트코인을 탄생시켰습니다.

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

 

 

PBFT (Practical Byzantine Fault Tolerance)

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

 

블록체인 : BFT & PBFT : 배경, 출현, 원리, 필요성 3

 

즉 네트워크에 배신자 노드가 어느 정도 있다고 해도 네트워크 내에서 이루어지는 합의의 신뢰를 보장하는 알고리즘입니다. 현재까지 블록체인 합의 알고리즘 중 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 사례

PBFT 알고리즘을 블록의 합의에 적용한 대표적인 사례로는 Tendermint를 들 수 있습니다. Tendermint는 Propose, Prevote, Precommit 과정을 거쳐 블록을 생성합니다. 각 라운드마다 블록을 제안하며, 매 라운드에서 합의를 거쳐 블록을 생성합니다.

 

 

참조

http://www.kmooc.kr/courses/course-v1:POSTECHk+CSED490U1+2021_T1/about 

블록체인 입문