Miranda Christ
April 5, 2023 at 11:00 AM on Zoom / Soda Hall
Limits on revocable proof systems, with implications for stateless blockchains
Abstract:
In traditional blockchains, parties that validate transactions must store a large amount of information– for Bitcoin, for example, this includes all unspent coins and requires several GB. For a cryptocurrency with enough throughput to support truly everyday transactions, this storage cost would become prohibitive, necessitating expensive hardware and limiting the number of validators, posing a risk to decentralization. The more recently proposed stateless blockchain framework lessens the storage burden on validators by having them store only a succinct state commitment and introducing a requirement that users submit proofs that their coins are unspent when making transactions.
Curiously, all proposed stateless blockchain schemes share the undesirable property that users must continually update their proofs as other users in the system make transactions. Ideally, we'd like for users to do no work at all until they make a transaction. Can we achieve this, or is the need for proof changes fundamental?
In this talk, we give an overview of stateless blockchains and discuss our recent result (appearing in Financial Cryptography 2023) answering this question. We show that, unfortunately, these proof updates are necessary. In doing so, we introduce the general notion of a revocable proof system (RPS), which captures stateless blockchains as well as several other cryptographic primitives. We prove an information-theoretic result on the relation between succinct state size in the RPS and the required number of local proof updates as statements are revoked (e.g. coins are spent). We apply our result to conclude that there is no useful tradeoff point when building a stateless cryptocurrency: the system must either have a linear-sized global state (in the number of unspent coins) or require a linear rate of local proof updates. We show how our result also provides new lower bounds for set commitments, vector commitments and authenticated dictionaries.
Bio: Miranda Christ is a PhD student at Columbia University, where she is co-advised by Tal Malkin and Mihalis Yannakakis. She's currently visiting the Simons Institute, where she's participating in the Meta-Complexity Program. Her research explores topics in cryptography and complexity theory, including anonymous communication, blockchains, and differential privacy. Her work aims to build theoretical foundations to aid in understanding practically motivated problems.