BFT: 비잔틴 장군 문제

기존 합의 알고리즘의 문제

• 작업증명 알고리즘과 지분증명 알고리즘이 적용된 블록체인이 작동하기 위해서는 내부 가상 화폐 등의 보상 시스템이 꼭 필요
• 블록체인의 노드들이 작업증명 알고리즘에서 사용하는 에너지 낭비 방식의 채굴을 수행하는 이유는 블록체인 네트워크에서 주는 가상 화폐 보상을 얻기 위함(지분 증명 또한 마찬가지)
• 내부 화폐 및 보상이 없으면 블록을 생성할 이유도 없고 지분 증명 메커니즘 자체를 사용할 수 없게 됨
• 이러한 이유 때문에 가상 화폐외의 다른 많은 서비스를 수행하는 사설 블록체인의 경우, 내부화폐라는 보상없이 합의 알고리즘을 사용할 수 없다.
• 기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있따는 문제가 존재

ex) 작업증명
A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택한다.
이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 된다.

• 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에는 적용이 어려운 문제점이 있다

CFT(Crach Fault Tolerance) vs. BFT(Byzantine Fault Tolerance)

• CFT는 분산시스템에서 노드가 비정상적인 충돌에 의해 문제가 생기더라도, 나머지 시스템에서 서비스를 할 수 있게 하는 작동방식
• BFT는 더 복잡하며 악의적인 행위자가 있을 수 있는 시스템을 처리
• 블록체인 시스템에선 둘 모두 합의라는 방식을 거치게 되는데, 비트코인의 경우는 일반적인 CFT, BFT 보다 높은 수준의 신뢰작업을 필요로 한다.(PoW)
• 컨소시엄형 블록체인 시스템에서는 보통 조직들이 이미 신원확인 등을 통해 허가를 받은 상태에서 참여하기 때문에, 악의적인 행위를 하지 않을 것이라 믿고 서비스한다. => 특정 상왕에 노드에 문제가 생기는 경우에 대해서만 염두에 둔 CFT 기반의 오더링 알고리즘이 우선되고 있다.

BFT(Byzantine Fault Tolerance)

• Byzantine Fault Tolerance 라는 용어를 '비잔티움 장애 허용'이라고 주로 번역되는데, 번역에 따라 'Tolerance'를 '내성'이라고 번역하는 경우도 있다.
• 비잔티움 장군 중 배신자를 '허용한다'가 아니라 "배신자가 있어도 견딘다"라는 의미를 나타내기도 한다.

비잔틴 장군 문제의 상황

• n개의 비잔틴 부대가 적의 도시를 포위하고 있고, 각 부대는 부대마다 배치된 장군의 명령에 따른다.
• 한명의 장군은 나머지 n-1명의 장군과 통신할 때 각각의 장군에게 전령을 보내는 것으로만 통신할 수 있다.
• 장군들은 지금 총 공격을 할 지, 조금 더 기다릴 지 합의하여야 한다.
• 장군들 중 배신자가 있을 수 있고, 배신자들은 근거없이 아무 의겨ㅑㄴ이나 제시 할 수 있다.
• 배신한 장군들의 방해를 뚫고 공격 여부를 합의할 방법(알고리즘)이 필요하게 된다.

처리 절차

• 우선 클라이언트가 모든 노드에 요청을 브로드캐스트 한다.
• 리더가 처음 순차적으로 명령을 다른 노드에 전달
• 각 노드는 브로드캐스트 된 명령을 받게되면 리더를 포함한 모든 노드에 회신을 한다.
• 각 노드는 전달된 명령을 일정 수 이상(2n)이 수신하면 리더를 포함한 모든 노드에 수신한 신호를 재 전송한다.
• 각 노드는 수신된 명령을 일정 수 이상(2n)수신하면 명령을 실행하고 블록을 등록해 Client에 Replay된 메세지를 반환한다.
• PoW나 PoS와는 달리 다수결로 의사결정한 뒤 블록을 만들기 때문에 블록체인의 분기가 발생하지 않는다.
• 한 번 확정된 블록은 변경되지 않기 때문에 완결성을 확보할 수 있다.
• PoW와 같이 조건을 만족시킬 때까지 계산을 반복하지 않아도 되기 때문에 매우 고속으로 동작

부정 사용을 하고자 해도 과반수를 획득해야 하며 만약 리더가 거짓말을 한다 해도 모든 참가자가 리더의 움직임을 감시해 거짓말이라고 판단한다면 다수결로 리더 교체를 신청할 수 있기 때문에 장애에 매우 강력한 내성을 지닌 알고리즘이다.

반면 언제나 참가자 전원과 의사소통ㅇ르 해야 하기 때문에 참가자가 증가하면 통신량이 증가하고 처리량이 저하된다. 따라서 PoW나 PoS는 수천개의 노드를 만들 수 있지만 PBFT는 수십개의 노드가 한계이다.

PBFT(Practical Byzantine Fault Tolerance)

• PBFT는 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘
• 기존의 BFT 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였다.

PBFT의 장점

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

Tendermint

• Tendermint는 Cosmos에서 사용하는 합의 알고리즘
• PBFT 알고리즘을 공개 및 비공개 블록체인에 맞도록 개량한 합의 알고리즘
• 전통적인 합의 알고리즘이 블록체인에 적용된 의미있는 사례이며 DPoS개념과 PBFT 개념을 섞어 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘이다.
• PBFT와의 차이점은 기존의 PBFT는 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만 Tendermint는 지분을 기반으로 투표를 하게 된다.(투표하는 노드의 수보다는 지분이 중요)
• Tendermint는 투표를 할 때 Locking 메커니즘을 통해 투표에 참여한 지분을 네트워크에 동결시키고 이를 해제하는 메커니즘을 통해 이중 투표 문제를 막고 지분으로 네트워크를 유지하게 한다.
• 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않던 문제(Nothing of Stake)를 해결하였다.

Tendermint의 장점

1. Tendermint는 블록을 노드들에게 전파(Gossip)하는 방식을 단순화하고 노드의 수를 늘릴 수 있게 했다.
2. Tendermint는 블록제안자를 수시로 교체할 수 있게 하여 안정성을 높혔다.
3. Tendermint는 비잔티움 노드를 쉽게 발견하여 처벌 할 수 있도록 했다.

PBFT의 한계

• PBFT는 합의 그룹 크기가 커짐에 따라 합의 속도가 느려지는 문제가 있다.
• 100개 이상의 노드를 운영하기 쉽지 않다.