Byzantine Generals & Sybil Attacks

We’ve established the goal: get untrusting, anonymous computers to agree on one ledger with no boss. Two famous obstacles stood in the way. Bitcoin’s genius is that one mechanism (Proof of Work) defeats both at once — but first you have to understand why they’re so hard.

Obstacle 1 — The Byzantine Generals Problem

This is the formal model of consensus among parties when some are malicious. It was described by Lamport, Shostak, and Pease in 1982.

The story

Several generals surround a city, each with an army. They can only communicate by sending messengers through enemy territory. They must reach a unanimous decision — all attack or all retreat. If some attack while others retreat, they lose.

Now add the hard parts:

• Some generals may be traitors who send different messages to different people (“attack” to one, “retreat” to another) specifically to sabotage agreement.
• Messengers can be delayed, lost, or even forged.

Can the loyal generals still reach reliable agreement despite traitors and unreliable messaging? That is the Byzantine Generals Problem, and “Byzantine fault tolerance” (BFT) is the name for any system that can.

Why it maps onto Bitcoin

Bitcoin’s network is exactly this scenario: thousands of computers, scattered worldwide, communicating over an unreliable internet, some of them honest and some actively trying to cheat (e.g., to double-spend). They must agree on one transaction history. Solving Byzantine agreement in an open network was widely considered the core unsolved barrier to decentralized digital cash.

The quantitative core: you need 3f + 1

The 1982 result is sharper than “it’s hard.” With oral (forgeable) messages, Byzantine agreement is only possible when fewer than one-third of participants are faulty — you need at least 3f + 1 total nodes to tolerate f traitors. The smallest case is famous: with 3 generals and 1 traitor, agreement is provably impossible — a loyal general hearing conflicting orders can’t tell which of the other two is lying.

3 generals, 1 traitor  →  IMPOSSIBLE  (no way to confirm an honest majority)
4 generals, 1 traitor  →  possible     (3f + 1 with f = 1)

Classic BFT protocols — most famously PBFT (Castro & Liskov, 1999) — do achieve this bound, but with a catch that’s fatal for our purposes: they assume a known, fixed list of participants. Everyone must know exactly who the N generals are. That assumption is precisely what an open network lacks — which leads straight into the second obstacle.

Obstacle 2 — The Sybil Attack

Suppose you try the democratic fix: let the computers vote on the correct ledger; majority wins. In a closed system with known participants, voting can work. In an open, permissionless network like Bitcoin’s, it collapses — because of the Sybil attack.

The problem with voting when identities are free

Anyone can join Bitcoin’s network. Creating a “node” is free — just run some software. So an attacker can spin up a million fake nodes and instantly command a fake majority.

Concretely: suppose the honest network is 10,000 nodes. Overnight, one attacker scripts 10,001 fake nodes on cheap cloud VMs — or even one machine presenting 10,001 identities — for trivial cost, and the “majority” is now theirs. When dishonest identities are free to mint, the honest count simply doesn’t matter.

1 attacker
   ├── fake node #1 ┐
   ├── fake node #2 ├─ all controlled by ONE actor, ~$0 each
   └── fake node #N ┘  →  a manufactured "majority" that defeats any head-count vote

This is also why PBFT-style voting can’t save us: it needs a known member list, but an open network can’t maintain one without already having a Sybil-proof way to decide who counts — the very problem we’re trying to solve.

If influence is “one identity, one vote,” and identities cost nothing, then votes cost nothing, and any attacker can manufacture as many as they like.

This is named after the book Sybil, about a person with many personalities — one real actor wearing many masks.

The crux

To make voting meaningful in an open network, you must make influence expensive and unforgeable — tied to some scarce, real-world resource that can’t be faked by copying software. Remember this sentence. The next page shows the failed attempts, and the page after reveals how Bitcoin nails it.

Putting them together

Decentralized digital money needs a mechanism that simultaneously:

1. Reaches Byzantine agreement — one consistent history even when some participants lie, and
2. Resists Sybil attacks — so an attacker can’t just fake a majority of participants.

For decades, nobody had one mechanism that did both in an open, permissionless setting. That’s the gap Satoshi closed.

Under the hood — a second reason classic BFT can’t run an open network

The page’s headline objection to PBFT is the known membership list. There’s a quieter one: message complexity. In PBFT every replica talks to every other replica to agree on each value, so traffic grows like n² — fine for a handful of servers in one data center, hopeless for thousands of anonymous nodes scattered worldwide. So even if you magically solved Sybil and handed PBFT a perfect member list, it still wouldn’t scale to a planet-sized, ever-changing network. Nakamoto consensus dodges both problems by never taking a vote at all: instead of nodes counting each other, they each independently measure the same external thing — which chain carries the most work.

Check your understanding

1. Restate the Byzantine Generals Problem in your own words. What are the two “hard parts”?
2. Why is Bitcoin’s network a real-world instance of this problem?
3. Why does “one node, one vote” fail in an open network?
4. Complete the sentence: to make voting meaningful, influence must be made ______ and ______.
5. What is the 3f + 1 requirement, and why does classic BFT’s reliance on a known membership list make it unusable for an open, permissionless network?

Show answers

1. It’s the problem of reaching unanimous agreement among parties when some are malicious and communication is unreliable: several generals must all attack or all retreat, coordinating only by messenger. The two hard parts are traitors who send conflicting messages to sabotage agreement, and messengers that can be delayed, lost, or forged.
2. Bitcoin is thousands of computers scattered worldwide, talking over an unreliable internet, with some honest and some actively trying to cheat (e.g. to double-spend) — yet they must agree on one transaction history. That is exactly Byzantine agreement, and solving it in an open network was seen as the core unsolved barrier to decentralized digital cash.
3. Because identities are free to create — running a node costs nothing — an attacker can spin up a million fake nodes (or one machine wearing 10,001 masks) for trivial cost and manufacture a fake majority. This is the Sybil attack: when votes cost nothing, any attacker can mint as many as they like, so the honest head-count stops mattering.
4. Influence must be made expensive and unforgeable — tied to some scarce, real-world resource that can’t be faked by copying software.
5. 3f + 1 is the minimum number of total nodes needed to tolerate f traitors under oral (forgeable) messages — agreement is only possible when fewer than one-third are faulty (3 generals, 1 traitor is provably impossible; 4 works). Classic BFT like PBFT hits this bound but assumes a known, fixed list of participants — and an open network can’t maintain one without already having a Sybil-proof way to decide who counts, which is the very problem being solved.