Start Here

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

Basics, foundations, and classics

1. Definition of Consensus, Agreement, and Broadcast.
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.
6. Finality Is in the Eye of the Behodler

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.
• The partial synchrony progress cheat sheet summarizes how progress arguments and leader changes fit together in partially synchronous protocols.

Basic 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.
• Partial synchrony is one of the most used models in real-world systems today.
  • Single-shot Paxos.
  • Single-shot PBFT.

More variants of consensus and broadcast

• Approximate agreement is a variation that considers rational input values.
• Several relaxations of Broadcast.
• Agreement under omission failures with non-uniformity and weak validity shows how relaxing uniform agreement and strong validity changes what is possible.

More synchronous 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)$ communication.
• A non-equivocation protocol (with a PKI) for $f < n$: Crusader Broadcast.
• Use of randomization in synchronous agreement protocols for crash failures and omission failures.
• Scalable Agreement obtains near-linear expected communication and constant expected time against a weak adaptive omission adversary.

More partially synchronous protocols

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.
• What is responsiveness?.
• Some design principles.
• Practical Byzantine Fault Tolerant Consensus (PBFT).
• Two Round HotStuff with SMR and accountability.
• Information Theoretic HotStuff.

Simplex and variants

• From Tendermint to Simplex
• Benign Simplex
• From Benign Simplex to Byzantine Simplex
• 2-round BFT in Simplex style
• 2-round BFT in Simplex style for n=5f-1
• Concurrent 2-round and 3-round Simplex-style BFT
• Variants of Simplex with Reduced Bad-case Latency: C-Simplex and Kuplex
• Concurrent 2-round and 3-round BFT protocols under granular synchrony
• Partial Synchrony variants.

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.
• From single-shot consensus to SMR.
• To learn about SMR protocols, 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.
• The scalability and performance of a State Machine Replication system are not just about consensus, but also about data and execution.
• A simple payment system.

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?
• An Analysis of Latency and Block Capacity in Nakamoto Consensus studies the strategic latency-capacity trade-off in fast-block regimes.

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 worst-case 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

• Why BFT in partial synchrony and $3f+1$ needs three rounds
• 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 was the first blockchain (or how to timestamp a digital document)?
• What are blockchains useful for, really?
• 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
• Blind signatures and threshold encryption.
• 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.

Math

• Lagrange’s Theorem through the algorithmic lens.

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

Protocol design and analysis

• 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.
• 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
• Consensus by Dfinity: in synchrony and Consensus by Dfinity - Part II (Internet Computer Consensus): in partial synchrony
• Sandglass: Safe Permissionless Consensus.
• HotStuff-1 and the Prefix Speculation Dilemma in BFT Consensus.
• Carry: HotStuff Linearity with Tail-Forking-Resilience.
• Reasoning about Distributed Protocols with Smart Casual Verification.

Systems and applications

• 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?
• EIP-1559 in Retrospect
• Colordag: From always-almost to almost-always 50% selfish mining resilience
• He-HTLC - Revisiting Incentives in HTLC.
• Decentralization of Ethereum Builder Market.
• DPaaS - Improving Decentralization by Removing Relays in Ethereum PBS.

DAG protocols

• DAG Meets BFT - The Next Generation of BFT Consensus.
• Sailfish: Improving the Latency of DAG-based BFT.
• Shoal++: High Throughput DAG-BFT Can Be Fast!.
• What’s DAG got to do with it?.
• Graded dispersal with perfect security.