Byzantine Generals Problem

Lamport, Shostak and Pease published the allegory in ACM TOPLAS in July 1982 to explain interactive consistency in a replicated computer system. Several separated generals must choose one plan while one or more traitors may send different claims to different recipients. A Byzantine fault is therefore stronger than a crash: a faulty component may lie, equivocate, omit messages or appear correct to only part of the system. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

The paper separates two requirements. IC1: every loyal lieutenant obeys the same order. IC2: if the commanding general is loyal, every loyal lieutenant obeys the order he sends. Modern consensus usually expresses related properties as agreement or safety, validity and termination or liveness. These properties are meaningful only together with a stated network model, authentication assumptions and a maximum number of faults. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

In the paper's oral-message model, delivered messages identify their sender but can be forged only by that sender, absence can be detected, and every pair of processes can communicate directly. OM(0) follows the commander. OM(m) recursively forwards every received value through the other lieutenants and applies a deterministic majority function. To tolerate m Byzantine processes without signatures it needs at least 3m+1 participants; equivalently, strictly more than two thirds must be loyal. Three processes cannot tolerate one traitor because the loyal recipient cannot distinguish a lying commander from a lying peer. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]

Authenticated messages change the result because an unforgeable signature exposes equivocation and a traitor cannot alter a loyal participant's signed order. Lamport's signed-message algorithm relays previously unseen signed values and then applies the same deterministic choice to the collected set. Under the paper's ideal signature assumptions, Byzantine agreement is possible for any number of traitors, but signatures authenticate origin; they do not make a false statement true, deliver a delayed message or keep a compromised signing key honest. Dolev and Strong later tightened authenticated Byzantine agreement and its round bounds. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]

Whether progress can be guaranteed depends on timing. The 1985 Fischer–Lynch–Paterson result shows that a completely asynchronous deterministic message-passing system with even one process allowed to crash has an admissible execution in which consensus never terminates. FLP does not say real systems never agree. A liveness guarantee needs additional assumptions, such as eventual timing bounds or a failure detector with specified properties, or a switch to a randomized protocol. Appointing a leader alone is insufficient. During a long network partition, a safe protocol may stop completing operations. [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 and Barbara Liskov’s 1999 PBFT applies Byzantine agreement to replicated state machines. In the basic configuration n = 3f+1, it tolerates f Byzantine replicas. Being prepared includes a pre-prepare from the primary and 2f matching prepare messages; local commitment requires being prepared and 2f+1 matching commit messages. Quorum intersections and view-change rules prevent conflicting commitments. Authentication, sequence numbers, checkpoints and view changes handle forgery, replay, log growth and a faulty leader. Known membership and deterministic finality differ from an open Proof of Work network. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]

Bitcoin does not run the 1982 OM algorithm or PBFT and does not count named nodes. Sybil-resistant Proof of Work weights competing histories by accumulated work; each Full Node independently rejects blocks that violate consensus rules and follows the valid chain with the most cumulative work. Temporary forks are expected. Under assumptions about an honest work majority and communication, replacement probability falls with confirmation depth, but this is not mathematical irreversibility. The Bitcoin Backbone model formalizes common prefix, chain growth and chain quality with explicit adversarial-work and network assumptions, giving probabilistic guarantees. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]

Saying Bitcoin solved the Byzantine Generals Problem hides a model change. Classical agreement starts with a fixed group of known identities and a fault bound f; Bitcoin admits changing pseudonymous participants and an external scarce resource. Its guarantees still require concrete message-delivery assumptions. Proof of Work limits Sybil influence but does not prevent eclipse attacks, censorship, selfish mining, software bugs or a majority-hash-power reorganization. A threat model must specify the adversary, timing, membership and finality; the BFT label alone is insufficient. [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]