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.
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)