Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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× to 41× 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 (blog 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× to 41× faster than in SNARK-based Merkle trees.

Original languageEnglish (US)
Title of host publicationProceedings of the 31st USENIX Security Symposium, Security 2022
PublisherUSENIX Association
Pages3001-3018
Number of pages18
ISBN (Electronic)9781939133311
StatePublished - 2022
Externally publishedYes
Event31st USENIX Security Symposium, Security 2022 - Boston, United States
Duration: Aug 10 2022Aug 12 2022

Publication series

NameProceedings of the 31st USENIX Security Symposium, Security 2022

Conference

Conference31st USENIX Security Symposium, Security 2022
Country/TerritoryUnited States
CityBoston
Period8/10/228/12/22

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments'. Together they form a unique fingerprint.

Cite this