Andrew Lewis-Pye

Andrew Lewis-Pye, Patrick O'Grady

In leader-based protocols for State Machine Replication (SMR), the leader's outgoing bandwidth is a natural throughput bottleneck. Erasure coding can alleviate this by allowing the leader to send each processor a single fragment of each block, rather than a full copy. The \emph{data expansion rate}, the ratio of total data sent to payload size, determines how close throughput can get to the underlying network bandwidth. We investigate the fundamental limits and possibilities for bandwidth-efficient leader-based consensus. On the negative side, we prove that protocols with 2-round finality (one round of voting) cannot achieve a data expansion rate below approximately 2.5, a bound that is matched by existing protocols. On the positive side, we show that protocols with 3-round finality (two rounds of voting) can push the data expansion rate arbitrarily close to 1. The key insight is that the second voting round provides a recovery mechanism: leaders can attempt aggressive erasure codes and safely fall back to more conservative ones when reconstruction fails, without compromising consistency. We present two protocols with 3-round finality realising this approach. Carnot 1 assumes $n \geq 4f+1$ processors (of which at most $f$ may be Byzantine) and achieves a clean design requiring no additional fragment dissemination beyond the initial protocol messages. Carnot 2 operates under the optimal resilience assumption $n \geq 3f+1$, at the cost of additional fragment dissemination when Byzantine processors interfere. Both protocols can incorporate stable leaders and optimistic proposals to maximise throughput and minimise latency. Under favourable conditions, with correct leaders and few actual faults, both protocols allow leaders to use data expansion rates approaching 1; under adversarial conditions, leaders can revert to safe expansion rates of approximately $1.33$ and $1.5$, respectively.

Andrew Lewis-Pye, Tim Roughgarden

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 (Lewis-Pye and Roughgarden, 2021), 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.

Andrew Lewis-Pye, Tim Roughgarden

Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. Byzantine fault-tolerant (BFT) inspired protocols). These fundamental differences have hindered "apples-to-apples" comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work (PoW) and proof-of-stake (PoS) protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process that are significant for protocol design. We demonstrate the utility of our general framework with several concrete results: 1. We prove a CAP-type impossibility theorem asserting that liveness with an unknown level of participation rules out security in a partially synchronous setting. 2. Delving deeper into the partially synchronous setting, we prove that a necessary and sufficient condition for security is the production of "certificates," meaning stand-alone proofs of block confirmation. 3. Restricting to synchronous settings, we prove that typical protocols with a known level of participation (including longest chain-type PoS protocols) can be adapted to provide certificates, but those with an unknown level of participation cannot. 4. Finally, we use our framework to articulate a modular two-step approach to blockchain security analysis that effectively reduces the permissionless case to the permissioned case.