Limits on Revocable Proof Systems
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. Miranda Christ (Columbia) addresses the possibility of statelessness. 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. In this talk, Miranda gives an overview of stateless blockchains and discuss her recent result answering this question. She shows that these proof updates are necessary. In doing so, she introduce the general notion of a revocable proof system (RPS), which captures stateless blockchains as well as several other cryptographic primitives. She proves 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). She applies the 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. She also shows how our result also provides new lower bounds for set commitments, vector commitments, and authenticated dictionaries. This is joint work with Joseph Bonneau, done primarily at a16z Crypto Research.
About the speaker
Miranda is a PhD student at Columbia University, where she is co-advised by Tal Malkin and Mihalis Yannakakis and is a member of the Theory Group and Crypto Lab. 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.
About a16z crypto research
a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet. Our researchers are technologists, scientists, cryptographers, and cryptocurrency experts, working to bridge the worlds of academic theory with industry practice, and to help shape crypto and web3 as a formal area of study. More about us: a16z.com/2022/04/21/announcing-a16z-crypto-research