Byzantine Generals Problem

비잔틴 장군 문제(Byzantine Generals Problem) 는 일부 참가자(노드)가 신뢰할 수 없거나 악의적인(배신자) 네트워크에서의 합이를 달성하기 위한 분산 컴퓨팅 사고 실험이다.

상황은 다음과 같다. 비잔틴 제국의 장군들이 적의 성을 포위하고 있다. 이 성은 매우 강력해서, 모든 부대가 동시에 공격해야만 함락시킬 수 있다. 만약 일부는 공격하고 일부는 후퇴하면, 비잔틴 군대는 각개격파 당해 패배한다.

하지만 장군들은 서로 멀리 떨어져 있어 전령(Messenger) 을 통해서만 소통할 수 있다. 여기서 심각한 문제가 발생한다.

  1. 배신자의 존재: 장군들 중에는 적과 내통하는 '배신자(Traitor)' 가 섞여 있을 수 있다.
  2. 거짓 정보: 배신자는 A 장군에게는 "공격하자"고 하고, B 장군에게는 "후퇴하자"고 거짓 전령을 보내 혼란을 일으킬 수 있다.
  3. 메시지 전달 실패: 전령이 가다가 적에게 잡히거나(네트워크 지연/단절), 메시지가 변조될 수 있다.

질문:

  • 배신자가 몇 명이 있든, 전령이 가끔 사라지든 상관없이, 충직한 장군들이 '동시 공격' 이라는 하나의 합의에 도달할 수 있는 완벽한 알고리즘이 존재하는가?

위 질문을 컴퓨터 과학적으로 바꾸면 다음과 같다.

일부 노드가 악의적으로 행동하고, 메시지가 손실·변조될 수 있는 환경에서, 나머지 정상 노드들이 동일한 결정을 내릴 수 있는가? 이것이 바로 분산 합의(Distributed Consensus) 문제이다.

  • 장군들: 분산 네트워크의 노드(Node)
  • 전령: 노드 간의 네트워크 통신(P2P)
  • 공격/후퇴: 블록의 유효성 검증(Valid/Invalid) 또는 합의(Consensus)
  • 배신자: 해킹당한 노드, 악의적인 채굴자, 또는 오류로 인해 엉뚱한 값을 보내는 버그가 있는 소프트웨어

램포트의 논문에 따르면, 비잔틴 장군 문제는 배신자의 수가 전체 장군의 1/3(약 33%) 보다 적을 때만 해결 가능합니다. 반대로 말하면, 배신자가 전체의 1/3 이상이면, 수학적으로 완벽한 합의는 불가능하다. (BFT 알고리즘의 한계)

사토시 나카모토는 이 문제를 수학이 아닌 '경제학' 과 '확률' 로 우회하여 해결했다. 비트코인은 비잔틴 문제에 대해서 "완벽한 합의는 불가능하니 대신 확률적으로 거의 확실한 합의를 만들자" 라는 태도를 취한다. “시간이 지나면 되돌릴 수 없는 합의” 를 만드는 것이 핵심이며, 이것이 작업 증명(Proof of Work) + Longest Chain Rule 의 본질 이다.

해법 1: 거짓말에 비용을 부과하라 (Cost):

  • 비트코인에서 배신자가 네트워크를 속이려면, 전 세계 채굴 파워의 51%를 능가하는 비용을 지불해야 한다. 이는 경제적으로 수지가 맞지 않는 장사이다.
    • 전체 네트워크의 연산력(Hash Power)이 100이고, 해커가 10을 가졌다고 가정한다.
    • 정상 네트워크는 10분마다 90의 힘으로 블록을 쌓고, 해커는 10의 힘으로 쌓는다.
    • 시간이 지날수록 정상 체인과 해커 체인의 길이 차이는 지수 함수적으로 벌어진다.
    • 따라서 해커가 기존 체인을 추월하려면 전 세계 연산력의 51% 이상을 가져야만 한다(51% Attack).

해법 2: 가장 긴 체인을 믿어라 (Longest Chain Rule):

  • 모든 장군(노드)은 10분마다 퀴즈를 푼다. 퀴즈를 푼 장군은 "공격하라(이 블록이 진짜다)"라고 외친다. 다른 장군들은 "가장 많은 에너지가 투입된(가장 긴) 명령서" 를 진실로 받아들인다. 배신자가 거짓 장부를 만들려면, 정직한 장군들보다 더 빨리 퀴즈를 풀어야 하는데, 정직한 장군들이 다수(51% 이상)라면 확률적으로 배신자는 영원히 따라잡을 수 없다.

블록체인은 "배신자가 51%를 넘지 않는다면, 시간이 지날수록 합의가 뒤집힐 확률은 0에 수렴한다" 는 확률적 합의(Probabilistic Finality) 를 채택함으로써 비잔틴 장군 문제를 현실 세계에서 해결해냈다. 블록체인은 "서로 믿을 수 없는 주체들이, 중앙의 중재자 없이도 협력할 수 있게 만든 신뢰 프로토콜(Trust Protocol)" 이며, 그 근간에는 비잔틴 장군 문제의 해결이 있다.