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.
(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 guaranteed to solve the Byzantine agreement problem in a finite amount of time.
(4) In the quasi-permissionless and synchronous setting, every proof-of-stake protocol that does not use advanced cryptography is vulnerable to long-range attacks.

Permissionless Consensus: pdf

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.

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.

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.

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

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

This is joint work with Ittai Abraham.

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

Blockchain protocols come with a variety of security guarantees. For example, BFT-inspired protocols such as Algorand tend to be secure in the partially synchronous setting, while longest chain protocols like Bitcoin will normally require stronger synchronicity to be secure. Another fundamental distinction, directly relevant to scalability solutions such as sharding, is whether or not a single untrusted user is able to point to certificates, which provide
incontrovertible proof of block confirmation. Algorand produces such certificates, while Bitcoin does not. Are these properties accidental? Or are they inherent consequences of the paradigm of protocol design? Our aim in this paper is to understand what, fundamentally, governs the nature of security for permissionless blockchain protocols. Using the framework developed in ‘Byzantine Generals in the Permissionless Setting’, we prove general results showing that these questions relate directly to properties of the user selection process, i.e. the method (such as proof-of-work or proof-of-stake) which is used to select users with the task of updating state. Our results suffice to establish, for example, that the production of certificates is impossible for proof-of-work protocols, but is automatic for standard forms of proof-of-stake protocols. As a byproduct of our work, we also define a number of security notions and identify the equivalences and inequivalences among them.

How does blockchain security dictate blockchain implementation? pdf (CCS 2021)

This is joint work with Tim Roughgarden.

This is an invited expository article for the Notices of the American Mathematical Society, which requires (almost) no background knowledge, and aims to introduce cryptocurrency protocols in simple terms. 

Notices of the American Mathematical Society, 67 (9), 2020, pdf.

This article will also appear in the 2021 edition of the annual series The Best Writing on Mathematics, published by The Princeton University Press.