Paper 2020/1161
KVaC: Key-Value Commitments for Blockchains and Beyond
Shashank Agrawal and Srinivasan Raghuraman
Abstract
As blockchains grow in size, validating new transactions becomes more and more resource intensive. To deal with this, there is a need to discover compact encodings of the (effective) state of a blockchain -- an encoding that allows for efficient proofs of membership and updates. In the case of account-based cryptocurrencies, the state can be represented by a key-value map, where keys are the account addresses and values consist of account balance, nonce, etc. We propose a new commitment scheme for key-value maps whose size does not grow with the number of keys, yet proofs of membership are of constant-size. In fact, both the encoding and the proofs consist of just two and three group elements respectively (in groups of unknown order like class groups). Verifying and updating proofs involves just a few group exponentiations. Additive updates to key values enjoy the same level of efficiency too. Key-value commitments can be used to build dynamic accumulators and vector commitments, which find applications in group signatures, anonymous credentials, verifiable databases, interactive oracle proofs, etc. Using our new key-value commitment, we provide the most efficient constructions of (sub)vector commitments to date.
Note: Minor edits.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2020
- Keywords
- commitmentsaccumulatorsblockchainskey-valueefficientRSA
- Contact author(s)
-
srini131293 @ gmail com
shashank agraval @ gmail com - History
- 2020-10-05: revised
- 2020-09-25: received
- See all versions
- Short URL
- https://ia.cr/2020/1161
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1161,
author = {Shashank Agrawal and Srinivasan Raghuraman},
title = {KVaC: Key-Value Commitments for Blockchains and Beyond},
howpublished = {Cryptology ePrint Archive, Paper 2020/1161},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1161}},
url = {https://eprint.iacr.org/2020/1161}
}
