비잔틴 장군 문제는 고장 난 프로세스가 임의로 행동하고 수신자마다 모순된 메시지를 보낼 때 정상 프로세스가 하나의 결정에 합의할 수 있는지 묻는다. Lamport, Shostak, Pease의 1982년 정식화는 서명 없는 구두 메시지에서 m명의 배신자를 허용하려면 최소 3m+1명이 필요함을 증명하고 구두 및 서명 메시지의 재귀 알고리즘을 설명한다. 이는 정확한 가정 아래의 결과이며 모든 블록체인 합의의 동의어가 아니다.
Lamport, Shostak, Pease는 복제 시스템의 상호 일관성을 설명하려고 1982년 7월 ACM TOPLAS에 비유를 발표했다. 떨어진 장군들은 하나의 계획을 골라야 하지만 배신자는 수신자마다 다른 말을 보낼 수 있다. 비잔틴 장애는 단순 중단보다 강하며 거짓말, 모순 전송, 누락, 관찰자별로 다른 정상 동작을 포함한다. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
논문은 IC1, 즉 모든 충성스러운 부관이 같은 명령을 따르는 것과 IC2, 지휘관이 충성스러우면 그 명령을 따르는 것을 구분한다. 현대 용어로는 합의 또는 안전성, 유효성, 종료 또는 활성이다. 네트워크 모델, 인증, 최대 장애 수를 명시해야 보장의 뜻이 생긴다. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
구두 메시지 모델은 직접 송신자를 알고 누락을 감지하며 모든 쌍이 통신하지만 배신자는 다른 값을 보낼 수 있다. OM(m)은 값을 재귀 중계하고 결정적 다수를 적용한다. m개 비잔틴 프로세스를 견디려면 최소 3m+1명, 즉 3분의 2 초과가 충성스러워야 한다. 세 프로세스는 거짓 지휘관과 거짓 동료를 구별하지 못한다. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
위조 불가능 서명은 모순 전송을 드러내고 충성자의 서명 명령 변경을 막는다. 알고리즘은 새 서명값을 중계하고 수집 집합에 동일한 결정을 적용한다. 이상적 가정에서는 배신자 수에 제한이 없다. 그러나 서명은 출처만 증명하고 진실, 제때 배달, 침해된 키의 정직성은 보장하지 않는다. Dolev–Strong은 이후 라운드 경계를 엄밀화했다. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
진행을 보장할 수 있는지는 시간 조건에 달려 있다. 1985년 Fischer–Lynch–Paterson의 결과에 따르면 완전히 비동기적인 결정론적 메시지 전달 시스템에서는 단 하나의 프로세스만 중단될 수 있어도 합의가 끝나지 않는 허용된 실행이 존재한다. FLP는 실제 시스템이 절대로 합의할 수 없다는 뜻이 아니다. 진행성 보장에는 결국 성립하는 시간 상한이나 특정 성질을 갖춘 장애 감지기 같은 추가 가정, 또는 무작위화 프로토콜로의 변경이 필요하다. 리더를 지정하는 것만으로는 부족하다. 네트워크가 오래 분리되면 안전한 프로토콜은 작업 완료를 멈출 수 있다. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Miguel Castro와 Barbara Liskov가 1999년 발표한 PBFT는 비잔틴 합의를 복제 상태 기계로 구현한다. 기본 구성 n = 3f+1에서 비잔틴 복제본 f개를 견딘다. 준비 완료에는 주 복제본의 pre-prepare와 일치하는 prepare 메시지 2f개가 포함되며, 로컬 확정에는 준비 완료와 일치하는 commit 메시지 2f+1개가 필요하다. 정족수의 교집합과 뷰 변경 규칙이 모순된 확정을 막는다. 인증, 일련번호, 체크포인트, 뷰 변경은 위조, 재전송 공격, 로그 증가, 결함 있는 리더에 대처한다. 알려진 복제본 집합과 결정론적 최종성은 개방형 Proof of Work 네트워크와 다르다. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin은 OM이나 PBFT를 실행하지 않으며 이름이 있는 노드 수를 세지 않는다. Sybil 공격에 저항하는 Proof of Work는 경쟁하는 이력에 누적 작업량으로 가중치를 준다. 각 Full Node는 합의 규칙을 위반하는 블록을 독립적으로 거부하고 누적 작업량이 가장 큰 유효 체인을 따른다. 일시적 분기는 예상된 현상이다. 정직한 작업량의 우세와 통신 조건을 가정하면 승인 깊이가 깊어질수록 덮어쓸 확률이 낮아지지만, 수학적인 불가역성은 아니다. Bitcoin Backbone 모델은 공격자의 작업량 비율과 네트워크 조건을 명시하여 공통 접두부, 체인 성장, 체인 품질을 형식화한다. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Bitcoin이 비잔틴 장군 문제를 해결했다는 표현은 모델의 변화를 숨기는 축약이다. 고전적 합의는 신원이 알려진 고정 집단과 장애 한도 f에서 출발한다. Bitcoin은 변동하는 가명 참여자와 외부의 희소 자원을 허용한다. 그 보장에도 메시지 전달에 관한 구체적인 가정이 필요하다. Proof of Work는 Sybil 신원의 영향력을 제한하지만 이클립스 공격, 검열, 이기적 채굴, 소프트웨어 오류, 해시레이트 과반에 의한 재구성을 막지는 않는다. 위협 모델은 공격자, 시간 조건, 구성원, 최종성을 정의해야 하며 BFT라는 이름만으로는 부족하다. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
더 정확히 이해하려면 이 항목과 함께 다음도 읽어 보세요 Nakamoto consensus, Proof of Work, 합의 규칙, 이중 지불, Bitcoin, Finality.