## Consensus cheat sheet

Crash Omission Byzantine Synchrony $f&lt;n$ is possible $f+1$ round executions must exist $f \geq n/2$ is impossible $f&lt;n/2$ possible with PKI / PoW $f \geq n/3$ impossible without PKI/PoW Partial Synchrony $f \geq n/2$ is impossible $f&lt;n/2$ is possible $f&lt;n/3$ is possible $f \geq n/3$ is impossible Asynchrony non terminating executions must exist $f&lt;n/2$ possible in $O(1)$ expected $f&lt;n/3$ possible in $O(1)$ expected [Read More]
Tags: dist101

## Nakamoto's Longest-Chain Wins Protocol

In this post, we will cover Nakamoto’s Consensus protocol presented in the Bitcoin whitepaper. There are a lot of posts and videos that explain this seminal and simple protocol. Our goal in this post will be to intuitively piece out the need for different aspects of the protocol, such as proof-of-work and how network synchrony plays a role in the protocol. [Read More]

## Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$ if the Adversary can Simulate

The classic FLM lower bound says that in Synchrony, Byzantine Agreement is impossible when $n \leq 3f$. We discussed this important bound in a previous post. In this post we strengthen the FLM lower bound in two important ways: Maybe randomization allows circumventing the FLM lower bound? No! Even allowing $\leq 1/3$ error, this bound still holds (based on unpublished work of Yao and Karlin, see the work of Graham... [Read More]

## Distributed consensus made simple (for real this time!)

Multi-Paxos is the de facto solution for deciding a log of commands to execute on a replicated state machine, yet it’s famously difficult to understand, motivating the switch to ‘simpler’ consensus protocols such as Raft. The conventional wisdom is that the best way to use Paxos (aka Synod, or single-shot Paxos), to decide a log of commands is to run many instances of it, where the $i^{th}$ instance decides the... [Read More]
Tags: dist101 paxos

## The round complexity of Reliable Broadcast

Reliable Broadcast is an important building block of many Asynchronous protocols. There is a broadcaster that has some input value, $v$, and a non-faulty party that terminates needs to output a value. Reliable Broadcast is defined via two properties: [Read More]

## Optimal Communication Complexity of Authenticated Byzantine Agreement

Communication complexity of Byzantine Agreement (BA) has been studied for decades. Dolev and Reischuk showed that quadratic communication is necessary for BA with perfect security, i.e., without error. Berman, Garay, and Perry showed that this lower bound is tight for the unauthenticated setting (without signatures) with $f &lt; n/3$. However, for $f \ge n/3$, the best solution so far is still the Dolev-Strong protocol with cubic communication, so a linear... [Read More]

## Information Theoretic HotStuff (IT-HS): Part One

This post is the first of two on Information Theoretic HotStuff (IT-HS). Information Theoretic HotStuff is a Byzantine Consensus protocol in the partially synchronous model. It replaces all of HotStuff’s cryptographic signatures with simple information theoretic message passing techniques over authenticated channels. Information theoretic protocols are often easy to reason about, form a great introduction for learning the basics of consensus, have less of an attack surface, and highlight useful... [Read More]
Tags: dist101

## The Private Set Intersection (PSI) Protocol of the Apple CSAM Detection System

In this post, we will discuss the cryptographic construction used in Apple’s new system for detecting CSAM - Child Sexual Abuse Material. This cryptographic construction implements a new variant of PSI - Private Set Intersection. While a lot of attention has been paid to the broad implications of this system, the technical details of the PSI construction have not been highlighted, even though Apple published a detailed technical description of... [Read More]

## Simplifying Raft with Chaining

Raft is a consensus algorithm for deciding a sequence of commands to execute on a replicated state machine. Raft is famed for its understandability (relative to other consensus algorithms such as Paxos) yet some aspects of the protocol still require careful treatment. For instance, determining when it is safe for a leader to commit commands from previous leaders or when it is safe for servers to delete or overwrite commands... [Read More]

## Benign Hotstuff

In this post we describe a variant of Paxos (or Raft or Lock-Commit) that is inspired by looking through the lens of HotStuff and Blockchain protocols. The most noticeable difference is that while Paxos and Raft aim to maintain a stable Primary/Leader (and change views infrequently), in Benign Hotstuff (as in HotStuff), the Primary is rotated every round! A more subtle difference is that in Paxos and Raft each block... [Read More]

## Living with Asynchrony: the Gather protocol

A very useful tool in Asynchronus distributed computing is Reliable Broadcast, or simply called Broadcast. It allows a leader to send a message, knowing that all parties will eventually receive the same message, even if a malicious adversary control $f$ parties and $f&lt;n/3$. Broadcast is deterministic and takes just a constant number of rounds. [Read More]

## Good-case Latency of Byzantine Broadcast: the Synchronous Case

In our first post, we presented a summary of our good-case latency results for Byzantine broadcast (BB) and state machine replication (SMR), where the good case measures the latency to commit given that the broadcaster or leader is honest. In our second post, we discussed our results for partial synchrony, and described a new BFT SMR protocol named (5f-1)-SMR that can commit a decision within $2$ rounds in the good... [Read More]