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, have a suggestion to improve, or any other comment: drop us a comment or send us email - your feedback is very valuable.
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.
The Synchronous model is a good place to start because protocols are simpler.
Classic Byzantine agreement protocol for $f\leq n/2$: the Phase-King.
Classic Byzantine Broadcast protocol (with a PKI) for $f < n$: the Dolev-Strong Authenticated Broadcast protocol.
A non-equivocation protocol (with a PKI) for $f < n$: Crusader Broadcast.
More recent State Machine Replication protocols:
- Sync HotStuff.
- An optimal optimistically responsive synchronous protocol.
- A simple, streamlined synchronous protocol called Streamlet.
- Survey of authenticated protocols under the synchrony assumption.
Use of randomization in synchronous agreement protocols:
Partially Synchronous Protocols
Partial synchrony is one of the most used models in real word systems today.
Single shot Paxos.
Taking ideas from the Byzantine setting and applying them to the benign setting:
The Byzantine setting:
- An important building block: provable broadcast.
- Single shot PBFT.
- Two Round HotStuff with SMR and accountability.
- Single shot to SMR is covered here.
- Information Theoretic HotStuff.
Fundamental lower bound in asynchrony: The FLP lower bound showing the impossibility of consensus under even one crash fault.
Important building blocks in asynchrony:
- The Reliable Broadcast protocol.
- The Reliable Gather is a multi-leader generalization of reliable broadcast.
- We discusses how to measure round complexity in asynchrony and also improved round complexity for reliable broadcast.
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.
Reaching Asynchronous Agreement on a Core Set.
State Machine Replication
Define state machine replication (SMR).
Levels of SMR fault tolerance.
The scalability and performance of a State Machine Replication system are not just about consensus, but also about data and execution.
Lower bounds give us powerful tools to understand the fundamental limitations and model assumptions.
Lower bounds on the size of the adversary:
Folklore (aka CAP theorem for synchrony): Consensus with Omission failures requires $f<n/2$.
The CAP theorem for partial synchrony: Any system, in the face of a perceived 50-50 split, can either maintain safety or liveness, but not both.
- Split brain attacks:
- Dwork, Lynch, Stockmeyer 1988 (DLS) lower bound: Byzantine Consensus in Partial Synchrony requires $f<n/3$.
- CJKR lower bound: Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony.
- TEEs without state need $3f+1$ in Partial Synchrony because of the rollback adversary.
- Strengthening the FLM lower bound with randomization and a weaker problem: Crusader Agreement with $\leq 1/3$ error is impossible for $n\leq 3f$ if the adversary can simulate.
Lower bounds on the number of messages
- Dolev and Reischuk 1982 (DR) lower bound: Consensus (even with omission failures) needs a quadratic number of messages.
- Extending Dolev and Reischuk to Byzantine crusader broadcast.
Lower bounds on the round complexity
- Fischer, Lynch, Paterson 1985 (FLP) lower bound, three part series:
- Consensus must have some initial state that is uncommitted:
- This implies executions with at least $f+1$ rounds in Synchrony.
- The FLP result: non-terminating executions in Asynchrony.
Lower bounds due to privacy requirements
- 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.
What is a blockchain?
What are blockchains useful for, really?
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:
- Defining the problem and achieving a committee-based sub-quadratic communication protocol
- Achieving adaptive security for the committee-based protocol
A glimpse at Zero knowledge proofs
Bilinear accumulators from polynomial commitments.
range proofs from polynomial commitments.
A lightweight mathematical intro to Polynomials over a finite field.
The basics of Polynomial secret sharing.
Secret Sharing and MPC
Polynomial secret sharing is a base for deep connections between cryptography and distributed computing.
- Polynomial secret sharing against a passive adversary
Against a crash adversary.
- Chaum’s Dining Cryptographers and the additivity of polynomial secret sharing.
Research Oriented Posts
Survey of modern Authenticated Synchronous BFT protocols (updated in March 2021).