Consensus: work, stake and fault tolerance

Thousands of computers, none of them in charge, with some of them possibly lying, have to agree on a single order of transactions. Leslie Lamport, Robert Shostak and Marshall Pease framed it in a 1982 paper.

Lamport describes the paper as posing the problem in terms of a group of generals, “some of whom may be traitors, who have to reach a common decision.”

A system that reaches the right decision despite some liars is Byzantine fault tolerant. The classical result: with messages that can’t be signed, agreement needs more than two thirds of the participants honest, so fewer than a third can lie.

Signatures lower that bar only on a network that delivers on time. Where messages can be delayed with no known limit, the one-third line holds even with signatures, and Ethereum’s finality has to work under that condition.

In ethereum.org’s words, “Consensus mechanisms are the complete stack of ideas, protocols and incentives” that let a network of nodes agree, and they need a way to make votes expensive (“Sybil resistance,” so nobody can vote a thousand times by running a thousand computers), and a “chain selection rule” to pick the correct history when there are two. Bitcoin and Ethereum chose different answers to the first part.