Paper 2024/1631
Sparrow: Space-Efficient zkSNARK for Data-Parallel Circuits and Applications to Zero-Knowledge Decision Trees
Abstract
Space-efficient SNARKs aim to reduce the prover's space overhead which is one the main obstacles for deploying SNARKs in practice, as it can be prohibitively large (e.g., orders of magnitude larger than natively performing the computation). In this work, we propose Sparrow, a novel space-efficient zero-knowledge SNARK for data-parallel arithmetic circuits with two attractive features: (i) it is the first space-efficient scheme where, for a given field, the prover overhead increases with a multiplicative sublogarithmic factor as the circuit size increases, and (ii) compared to prior space-efficient SNARKs that work for arbitrary arithmetic circuits, it achieves prover space asymptotically smaller than the circuit size itself. Our key building block is a novel space-efficient sumcheck argument with improved prover time which may be of independent interest. Our experimental results for three use cases (arbitrary data parallel circuits, multiplication trees, batch SHA256 hashing) indicate Sparrow outperforms the prior state-of-the-art space-efficient SNARK for arithmetic circuits Gemini (Bootle et al., EUROCRYPT'22) by
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ACM CCS 2024
- Keywords
- zkSNARKsspace-efficient zkSNARKszero-knowledge proofsproof of training
- Contact author(s)
-
cpappas @ connect ust hk
dipapado @ cse ust hk - History
- 2024-10-14: approved
- 2024-10-11: received
- See all versions
- Short URL
- https://ia.cr/2024/1631
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1631, author = {Christodoulos Pappas and Dimitrios Papadopoulos}, title = {Sparrow: Space-Efficient {zkSNARK} for Data-Parallel Circuits and Applications to Zero-Knowledge Decision Trees}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1631}, year = {2024}, url = {https://eprint.iacr.org/2024/1631} }