# 비잔틴 장군 문제 (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) 항목도 참고하십시오.

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

---
출처: https://achivx.kr/glossary/byzantine-generals-problem-%EB%B9%84%EC%9E%94%ED%8B%B4-%EC%9E%A5%EA%B5%B0-%EB%AC%B8%EC%A0%9C/ · ACHIVX 용어 사전 · 수정일 2026-10-20