### Limits on revocable proof systems, with applications to stateless blockchains

##### Abstract

Motivated by the goal of building a cryptocurrency with succinct global state, we introduce the abstract notion of a revocable proof system. We prove an information-theoretic result on the relation between global state size 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 trade-off point when building a stateless cryptocurrency: the system must either have a linear-sized global state (in the number of accounts in the system) or require a near-linear rate of local proof updates. The notion of a revocable proof system is quite general and also provides new lower bounds for set commitments, vector commitments and authenticated dictionaries.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
Authenticated data structures blockchains accumulators cryptocurrency
Contact author(s)
mchrist @ cs columbia edu
jbonneau @ gmail com
History
2022-10-28: approved
See all versions
Short URL
https://ia.cr/2022/1478

CC BY

BibTeX

@misc{cryptoeprint:2022/1478,
author = {Miranda Christ and Joseph Bonneau},
title = {Limits on revocable proof systems, with applications to stateless blockchains},
howpublished = {Cryptology ePrint Archive, Paper 2022/1478},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1478}},
url = {https://eprint.iacr.org/2022/1478}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.