BFT 합의알고리즘은 과연 비잔틴 장군 문제인가?

암호화폐의 합의 알고리즘이 비잔틴 장문 문제의 해결이라고 알려져 있습니다.

이 때문에 이더리움 및 텐더민트 등에서 사용하는 합의 알고리즘인 투표 시스템은 비잔틴 장애 허용(BFT, Byzantine Fault Tolerance)을 적용하고 있습니다.

BFT의 가장 큰 특징은 블록을 확정(finalization)하는데 전체 투표자 중에서 2/3 이상의 동의(디지털 서명)가 필요합니다.

하지만, 저는 암호화폐에서 투표로 블록을 생성하는 합의 알고리즘은 비잔틴 장군 문제, 즉 BFT가 아니라고 생각합니다.

비잔틴 장애 허용1: https://ko.wikipedia.org/wiki/%EB%B9%84%EC%9E%94%ED%8B%B0%EC%9B%80_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9
비잔틴 장애 허용2: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance

이에 대한 설명을 아래에 적겠습니다.

1). 사토시가 PoW 합의 알고리즘이 비잔틴 장군 문제의 해결이라고 주장함.

이와 같은 시각이 생긴 것은 사토시가 PoW 합의 알고리즘이 비잔틴 장군 문제의 해결이라고 주장하면서 시작되었습니다. 이에 대한 사토시의 주장은 아래의 링크에서 확인할 수 있습니다.

사토시의 이메일: http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

저는 PoW 합의 알고리즘이 비잔틴 장군 문제의 해결이라는 것에 대해서는 깊이 생각해보지 않아서.. 이에 대한 저의 의견은 없습니다.

2). 비잔틴 장군 문제에 대한 간단한 이해

이제 제일 처음 비잔틴 장군 문제를 제기했던 Lamport의 논문을 통해서 비잔틴 장군 문제를 살표보겠습니다.

논문: http://bnrg.cs.berkeley.edu/~adj/cs16x/hand-outs/Original_Byzantine.pdf

아래는 논문에 있는 비잔틴 문제를 보여줍니다.

한명의 지휘관(commander)와 두명의 중위(lieuteenant)로 이루어지고, 공격과 후퇴를 할지에 대한 결정과정을 보여줍니다.

이때 지휘관은 성을 공격할지 또는 후퇴만을 명령할 수 있고, 이들 사이에 비잔틴(배신자)가 어느 정도까지 있어야 올바른 합의에 도달할 수 있는지를 보여줍니다. 여기서 배신자는 비잔틴이라고 부릅니다.

아래 그림에서 비잔틴, 즉 배신자의 특징을 알 수 있습니다.

위의 그림에서 비잔틴이 중위2인 경우이고, 아래의 그림은 비잔틴(배신자)가 지휘관인 경우를 보여줍니다.

먼저 중위2가 배신자인 경우이고, 중위1은 (공격, 후퇴)라는 명령을 받게 되며, 이것은 중위2가 지휘관에게서 받은 명령을 위조하였기 때문입니다.

여기서 배신자인 중위2가 지휘관에게서 받은 명령인 공격 대신에 후퇴를 중위1에게 전달해줍니다.

이 경우 중위1은 (공격, 후퇴)라는 명령을 받아서 자신이 공격할지 또는 후퇴할지를 결정하지 못하는 상태가 됩니다. 결국 지휘관 혼자 성을 공격하는 상황이 발생하여 이 군대는 공격에 실패를 하게 됩니다.

아래 그림에서 비잔틴이 지휘관인 경우를 보여줍니다.

위 그림과 같이 지휘관은 중위1에게 공격을 명령하고 중위2에게는 후퇴를 명령하게 됩니다.
즉, 각각의 부하게 다른 명령을 하는 것입니다.

이 경우 중위1과 중위2는 각각 (공격, 후퇴)를 전달받아서, 이들은 후퇴 및 공격 결정을 할 수 없는 상태가 됩니다.

위와 같은 상황에서 올바른 결정을 할 수 없기 때문에 아래 그림은 이에 대한 해결책을 보여줍니다.

이 경우 중위3이 배신자이어서 지휘관에서 받은 v 대신에 x를 중위 2에게 보내줍니다.

이때 중위2는 지휘관, 중위1과 중위3으로부터 (v, v, x)를 받아서 올바른 결정을 하게 됩니다.

이 때문에 배신자가 전체 중에서 1/3보다 작아야 하고, 전체 중 2/3보다 많으면 올바른 결정을 하게 되는 것입니다. 즉, BFT는 전체 투표자 중에서 2/3 이상이 동의해야 블록을 확정(finalization)할 수 있습니다.

하지만, 위 경우는 구두 메시지(oral message)를 전달하는 경우에 해당합니다.

만약 디지털 서명을 메시지에 추가한다면 이 메시지를 변조할 수 없기 때문에 이 문제는 다수(majority) 문제로, 1/2로 결정하는 것으로 보입니다.

3). 암호화폐의 BFT(Byzantine fault tolerance)가 비잔틴 장군 문제일까?

저는 BFT를 알았을 때부터 투표 방식의 합의 알고리즘이 비잔틴 장군 문제가 아니라는 생각이 있었습니다.

그러면, 텐더민트의 BFT를 예로 그 이유를 살펴보겠습니다.

텐더민트1: https://tendermint.com/static/docs/tendermint.pdf
텐더민트2: http://tendermint.readthedocs.io/projects/tools/en/master/

간단하게 텐더민트 합의알고리즘을 설명하면, 초기 100명의 검증자(validator)들이 자체적인 가쉽 프로토콜을 구성하고, 리더를 선출하여 이 리더가 블록을 생성하여 다른 검증자에게 전파시키면 검증자들은 이에 대한 투표를 해서 2/3의 승인을 얻으면, 다음 블록을 생성하는 방법을 사용합니다.

가쉽 프로토콜1: https://1ambda.github.io/cloud-computing/cloud-computing-2/
가쉽 프로토콜2: https://en.wikipedia.org/wiki/Gossip_protocol

물론 이때 각 검증자는 자신의 투표에 디지털 서명을 하여 위조가 불가능하게 하며, 이들의 공개키로 투표의 위조 여부를 검증합니다.

본인이 생각하기에, 이런 BFT 합의 시스템이 비잔틴 장군 문제가 아닌 것은 아래와 같습니다.

첫째로, 각 검증자들이 투표를 할 때 디지털 서명을 하기 때문에 공격자가 lamport의 논문의 비잔틴이 아니며, 즉 구두 메시지(oral message)가 아니며, 서명된 메시지( signed message) 문제입니다.

둘째로, lamport의 논문에서 중위는 자신의 의견이 포함이 안됩니다.

즉, 이 논문에서 중위는 전달받은 메시지의 과반 여부로 공격과 후퇴를 결정합니다. 즉, 이것은 자신은 투표에 참여하지 않는 방법입니다.

하지만, 위 BFT는 모든 검증자가 참여하여 자신의 의사를 표시하는 투표시스템입니다.

또한 비잔틴 장군 문제는 1) 지휘관과 2) 이 지휘관의 명령을 따르는 중위로 구성되어 있습니다.

이 때문에 텐더민트의 bft도 리더를 뽑고, 이 리더가 블록을 생성한 후 검증자에게 이를 전파한 후 검증자들이 투표를 하는 방법입니다.

이런 투표 시스템에서 비잔틴 장군 문제를 회피하기 위한 제 아이디어는 다음과 같습니다.

일단 리더가 블록을 완전히 생성하고 이를 검증자들이 투표를 하는 방법을 조금 바꾸었습니다.

제 방법은 리더와 검증자가 블록을 생성하는데 부분적으로 참여하는 것입니다.

즉, 리더가 블록에 포함될 거래해시(txid)를 모두 지정하면, 검증자가 이 txid로 블록을 만들고, 이때의 블록 해시를 네트워크에 전파시키는 방법입니다.

이 방법의 특징은 블록생성은 리더와 검증자가 절반씩 참여하기 때문에 이것은 비잔틴 장군 문제가 아닙니다.

이것의 장점은 정해진 순서에 의해서 txid를 블록에 포함하면, 모든 검증자의 블록해시가 동일해야 합니다.

또한 리더도 정해진 기준에 의해서 블록에 포함될 txid를 선택하도록 강제한다면, 리더가 비잔틴이 되기도 힘들 것입니다.

4.) 결론

위와 같은 이유로 저는 암호화폐의 합의 알고리즘에서 투표시스템은 비잔틴 장군 문제가 아니라고 생각합니다.

즉, 이런 투표 시스템은 과반 문제이기 때문에, 전체 투표자의 1/2의 동의가 요구되는 시스템이라고 생각합니다.

---

이 글은 나중에 영어로 번역하여 올릴 예정입니다.
처음에는 이 내용을 논문으로 쓰려다가 증명을 해야하는 등 어려움이 예상되어서,, 내용을 간략하게 소개하였습니다.