# 04 — Consensus Picture the moment the last module set up: two miners find valid blocks in the same second. Both chains are internally flawless — every hash checks out, every signature verifies. Ten thousand nodes now have to pick one, with no coordinator, and some fraction of them actively lying. How would you break the tie? [[01 Replicated State Machines]] named this exact job: in the log → apply → state pipeline, consensus is the middle column — the machinery that produces *one canonical order* for every replica to apply. Raft and Paxos get that one order cheaply, because a trusted leader and a crash-only quorum are enough to arbitrate. Here the leader might be lying, the quorum might be colluding, and lying might be profitable. Producing one order under those conditions — with no "same team" assumption to fall back on — is what the rest of this module supplies. Consensus, then, hides two questions that sound alike but aren't: *which block comes next?* and *when is the answer final?* Keep them separate as you read — the distinction pays off. ## A. Proof of Work Bitcoin's approach: make proposing blocks expensive. **Miners** vary a field called `nonce` in the block header until: ```text hash(block_header) < target ``` The lower the target, the harder the search. Finding a solution takes quintillions of guesses; checking one takes a single hash. Whoever finds it proposes the next block, and the chain-selection rule is simply: > Follow the valid chain with the most accumulated work. "Accumulated work" is not just block count — a deeper chain with higher total difficulty wins, even if it has fewer blocks. Why does this work? Because rewriting history now means redoing its work — faster than the honest network extends it. An attacker doesn't need to break any cryptography; they need to out-spend everyone else's electricity bill, indefinitely. The defense isn't mathematical impossibility. It's economics. The finality this produces is probabilistic: no block is ever absolutely final, but each block built on top makes reversal exponentially less likely. Bitcoin's "6 confirmations" folklore is just a conventional risk tolerance, not a magic threshold. More in [[Finality]]. ### Why "accumulated work" only grows — and why catching up gets exponentially harder Two separate facts are hiding inside "follow the chain with the most accumulated work." Untangling them gives you the actual mechanism, not just the folklore. **Fact 1 — accumulated work is a running total.** Each block's difficulty target implies an *expected* number of hash attempts to solve it — call it `work(B_i)`. The chain's score is a running sum, exactly like an accumulator variable in a loop: ```text total_work(chain) = work(B_0) + work(B_1) + ... + work(B_n) ^ monotonic accumulator — every new block only adds, never subtracts ``` That alone explains "longer, harder-worked chains win" — same reason a running total that only ever adds positive terms can't go down. Nothing subtle yet. The subtlety is in fact 2. **Fact 2 — rewriting an old block means redoing a growing suffix.** You saw the mechanism in [[03 Blocks, Hashes, and History]]: change `B_k`, its hash changes, `B_{k+1}.parent_hash` no longer matches, so `B_{k+1}` needs fresh proof-of-work too, which breaks `B_{k+2}`, and so on to the tip: ```text Attack B_k, currently (n - k) blocks deep: redo PoW(B_k) — new nonce, new hash → breaks B_{k+1}.parent_hash redo PoW(B_{k+1}) — reseal it → breaks B_{k+2}.parent_hash redo PoW(B_{k+2}) — reseal it ... redo PoW(B_n) — meanwhile the honest chain added B_{n+1}, B_{n+2}, ... ``` Every block you must reseal is another independent proof-of-work puzzle — another draw from `work(B_i)`. The deeper the target block, the more puzzles stand between it and the tip you're racing to overtake. "More confirmations" isn't a vague comfort blanket; it's literally more accumulated work standing in the way. **Why "harder" is exponential, not linear — the footrace.** Here's the part worth sitting with. The attacker isn't chipping away at a fixed backlog while the world stands still — the honest network keeps mining new blocks the entire time the attacker works in private. So this is a race between two accumulators, one running faster than the other (assuming the attacker holds less than half the network's hash power). That setup is the classic **gambler's ruin** problem from probability, wearing a different costume. Treat the attacker's deficit — how many blocks behind — as a gambler's losses in a biased coin-flip game. If the attacker wins any given "lap" with probability `q` and the honest network wins with `p = 1 - q`, where `q < p`, the probability the attacker *ever* fully catches up from `z` blocks behind is approximately: ```text P(catch up from z blocks behind) ≈ (q / p)^z ``` That's exponential decay in `z`, not linear. Going from 1 block behind to 6 doesn't make the task 6× harder — it raises `(q/p)` to the 6th power. A modest disadvantage compounds fast. This is the actual mechanism behind the Bitcoin whitepaper's confirmation-count math (section 11, for the full derivation) — the reason "6 confirmations" sits on a curve that's already falling steeply, even though the exact cutoff is still a chosen risk tolerance, not a law of nature. **The curve, drawn out.** Numbers make the shape of "exponential" concrete faster than algebra does. Here's `P(catch up from z blocks behind)` for two attackers — a small miner with 10% of network hash power, and a much bigger one with 30%: ```text P(attacker eventually overtakes), by depth z [≈ (q/p)^z] small miner (q=0.10) large pool (q=0.30) z=0 100.0% #################### 100.0% #################### z=1 11.1% ## 42.9% ######### z=2 1.2% 18.4% #### z=3 0.1% 7.9% ## z=4 0.0% 3.4% # z=5 0.0% 1.4% z=6 0.0% 0.6% ``` Read it left to right, not just top to bottom. Both bars collapse fast — that's the exponential. But notice *how much* faster the small miner's bar disappears: by block 2 it's already visually zero, while the large pool's bar is still limping along past block 6. That's why "how many confirmations is safe" isn't one universal number — it depends on who you think you're defending against. A payment processor worried about a stray small miner can relax after 2-3 blocks; an exchange worried about a well-funded attacker wants more, which is exactly why some exchanges require far more than 6 confirmations for large deposits. **Tying it together.** "Most accumulated work" is a running sum (fact 1) that an attacker must out-produce across a growing suffix of blocks (fact 2), while racing a moving target whose lead compounds exponentially against them if they're the minority (fact 3, gambler's ruin). Structure — the hash-pointer chaining from Module 03 — is what makes the suffix exist at all. Economics — the cost of hash power — is what makes winning that race a losing proposition without a majority. Same split named at the end of the last module: structure makes tampering evident; economics makes it expensive. | **Good** | **Bad** | |---|---| | Simple, battle-tested | Energy-intensive | | Permissionless | Low throughput | | Robust incentives | Probabilistic finality | | No validator registry needed | Mining centralization pressure | ## B. Proof of Stake Ethereum's current answer replaces burned electricity with capital at risk. A few terms before the flow: - **Validator** — a participant who locks (stakes) ETH and may propose or vote on blocks. - **Attestation** — a signed vote for what a validator believes is the correct chain head. - **Checkpoint** — a boundary in the chain where finality can be declared. - **Slashing** — destroying a validator's staked collateral as punishment for misbehavior. - **Equivocation** — signing two incompatible statements about the chain head (the main slashable offense). The rough loop: 1. Validators stake ETH. 2. One is selected to propose a block. 3. Others attest to what they see as the head. 4. Votes justify and finalize checkpoints. 5. Misbehavior gets penalized or slashed. The shift in mechanism is worth appreciating. Proof-of-work makes history expensive to *produce*. Proof-of-stake makes contradiction expensive to *survive*: a validator who signs two conflicting blocks has created cryptographic evidence of its own misbehavior, and the protocol uses that evidence to destroy its stake. Finality becomes economic: a finalized block can only revert if a large fraction of all staked capital knowingly commits a slashable offense. In other words, the guarantee has a price tag — and unusually for security guarantees, the price is public. | **Good** | **Bad** | |---|---| | Energy efficient | More protocol complexity | | Faster economic finality | Stake centralization risk | | Slashing punishes equivocation | Liquid staking concentration | | More flexible than PoW | Governance/social recovery assumptions | ## C. BFT consensus The third family predates blockchains entirely. **Byzantine** replicas may lie or collude — not just crash. Classical Byzantine fault tolerance — PBFT, Tendermint, HotStuff — are voting protocols designed for that threat model. PBFT is the classic academic reference; Tendermint and HotStuff are modern descendants common in appchains. The standard bound, as in [[01 Replicated State Machines]] and [[Distributed Systems Bridges]]: ```text n >= 3f + 1 ``` to tolerate `f` Byzantine nodes (`f` = how many may lie), with agreement proceeding in voting rounds: ```text propose -> prevote -> precommit -> commit ``` If this looks like Paxos with an extra round, that's roughly what it is — the extra round exists because nodes may lie, so every claim needs a quorum that can be cross-checked against other quorums. The reward is immediate, deterministic finality: once two-thirds sign, the block is committed, and forks simply don't happen in normal operation. The catch? Someone has to know who the validators are. BFT trades openness for speed — which is why you find it in appchains and consortium settings more than in open, planetary-scale systems. | **Good** | **Bad** | |---|---| | Fast, deterministic finality | Smaller validator sets | | Efficient | More permissioned | | Good for appchains | Harder at huge open scale | ## D. The two families, side by side | **Feature** | **Nakamoto-style** | **BFT-style** | |---|---|---| | Canonical chain | Heaviest/longest valid chain | Quorum-signed block | | Finality | Probabilistic | Deterministic/economic | | Participation | Very open | Validator-set based | | Latency | Slower | Faster | | Forks | Normal | Exceptional | | Examples | Bitcoin, early Ethereum | Tendermint, HotStuff-like systems | **Nakamoto consensus** (Bitcoin-style): the longest or heaviest valid chain wins; forks are normal; finality is probabilistic. ## Ethereum's hybrid design (Gasper) Here's a satisfying detail: Ethereum PoS is deliberately *both*. It combines two mechanisms with easy-to-mix-up names: - **LMD-GHOST** — the fork-choice rule. Validators' attestations pick which head to build on; there's always a tip, even during network trouble. - **Casper-FFG** — the finality gadget. Checkpoints become irreversible after enough attestations; misbehavior is slashable. - **Gasper** — the name for using both together: liveness from Nakamoto-style fork choice, finality from BFT-style checkpoints. See [[Distributed Systems Bridges]] for fork choice vs finality as separate questions. ## Fork choice vs finality Now let's give the two questions from the opening their proper names. **Fork choice** answers: given competing valid heads, which one do I build on? ```text B3a / B0-B1-B2 \ B3b ``` Proof-of-work answers with accumulated work; proof-of-stake with accumulated attestations. Either way, fork choice runs constantly and silently on every node — it's the background hum of the network. **[[Finality]]** answers: when do I stop worrying that the choice will change? Because until finality, the tip of the chain is provisional — and sometimes it genuinely moves. That's a [[Reorgs|reorg]]: canonical history switching branches. Here's the counterintuitive part for anyone from traditional systems: in Nakamoto consensus, shallow reorgs are routine weather, not disaster. The practical consequence is that anything built on top of a chain must treat pre-finality data as provisional. Indexers that forget this credit deposits twice ([[08 Nodes, RPCs, and Indexers]]). And one honest footnote beneath all of it: social finality. When something breaks catastrophically enough, humans decide which software to run. Every chain has this layer; the well-designed ones just make sure it's almost never needed. ## Learning outcomes Questions worth trying on: - Could you explain to a distributed-systems colleague what Nakamoto consensus achieves that Paxos can't — and what it pays for the privilege? - If someone claims "proof-of-stake is just voting by the rich," could you steelman the objection and then answer it, using slashing? - Could you explain why Ethereum wants *both* a fork-choice rule and a finality gadget — and what breaks with only one? - A payment lands in a block. Under PoW, PoS, and Tendermint respectively: when would you ship the goods, and why? - Could you explain why reversing a transaction 6 blocks deep isn't "6× harder" than reversing one 1 block deep, but *far* harder than that — and name the probability argument underneath? - And the thread to pull forward: a block has been chosen. Now something has to actually *run* its transactions, identically, on every node. What kind of machine can promise that? ## Checkpoint 1. What does `n >= 3f + 1` assume? *(Hint: `f` is how many nodes may lie; you need enough honest nodes to outvote them. If unsure, revisit "BFT consensus" or [[Distributed Systems Bridges]].)* 2. Why does a deeper reorg cost exponentially more under proof-of-work, and what's the proof-of-stake analogue of that cost? *(If unsure, revisit "Why 'accumulated work' only grows..." in section A, then section B, then [[Reorgs]].)* 3. Fork choice and finality — one sentence each, plus one sentence on why they're different questions. *(Hint: fork choice = which head to build on now; finality = when that choice is irreversible. If unsure, revisit "Fork choice vs finality", [[Finality]], or [[Distributed Systems Bridges]].)* **Exercise.** Add naive proof-of-work to your toy chain from module 03: a difficulty target, a mining loop, the longest-chain rule. Then simulate two nodes mining concurrently and let one reorg the other. Watch a transaction vanish from history in your own code — it produces exactly the right kind of unease, and you'll never design a naive indexer afterward. ## Resources - **Stanford CS251** — the consensus lectures; the best structured treatment of both families. - **Ethereum.org docs: Consensus, Gasper, Proof-of-Stake** — canonical description of the hybrid design. - **Bitcoin whitepaper** — still the cleanest few pages on Nakamoto consensus ever written. --- Next: the block is chosen. Now every node must compute the same new state from it — how? → [[05 Execution and Smart Contracts]]