Paper 2022/1576

Folding Schemes with Selective Verification

Carla Ràfols, Pompeu Fabra University
Alexandros Zacharakis, Toposware Inc.

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.

Available format(s)
Cryptographic protocols
Publication info
Folding Aggregation Delegation of computation SNARKs Vector commitments Verifiable databases
Contact author(s)
carla rafols @ upf edu
alexandros zacharakis @ toposware com
2022-11-25: revised
2022-11-14: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Carla Ràfols and Alexandros Zacharakis},
      title = {Folding Schemes with Selective Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1576},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.