FLIP-and-Prove R1CS

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 ’10), 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+r-Groth 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 “provingas-a-service” scenarios where all witnesses reside on a single machine.