This page contains material for a graduate course on Blockchains, Distributed Computing, and Cryptography.

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 an email - your feedback is very valuable.

Basics, Foundations, and Classics

1. Definition of Consensus and Agreement.
2. The network model: Synchrony, Asynchrony and Partial synchrony.
3. The threshold adversary model.
4. The power of the adversary: Type (passive, crash, omission, or Byzantine), Power (unbounded, computational, or fine-grained), Adaptivity (static, delayed adaptive, weak adaptive, adaptive, or strongly adaptive), Visibility (full information or private channel), Mobility (fixed or mobile).
5. Many protocols need a trusted setup phase.

Consensus cheat sheet

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.

• Classic Byzantine agreement protocol: 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.
• How recursion helps solve consensus with optimal $O(n^2)$ message complexity.

Use of randomization in synchronous agreement protocols:

• For crash failures.
• For omission failures.

Partially Synchronous Protocols

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

Single shot Paxos.

Taking ideas from the Byzantine setting and applying them to the benign setting:

• Benign Hotstuff.
• Simplifying Raft with Chaining.
• Log Paxos is a modern take on multi-Paxos.

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.

Asynchronous Protocols

Fundamental lower bound in asynchrony: The FLP lower bound showing the impossibility of consensus under even one crash fault.

Important building blocks in asynchrony:

1. The Reliable Broadcast protocol.
2. The Reliable Gather is a multi-leader generalization of reliable broadcast.
3. We discuss how to measure round complexity in asynchrony and also improved round complexity for reliable broadcast.

Asynchronous Agreement

Living with asynchrony and eventually reaching agreement by combining binding and randomness.

Multi-world Validated Asynchronous Byzantine Agreement

Series on Binary Asynchronous Agreement:

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

Reaching Asynchronous Agreement on a Core Set.

Verifiable Information Dispersal.

State Machine Replication

Define state machine replication (SMR).

Levels of SMR fault tolerance.

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.

Nakamoto Consensus

The Bitcoin revolution brought many breakthroughs in distributed computing, economics, and cryptography. One of the striking breakthroughs in distributed computing was a new form of Byzantine Agreement now called Nakamoto Consensus.

• What is Nakamoto consensus?
• Bitcoin’s setup assumption.
• Security proof of Nakamoto consensus and an older post.
• What is the problem of selfish mining?

Lower Bounds

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

Lower bounds on the size of the adversary:

• State Machine replication can work only for minority failures:
  • 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.
  • The CAP theorem for synchrony and omission: Consensus with Omission failures even in lock step requires $f<n/2$.
  • Strengthening the lower bound: $f<n/2$ is required in lock step even if the adversary can choose either send omission or receive omission (but not both).
  • CAP type theorems in the permissionless setting
• Split brain lower bounds:
  • Dwork, Lynch, Stockmeyer (DLS 1988) 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.

• 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 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.
• Extending Dolev and Reischuk to randomized protocols against a strongly adaptive adversary.

Lower bounds on the round complexity and existence of infinite executions

• The simplest proof that any consensus protocol in asynchrony must have an infinite execution even against a single crash failure.

• The same proof also shows that any consensus protocol in synchrony must have an infinite execution against a single mobile crash failure.

• Early stopping lower bounds provide a bound on the number of rounds in execution where there are $0\leq f\leq t$ faults. In particular, in the best case executions where there are no faults at all ($f=0$).
  • $\min\{f+2,t+1\}$ round lower bound for Early Stopping for consensus with crashes and Early Deciding for uniform consensus with omission (crashes with fixed first)
• Fischer, Lynch, Paterson 1985 (FLP) lower bound, three-part series using bi-valency (uncommitted configuration) arguments:
  • 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 on the good case latency - the number of rounds when the broadcaster is non-faulty and the network is synchronous: a complete categorization
• The good case latency of optimistically responsive rotating leader protocols requires $2\Delta$.

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 when $n/4 \leq f < n/3$. So Asynchronous Verifiable Secret sharing (and Asynchronous MPC) with perfect security needs $f<n/4$.

• The SAP theorem for storing secret keys the analog of the CAP theorem for storing private keys.

Liveness attacks

• Raft does not guarantee liveness under omission faults.

Lower bounds on stronger notions of validity

• Lower bounds for strong validity

Blockchains

What is a blockchain?

What are blockchains useful for, really?

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

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

What does checkpointing a blockchain mean?

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

Cryptography

• Cryptographic hash functions.
• Merkle trees.
• A glimpse at Zero knowledge proofs
• Bilinear accumulators from polynomial commitments.
• Range proofs from polynomial commitments.
• Private set intersection: part 1 and part 2. Apple is using PSI for CSAM detection.

Polynomials

• A lightweight intro to Polynomials over a finite field.
• The basics of Polynomial secret sharing.
• The Fast Fourier Transform over finite fields.
• What is Verifiable Information Dispersal.

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.
• The BGW88 protocol for Verifiable Secret Sharing.
• Chaum’s Dining Cryptographers and the additivity of polynomial secret sharing.

Research Oriented Posts

• What is the difference between PBFT, Tendermint, SBFT, and HotStuff ? and How does HotStuff-2 relate to these protocols?

• Survey of modern Authenticated Synchronous BFT protocols (updated in March 2021).

• Sync HotStuff.

• Optimal Optimistic Responsiveness.

• Encrypted Blockchain Databases part 1 and part 2.

• Asynchronous Fault-Tolerant Computation with Optimal Resilience.

• Resolving the Availability-Finality Dilemma.

• BFT Protocol Forensics.

• Can we Obtain Player Replaceability and Forensic Support Simultaneously?

• Good-case Latency of Byzantine Broadcast: the Synchronous Case and a Complete Categorization.

• 2-round BFT SMR with n=4, f=1.

• Optimal Communication Complexity of Authenticated Byzantine Agreement

• Good-case Latency of Rotating Leader Synchronous BFT

• EIP-1559 in Retrospect

• Colordag: From always-almost to almost-always 50% selfish mining resilience

• Consensus by Dfinity: in synchrony and Consensus by Dfinity - Part II (Internet Computer Consensus): in partial synchrony

• Sandglass: Safe Permissionless Consensus.

• DAG Meets BFT - The Next Generation of BFT Consensus.

• He-HTLC - Revisiting Incentives in HTLC.

• Decentralization of Ethereum Builder Market.
• Sailfish: Improving the Latency of DAG-based BFT.
• Shoal++: High Throughput DAG-BFT Can Be Fast!.
• HotStuff-1 and the Prefix Speculation Dilemma in BFT Consensus.