Paper 2021/599

Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments

Shravan Srinivasan
Alexander Chepurnoy
Charalampos Papamanthou
Alin Tomescu
Yupeng Zhang

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. USENIX Security '22
vector commitments aggregation proof updates unstealability homomorphism polynomial commitments
Contact author(s)
sshravan @ cs umd edu
tomescu alin @ gmail com
2022-10-19: last of 2 revisions
2021-05-10: received
See all versions
Short URL
Creative Commons Attribution


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