1. Thunderella: Blockchains with Optimistic Instant Confirmation 2018 Blockchains Eurocrypt
    Rafael Pass and Elaine Shi
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @misc{cryptoeprint:2017:913,
    author = {Rafael Pass and Elaine Shi},
    title = {Thunderella: Blockchains with Optimistic Instant Confirmation},
    howpublished = {Cryptology ePrint Archive, Report 2017/913},
    year = {2017},
    note = {\url{https://eprint.iacr.org/2017/913}},
    }

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.

  1.