Paper 2022/1576

Folding Schemes with Selective Verification

Carla Ràfols, Pompeu Fabra University
Alexandros Zacharakis, 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
Creative Commons Attribution-NonCommercial-ShareAlike
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},
      note = {\url{https://eprint.iacr.org/2022/1576}},
      url = {https://eprint.iacr.org/2022/1576}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.