David Tse (Stanford)

Feb 12, 2020

Title and Abstract

Blockchains, branching random walks and the number e

Blockchains are probabilistic consensus protocols. A key performance measure of a blockchain is its security threshold: this is the maximum tolerable fraction of the total network resources an adversary can have such that the protocol is guaranteed to reach consensus with high probability regardless of the adversary's attack strategy. Many blockchains exhibit critical behavior around the security threshold. The original blockchain, due to Nakamoto, is based on Proof-of-Work and has a critical security threshold of 1/2. Proof-of-stake is an alternative class of blockchains without the energy consumption of Proof-of-work. What is the security threshold for the Proof-of-Stake version of Nakamoto's blockchain? The answer reveals a connection between blockchains, branching random walks and the number e. This is joint work with Amir Dembo and Ofer Zeitouni.

Bio

David Tse received the BASc degree in systems design engineering from University of Waterloo in 1989, and the MS and PhD degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1994 to 1995, he was a postdoctoral member of technical staff at A.T. & T. Bell Laboratories. 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.

David Tse was elected member of the U.S. National Academy of Engineering in 2018. He was the recipient of the IEEE Claude E. Shannon Award in 2017 and the IEEE Richard W. Hamming Medal in 2019. Previously, he received a NSF CAREER award in 1998, the Erlang Prize from the INFORMS Applied Probability Society in 2000 and a Gilbreth Lectureship from the National Academy of Engineering in 2012. He received multiple best paper awards, including the Information Theory Society Paper Award in 2003, the IEEE Communications Society and Information Theory Society Joint Paper Awards in 2000, 2013 and 2015, the Signal Processing Society Best Paper Award in 2012 and the IEEE Communications Society Stephen O. Rice Prize in 2013. For his contributions to education, he received the Outstanding Teaching Award from the Department of Electrical Engineering and Computer Sciences at U.C. Berkeley in 2008 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 is the inventor of the proportional-fair scheduling algorithm used in all third and fourth-generation cellular systems, serving 2.7 billion subscribers around the world. He is a member of the Stanford Center for Blockchain Research.