In this series of posts, we explore the marvelous world of consensus in the Asynchronous model. In this third post, we present a modern version of Ben-Or’s classic protocol that is part of our new work on Asynchronous Agreement. In the first post we defined the problem and in the second post we presented Ben-Or’s protocol. This is a simplified version extracted from our paper.
[Read More]
Asynchronous Agreement Part Two: Ben-Or's protocol
We continue to explore the marvelous world of consensus in the Asynchronous model. In this post, we present Ben-Or’s classic protocol from 1983. In the next post, we will present a more modern version that is a simplified version from our paper.
[Read More]
Asynchronous Agreement Part One: Defining the problem
In this series of posts, we explore the marvelous world of consensus in the Asynchronous model. In this post, we start by simply defining the problem. Recall the FLP theorem:
[Read More]
Consensus by Dfinity - Part I
This is part one of a two-part post on consensus protocols published by the Dfinity Foundation.
[Read More]
Consensus by Dfinity - Part II (Internet Computer Consensus)
This post is part two of a two-part post on consensus protocols published by the Dfinity Foundation; you can find part one here. This post will intuitively explain the Internet Computer Consensus.
[Read More]
EIP-1559 In Retrospect
On August 5, 2021, Ethereum implemented Ethereum Improvement Proposal 1559 (EIP-1559) on its mainnet as part of the London Hardfork, which modified the transaction fee mechanism on Ethereum from a first price auction to one that involves blocks of varying sizes, separating transaction fees as history-dependent base fees and tips, and burning of the base fees. How does such a mechanism fare in practice?
[Read More]
Colordag: From always-almost to almost-always 50% selfish mining resilience
The Selfish mining attack against blockchain protocols was discovered and formalized in 2013 by Eyal and Sirer (also see our blog post). The Bitcoin community has mentioned similar types of attacks in 2010. This attack remains a vulnerability of all operational blockchains we are aware of. For Bitcoin’s blockchain algorithm (under reasonable network assumptions), a coalition controlling over 1/4 of the mining power can improve its revenue using this attack....
[Read More]
Blockchain Resource Pools and a CAP-esque Impossibility Result
The consensus layers of different blockchain protocols can look very different from one another. For example, to achieve sybil-resistance, some protocols use proof-of-work (selecting each block producer randomly, with probability proportional to its computational power), while some use proof-of-stake (with probabilities proportional to the amount of locked-up stake). To achieve consensus, some blockchain protocols use a longest-chain rule to resolve forks in-protocol, while others use BFT-style consensus to (with high...
[Read More]
Good-case Latency of Rotating Leader Synchronous BFT
Synchronous consensus protocols can tolerate $f < n/2$ Byzantine failures but for $n/3 <f <n/2$ must depend on the maximum network delay $\Delta$ for their safety and progress. So these protocols must set $\Delta$ to be much larger than the actual network delay $\delta \ll \Delta$. The good news is in the multi-shot (blockchain) scenarios, modern synchronous protocols such as Sync HotStuff can essentially pipeline the $\Delta$-dependent delay:
[Read More]
Consensus cheat sheet
Crash Omission Byzantine Synchrony $f<n$ is possible $f+1$ round executions must exist $f \geq n/2$ is impossible $f<n/2$ possible with PKI / possible with PoW FLM: $f \geq n/3$ impossible without PKI/PoW Partial Synchrony CAP: $f\geq n/2$ is impossible Paxos: $f<n/2$ is possible $f<n/3$ is possible DLS: $f \geq n/3$ is impossible Asynchrony FLP: non-terminating executions must exist $f<n/2$ possible in $O(1)$ expected rounds $f<n/3$ possible in $O(1)$ expected...
[Read More]
The Ideal State Machine Model: Multiple Clients and Linearizability
We introduced state machines and state machine replication in an earlier post. In this post, we elaborate on the exact notion of safety and liveness that can be obtained by an ideal state machine when there are multiple clients.
[Read More]
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]
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 < 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]
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]
Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony
In this post, we explore a theorem of Clement, Junqueira, Kate, and Rodrigues from PODC 2012 regarding the limits of non-equivocation. Informally, this theorem says that neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony.
[Read More]