Cryptology ePrint Archive: Report 2016/917

Hybrid Consensus: Efficient Consensus in the Permissionless Model

Rafael Pass and Elaine Shi

Abstract: Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, permissioned setting has been extensively studied in the 30 years of distributed systems literature. Recent developments in Bitcoin and other decentralized cryptocurrencies popularized a new form of consensus in a “permissionless” setting, where anyone can join and leave dynamically, and there is no a-priori knowledge of the consensus nodes. Despite this exciting breakthrough, today’s permissionless consensus protocols, often referred to as “blockchains”, are known to have terrible performance, which has resulted in heated, and at times acrimonious debates in the community. First, we show that unfortunately a performance loss is inherent for any protocol that secures against at least 1/3 corruptions in hashpower. Specifically, we formally define a new performance measure called responsiveness, and show that any responsive permissionless consensus protocol cannot tolerate 1/3 or more corruptions in hashpower. Next, we show a tightly matching uppper bound. Specifically, we propose a new permissionless consensus protocol called hybrid consensus, that is responsive and secures against up to 1/3 corruptions in hashpower. Hybrid consensus's idea is to bootstrap fast permissionless consensus by combining an inefficient blockchain protocol with a fast permissioned consensus protocol. Hybrid consensus uses the blockchain not to agree on transactions, but to agree on rotating committees which in turn execute permissioned consensus protocols to agree on transactions. While the high-level idea is intuitive, formally instantiating and reasoning about the protocol exposed a multitude of non-trivial technical subtleties and challenges.

Category / Keywords: cryptographic protocols / consensus, blockchains, optimal resilience, distributed systems, cryptocurrency

Date: received 21 Sep 2016, last revised 16 Feb 2017

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170217:041543 (All versions of this report)

Short URL: ia.cr/2016/917

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]