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

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.

Basic protocols

More variants of consensus and broadcast

More synchronous protocols

More partially synchronous protocols

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

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

Liveness attacks

Lower bounds on stronger notions of validity

Blockchains

What is player replaceability? A series:

Cryptography

Polynomials

Secret Sharing and MPC

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

Research Oriented Posts