The view synchronization problem lies at the heart of many Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocols in the partial synchrony model, since these protocols are usually based on views. Liveness is guaranteed if honest processors spend a sufficiently long time in the same view during periods of synchrony, and if the leader of the view is honest.
Ensuring that these conditions occur, known as Byzantine View Synchronization (BVS), has turned out to be the performance bottleneck of many BFT SMR protocols.

A recent line of work has shown that, by using an appropriate view synchronization protocol, BFT SMR protocols can achieve $O(n^2)$ communication complexity in the worst case after GST, thereby finally matching the lower bound established by Dolev and Reischuk in 1985. However, these protocols suffer from two major issues:
(a) When implemented so as to be optimistically responsive, even a single Byzantine processor may infinitely often cause $\Omega(n\Delta)$ latency between consecutive consensus decisions.
(b) Even in the absence of Byzantine action, infinitely many views require honest processors to send $\Omega(n^2)$ messages.

Here, we present Lumiere, an optimistically responsive BVS protocol which maintains optimal worst-case communication complexity while simultaneously addressing the two issues above: for the first time, Lumiere enables BFT consensus solutions in the partial synchrony setting that have $O(n^2)$ worst-case communication complexity, and that eventually always (i.e., except for a small constant number of “warmup” decisions) have communication complexity and latency which is linear in the number of actual faults in the execution.

Lumiere pdf, PODC 2024.

This is joint work with Dahlia Malkhi, Oded Naor, and Kartik Nayak.

Blockchain protocols typically aspire to run in the permissionless setting, in which nodes are owned and operated by a large number of diverse and unknown entities, with each node free to start or stop running the protocol at any time. This setting is more challenging than the traditional permissioned setting, in which the set of nodes that will be running the protocol is fixed and known at the time of protocol deployment. The goal of this paper is to provide a framework for reasoning about the rich design space of blockchain protocols and their capabilities and limitations in the permissionless setting.
This paper offers a hierarchy of settings with different “degrees of permissionlessness”, specified by the amount of knowledge that a protocol has about the current participants: These are the fully permissionless, dynamically available and quasi-permissionless settings.
The paper also proves several results illustrating the utility of our analysis framework for reasoning about blockchain protocols in these settings. For example:
(1) In the fully permissionless setting, even with synchronous communication and with severe restrictions on the total size of the Byzantine players, every deterministic protocol for Byzantine agreement has an infinite execution in which honest players never terminate.
(2) In the dynamically available and partially synchronous setting, no protocol can solve the Byzantine agreement problem with high probability, even if there are no Byzantine players at all.
(3) In the quasi-permissionless and partially synchronous setting, by contrast, assuming a bound on the total size of the Byzantine players, there is a deterministic protocol proof-of-stake protocol for state machine replication.

(4) In the dynamically available, authenticated, and synchronous setting, no optimistically responsive
state machine replication protocol guarantees consistency and liveness, even when there are no Byzantine players at all.
(5) In the quasi-permissionless and synchronous setting, every proof-of-stake protocol that uses only time-malleable oracles is vulnerable to long-range attacks.

Permissionless Consensus: pdf

This is joint work with Tim Roughgarden.

This journal version of the paper subsumes the earlier conference versions “Byzantine Generals in the Permissionless Setting” and “Resource Pools and the CAP Theorem”, substantially revises the frameworks presented in those papers, and presents a number of new results.

a16z asked me to produce a list of resources for those who want to get quickly up-to-date with the consensus literature. You can find it here.

View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficiency of view synchronisation is measured as the word complexity and latency required for moving from being synchronised in a view of one correct leader to being synchronised in the view of the next correct  leader.

The efficiency of view synchronisation has emerged as a major bottleneck in the efficiency of SMR systems as a whole. A key question remained open: Do there exist view synchronisation protocols with asymptotically optimal quadratic worst-case word complexity that also obtain linear message complexity and responsiveness when moving between consecutive correct leaders? 

We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming minimal clock synchronisation, called \emph{Fever}.  If $n$ is the number of processors and $t$ is the largest integer $<n/3$, then Fever has resilience $t$, and in all executions with at most $0\leq f\leq t$ Byzantine parties and network delays of at most $\delta \leq \Delta$ after $GST$ (where $f$ and $\delta$ are unknown), Fever has worst-case word complexity $O(fn+n)$ and worst-case latency $O(\Delta f + \delta)$.

Fever: pdf (OPODIS 2023)

This is joint work with Ittai Abraham.

While the original purpose of blockchains was to realize a payment system, it has been shown that, in fact, such systems do not require consensus and can be implemented deterministically in asynchronous networks. State-of-the-art payment systems employ Reliable Broadcast to disseminate payments and prevent double spending, which entails O(n^2) communication complexity per payment even if Byzantine behavior is scarce or non-existent.
Here we present Flash, the first payment system to achieve O(n) communication complexity per payment in the good case and O(n2) complexity in the worst-case, matching the lower bound. This is made possible by sidestepping Reliable Broadcast and instead using the blocklace — a DAG-like partially-ordered generalization of the blockchain — for the tasks of recording transaction dependencies, block dissemination, and equivocation exclusion, which in turn prevents doublespending.
Flash has two variants: for high congestion when multiple blocks that contain multiple payments are issued concurrently; and for low congestion when payments are infrequent.

Flash: An Asynchronous Payment System with Good-Case Linear Communication Complexity, pdf.

This is joint work with Ehud Shapiro and Oded Naor.

Here is a link to a tutorial I recently gave on direct acyclic graph (DAG) based consensus protocols at a16z. In this talk, I introduce DAGs, which allow blocks to have multiple parents or children, thus resolving the problem of “forks” in blockchains. The resulting structure is a Directed Acyclic Graph (rather than a chain). I show how to think about such structures and then focus on state-of-the-art protocols such as Cordial Miners, DAG-Rider, and Bullshark.

Link to talk

Proofs in the consensus literature are often presented without much explanation as to why protocols are defined the way they are, and without a clear narrative navigating the different results achieved by a zoo of possible setup assumptions. These notes (under construction) attempt to rectify that. The aim is to give clear and succinct explanations of the most important results from the literature. I’ll post updates frequently…

Consensus in 50 pages, pdf

Here are some links to recent talks I gave at a16z, which are based on these notes:

Intro to Consensus Part I

Intro to Consensus Part II

Before the collapse of Terra, I performed an analysis showing that it was a matter of when not if the currency would collapse (unless serious changes were made). Here are the slides of a talk I gave explaining this analysis at a16z this summer.

Terra talk slides pdf

We consider the message complexity of State Machine Replication protocols dealing with Byzantine failures in the partial synchrony model. A result of Dolev and Reischuk gives a quadratic lower bound for the message complexity, but it was unknown whether this lower bound is tight, with the most efficient known protocols giving worst-case message complexity O(n^3). We describe a protocol which meets Dolev and Reischuk’s quadratic lower bound, while also satisfying other desirable properties. To specify these properties, suppose that we have n replicas, f of which display Byzantine faults (with n≥3f+1). Suppose that Δ is an upper bound on message delay, i.e. if a message is sent at time t, then it is received by time max{t,GST}+Δ. We describe a deterministic protocol that simultaneously achieves O(n^2) worst-case message complexity, optimistic responsiveness, O(fΔ) time to first confirmation after GST and O(n) mean message complexity.

Message Goat, pdf