Paper 2025/813

HydraProofs: Optimally Computing All Proofs in a Vector Commitment (with applications to efficient zkSNARKs over data from multiple users)

Christodoulos Pappas, Hong Kong University of Science and Technology
Dimitris Papadopoulos, Hong Kong University of Science and Technology
Charalampos Papamanthou, Yale University
Abstract

In this work, we introduce HydraProofs, the first vector commitment (VC) scheme that achieves the following two properties. (i) The prover can produce all the opening proofs for different elements (or consecutive sub-arrays) for a vector of size N in optimal time O(N). (ii) It is directly compatible with a family of zkSNARKs that encode their input as a multi-linear polynomial, i.e., our VC can be directly used when running the zkSNARK on its pre-image, without the need to open'' the entire vector pre-image inside the zkSNARK. To the best of our knowledge, all prior VC schemes either achieve (i) but are not efficiently pluggable'' into zkSNARKs (e.g., a Merkle tree commitment that requires re-computing the entire hash tree inside the circuit), or achieve (ii) but take (NlogN) time. We then combine HydraProofs with the seminal GKR protocol and apply the resulting zkSNARK in a setting where multiple users participate in a computation executed by an untrusted server and each user wants to ensure the correctness of the result and that her data was included. Our experimental evaluation shows our approach outperforms prior ones by 4-16x for prover times on general circuits. Finally, we consider two concrete application use cases, verifiable secret sharing and verifiable robust aggregation. For the former, our construction achieves the first scheme for Shamir's secret sharing with linear time prover (lower than the time needed for the dealer computation). For the second we propose a scheme that works against misbehaving aggregators and our experiments show it can be reasonably deployed in existing schemes with minimal slow-downs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. IEEE Symposium on Security and Privacy 2025
Keywords
Vector CommitmentszkSNARKs
Contact author(s)
cpappas @ connect ust hk
dipapado @ ust hk
charalampos papamanthou @ yale edu
History
2025-05-09: approved
2025-05-07: received
See all versions
Short URL
https://ia.cr/2025/813
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/813,
      author = {Christodoulos Pappas and Dimitris Papadopoulos and Charalampos Papamanthou},
      title = {{HydraProofs}: Optimally Computing All Proofs in a Vector Commitment (with applications to efficient {zkSNARKs} over data from multiple users)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/813},
      year = {2025},
      url = {https://eprint.iacr.org/2025/813}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.