The Byzantine generals problem: two loyal villagers per liar, and how Bitcoin dodged it
The Byzantine generals problem asks how a group can agree on a plan when some members lie. In 1982, Lamport, Shostak and Pease proved that with ordinary messages you need more than two-thirds honest members. Proof-of-stake chains still live by that bound, and Bitcoin's proof of work found a way to agree without counting members at all.
Three houses in the village must decide together whether to open the new mill on Monday. They can't meet; they can only send messages. Anna decides and sends word to the other two: Monday. One of them is the miller. The other is Ben.
Ben tells the miller: "Anna told me Tuesday." Now the miller holds one "Monday" from Anna and one "Anna said Tuesday" from Ben. Either Anna sent two different orders, or Ben is lying. From where the miller sits, both look the same. Three houses, one liar, no safe decision.
Add a fourth honest house, and the honest ones can outvote the noise. That's the Byzantine generals problem in a sentence: how many liars can a group survive and still agree? The answer, proved in 1982, is under one-third. Many proof-of-stake chains still live by it.
What it is
The Byzantine generals problem is the question of how independent parties can reach the same decision when some of them may send false or conflicting messages. The 1982 paper opens with the real-world version: "Reliable computer systems must handle malfunctioning components that give conflicting information" (Lamport, Shostak and Pease, 1982).
A system that keeps working despite such liars is called Byzantine fault tolerant. A blockchain is exactly that kind of system: thousands of computers that must agree on one notebook, some of which may be broken or run by Ben.
How it unfolded
- April 1980: the bound. Marshall Pease, Robert Shostak and Leslie Lamport publish "Reaching agreement in the presence of faults" in the Journal of the ACM. In his notes on his own papers, Lamport credits the key result to his co-author: "Pease invented the 3n+1-processor solution" (Lamport).
- July 1982: the generals. The same three, at SRI International, publish "The Byzantine Generals Problem" in ACM Transactions on Programming Languages and Systems. With ordinary messages, it is "solvable if and only if more than two-thirds of the generals are loyal." And: "no solution with fewer than 3m + 1 generals can cope with m traitors" (Lamport, Shostak and Pease, 1982).
- The name. Lamport's notes say he first wanted "The Albanian Generals Problem", until a colleague pointed out that there were Albanians outside Albania. "The obviously more appropriate Byzantine generals then occurred to me" (Lamport).
- The escape hatch. The same paper shows that with unforgeable signed messages the problem "is solvable for any number of generals and possible traitors". Ben can't claim Anna said Tuesday if Anna signs her messages. Digital signatures would become a pillar of every blockchain.
- February 1999: practical. Miguel Castro and Barbara Liskov of MIT present Practical Byzantine Fault Tolerance (PBFT), an algorithm that "works in asynchronous environments like the Internet", using three rounds of messages called pre-prepare, prepare and commit. Their test file service was "only 3% slower" than one without the protection (Castro and Liskov, 1999). The catch: everyone has to know the list of participants.
- 13 November 2008: no list needed. Replying on the Cryptography Mailing List, Satoshi Nakamoto writes: "The proof-of-work chain is a solution to the Byzantine Generals' Problem." In his story, generals agree on an attack time by building on the first chain they hear, and "After two hours, one attack time should be hashed by a chain of 12 proofs-of-work" (Nakamoto, 2008). Nobody counts generals. They count work.
The arithmetic of 3f + 1
To survive f liars you need at least 3f + 1 members. Recomputed for a few sizes:
- 4 members: survives 1 liar.
- 21 members: survives 6. Seven liars would need 22.
- 27 members: survives 8. Nine would need 28.
That last number should look familiar. TRON's 27 Super Representatives solidify a block once 19 of them have built on it (TRON docs), so 9 silent producers can stall it.
Ethereum counts stake instead of heads, but keeps the bound: checkpoints need votes "representing at least two-thirds of the total staked ETH" (ethereum.org). A third of the stake can stall the seal. More than a third, slashed, is what it costs to break one.
Why it matters
- It sets the danger line. Every BFT-style chain is safe while liars hold under a third, of members or of stake. Above that, the maths stops helping.
- It explains the Sybil problem. Counting heads only works if heads can't be faked. Bitcoin made a vote cost work; proof of stake makes it cost a deposit. "Proof of work vs proof of stake" weighs the two.
- Who pays. Honest members pay in extra messages and waiting. That's the price of not having to trust anyone.
Where people get it wrong
- "Bitcoin solved a problem nobody had solved." PBFT solved it in 1999 for known members. Bitcoin's step was open membership, where anyone can join without permission.
- "51% honest is enough." For classic BFT agreement with ordinary messages, the paper's line is more than two-thirds. Bitcoin's honest-majority rule rests on a different model, counting work instead of votes.
- "It's about armies." The generals are a story. The paper was about computer systems with failing parts.
Count your liars
Next time a project says its network is "Byzantine fault tolerant", ask two things: how many parties sign, and who decides who they are? If it's 21 friends of the founder, the 3f + 1 maths protects you from six of them going rogue at once, and from nothing else.
Ben, for his part, has learned to sign his messages. It didn't help. Now everyone can prove what he said.
Frequently asked questions
What is the Byzantine generals problem?
It is the problem of getting independent parties to agree on one decision when some of them may lie or send conflicting messages. Leslie Lamport, Robert Shostak and Marshall Pease described it in a 1982 paper using generals who can only communicate by messenger.
Why do you need more than two-thirds honest participants?
The 1982 paper proved that with ordinary messages, no solution with fewer than 3m + 1 participants can cope with m traitors. So at most one-third minus one can be dishonest. With three participants and one liar, the honest two can't tell who is lying.
What is Byzantine fault tolerance?
It is the ability of a system to keep working correctly even when some of its parts fail or act maliciously. Blockchains need it because any participant might be faulty or dishonest.
Did Bitcoin solve the Byzantine generals problem?
Satoshi Nakamoto wrote on 13 November 2008 that the proof-of-work chain is a solution to it. Earlier solutions such as PBFT worked for a known list of participants; Bitcoin's approach lets anyone join by counting computing work instead of members.
What is PBFT?
Practical Byzantine Fault Tolerance is an algorithm by Miguel Castro and Barbara Liskov, presented in February 1999. It lets a known group of replicas agree over a network like the Internet, tolerating up to one-third faulty members, through three message phases.
Sources
- Marshall Pease, Robert Shostak and Leslie Lamport, Reaching agreement in the presence of faults (Journal of the ACM, April 1980), as listed in Leslie Lamport's publications page
- Leslie Lamport, Robert Shostak and Marshall Pease, The Byzantine Generals Problem (ACM TOPLAS, vol. 4, no. 3, July 1982)
- Miguel Castro and Barbara Liskov, Practical Byzantine Fault Tolerance (OSDI, New Orleans, February 1999)
- Satoshi Nakamoto, Re: Bitcoin P2P e-cash paper (Cryptography Mailing List, 13 November 2008), via the Satoshi Nakamoto Institute
- ethereum.org, Proof-of-stake (PoS)
- TRON protocol documentation, DPoS consensus mechanism

