BFT: 비잔틴 장군 문제

독수리박박·2023년 9월 9일

BFT는 기존 확률적 합의 알고리즘의 문제점을 개선하고자 기존 분산시스템에서 상태 기계 복제(State Machine Repliecation)를 위해 활용한 합의 알고리즘 방식이다.

기존 합의 알고리즘의 문제

기존의 작업증명, 지분증명 알고리즘이 적용된 블록체인이 작동하기 위해서는 내부 가상 화폐등의 보상 시스템이 꼭 필요하다.

기존 알고리즘은 가상화폐가 필요하다는 문제 말고도 부분 분기가 일어날 수 있다는 문제가 존재한다. 만약 A와 B블록이 동시에 생성된다면 각 노드는 A와 B 중 하나를 선택한다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 되고 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어렵다는 문제가 존재한다.

CFT vs BFT

BFT는 CFT(Crash Fault Tolerance)에 비해서 더 복잡하며 악의적인 행위자가 있을 수 있는 시스템을 처리한다.

컨소시엄형 블록체인 시스템(하이퍼레저 패브릭 등)에서는 조직들이 이미 신원확인을 통해 확인한 사용자들만이 사용하기 때문에 악의적인 행위를 하지 않을 것이라 믿고 서비스를 한다.

따라서 하이퍼레저 패브릭 같은 컨소시엄형 블록체인 시스템에서는 CFT기반의 알고리즘이 우선시 된다.

BFT(Byzantine Fault Tolerance)란?

처음 비잔틴 장군 문제가 언급된 것은 인공위성과 비행기에서 쓰기 위한 장애 없는 분산 컴퓨터 시스템을 연구하던 1982년 논문에서 처음으로 언급되었습니다. 중앙 통제 장치가 없는 분산 컴퓨터 시스템은 일부 노드의 장애와 해킹 공격이 있으면 시스템을 안정적으로 운영하기 어렵다는 내용과 함께 언급되었습니다.

이것을 비잔틴 장군 문제와 연관지어 설명한다면 배신자가 있는 상황에서는 여러 장군이 받은 명령을 진실이라고 확정하기 어렵다는 말로 비유를 했습니다.

비잔틴 장군의 문제 상황

n개의 비잔틴 부대가 적의 도시를 포위하고 있고, 각 부대는 부대마다 배치된 장군의 명령에 따른다. 한 명의 장군은 나머지 n-1명의 장군과 통신할 때 각각의 장군에게 전령을 보내는 것으로만 통신이 가능하다.

장군들은 지금 총공격할지, 조금 더 기다릴지 합의하여야 한다. 하지만 장군 중 배신자가 존재할 수 있고, 배신자들은 이상한 의견을 제시할 수 있다.

배신한 장군들의 의견을 무시하고 올바른 공격 여부를 합의할 방법(알고리즘)이 필요하게 된다.

처리 절차

1. 클라이언트가 모든 노드에 용청을 브로드캐스팅한다.
2. 리더가 처음 순차적으로 다른 노드들에게 명령을 전달한다.
3. 각 노드들은 브로드캐스팅된 명령을 받게 된다면 리더를 포함한 모든 노드에 회신한다.
4. 각 노드는 전달된 명령을 일정 수 이상(2n)이 수신하면 리더를 포함한 모든 노드에 수신한 신호를 재전송한다.
5. 각 노드는 수신된 명령을 일정 수 이상(2n)이 수신하면 명령을 실행하고 블록을 등록에 Client에 Replay된 메시지를 반환한다.

장점

PoW나 PoS와 달리 다수결로 의사 결정한 뒤 블록을 만들기 때문에 블록체인의 분기가 발생하기 않는다 => 완결성을 확보할 수 있다
Pow와 같이 조건을 만족시킬 때까지 계산을 반복하지 않아도 되기 때문에 매우 고속으로 작동한다.
부정 사용을 하고자 해도 과반수를 얻어야 하며 만약 다른 참가자들이 리더가 거짓말을 하는 것 같다면 리더의 움직임을 감시해 다수결로 리더 교체를 신청할 수 있기 때문에 장애에 매우 강력한 내성을 지님

단점

언제나 참여자 전원이 소통을 해야하기 때문에 통신량이 증가하고 처리량이 저하된다. 따라서 PoW나 PoS같이 수 천개의 노드가 동시에 참여하기 힘들다.(사실상 불가능..!) 수십개의 참여자(노드)가 한계이다.

PBFT(Practical Byzantine Fault Tolerance)

PBFT는 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재하며 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘이다.

한마디로 기존 BFT 합의 알고리즘이 동기식(순차적) 네트워크에서만 합의할 수 있었던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있도록 하였다.

이 그림은 PBFT의 동작 방식을 나타낸 것이다. 사실 위의 BFT 그림에서 Leader 노드가 Primary 노드로 바뀐 것 뿐이다. 그리고 Leader, Primary Node는 비슷한 맥락에서 사용된다.(같은 뜻이다.)
Leader나 Primary노드는 클라이언트의 요청 순서를 정렬하고, 요청에 대한 결과를 기재하여 최초로 다른 노드들에게 전달하는 역할을 한다.

처리 절차

1. 리더가 클라이언트의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에게 전파한다.
2. 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에게 전파한다.
3. 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메세지(정족수 이상)가 무엇인지 다른 노드들에게 전파한다.
4. 모든 과정이 끝나면 모든 노드는 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 된다.

장점

트랜잭션의 완결성과 빠른 거래 확정 : PBFT는 다음 블록 합의가 이루어진다면 제안된 블록의 합의 내용이 확정되어서 한번 확인(1 Confimation)으로 거래가 완결 되기 때문에 거래 확정 시간이 짧다.
저에너지로 비용 감소 : PBFT는 작업증명방식(PoW)이 아닌 지분증명방식(PoS)을 기본으로 하여 에너지 사용량이 적고, 따라서 거래 비용이 적다.