Paper 2022/1576
Folding Schemes with Selective Verification
, Pompeu Fabra University, Toposware Inc.Abstract
In settings such as delegation of computation where a prover is doing computation as a service for many verifiers, it is important to amortize the prover’s costs without increasing those of the verifier. We introduce folding schemes with selective verification. Such a scheme allows a prover to aggregate m NP statements $x_i\in \mathcal{L}$ in a single statement $x\in\mathcal{L}$. Knowledge of a witness for $x$ implies knowledge of witnesses for all $m$ statements. Furthermore, each statement can be individually verified by asserting the validity of the aggregated statement and an individual proof $\pi$ with size sublinear in the number of aggregated statements. In particular, verification of statement $x_i$ does not require reading (or even knowing) all the statements aggregated. We demonstrate natural folding schemes for various languages: inner product relations, vector and polynomial commitment openings and relaxed R1CS of NOVA. All these constructions incur a minimal overhead for the prover, comparable to simply reading the statements.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Folding Aggregation Delegation of computation SNARKs Vector commitments Verifiable databases
- Contact author(s)
-
carla rafols @ upf edu
alexandros zacharakis @ toposware com - History
- 2022-11-25: revised
- 2022-11-14: received
- See all versions
- Short URL
- https://ia.cr/2022/1576
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2022/1576,
author = {Carla Ràfols and Alexandros Zacharakis},
title = {Folding Schemes with Selective Verification},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1576},
year = {2022},
url = {https://eprint.iacr.org/2022/1576}
}
