FLIP-and-Prove R1CS
Open Access
- 8 January 2026
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (4)
Abstract
We present the first folding framework that achieves sub-linear verification and communication when a single prover must convince a verifier of $k$ independent R1CS instances. FLIP (Fold-Inner-Product) folds the $k$ instance–witness pairs in only $\log k$ rounds. Built on the homomorphic two-tier commitment of Abe et al. (CRYPTO 2010), FLIP transmits $O(\log k)$ group elements. r-Groth is a commit-and-prove variant of Groth16 that natively handles relaxed R1CS. It retains Groth16’s three-element proof and two pairing checks, requires only a slightly modified (instance-independent) trusted setup, and does not rely on elliptic-curve cycles or foreign-field arithmetic. Combined, FLIP+rGroth replace the $k-1$ extra Groth16 proofs demanded by aggregation schemes and avoid the heavy verifier-in-circuit logic of recursive systems. The total prover work is essentially one Groth16 run plus light folding, while the verifier processes $O(\log k)$ group elements and two pairings. This design is immediately applicable to roll-ups, Proof-of-Space, and other “proving-as-a-service” scenarios where all witnesses reside on a single machine.
Keywords
Funding Information
- Agencia Estatal de Investigación (CEX2021-001195-M, PID2021-128521OB-I00)
- Ministerio de Ciencia, Innovación y Universidades
- Instituto Nacional de Ciberseguridad (C057/23)
This publication has 37 references indexed in Scilit:
- Algebraic Reductions of Knowledge2023
- SnarkPack: Practical SNARK Aggregation2022
- Nova: Recursive Zero-Knowledge Arguments from Folding Schemes2022
- Proofs for Inner Pairing Products and Applications2021
- Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments2021
- Recursive Proof Composition from Accumulation Schemes2020
- Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup2020
- Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS2020
- Tight Proofs of Space and Replication2019
- Efficient Verifiable Delay Functions2019