### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2020/1161

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}
}

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