Paper 2021/599

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision.USENIX Security '22
Keywords
vector commitmentsaggregationproof updatesunstealabilityhomomorphismpolynomial commitments
Contact author(s)
tomescu alin @ gmail com
History
2022-03-21: revised
2021-05-10: received
See all versions
Short URL
https://ia.cr/2021/599
License
Creative Commons Attribution
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.