Paper 2024/1364

FLIP-and-prove R1CS

Abstract

We present the first folding framework that achieves sublinear verification and communication when a single prover must convince a verifier of $k$ independent R1CS instances. - $\mathbf{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. - $\mathbf{r \operatorname{-} 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 "proving-as-a-service" scenarios where all witnesses reside on a single machine.