Cryptology ePrint Archive: Report 2018/302

Rethinking Large-Scale Consensus

Rafael Pass and Elaine Shi

Abstract: In this position paper, we initiate a systematic treatment of reaching consensus in a permissionless network. We prove several simple but hopefully insightful lower bounds that demonstrate exactly why reaching consensus in a permissionless setting is fundamentally more difficult than the classical, permissioned setting. We then present a simplified proof of Nakamoto's blockchain which we recommend for pedagogical purposes. Finally, we survey recent results including how to avoid well-known painpoints in permissionless consensus, and how to apply core ideas behind blockchains to solve consensus in the classical, permissioned setting and meanwhile achieve new properties that are not attained by classical approaches.

Category / Keywords: cryptographic protocols / blockchain, consensus

Original Publication (with minor differences): CSF 2017, invited paper

Date: received 29 Mar 2018, last revised 12 Nov 2020

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201112:143409 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]