Paper 2020/355

Permissionless Consensus in the Resource Model

Benjamin Terner

Abstract

In the permissionless regime of distributed computing, participants may join and leave an internet-scale protocol execution at will. The permissionless regime poses challenges to the classical techniques used for consensus protocols, in which participants attempt to agree on a function of their inputs. For example, classical consensus techniques require bounding the numbers of honest and corrupt participants, and for honest participants to remain online throughout. Bitcoin's introduction of Proof of Work enabled dynamic participation by shifting focus from the number of parties to the number of hash puzzles that parties collectively solve, and in turn, enforcing constraints on the blocks sent by honest parties. Other Bitcoin-inspired works have developed Proof of X (PoX) variants to remediate the shortcomings of Proof of Work. We propose a new abstraction called resources and argue that in practice, several PoX variants appear to implement resources. For every resource that a party obtains, it is permitted to send a special protocol message. We show that given few additional assumptions, resources are sufficient to achieve consensus in the permissionless regime, even in the presence of a full-information adversary that can choose which parties get resources and when they get them. In particular, it is not necessary to know a bound on the network delay, participants do not need clocks, and participants can join and leave the execution arbitrarily, even after sending only a single message. We require only a known upperbound on the rate at which resources enter the system, relative to the maximum network delay (without needing to know the network delay), and that over the long term, a majority of resources are acquired by honest participants. Our protocol for consensus in the permissionless model follows from a protocol for graph consensus, which we define as a generalization of blockchains. Our graph consensus works even when resources enter the system at high rates, but the required honest majority increases with the rate. We show how to modify the protocol slightly to achieve one-bit consensus. Finally, we show that for every graph consensus protocol that outputs a majority of honest vertices there exists a one-bit consensus protocol.

Note: revised to simplify the model and expand on the fit of proof-of-x within the model