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:
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
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.
In the distributed computing literature, consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the ‘blockchain’ literature, this is referred to as the permissioned setting. What differentiates the most prominent blockchain protocol Bitcoin from these previously studied protocols is that it operates in a permissionless setting, i.e. it is a protocol for establishing consensus over an unknown network of participants that anybody can join, with as many identities as they like in any role. The arrival of this new form of protocol brings with it many questions. Beyond Bitcoin, what can we prove about permissionless protocols in a general sense? How does recent work on permissionless protocols in the blockchain literature relate to the well-developed history of research on permissioned protocols in distributed computing?
To answer these questions, we describe a formal framework for the analysis of both permissioned and permissionless systems. Our framework allows for “apples-to-apples” comparisons between different categories of protocols and, in turn, the development of theory to formally discuss their relative merits. A major benefit of the framework is that it facilitates the application of a rich history of proofs and techniques in distributed computing to problems in blockchain and the study of permissionless systems. Within our framework, we then address the questions above. We consider the Byzantine Generals Problem as a formalisation of the problem of reaching consensus, and address a programme of research that asks, “Under what adversarial conditions, and for what types of permissionless protocol, is consensus possible?”
We prove several results for this programme, our main result being that deterministic consensus is not possible for decentralised permissionless protocols. To close, we give a list of seven open questions.
Byzantine Generals in the Permissionless Setting, FC23 pdf.
This is joint work with Tim Roughgarden. This paper also replaces earlier versions of the paper, “A General Framework for the Security Analysis of Blockchain Protocols” and “Resource Pools and the CAP Theorem”.
In this paper my coauthors and I introduce the idemetric property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We also consider how satisfaction of the idemetric property is relevant to algorithm design.
Proceedings of the Royal Society A, 475(2222), 2019, pdf.
This is joint work with Barmpalias, Huang, Li, Li, Pan and Roughgarden.
According to Kolmogorov complexity, every finite binary string is compressible to a shortest code — its information content — from which it is effectively recoverable. In this paper my coauthor Barmpalias and I investigate the extent to which this holds for infinite binary sequences (streams). We devise a new coding method which uniformly codes every stream X into an algorithmically random stream Y, in such a way that the first n bits of X are recoverable from the first I(X_n) bits of Y, where I is any partial computable information content measure which is defined on all prefixes of X, and where X_n is the initial segment of X of length n. As a consequence, if g is any computable upper bound on the initial segment prefix-free complexity of X, then X is computable from an algorithmically random Y with oracle-use at most g. Alternatively (making no use of such a computable bound g) one can achieve an oracle-use bounded above by K(X_n)+log n. This provides a strong analogue of Shannon’s source coding theorem for algorithmic information theory.
With Barmpalias, IEEE Transactions on Information Theory, 65 (7), 2019, pdf.
Andrew Lewis-Pye 