Cryptology ePrint Archive: Report 2017/913

Thunderella: Blockchains with Optimistic Instant Confirmation

Rafael Pass and Elaine Shi

Abstract: State machine replication, or “consensus”, is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous “fall-back” path (which only gets executed if something goes wrong); as a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet “optimistically” (if a super majority of the players are honest), the protocol “instantly” confirms transactions. We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically—if 3/4 of the computing power is controlled by honest players, and a special player called the “accelerator”, is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority.

Category / Keywords: cryptographic protocols / blockchains, optimistic responsiveness

Date: received 19 Sep 2017

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170924:215350 (All versions of this report)

Short URL: ia.cr/2017/913

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]