On an Asymptotic Criterion for Blockchain Design

Abstract: The salient feature of blockchains is the use of a stochastic growth process to generalize the notion of consensus in the classical Byzantine Generals Problem. In this talk, we introduce the Asynchronous Composition Model to study a sequence of random graphs growing according to blockchain dynamics. The term “asynchronous” refers to the fact that our updates take the form $X_t =X_{t-1} \cup f( X_{t – \xi_t})$, where $\xi_t$ is random, and $f$ adds a single vertex to the graph.

We discuss the limiting behavior of asynchronous composition as time goes to infinity. Our main focus is the one-endedness of the limit random graph, which is a precise statement of the notion that the limit graph “only grows to infinity in one direction.” One-endedness is a key property for ensuring the consensus dynamics in a blockchain. In particular, we establish one-endedness for the Nakamoto rule, the canonical choice in protocols like Bitcoin, and the $f_2$ rule from the Iota protocol, the most non-trivial rule used in a widely adopted blockchain protocol.

Bio: Aditya Gopalan is a PhD student in the Industrial and Enterprise Systems Engineering Department at the University of Illinois Urbana-Champaign. He is advised by Partha Dey. He is broadly interested in applied probability, with a current methodological focus on point process dynamics, stochastic growth processes, and stochastic recursive sequences with random delays. Some applications of his interest include blockchains, opinion dynamics, first-passage percolation, and queueing.

Aditya received his bachelor’s degree from MIT in 2018.

*** The event will take place in a hybrid format. The location for in-person attendance will be room 2311 EECS. Attendance will also be available via Zoom.

Join Zoom Meeting https:https://umich.zoom.us/j/99102451525

Meeting ID: 991 0245 1525

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to: Sher Nickrand([email protected]) or Michele Feldkamp ([email protected])