International Association
for Cryptologic Research

Nakamoto’s Bitcoin protocol inspired interest in the permissionless regime of distributed computing, in which participants may join and leave an internet-scale protocol execution at will, without needing to register with any authority. 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. Crucially, classical consensus techniques require honest participants to remain online and active, and to know an upperbound on the number of participants. Bitcoin addresses this issue by requiring Proof of Work in order to send a message in protocol, and other Bitcoin-inspired works have developed Proof of X variants to remediate the shortcomings of Proof of Work. We propose an abstraction for Proof of X called resources, inspired by how many variants are used in practice. We then show that given few additional assumptions, resources are sufficient to achieve consensus in the permissionless regime. In particular, with appropriate assumptions about resources, 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. The core idea is to shift focus from the proportion of honest parties in an execution to the proportion of messages sent by honest parties. We formally model consensus protocols in the permissionless regime, and show how to parameterize a permissionless execution using only the long-term proportion of resources acquired by honest participants and an upperbound on the rate at which resources enter the system, relative to the maximum network delay (without needing to know the network delay). Along the way, we provide a generalized definition of blockchains which we call graph consensus. We present a protocol in the permissionless regime that achieves graph consensus, even when resources enter the system at high rates, but the required honest majority increases with the rate. We show how the protocol can be modified 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.