### Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments

Shravan Srinivasan, Alexander Chepurnoy, Charalampos Papamanthou, Alin Tomescu, and Yupeng Zhang

##### Abstract

We present Hyperproofs, the first vector commitment (VC) scheme that is efficiently maintainable and aggregatable. Similar to Merkle proofs, our proofs form a tree that can be efficiently maintained: updating all $n$ proofs in the tree after a single leaf change only requires $O(\log{n})$ time. Importantly, unlike Merkle proofs, Hyperproofs are efficiently aggregatable, anywhere from $10\times$ to $41\times$ faster than SNARK-based aggregation of Merkle proofs. At the same time, an individual Hyperproof consists of only $\log{n}$ algebraic hashes (e.g., 32-byte elliptic curve points) and an aggregation of $b$ such proofs is only $O(\log{(b\log{n})})$-sized. Hyperproofs are also reasonably fast to update when compared to Merkle trees with SNARK-friendly hash functions. As another benefit over Merkle trees, Hyperproofs are homomorphic: digests (and proofs) for two vectors can be homomorphically combined into a digest (and proofs) for their sum. Homomorphism is very useful in emerging applications such as stateless cryptocurrencies. First, it enables unstealability, a novel property that incentivizes proof computation. Second, it makes digests and proofs much more convenient to update. Finally, Hyperproofs have certain limitations: they are not transparent, have linear-sized public parameters, are slower to verify, and have larger aggregated proofs and slower verification than SNARK-based approaches. Nonetheless, end-to-end, aggregation and verification in Hyperproofs is $10\times$ to $41\times$ faster than in SNARK-based Merkle trees.

Available format(s)
Publication info
Published elsewhere. Major revision.USENIX Security '22
Keywords
Contact author(s)
tomescu alin @ gmail com
History
2022-03-21: revised
See all versions
Short URL
https://ia.cr/2021/599

CC BY

BibTeX

@misc{cryptoeprint:2021/599,
author = {Shravan Srinivasan and Alexander Chepurnoy and Charalampos Papamanthou and Alin Tomescu and Yupeng Zhang},
title = {Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments},
howpublished = {Cryptology ePrint Archive, Paper 2021/599},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/599}},
url = {https://eprint.iacr.org/2021/599}
}

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