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.

Synchronous Protocols

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

More recent State Machine Replication protocols:

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:

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 discusses how to measure round complexity in asynchrony and also improved round complexity for reliable broadcast.

Series on 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.

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.

Lower Bounds

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

Lower bounds on the size of the adversary:

Lower bounds on the number of messages

Lower bounds on the round complexity and existence of infinite executions

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$.

Liveness attacks

Lower bounds on stronger notions of validity


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:



Secret Sharing and MPC

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

Research Oriented Posts