Examples#
This gallery walks through blockchainkit.consensus, one experiment per
breakthrough on the consensus history page: Byzantine agreement, randomized and
partially synchronous consensus and the FLP impossibility, PBFT, pricing
functions and proof of work, Nakamoto consensus and GHOST, the attacker’s
odds and selfish mining, and proof of stake with sortition, slashing and
finality.
Each script is self-contained and runs with
python examples/consensus/<section>/<script>.py.
Agreement protocols#
Byzantine generals, randomized and partially synchronous consensus, and PBFT.
The Byzantine generals problem (Lamport, Shostak and Pease 1982)
Randomized consensus: agreeing by flipping coins (Ben-Or 1983)
FLP: no deterministic consensus in an asynchronous network (1985)
Partial synchrony: timeouts that eventually work (Dwork, Lynch and Stockmeyer 1988)
Practical Byzantine Fault Tolerance (Castro and Liskov 1999)
Attacks and their probabilities#
Catching up from behind, double spending, and selfish mining.
The gambler’s ruin: catching up from behind (Pascal, Fermat and Huygens 1656)
How many confirmations? Nakamoto’s double-spend calculation (2008)
Selfish mining: majority is not enough (Eyal and Sirer 2014)
Nakamoto consensus#
Cumulative-work fork choice and GHOST.
Nakamoto consensus: a payment, a fork, and a reorganization (2008)
GHOST: follow the heaviest subtree (Sompolinsky and Zohar 2013)
Proof of stake#
Stake-weighted selection, nothing at stake, sortition, and finality.
Proof of stake: a stake-weighted proposer lottery (Peercoin 2012)
Nothing at stake: why proof of stake needs penalties (Buterin 2014)
Cryptographic sortition: a secret, stake-weighted committee (Algorand 2017)
Casper FFG: finality by two-thirds votes and slashing (Buterin and Griffith 2017)
Proof of work#
Pricing functions, Hashcash, and difficulty retargeting.
Pricing via processing: making junk mail expensive (Dwork and Naor 1992)
Hashcash: proof of work you can verify in one hash (Back 1997)
Difficulty retargeting: keeping ten-minute blocks (Bitcoin 2009)