Garuda and Pari: Faster and Smaller 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 it. 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. This is smaller than the sizes for Groth16 [Groth, EUROCRYPT '16] and Polymath [Lipmaa, CRYPTO '24]. PARI also 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) for non-uniform computations. These benefits enable significant prover-time savings compared to state-of-the-art SNARKs. 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 with our EPC schemes. smaller than those that do not. Proof size. From the proof-size perspective, the state-of-theart SNARKs are Groth16 [32] and Polymath [39] . Over the BLS12-381 curve, Groth16 proofs are just 192 bytes, while Polymath proofs are 176 bytes. An important open question has thus been: what is the shortest proof size for a SNARK for NP? Our contributions We answer all the foregoing questions in the affirmative by constructing two new SNARKs: GARUDA and PARI. While both schemes share a common construction methodology, they exhibit different performance profiles and target distinct application scenarios. We detail the ideas behind these SNARKs next. GARUDA: custom gates and free linear gates. GARUDA is a SNARK for Generalized Rank-1 Constraint Satisfiability (GR1CS), an NP-complete language that we introduce, which extends the popular Rank-1 Constraint Satisfiability (R1CS) with support for custom gates. For a constraint system of size n, GARUDA's prover requires O(n) field operations and O(n) group operations. It also achieves O(log n) proof size and verifier time. We prove (an interactive version of) GARUDA secure in the algebraic group model (AGM) [25] . PARI: a 2-group element SNARK. PARI is a new SNARK for 'square' R1CS [34] that achieves a proof size of two group elements (and two field elements) over Type-III pairingfriendly groups. When instantiated with the BLS12-381 curve, PARI achieves a proof size of just 1280 bits, which is the smallest in the literature. More generally, no matter the choice of pairing-friendly curve, PARI's proof size is always smaller than that of the state-of-the-art prior work [32, 39] . The prover and verifier times for PARI are also similar to those for Groth16 [32] : for a circuit of size n, PARI's prover requires O(n log n) field operations and O(n) group operations, while its verifier cost is dominated by 3 pairings. Like GARUDA, we prove an interactive version of PARI secure in the AGM. New methodology: succinct arguments from equifficient polynomial commitments. We present a methodology for constructing succinct arguments for GR1CS that extends the popular 'Polynomial Interactive Oracle Proof (PIOP) + Polynomial Commitment (PC)' framework [19, 14] to work with a new kind of PC scheme that enforces "equal-coefficient", or equifficient, constraints. Roughly, such equifficient PC (EPC) schemes enforce the additional property that given a batch of polynomials p 1 , . . . , p n and associated bases B 1 , . . . , B n , the coefficient vectors of these polynomials in their respective bases are equal. Our new 'PIOP + EPC' methodology leverages EPC schemes to enforce linear constraints, as opposed to prior PIOP-based constructions [19, 48] which use complex PIOPs for this task. This shift enables constructions of succinct arguments that can use simpler PIOPs that are responsible only for non-linear checks. We provide a generic construction of EPC schemes from any pairing-based (plain) PC schemes where the commitment to a polynomial is a Pedersen-like commitment [45] . A number of popular PC schemes satisfy this constraint, including the KZG [36] and PST [44] schemes. We also describe an extension that allow producing a single batch commitment to multiple polynomials where the commitment size is independent of the number of polynomials in the batch. This property is