The foundations of validation

A protocol can allow a million validators and still depend on a handful of operators. Stake gathers in pools and custodians; many validators run the same software on the same few cloud providers, so one bug or one outage can remove a large share at once. Running several independent software clients, and splitting one validator’s key among several machines, are the usual defences.

Validators are paid for doing their duties and lose a little for missing them. Provable misbehaviour — signing two conflicting blocks, or two contradictory votes — is punished by destroying part of the stake, called slashing; Vitalik Buterin proposed it in 2014. It answers the “nothing at stake” problem: without a penalty, voting for every competing chain at once would cost nothing.

In proof of work a block only becomes less likely to be reversed as more blocks are built on it. Proof-of-stake protocols can do better: once validators holding two-thirds of the stake have voted for a block, reversing it would require at least a third of all stake to contradict itself provably, and be slashed. Casper FFG, published in 2017, proved this property under the name “accountable safety”; it is widely known as “economic finality”.

One validator proposes each block, chosen pseudo-randomly with probability in proportion to stake. The randomness must be unpredictable, or the next proposer can be attacked in advance, and hard to bias, or proposers will steer it. Verifiable random functions — Micali, Rabin and Vadhan, 1999 — let a validator prove it was selected without anyone knowing beforehand.

In an open network identities are free, so votes cannot be counted per participant. They are weighted instead by something scarce. Proof of work, in the Bitcoin paper of 2008, weights by computation. Proof of stake weights by locked capital: the idea was set out on a public forum in 2011 and first implemented, in hybrid form, in Peercoin in 2012.

Pease, Shostak and Lamport showed in 1980, and restated in 1982 as the “Byzantine generals problem”, that without unforgeable signatures agreement is possible only if fewer than a third of the participants are faulty in arbitrary — “Byzantine” — ways. Fischer, Lynch and Paterson showed in 1985 that with no bound on message delay, no deterministic protocol can guarantee agreement if even one participant may fail. Practical protocols therefore assume delays are eventually bounded, the model of Dwork, Lynch and Stockmeyer (1988). Castro and Liskov made such a protocol efficient in 1999.

A blockchain is one program run in step by many computers. Each must apply the same transactions in the same order. Checking that a block obeys the rules is something every node does for itself; agreeing which valid block comes next is consensus, and that is the validators’ work.