Paper 2020/1021

Consensus Redux: Distributed Ledgers in the Face of Adversarial Supremacy

Abstract

Permissionless distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints on the resources available to an adversary relative to the resources of the participants that follow the protocol. Given their permissionless participation convention and their intended long-livedness, a critical open security question is their behavior---and potential resilience---to temporary spikes in adversarial resources. In this work we give the first thorough treatment of the self-healing properties of Nakamoto ledgers, addressing both proof-of-work (PoW) and proof-of-stake (PoS) protocols. First, we present a unified model that allows us to define self-healing for both of these protocol classes. Then we provide a formal analysis establishing self-healing with respect to both consistency and liveness in both classes, quantifying the resulting vulnerability period as a function of the magnitude of the spike. Finally, we provide numerical simulations giving explicit quantitative bounds relevant for practice.