Rafael Pass: Rethinking Large-Scale Consensus through Blockchains

Friday, December 2, 2016 - 10:30am to 12:00pm
Hewlett G882
Rafael Pass, Cornell University


The literature on distributed computing (as well as the cryptographic literature) typically considers two types of players---honest ones and corrupted ones. Resilience properties are then analyzed assuming a lower bound on the fraction of honest players. Honest players, however, are not only assumed to follow the prescribed the protocol, but also assumed to be *online* throughout the whole execution of the protocol.
The advent of “large-scale” consensus protocols (such as e.g., the blockchain protocol) where we may have millions of players, makes this assumption unrealistic. In this work, we initiate a study of distributed protocols in a “sleepy” model of computation, where players can be either online (awake) or offline (asleep), and their online status may change at any point during the protocol. The main question we address is:
Can we design consensus protocols that remain resilient under “sporadic participation”, where at any given point, only a subset of the players are actually online?
As far as we know, all standard consensus protocols break down under such sporadic participation, even if we assume that 99% of the online players are honest. Our main result answers the above question in the affirmative, assuming only that a majority of the online players are honest. Perhaps surprisingly, our protocol significantly departs from the standard approaches to distributed consensus, and we instead rely on key ideas behind Nakamoto’s blockchain protocol (while dispensing with “proofs-of-work”).
Based on joint work with Iddo Bentov and Elaine Shi.