Rafael Pass: Analysis of the Blockchain Protocol in Asynchronous Networks
Date: Friday, May 06, 2016
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Location: Hewlett, Gates Bldg, G882
Host: Vinod Vaikuntanathan
Contact: Deborah Goodwin, 617.324.7303, email@example.com
Speaker URL: None
TALK: Rafael Pass: Analysis of the Blockchain Protocol in Asynchronous Networks
Nakamotos famous blockchain protocol enables achieving consensus in a so-called *permissionless* settinganyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents sybil attacks (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. moderately hard functions) introduced by Dwork and Naor (Crypto92).
Prior works that analyze the blockchain protocol either make the simplifying assumption that network channels are fully synchronous (i.e. messages are instantly delivered without delays) (Garay et al, Eurocrypt15) or only consider specific attacks (Nakamoto08; Sampolinsky and Zohar, FinancialCrypt15); additionally, as far as we know, none of them deal with players joining or leaving the protocol.
We prove that the blockchain consensus mechanism satisfies a strong forms of consistency and liveness in an asynchronous network with adversarial delays that are a-priori bounded, within a formal model allowing for adaptive corruption and spawning of new players, assuming that the computational puzzle is modeled as a random oracle. (We complement this result by showing a simple attack against the blockchain protocol in a fully asynchronous setting, showing that the puzzle-hardness needs to be appropriately set as a function of the maximum network delay.)
As an independent contribution, we define an abstract notion of a blockchain protocol and identify appropriate security properties of such protocols; we prove that Nakamotos blockchain protocol satisfies them and that these properties are sufficient for typical applications. We finally show how to use our analysis to build *new* blockchain protocols that overcome some of the bottlenecks in Nakamotos original protocol.
The analysis of Nakamotos blockchain is based on joint work with Lior Seeman and abhi shelat, and new blockchain protocols are based on joint work with Elaine Shi.
No prior knowledge of Bitcoin or the blockchain will be assumed.
Created by Deborah Goodwin at Monday, May 02, 2016 at 2:05 PM.