TY - GEN

T1 - Hyperproofs

T2 - 31st USENIX Security Symposium, Security 2022

AU - Srinivasan, Shravan

AU - Chepurnoy, Alexander

AU - Papamanthou, Charalampos

AU - Tomescu, Alin

AU - Zhang, Yupeng

N1 - Funding Information:
The authors are incredibly thankful to Julian Loss for helping us understand the subtle differences between the generic group model and the algebraic group model. This research was supported in part by Ergo Platform, the National Science Foundation, VMware, the Ethereum Foundation and Protocol Labs.
Publisher Copyright:
© USENIX Security Symposium, Security 2022.All rights reserved.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85141001983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85141001983&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85141001983

T3 - Proceedings of the 31st USENIX Security Symposium, Security 2022

SP - 3001

EP - 3018

BT - Proceedings of the 31st USENIX Security Symposium, Security 2022

PB - USENIX Association

Y2 - 10 August 2022 through 12 August 2022

ER -