This page contains material for a graduate course on Blockchains and Distributed Computing with a dash of Cryptography (stay tuned for more). Or read posts chronologically.

We would love to get your feedback. If you find a post helpful or have a suggestion to improve, drop us a comment on Twitter.

Basics, Foundations, and Classics

Start with the definition of Consensus and Agreement. Then learn about the network model, the threshold adversary model, and the power of the adversary. Many protocols need a trusted setup phase. The consensus cheat sheet gives a quick overview of what is possible and impossible. You can build half a course just from the upper bounds and lower bounds linked from it.

Variants of Consensus and Broadcast

Approximate agreement is a variation that considers rational input values.

This post covers several relaxations of Broadcast.

Synchronous Protocols

The Synchronous model is a good place to start because protocols are simpler.

For a simple and classic synchronous Byzantine agreement protocol, checkout Phase-King.

Under synchrony, a classic Byzantine Broadcast protocol (with a PKI) is the Dolev-Strong Authenticated Broadcast protocol.

More recent State Machine Replication protocols such as Sync HotStuff, an optimal optimistically responsive synchronous protocol, and a simple, streamlined synchronous protocol called Streamlet. This post provides a survey of authenticated protocols under the synchrony assumption.

For a simple non-equivocation protocol, see Crusader Broadcast.

Partially Synchronous Protocols

Partial synchrony is one of the most used models in real word systems today.

Modern variants of the classic protocols of Paxos and Raft are covered in Benign Hotstuff and Simplifing Raft with Chaining. Log Paxos is a modern take on multi-Paxos. It is both surprisingly simple and concretely efficient.

An important building block is provable broadcast.

Single shot Paxos, followed by single shot PBFT, followed by Two Round HotStuff. The path from single shot to SMR is covered here.

For Byzantine adversaries, see Information Theoretic HotStuff.

Asynchronous Protocols

One of the core challenges of distributed computing is tolerating failures in an asynchronous network. The classic FLP lower bound is a fundamental result showing the impossibility of consensus under even one crash fault.

A basic building block in asynchrony is the Reliable Broadcast protocol.

How do you measure round complexity in asynchrony (and can you improve the round complexity of reliable broadcast)?

The multi-leader generalization of reliable broadcast is called Reliable Gather.

Series on Asynchronous Agreement:

Define the problem;
present Ben-Or’s protocol;
provide a modern version;
Introduce Crusader Agreement and Binding Crusader Agreement;
use BCA to efficiently solve Binary Byzantine Agreement from a strong common coin.

State Machine Replication

This post defines state machine replication (SMR). There are several levels of SMR fault tolerance.

This post formally defines the ideal state machine model and Linearizability.

The scalability and performance of a State Machine Replication system are not just about consensus, but also about data and execution.

How DAGs improve the performance of SMR.

To learn about upper bounds, start with a simple SMR for crash failures. Then extend SMR to omission failures: First via single shot and then via the lock-commit paradigm to multi-shot consensus.

In partial synchrony, Log Paxos shows how to extend Paxos to multi-Paxos in a straightforward and efficient manner.

Lower Bounds

Lower bounds give us powerful tools to understand the fundamental limitations and model assumptions.

Folklore (aka CAP theorem): Consensus with Omission failures requires $f<n/2$.
Dwork, Lynch, Stockmeyer 1988 (DLS) lower bound: Byzantine Consensus in Partial Synchrony requires $f<n/3$.
Fischer, Lynch, Merritt (FLM)lower bound: Byzantine Consensus with no PKI (or more generally when the adversary can simulate) requires $f<n/3$.
Strengthening the FLM lower bound: Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$ if the Adversary can Simulate.
Dolev and Reischuk 1982 (DR) lower bound: Consensus often needs a quadratic number of messages.
Fischer, Lynch, Paterson 1985 (FLP) lower bound: Consensus must have some initial state that is uncommitted and this implies executions with at least $f+1$ rounds in Synchrony and non-terminating executions in Asynchrony (the FLP impossibility).
Ben-Or, Kelmer, Rabin 1994 (BKR) lower bound: Asynchronous Verifiable Secret Sharing must have a non-zero probability of not terminating.
Raft does not guarantee liveness under omission faults.
CJKR lower bound: Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony.

Blockchains

What is a blockchain?

What are blockchains useful for, really?

What was the first blockchain (or how to timestamp a digital document)?

What is Nakamoto Consensus? How do you prove Nakamoto Consensus is secure?

Do proof-of-work blockchains need any setup assumptions??

What does checkpointing a blockchain mean?

What is the problem of selfish mining?

The simplest L2 solution is a payment channel.

What is player replaceability? A series:

Cryptography

Some important tools:

Cryptographic hash functions.
Merkle trees.
A lightweight mathematical intro to Polynomials over a finite field.
The basics of Polynomial secret sharing.
A glimpse at Zero knowledge proofs
Bilinear accumulators from polynomial commitments.
range proofs from polynomial commmitments.
Private set intersection: part 1 and part 2. Apple is using PSI for CSAM detection.

Polynomial secret sharing is a base for deep connections between cryptography and distributed computing.

Polynomial secret sharing agains a passive adversary, against a crash adversary.

The BGW88 protocol for Verifiable Secret Sharing.

Chaum’s Dining Cryptographers and the additivity of polynomial secret sharing.

Start Here