비잔틴 장군 문제 (Byzantine Generals Problem)

비잔틴 장군 문제는 집단의 모든 구성원이 하나의 전략에 합의해야 하지만, 일부 구성원이 배신할 수 있고 서로 주고받는 통신을 신뢰하거나 확인할 수 없는 상황에서 합의에 도달하는 문제입니다. 분산 시스템에서 일부 노드가 고장 나거나 악의적으로 거짓 정보를 보낼 때도 정상 노드들이 같은 결정에 이르게 하는 문제를 비유적으로 표현한 것입니다.

문제의 설정

레슬리 램포트, 로버트 쇼스탁, 마셜 피스가 1982년 논문 「The Byzantine Generals Problem」에서 정식화했습니다. 도시를 에워싼 여러 장군이 공격할지 후퇴할지 결정해야 하며, 전령을 통해서만 연락할 수 있습니다. 일부 장군은 배신자로서 장군마다 서로 다른 메시지를 보낼 수 있습니다. 논문은 이를 지휘관 한 명이 나머지 장군(부관)들에게 명령을 보내는 형태로 정리하며, 해법은 다음 두 조건을 만족해야 합니다.

1. 합의: 모든 충성스러운 장군은 같은 결정을 내립니다.
2. 타당성: 지휘관이 충성스럽다면, 충성스러운 장군들은 지휘관의 명령을 따릅니다.

3f + 1의 한계

서명 없이 구두 메시지만 주고받는 경우, 배신자가 f명일 때 문제를 풀려면 장군이 최소 3f + 1명 있어야 합니다. 예를 들어 장군이 세 명이고 그중 한 명이 배신자라면, 충성스러운 장군은 누가 거짓말을 하는지 구별할 수 없습니다. 반면 위조할 수 없는 서명을 쓰면 메시지 출처를 확인할 수 있어 더 적은 수의 정직한 참가자로도 합의가 가능합니다. 또한 메시지 지연에 상한이 없는 완전 비동기 네트워크에서는 단 하나의 고장 노드만 있어도 결정적 합의 알고리즘이 항상 끝난다고 보장할 수 없다는 결과(FLP 불가능성, 1985)도 알려져 있습니다.

블록체인이 문제를 다루는 방식

• 고전 BFT 프로토콜: PBFT(1999) 같은 프로토콜은 참가자 목록이 정해져 있다는 전제에서 n ≥ 3f + 1개의 노드로 투표를 여러 단계 진행해 확정적인 합의를 냅니다. Tendermint 계열과 여러 지분 증명 체인이 이런 방식을 응용합니다.
• 작업 증명(나카모토 합의): 비트코인은 참가자 목록 없이 누구나 참여할 수 있는 환경에서, 투표권을 계산 능력에 연동하고 가장 많은 작업이 쌓인 체인을 따르게 합니다. 정직한 참가자가 해시 파워의 과반을 가진다는 전제에서, 블록이 쌓일수록 결과를 뒤집기 어려워지는 확률적 합의를 얻습니다.

암호화폐와의 관계

블록체인에서는 노드가 장군, 거래 내역이 전략에 해당합니다. 일부 노드가 거짓이거나 부정확한 거래 정보를 퍼뜨려도 정직한 노드들이 같은 원장에 합의해야 이중 지출을 막을 수 있습니다. 이렇게 일부 참가자의 임의적 고장이나 악의적 행동을 견디는 성질을 비잔틴 장애 허용(BFT)이라고 합니다. 비잔틴 장애 허용(BFT) 항목도 참고하십시오.

같은 원리는 항공기 비행 제어처럼 중복된 구성 요소가 서로 다른 값을 낼 수 있는 안전 필수 시스템에서도 쓰입니다.