Garuda and Pari: Smaller and Faster SNARKs via Equifficient Polynomial Commitments
SNARKs are powerful cryptographic primitives that allow a prover to produce a succinct proof of a computation. Two key goals of SNARK research are to minimize the size of the proof and to minimize the time required to generate the proof. In this work, we present new SNARK constructions that push the frontier on both of these goals. Our first construction, Pari, is a SNARK that achieves the smallest proof size amongst all known SNARKs. Specifically, Pari achieves a proof size of just two group elements and two field elements, which, when instantiated with the BLS12-381 curve, totals just 160 bytes, smaller than that of Groth16 [Groth, EUROCRYPT ’16] and Polymath [Lipmaa, CRYPTO ’24]. Pari achieves the lowest known gas cost for on-chain SNARK verification, reducing the gas cost by 6% compared to Groth16 and 17% compared to FFLONK. Our second construction, Garuda, is a SNARK that reduces proof generation time by supporting, for the first time, arbitrary “custom” gates and free linear gates (in terms of cryptographic costs). To demonstrate Garuda’s performance, we implement and evaluate it, and show that it provides significant prover-time savings compared to state-of-the-art SNARKs (Groth16 and HyperPlonk [EUROCRYPT ’23]) Both constructions rely on a new cryptographic primitive: “equifficient” polynomial commitment (EPC) schemes that enforce that committed polynomials have the same representation in particular bases. We provide both rigorous security definitions for this primitive as well as efficient constructions for univariate and multilinear polynomials. Our constructions are obtained via a new compiler that obtains a succinct argument by combining polynomial IOPs [Bunz et al., EUROCRYPT ’20; Chiesa et al, EUROCRYPT ’20] with our EPC schemes. As a matter of independent interest, we show that this argument achieves state-restoration soundness if the underlying PIOP does.