DeCenter Seminar: What insights can we learn from the Bitcoin algorithm?

November 15, 2023 4:30 pm

Friend Center, Convocation Room (113)

Speaker: Ling Ren, University of Illinois at Urbana-Champaign

Bitcoin’s longest-chain algorithm, also known as Nakamoto consensus, is a novel solution to the classic Byzantine fault-tolerant (BFT) consensus problem. What is fundamentally novel about it, and what algorithmic insights can we learn from it? In this talk, I will discuss some insights and inspirations we gained from Bitcoin that led to new advances in BFT consensus.

First, Nakamoto consensus supports dynamic participation. The Bitcoin system has operated for over a decade, during which it has witnessed a rapid increase and sudden drops in the participation level. But to support this phenomenal level of robustness, longest-chain protocols suffer from long latency as a fundamental trade-off. Classic BFT protocols, on the other hand, can achieve constant latency but cannot make progress under dynamic participation. I will present a protocol that simultaneously supports dynamic participation and achieves constant latency. The core technique is to extend the classic BFT approach from static quorum size to dynamic quorum size according to the current participation level.

Second, Bitcoin uses a sparse peer-to-peer network to reduce communication. This ingredient loosely inspired us to design a Byzantine agreement protocol tolerating minority faults with quadratic communication. This meets the well-known Dolev-Reischuk lower bound and closes a 40-year open problem on the optimal communication complexity of Byzantine agreement. Third, Bitcoin allows individual clients to make their own assumptions about the network and opt for different security-efficiency trade-offs. We propose the notion of flexible Byzantine fault tolerance to capture and generalize this property. If time permits, I will also briefly discuss other core features of Nakamoto consensus that may inspire important future research.

Ling Ren is an assistant professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. Prior to joining the University of Illinois, he obtained his Ph.D. from MIT and worked at VMware Research. He has won several awards, including NSF CAREER Award, Google Research Scholar Award, VMware Early Career Faculty Grant, Bitcoin Research Prize, Top Picks in Hardware and Embedded Security, and Best Paper Runner-Up and Best Student Paper at CCS.