Deconstructing the Blockchain to Approach Physical Limits

Wednesday, November 14, 2018 - 2:00pm to 3:00pm

Event Calendar Category

Other LIDS Events

Speaker Name

David Tse

Affiliation

Stanford University

Building and Room number

E18-304

Abstract

The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger for an electronic payment system, Bitcoin. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput, confirmation latency and confirmation reliability. These measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. Existing systems operate far away from these physical limits. In this work we introduce Prism, a new blockchain protocol, which can provably achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing the blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

 

This is joint work with Vivek Bagaria, Sreeram Kannan, Giulia Fanti and Pramod Viswanath. The full paper can be found at https://arxiv.org/abs/1810.08092.

Biography

David Tse received the B.A.Sc. degree in systems design engineering from University of Waterloo in 1989, and the M.S. and Ph.D. degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1995 to 2014, he was on the faculty of the University of California at Berkeley. He is currently the Thomas Kailath and Guanghan Xu Professor at Stanford University. He received the Claude E. Shannon Award in 2017 and was elected member of the U.S. National Academy of Engineering in 2018. Previously, he received an NSF CAREER award in 1998, the Erlang Prize from the INFORMS Applied Probability Society in 2000 and the Frederick Emmons Terman Award from the American Society for Engineering Education in 2009. He is a coauthor, with Pramod Viswanath, of the text Fundamentals of Wireless Communication, which has been used in over 60 institutions around the world. He received best paper awards from IEEE Information Theory, Communications and Signal Processing societies, and is the inventor of the proportional-fair scheduling algorithm used in all third and fourth-generation cellular systems.