Paper 2020/1161

KVaC: Key-Value Commitments for Blockchains and Beyond

Shashank Agrawal and Srinivasan Raghuraman


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)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Contact author(s)
srini131293 @ gmail com
shashank agraval @ gmail com
2020-10-05: revised
2020-09-25: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.