A commanding general sends one order, attack at dawn, to three lieutenants camped around a city. The order travels by messenger. One of the four men is a traitor, and nobody knows which one. If the traitor is the commander himself, he can tell two lieutenants to attack and the third to retreat. Can the loyal officers still end up doing the same thing? That puzzle is the Byzantine generals problem, and in 1982 Leslie Lamport, Robert Shostak and Marshall Pease showed that the answer is yes with four generals and one traitor, and no with three.
Twenty-six years later, on 13 November 2008, an unknown developer writing as Satoshi Nakamoto told a cryptography mailing list that his new design answered the same puzzle among strangers on the internet, where anyone can join and nobody keeps a list of who is who. The road between the two runs through aircraft computers, a renamed paper and an MIT file server, and it ends at two numbers that still decide how blockchains fail: one third and one half.
The Byzantine generals problem in plain words
Computers that work together fail in two broad ways. Some simply stop: a server crashes, a cable is cut. Others keep running and send wrong answers, and the worst of them send different wrong answers to different listeners. The generals story exists to make engineers take that second kind seriously. A traitor is any part that behaves arbitrarily: a broken sensor, a corrupted processor or, on a public blockchain, a participant who lies on purpose.
The previous lesson, what a consensus mechanism decides and why safety and liveness pull in different directions, set out the general question. The 1982 paper makes it exact. It reduces the whole army to one commander and his lieutenants and asks for two things. First, all loyal lieutenants obey the same order. Second, if the commander is loyal, every loyal lieutenant obeys the order he actually sent. The paper calls these the interactive consistency conditions, IC1 and IC2.
Both conditions matter. Without the first, the loyal camp splits. Without the second, the army could agree on anything, for instance always retreat, which is useless when the loyal commander says attack.
Money gives the same puzzle a familiar shape. A double spend is a traitor telling two listeners two different stories about the same coin, as the lesson on the double-spending problem showed with real attacks. A ledger shared by many computers is only useful if every honest copy tells the same story, even when some copies are run by liars.
Why three generals are not enough when one of them lies
The paper first sets the rules for what it calls oral messages, meaning messages a traitor can invent freely when he relays them. Three assumptions hold: every message that is sent is delivered correctly, the receiver knows who sent it, and the absence of a message can be detected. So the messengers are reliable. The problem sits entirely in the generals.
The three-general trap
Take a commander and two lieutenants, one of whom may be a traitor. Lieutenant 1 receives attack from the commander. Lieutenant 2 then tells him: the commander told me to retreat. Two scenarios fit those facts exactly. In the first, the commander is loyal and Lieutenant 2 is lying; IC2 then forces Lieutenant 1 to attack. In the second, the commander is the traitor and sent attack to one man and retreat to the other, while Lieutenant 2 reports honestly.
Lieutenant 1 sees the same messages in both worlds, so any rule that makes him attack in the first world makes him attack in the second. By symmetry, Lieutenant 2 in the second world must follow the order he received, retreat. The two loyal lieutenants then disagree, and IC1 breaks. The authors themselves warn readers to be “very suspicious of such nonrigorous reasoning”; their full proof is more careful than this sketch, and reaches the same conclusion.
Four generals, one traitor: the vote that saves the day
Add one loyal lieutenant and the trap opens. The algorithm the paper calls OM(1) has two rounds. In the first, the commander sends his order to each lieutenant. In the second, each lieutenant relays the order he received to the two others. Each lieutenant then takes the majority of the three values he holds. If a traitorous commander sends nothing at all, the paper fixes a default order, retreat, so that silence cannot stall the army.
The table below is our own illustration of the worst case, where the traitor is the commander and tries to split the camp.
| Lieutenant (all loyal) | Order from the commander | Orders relayed by the other two | Majority, so the decision |
|---|---|---|---|
| Lieutenant 1 | attack | attack (from L2), retreat (from L3) | attack |
| Lieutenant 2 | attack | attack (from L1), retreat (from L3) | attack |
| Lieutenant 3 | retreat | attack (from L1), attack (from L2) | attack |
Every loyal lieutenant ends with the same three values in a different order, so the majority gives each the same answer: IC1 holds. Now flip the case: the commander is loyal and says attack, and Lieutenant 3 is the traitor who relays retreat. Lieutenants 1 and 2 each hold attack, attack and retreat, so they both attack, which is what their loyal commander ordered. IC2 holds too. The traitor’s lie is outvoted because he has only one voice among three.
The general rule: more than two-thirds must be loyal
The 1982 paper generalises the result in both directions. Its abstract states that, with oral messages only, the problem is solvable “if and only if more than two-thirds of the generals are loyal”. Put in numbers: to cope with m traitors you need at least 3m + 1 generals. One traitor needs four generals, two traitors need seven, ten traitors need thirty-one. The algorithm OM(m) works for any such army by repeating the relay round m + 1 times, each general passing on what every other general claims to have heard.
That repetition is costly. The number of messages grows very fast with m, and the paper’s conclusion admits that a solution “seems to be inherently expensive”. Work by Fischer and Lynch, which the authors cite, shows that m + 1 rounds cannot be avoided. The only way to cut the cost, they write, is to assume something about which failures can happen, and the forty years since have largely been a hunt for assumptions that are cheap and still realistic.
Signed orders change the maths
The paper’s second algorithm, SM(m), adds one assumption. A loyal general’s signature cannot be forged, any change to a signed message can be detected, and anyone can check whose signature it is. Traitors may still collude and sign for one another. With that single change, the abstract says, “the problem is solvable for any number of generals and possible traitors”.
The reason is that a traitor can no longer put words in a loyal general’s mouth. In the three-general trap, Lieutenant 2 could claim the commander said retreat. With signatures he would have to show the commander’s signed order, and if the commander really did sign two different orders, both lieutenants hold the proof of his treachery and fall back on the same default. Agreement no longer depends on outnumbering the liars, only on relaying signed orders for enough rounds.
Two caveats keep this from sounding magic. First, the agreement in SM(m) is about following one commander’s order. When the goal is to agree on correct values that come from many machines, such as sensor readings, a majority of the inputs still has to be correct: Lamport’s own note on the 1980 paper puts the count at 2n+1 processors to tolerate n faults when signatures are used, against 3n+1 without them. Second, the paper’s signatures were not real cryptography. Lamport calls them “a metaphor”: they only had to resist random failures, not an intelligent adversary, so they were far easier to build than true digital signatures. Blockchains use the real thing, the kind explained in our lesson on private and public keys, which is why the signed case matters so much in practice.
Where the problem came from: aircraft computers and a renamed paper
The generals were born in avionics. In the 1970s NASA funded research at SRI International on how to make computers reliable enough to fly commercial aircraft. The project was called SIFT, and its overview paper by John Wensley and colleagues appeared in the Proceedings of the IEEE in October 1978. Lamport, who worked at SRI, says the project was perhaps most notable for producing the Byzantine generals problem and its solutions. The 1982 paper lists NASA among its funders, together with the Ballistic Missile Defense Systems Command and the Army Research Office.
The engineering worry was precise. A flight computer is made safe by running several copies of it and taking a majority vote. That works only if every copy reads the same input. A faulty sensor, or a radar site in a missile defence network, can send one value to one processor and another value to the next. Even an honest clock can cause it: two processors that read a clock while it ticks over may get the old time and the new one. Majority voting among the processors then has nothing consistent to vote on.
The results are older than the name. A 1980 paper by Pease, Shostak and Lamport, “Reaching Agreement in the Presence of Faults”, in the Journal of the ACM, already proved that 3n+1 processors are needed for n faults and gave the signature case. Lamport credits Shostak with the four-processor solution and the impossibility proof, and Pease with the general 3n+1 solution; the signed-message algorithm was his own. He also writes: “I am often unfairly credited with inventing the Byzantine agreement problem.” The problem, he says, was formulated by people working on SIFT before he arrived at SRI. The 1980 paper received the Dijkstra Prize in distributed computing in 2005.
What the 1982 paper added was the story. Lamport felt that Edsger Dijkstra’s dining philosophers, posed as a cute tale about philosophers at a table, had drawn more attention than more practical problems, and he wanted the same pull for this one. He looked for a nationality that would offend no reader. Albania was then a completely closed society, so his first title was The Albanian Generals Problem. His SRI colleague Jack Goldberg pointed out that there were Albanians outside Albania, and, in Lamport’s words, “The obviously more appropriate Byzantine generals then occurred to me.”
Lamport himself says the main reason for the new paper was to give the problem its new name. The reference is “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems, volume 4, number 3, July 1982, pages 382 to 401, and a free copy sits on Lamport’s own site: twenty pages, readable for anyone comfortable with a little induction.
The two generals problem: when the messengers get lost
The generals themselves were borrowed. Lamport says he took them from an older puzzle about two armies that must agree on whether to attack, which he notes is sometimes called the Chinese Generals Problem. That puzzle is a different one, and the two are often mixed up.
Its first published form is a 1975 paper by E. A. Akkoyunlu, K. Ekanadham and R. V. Huber, “Some Constraints and Tradeoffs in the Design of Network Communications”, presented at the fifth ACM Symposium on Operating Systems Principles (SOSP 1975, pages 67 to 74). Their appendix does not use generals at all. It tells the story of two groups of gangsters planning a job who can only coordinate by messages that may be lost on the way.
The argument runs like this. Group A sends a time. It cannot act until it knows the message arrived, so B must reply. But B cannot act until it knows its reply arrived, so A must confirm, and so on. Take any finite exchange that supposedly works and look at its last message: the sender cannot know it arrived, so the plan cannot depend on it, so a shorter exchange would have to work too. Repeat the reasoning and nothing is left. The authors note that the chain of confirmations is infinite even when no message is actually lost.
The contrast is simple to remember. In the two generals problem everybody is honest and the messengers are unreliable. In the Byzantine generals problem the messengers are reliable and some generals lie. Real networks have both troubles at once, so engineers settle for retries, timeouts and a small leftover doubt.
FLP: why no algorithm can be certain on a network with no clock
The 1982 solutions lean on a quiet assumption: a missing message can be detected. In practice that means a known maximum delivery time and clocks that agree to within a fixed error, as the paper’s section on implementation explains. Take those away and things get much worse.
In 1985 Michael Fischer, Nancy Lynch and Michael Paterson published “Impossibility of Distributed Consensus with One Faulty Process” in the Journal of the ACM. Their result covers a fully asynchronous system, where messages always arrive but may take any amount of time: “no completely asynchronous consensus protocol can tolerate even a single unannounced process death”. FLP, named after its authors, does not even need traitors. It assumes honest processes and a network that never loses a message. One process that silently stops is enough, because the others can never tell whether it has died or is just slow.
FLP does not say consensus is impossible in practice. It says no deterministic protocol can guarantee both that it always stays correct and that it always finishes, without some assumption about time. Every real protocol therefore picks a way out: a timing assumption, randomness, or both.
The way out that won came in 1988. Cynthia Dwork, Nancy Lynch and Larry Stockmeyer, in “Consensus in the Presence of Partial Synchrony” (Journal of the ACM, volume 35), assumed the network behaves badly for a while but eventually delivers messages within some bound nobody knows in advance. Their protocols never break safety, even during the bad period, and make progress once the network calms down. When the paper received the 2007 Dijkstra Prize, the prize citation described this eventual-synchrony approach as the leading way around the FLP result. PBFT, Tendermint and HotStuff all live in that partially synchronous world.
PBFT, 1999: Byzantine fault tolerance becomes practical
For seventeen years after the generals got their name, Byzantine fault tolerance stayed mostly in papers and in a few critical systems, because the known algorithms were too slow for ordinary services. Miguel Castro and Barbara Liskov of MIT changed that with “Practical Byzantine Fault Tolerance”, presented at the OSDI conference in New Orleans in February 1999.
PBFT runs a service on a fixed group of replicas, one of which acts as the primary and orders client requests. Each request passes through three phases, pre-prepare, prepare and commit, in which replicas exchange signed or authenticated messages until enough of them vouch for the same order. If the primary looks faulty or stalls, the others start a view change and the next replica takes over. With 3f + 1 replicas the system tolerates f faulty ones, and the paper notes that this is the minimum. The arithmetic behind it: any two groups of 2f + 1 replicas out of 3f + 1 overlap in at least f + 1 machines, so at least one honest machine sits in both and stops two conflicting decisions.
PBFT keeps safety even in an asynchronous network like the internet and relies on a weak timing assumption only for liveness, which, the authors write, lets it circumvent the FLP result. The headline number made engineers listen: their replicated file service was “only 3% slower than a standard unreplicated NFS”.
One assumption remained, and it matters for money. PBFT needs a known, fixed list of members. Each replica’s vote counts because each replica has an identity someone approved. On an open network that anyone can join, a single attacker can create thousands of identities and outvote everyone, which researchers call a Sybil attack. The Bitcoin white paper puts the same objection in one line: if the majority were one-IP-address-one-vote, it “could be subverted by anyone able to allocate many IPs”.
How Bitcoin solves the Byzantine generals problem with a chain of work
The Bitcoin white paper never uses the word Byzantine. The link was made in the discussion that followed. On the Cryptography mailing list, James A. Donald had argued that making everyone know that everyone knows a fact was, as in the Byzantine generals problem, the classic hard problem of distributed data processing. Satoshi Nakamoto’s reply, dated 13 November 2008 by the Nakamoto Institute’s archive, opens with a single line: “The proof-of-work chain is a solution to the Byzantine Generals’ Problem.”
He then retold the story his own way. A group of generals want to break into the king’s wi-fi by guessing the password together, and the attack only works if a majority strikes at the same time. Anyone can announce a time, and the first one each general hears counts. Instead of voting, each starts a proof of work that includes that time. If two times are proposed at once, some generals work on each, and as soon as one branch gets longer the others switch to it, since the longer chain holds more work. With every block taking about ten minutes of the whole group’s effort, he wrote that after two hours one attack time should be backed by a chain of 12 proofs of work, and every general can check that a majority must have produced it.
The trick is in what replaces the vote. The white paper says it plainly: “Proof-of-work is essentially one-CPU-one-vote.” A vote costs computation and electricity, not an identity, so fake members gain nothing. The condition, in the abstract: the system is secure as long as honest nodes together control more CPU power than any group of cooperating attackers. Our walk through the Bitcoin white paper, section by section covers the rest of the design, and how a blockchain works recalls how nodes pick one chain when two blocks appear.
Scale is the other change. PBFT was built for a small, known group of replicas. As of 7 November 2026, about 09:56 UTC, Bitcoin’s chain stood at block 974,916, and miners who never register anywhere supplied a three-day average hashrate of about 1,014 exahashes per second, according to mempool.space data.
Agreement that grows stronger with every block
Nakamoto consensus never gives the clean yes of PBFT. A block is agreed only with a probability that rises as more work piles on top of it. Section 11 of the white paper shows that an attacker with less than half the hash power falls behind at an exponential rate, so his chance of rewriting a block shrinks quickly with each confirmation. When two miners find blocks at once, the network briefly holds two branches and then settles on one; the lessons on finality and reorganisations and on soft and hard forks look at what happens when that settling goes wrong or when the rules themselves change.
Two caveats come with the honest-majority figure. Ittay Eyal and Emin Gun Sirer showed in 2013 that selfish mining, where a smart contract holding reserves of two or more tokens, supplied by users, that a decentralized exchange uses to execute trades automatically at a price set by a formula.">pool withholds blocks to waste others’ work, pays off for colluding groups well below one half; their proposed fix only protects against pools below one quarter of the hash power. That debate belongs to a later lesson on network attacks. The other caveat is concentration. Over the week to 7 November 2026, mempool.space attributed 23.1% of blocks to Foundry USA, 19.8% to AntPool and 17.3% to F2Pool, so three pools found 60.1% of blocks. A pool coordinates many independent miners who can leave it, so this is not ownership of hash power, but in practice the honest majority depends on the choices of a handful of coordinators. What a majority attacker could and could not do is set out in why a blockchain is hard to rewrite.
Is Bitcoin Byzantine fault tolerant? A disputed label
Many articles call Nakamoto consensus probabilistic Byzantine fault tolerance. The label is contested. Satoshi called the chain a solution to the problem. Juan Garay, Aggelos Kiayias and Nikos Leonardos, in their analysis “The Bitcoin Backbone Protocol” (Eurocrypt 2015), proved that the chain gives two lasting guarantees, which they call common prefix and chain quality, when the attacker holds less than half of the hashing power and the network is fast. On Byzantine agreement in the strict sense, though, they write that “Nakamoto’s suggestion falls short of solving it”. They describe a simple variant that does reach agreement if the attacker holds at most one third of the hash power, and a more elaborate one that works below one half under strong network timing.
Their abstract adds that the attacker’s share the system can survive shrinks as the network becomes less synchronous. Rafael Pass, Lior Seeman and abhi shelat, in a 2016 analysis, drew a similar picture: the chain stays consistent and live when message delays have a known bound, and a simple attack works in a fully asynchronous network, so the puzzle difficulty has to be set against the maximum delay. A fair summary: Bitcoin reaches an agreement that becomes practically certain over time, among anonymous participants, under assumptions about hash power and network delay. Whether that deserves the name Byzantine agreement depends on the definition you start from, and the literature does not settle it.
Today’s BFT blockchains: vote, finalise, or stop
Many proof-of-stake chains went back to the voting route, now with stake standing in for identity: a validator’s vote weighs as much as the tokens it has locked, which makes fake identities pointless again. The basics of that model sit in our proof-of-stake glossary entry; a full lesson on proof of stake will come later in this path.
Tendermint, described by Ethan Buchman, Jae Kwon and Zarko Milosevic in a 2018 paper, adds gossip-based messaging to the PBFT idea. Its engine today is CometBFT, a fork of Tendermint Core used by many chains built with the Cosmos tools. The CometBFT specification assumes that less than one third of the voting power is Byzantine, requires more than two thirds of precommit votes to commit a block, and says openly that “any 1/3+ coalition of validators can halt the blockchain by not broadcasting their votes”. If a fork ever did happen, the specification shows that more than a third of validators would have signed two conflicting blocks, which can be proved and punished.
That is the core trade-off of classic BFT: when too many voters are missing or lying, the chain stops rather than splits. Terra gave a public, if unusual, example on 12 May 2022. During the collapse of LUNA and UST, its validators halted the chain at block 7,603,700 to prevent governance attacks, since the price crash had sharply lowered their cost, Cointelegraph reported that day. The network was to go live again once two thirds of the voting power came back online, with new delegations disabled. It was a deliberate decision by the validators, not an automatic stall, but it rested on the same two-thirds rule.
HotStuff, by Maofan Yin, Dahlia Malkhi, Michael Reiter, Guy Golan Gueta and Ittai Abraham (2018, published at PODC 2019), is a leader-based, partially synchronous protocol whose communication grows only linearly with the number of replicas, including when the leader changes, where PBFT’s view change was much heavier. Several newer chains built their consensus on ideas from that family; Tendermint and HotStuff get their own lesson later in this path.
Ethereum mixes both worlds. Its fork-choice rule, LMD-GHOST, keeps the chain moving block by block, much like a heaviest-chain rule. On top of it, the Casper-FFG finality vote marks checkpoints as final once validators holding at least two thirds of the total staked ETH agree, and, according to ethereum.org’s proof-of-stake documentation, reverting a finalized block would cost an attacker at least one third of all staked ETH. As of 7 November 2026, about 09:56 UTC, a public beacon node showed the finalized epoch two epochs behind the head (487,553 against a head at epoch 487,555), which is the normal rhythm when the vote works.
One third or one half: the numbers to remember
Each line of the table below has its own assumptions, so read the second column before comparing the numbers.
| System | Fault and network model | Tolerates | What it needs |
|---|---|---|---|
| Byzantine generals, oral messages (1982) | arbitrary liars, synchronous network | m traitors | at least 3m + 1 generals (4 for 1 traitor) |
| Byzantine generals, signed messages (1982) | liars cannot forge loyal signatures | any number of traitors, for one commander’s order | signatures and synchrony |
| FLP (1985) | one silent crash, no clocks | none, if certainty is required | a timing assumption or randomness |
| PBFT (1999) | Byzantine replicas, safe even in asynchrony | f faulty out of 3f + 1 | a fixed, known group of replicas |
| Tendermint / CometBFT | Byzantine validators weighted by stake | less than 1/3 of voting power | more than 2/3 of precommits; 1/3 or more can halt |
| Ethereum finality (Casper-FFG) | Byzantine stakers | less than 1/3 of stake for finality safety | at least 2/3 of staked ETH to finalize |
| Bitcoin (Nakamoto consensus) | hash-power attacker, bounded delays | less than 1/2 of hash power, with probabilistic agreement | most cumulative work; selfish mining lowers the bar |
Read the table as a choice between two failure styles. A BFT chain with a two-thirds vote is final the moment the vote closes, but it can be stopped by one third of the voters. A Nakamoto chain keeps producing blocks whatever happens, but any recent block stays reversible in principle, and agreement is a matter of depth.
For a user, that difference is concrete. On a chain with BFT finality, a payment that is final will not be undone without a large, provable slashing of validators. On Bitcoin, the receiver chooses how many blocks to wait, and exchanges set their own confirmation counts for deposits.
Permissioned chains vote, public chains work: the NIST view
For readers in the United States, the clearest official description of these choices is the National Institute of Standards and Technology’s report NIST IR 8202, “Blockchain Technology Overview” (October 2018). It describes multi-round voting among stakers, which it says is sometimes referred to as Byzantine fault tolerance proof of stake, and round-robin block production used by some permissioned blockchain networks, where members are known and approved.
That split explains many enterprise projects. A consortium of banks or suppliers already knows its members, so the Sybil problem never arises and a PBFT-style vote gives fast, final agreement. A public network such as Bitcoin has no gatekeeper, so it pays for security with work. The NIST report is a technical overview, not a rule.
Key points
- The Byzantine generals problem asks how the honest parts of a system can agree when some parts lie, and lie differently to different listeners.
- With unsigned messages, more than two thirds must be honest: 3m + 1 participants for m liars. Unforgeable signatures lift that limit for following one leader’s order.
- The two generals problem (1975) is about lost messages between honest parties, not about liars.
- FLP (1985) rules out guaranteed consensus without timing assumptions; partial synchrony (1988) became the standard way around it, and PBFT (1999) made BFT fast for a known group of members.
- Bitcoin swapped the member list for proof of work and accepts agreement that firms up block by block, below half of the hash power in its basic model; classic BFT chains tolerate less than a third of bad voting power and halt rather than fork.
The next lesson, proof of work in depth, opens the box Satoshi pointed to: how a miner hashes a block header, how difficulty keeps blocks near ten minutes and what an attack on the work would cost today.
