이 글을 이해하기 위해서 컴퓨터 공학 지식이 필요하지 않습니다.
Byzantine Generals Problem (비잔틴 장군 문제)
1982년 논문에서 처음으로 언급된, 컴퓨터 공학에서 널리 알려져 있는 문제입니다.
- 여러 장군들이 각자의 부대를 지휘하고 있다.
- 장군들은 다른 장군에게 전령을 통해서만 이야기 할 수 있다.
- 장군들은 적을 관측한 후, 둘 중 하나의 결정 (공격 혹은 후퇴)를 내려야만 한다.
- 충성스런 장군들은 전령의 이야기가 타당하다면 움직이지만, 배신자 장군은 전령의 이야기를 따를 수도, 따르지 않을 수도 있다.
위 조건에서, 충성스런 장군들은 하나의 동일한 전략을 선택할 수 있어야 하고, 소수의 배신자 장군은 이 결정에 영향을 줄 수 없어야 합니다.
논문은 전체 장군 중 충성스러운 장군이 2/3을 초과 (more than) 하는 경우, 조건을 만족하는 방법이 있다고 설명합니다. 다시 말하면, 배신자 장군이 n명 섞여 있다면, 동일한 결정을 내리기 위해 3n + 1의 장군이 필요하다는 뜻이기도 합니다.
예)
- 장군이 3명 있다면, 그 중 1명이 배신자 인 경우, 남은 2 장군을 혼란스럽게 할 수 있습니다.
- 장군이 4명 있다면, 그 중 1명이 배신자 이어도, 남은 3 장군은 동일한 결정을 내릴 수 있습니다.
2명의 충성스런 장군과 1명의 배신자
A B C 3명의 장군이 있습니다. A가 전략을 결정하여 B와 C에게 전령을 보냅니다. A의 전령을 받은 B와 C는 자신이 받은 이야기를 서로에게 전달합니다.
최종적으로 B와 C는 2통의 메시지를 받습니다.
- A 에서 바로 온 메시지
- A가 배신자인 경우, A는 B와 C에게 서로 다른 메시지를 보낼 수 있습니다.
- B 혹은 C를 거쳐서 온 메시지
- B 혹은 C가 배신자인 경우, A의 지시와 다른 메시지를 상대에게 보낼 수 있습니다.
이 경우, 메시지가 2개 밖에 없기 때문에, 어느 쪽이 진실인지 판단할 방법이 없습니다.
3명의 충성스런 장군과 1명의 배신자
이번에는 4명의 장군 A B C D를 같은 방식으로, B C D는 자신을 제외한 3 장군의 전령을 각자 받습니다.
- A가 배신자인 경우, 선택지는 공격 혹은 후퇴 밖에 없기 때문에, B C D 중 2 명에게 같은 지시를 내려야 합니다.
- B C D는 받은 지시를 충실하게 다른 장군들에게 전달합니다.
- B C D 중에 배신자가 1명 있는 경우, A는 동일한 지시를 내리고, 배신자를 제외한 다른 2명은 A의 지시를 다른 장군들에게 충실하게 전달합니다.
자신을 제외한 3명의 장군 중에 배신자가 1명 섞여 있다고 하더라도, 다수결에 의해 충성스런 장군들은 공격이든 후퇴든 동일한 전략으로 움직일 수 있게 됩니다.
Blockchain Network
Byzantine Generals Problem 를 다시 풀어보면, 아래와 같습니다.
- 독립적인 컴퓨터들
- 인터넷 네트워크를 통해서만 다른 컴퓨터에 연락할 수 있으며
- 컴퓨터들은 특정한 목적을 위해 협력해야만 하고,
- 그 중에는 정상적이지 않은 컴퓨터들이 섞여 있다.
P2P Network 를 사용하는 Blockchain 이 성립하기 위해서는, 필연적으로 Byzantine Generals Problem 을 해결하기 위한 방법이 필요합니다. 네트워크를 구성하는 소수가 훼방을 놓아 전체 참여자가 영향을 받는다면, 그 누구도 Blockchain Network 를 신뢰할 수 없기 때문입니다.
이렇게 시스템을 구성하는 일부에 문제 (배신자 혹은 불안정한 상태)를 허용하는 시스템을 Byzantine Fault Tolerance (BFT) 라고 부르기도 합니다.
Reference
- Lamport, L.; Shostak, R.; Pease, M. (1982), "Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems.