[Resource Topic] 2022/1576: Folding Schemes with Selective Verification

Welcome to the resource topic for 2022/1576

Folding Schemes with Selective Verification

Authors: Carla Ràfols, Alexandros Zacharakis


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.

ePrint: https://eprint.iacr.org/2022/1576

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .