Paper 2022/1478
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-10-27: received
- See all versions
- Short URL
- https://ia.cr/2022/1478
- License
-
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}
}
