Distributed Consensus

Everything up to this point was mechanism. This is the actual problem.

Replication is easy: copy the data to many machines. Agreement is hard: when those machines see different things, decide which one is right — while some of them are slow, some are unreachable, and some may be lying.

The generals, and what the story is really about#

The usual framing: several generals surround a city, they must all attack or all retreat, they can only communicate by messenger, and some generals may be traitors sending contradictory orders. Can the loyal ones still reach a common plan?

Read past the costume and it describes something ordinary. Some participants may behave arbitrarily — not merely fail, but actively send different, plausible, incorrect information to different peers. A crashed node is easy; it says nothing. A Byzantine node says something different to everyone, and everything it says looks valid.

That is the situation a public blockchain is permanently in, because anyone can join and nobody vouched for them.

Where 3f+1 comes from#

The classic result: to tolerate f Byzantine participants you need at least 3f + 1 in total.

The reasoning is short. With n participants and f faulty ones, you cannot wait for more than n - f responses — the missing f may never reply. Of the n - f you did hear from, up to f may be lying. For the honest majority within your sample to be decisive, you need n - f - f > f, which rearranges to n > 3f.

FLP, and the honest version of what it says#

The other result worth knowing is FLP impossibility: in a fully asynchronous network — no bound at all on message delay — no deterministic protocol can guarantee consensus if even one participant may crash.

The intuition is that you cannot distinguish "crashed" from "very slow". A protocol that waits forever for a slow node can hang; one that gives up on it can be wrong.

This is often quoted as though consensus were impossible. It is not. Real systems escape it by weakening one assumption:

• Partial synchrony — assume messages eventually arrive within some bound, even if you do not know it. Safety always holds; liveness resumes once the network behaves. This is what PBFT-family protocols do.
• Randomisation — make the protocol probabilistic. It terminates with probability approaching one rather than with certainty. This is, in effect, what proof of work does.

Every production consensus protocol makes one of these two bargains. Knowing which one tells you how a network will behave when it is under stress.

Proof of work: no membership list required#

Voting protocols need to know who is voting. On an open network, anyone can create ten thousand identities for nothing, and any vote count becomes meaningless. That is the Sybil problem, and it is what makes open networks hard.

Proof of work's answer is to stop counting identities and start counting something that cannot be forged: computation.

To propose a block you must find a nonce such that the block's hash falls below a target. There is no shortcut; you try values until one works. The network adjusts the target so blocks arrive at a steady average rate.

  nonce = 0
while true:
    h = hash(header || nonce)
    if h < target:            # target sets the difficulty
        broadcast(block)
        break
    nonce += 1

Three consequences follow.

Identity stops mattering. You do not need to know who a miner is. You can verify their work in one hash operation.

Rewriting history costs what building it cost. To replace block 4,000 you must redo its work and every block after it, faster than the honest network is extending the current tip.

Finality is probabilistic. Two miners can find a block at once; the network briefly holds two branches and resolves to whichever accumulates more work. So a recent block might still be displaced, with a probability that falls sharply as blocks build on top.

The cost is energy, and it is not a side effect. The security is the expenditure. A cheaper proof of work is a less secure one.

BFT voting: known validators, fast finality#

Permissioned networks make a different bargain. Membership is known, so voting works, and the protocol can be explicit.

A round in a PBFT-style protocol, stripped to essentials:

1. A designated proposer broadcasts a block.
2. Every validator checks it and broadcasts a prepare vote.
3. On seeing 2f + 1 prepares, each broadcasts a commit vote.
4. On seeing 2f + 1 commits, the block is final. Not probably final. Final.

Two rounds of all-to-all messaging, which is where the n² growth lives. If the proposer is faulty or silent, validators time out and rotate to the next proposer, and the round starts again.

Reading a network's choice#

Given any chain, three questions locate its design:

1. Who may propose? Anyone with hardware, anyone with stake, or a named set.
2. How is disagreement resolved? Accumulated work, accumulated stake, or an explicit vote.
3. When is a block final? Probably, after k confirmations — or definitely, after one round.

Those three answers tell you the throughput you can expect, how the network behaves during a partition, and what an attacker would have to acquire.

Where this generalises#

None of this is specific to blockchain. Raft and Paxos solve the same agreement problem under a weaker fault model — nodes may crash but never lie — which is why they are far cheaper and why they run inside almost every distributed database you have used.

Blockchain consensus is what you reach for when "never lie" stops being a safe assumption about the other participants. That is the entire difference, and it explains the entire cost.