ZK13: Garuda & Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments

Transcript

[Music] Thank you guys. I'm Michael. Uh today I'm going to be talking about two new snark constructions that we call Garuda Empire. And we're going to do this by introducing a new cryptographic primitive that we call equicient polomial commitments. This is joint work with Pratush Mishra and Alireza Sherzad. So as many of you may know, snarks enable an untrusted prover to convince a weak verifier that a statement is true. The prover will pro prove that it knows a witness w satisfying a computational statement. An example of such a statement could be that the provers the pre-image of a shot 256 hash. While the trivial way of doing this is to have the

prover send the witness in the clear uh to the verifier um and just have the verifier check this relation itself. Snarks need to be succinct by definition, which means that the proof size and verifier time need to be strictly sublinear in the size of the witness. The general layout of a snark is that the computation or the circuit is fed into a setup algorithm which outputs prover and verifier keys. The prover will use this prover key along with a public input X and a private input W to generate a short proof. And then the verifier will check this proof using the verification key and the public input and output a decision on whether or not it accepts the claim. Formally snarks satisfy two security properties. The first of which

is completeness which says that if W is a valid witness then the prover always produces a valid proof that the verifier accepts. And the second one is knowledge soundness which says that if P does not know a valid witness then the verifier rejects. Another way of saying this is that if the prover actually manages to convince the verifier with a valid proof, then the provers the witness w. As we saw in the previous slide, snarks magically compress computations by making short proofs. So one natural question arises, how much can we actually compress this proof size by?

And so while this question might seem theoretical to you in nature in practical applications like blockchains the smaller that the proof is the less gas that we have to pay to keep it onchain. So if we look at short snarks the most popular one is grotth 16. Groth showed that the proof size for pairing based snarks must be at least two group elements and he also constructed an optimal three groupoup element snark that has 192 bytes and 128 bits of security. Very recently, Lintma constructed a snark with three group elements and one field element that totals just 176 bytes. The second natural question is how fast can we prove? So, cryptographers have spent the last

decade or so trying to reduce the overhead of proving and even the best snarks today are about three orders of magnitude slower than just running the native native computation without using a snark. And so, generally to make fast snark provers, there are two approaches in practice. The first one is to use techniques that only pay for nonlinear gates in your circuit. This is achieved using so-called linear or LPCP based snarks, which are those whose proofs are linear combination of elements inside of the common reference string. In this family of snark snarks, the provers for nonlinear constraints like multiplications, while additive constraints come for free and aren't a factor in the time complexity of the prover. The most famous example of a

snark that achieves this is grot 16. The second approach is to use custom gates. So instead of using addition and multiplication gates to express a big and repetitive operation like an elliptic curve operation, a range check and so on, we can use a higher degree gate or a single gate that's customized for that operation. This has the effect that it drastically reduces the size of the overall circuit and makes the snark prover faster. Unfortunately, there are no existing snarks that use both approaches simultaneously. We introduce two novel snarks Pari and Garuda that push the boundaries on both the proof size and prover time frontiers respectively. Pari is the smallest known

snark in terms of proof size just two group elements and two peeled elements in size and in 128 bits of security. This totals just 160 bytes on the curved BLS 12381. In terms of prover time, we introduce Garuda, which is the first snark with free addition gates that also supports custom gates. Garuda is about three times faster than Groth 16 and is two times faster than hyperplunk, the latter which does not have free addition gates but has custom. So we prove both of these security in we prove both of these snarks security in the random oracle model plus the algebraic group model.

And both of these snarks are circuit specific and require a trusted setup. And so to actually construct paranora we introduced a new flavor of polinomial commitment schemes that we call equicient polinomial commitment schemes or EPC for short. Equicient here just means equal coefficient. And to do this we develop a new framework by which to construct snarks based on the popular compiler approach which takes a polomial interactive oracle proof a polomial commitment scheme and compiles it into a snark. Our compiler replaces a polomial commitment scheme with an EPC scheme as a as a drop-in replacement. At a high level, inside of our hybrid model, the EPC scheme is used to enforce linear

constraints while the POP takes care of the nonlinear ones. And so we'll get into the details later, but first we need to cover some background. First up is the polomial IOP. A polinomial IOP is an interactive protocol between a prover and a verifier where the prover convinces a verifier of a computational statement. And so the prover and verifier exchange messages over multiple rounds and the prover sends messages called polinomial oracles. And the verifier responds by sending random challenges to those oracles. At the end of this interaction, the verifier will query the oracles at at points of its choosing and the prover will respond to them by providing the actual evaluation of the polomial at those query points. And the important

point here, the important point here is that rather than the prover sending over the polinomials in the clear which are of extremely large degree and expensive to communicate, the prover the prover has to give query access to evaluations of these polinomials. And finally, the verifier just takes the result of all of its queries and makes a decision on whether or not to accept or reject. And PIOPS also satisfies standard security notions like completeness and uh and soundness. Next up is the polomial commitment. So a polinomial commitment allows a sender or a committer to commit to a polomial inside an object called a commitment and later prove to a receiver an evaluation claim. namely that the polinomial inside of the commitment

evaluates to a claimed value at the query point of the receivers's choosing. And so the whole point of commit commitments is that they are much smaller than the actual polomial itself but let you prove properties about the polomial for example an evaluation claim without having to communicate the entire polomial to the receiver and so PC. So in the diagram the committer will generate a commitment CM and then send it to to a receiver and then the receiver will sample query point of its choosing and the committer response to this query with an evaluation proof pi and a claim evaluation of P at Z. Then the protocol ends when the receiver just checks the proof. PC schemes also satisfy notions of completeness and

extractability. the latter which says that if the receiver accepts the evaluation proof for the commitment then the sender knows a polomial such that P of Z equals V. Another property which you might be fi familiar with is binding which informally says that the commitment object is bound to the polomial inside of it. So once you commit you can't change the polomial and so taking these two ingredients the POP and the PC we can actually construct the snark and this is from prior work. The general idea is that we will replace polomial oracles inside of the pop with a polomial commitment scheme and then the prover can simply commit to a polinomial and when the verifier sends a query the prover will respond by sending the

corresponding evaluation at that query point along with the evaluation proof. So if we look at this diagram, the setup phase uses the POP specification to output the maximum degree of the polomials that are supported by the protocol and then the PC setup will use this degree bound to output committer keys and verification keys. So for example, if you're familiar with KZG, this bound is what determines the size of the powers of towel. Then the snark prover and snark verifier will interact over a number of rounds where the prover sends commitments and the verifier sends random challenges. So for example, if you're familiar with hyperplunk or Spartan, this can be a multivariate sum check. At the end of the interaction, the prover will commit will open the

commitments at the query points, potentially do other checks with the evaluations of these of these polomials in the commitments and then decide whether or not to accept or reject. And so importantly, this snark verifier only verifies uh only accepts if the POP verifier and the PC checks both pass. And so in the literature a popular way of arithmetizing a snark computation so turning a computation into a language that the snark can interpret is to use constraint systems. And one of the popular ones is R1CS or rank one constraint systems. In R1CS you represent your computation by matrices A, B and C and the relation AZ * BZ equals CZ and imposes quadratic

constraints on the elements in Z. And so in prior work, this means doing a PIOP for row check to make sure that the nonlinear multiplications are handled and also a PIOP for linch to take care of the linear constraints. And so while PIOPs for roche are really good, POPs for linch are very expensive and require sending numerous oracles from the prover to the verifier. And remember since these oracles are actually materialized as polinomial commitments, this leads to more MSMs and slower provers. And so the high level intuition here for this is that in roche polomial identities are much easier to verify but the polomials themselves the zb and zc can encode the witness in an arbitrary manner leaving a

large bulk of the work uh for lynch to do for the lynch p to do and so our idea is to combine the efficient nonpop based approach from snarks like ggpr13 and groth 16 for lchek and to use the existing pop based approaches for roach that are already very efficient. And so as a response to the current shortcomings of POP based lynch, we start by proposing a new interpretation for the lynch relation. And so the goal of an interactive proof for lynch is to prove to the verifier that a * z equals za as vectors much more efficiently than sending all of z in the clear and having

the verifier just check this relation itself. And so in modern shrarchs this is done using pops but again we actually want to do this using polomial commitment schemes. And so in our new new line check the first step is to express the relation A * Z= ZA as a linear combination of column vectors. And so recall from linear algebra that a matrix vector product is simply a linear combination of the columns of the matrix where the coefficients are the elements in Z. In the second step, we want to convert linch from the language of matrices to the language of polomials, which is crucial since snarks operate using polomials. And to do so, we interpolate these column vectors using LRT interpolation, which represent which

represents each vector as a polomial. And so this interpolated polomial has the property that its evaluations match the original vector entries over the domain of interpolation. And so now our matrix vector product has become a linear inter linear combination of polomials each of which interpol each of which interpolates these column vectors. And so now we can actually express ling in the language of polomials instead of the language of matrices because a * z equals za as vectors if and only if this linear combination of the ai polinomials holds over the entire domain of interpolation. And so in the third step, notice that in the definition of lining, ZA, ZB and ZC uh need need to have the same vector Z for all of them. And so

one way of thinking about this is that there's a coefficient equality constraint on these polomials when they are written in their designated bases. So to formalize our new interpretation using cryptography, we construct a new cryptographic primitive equal efficient polomial commitments that will enforce these coefficient equality constraints and as a result satisfy the linch relation. And so the upshot of this is that instead of designing a complex pop for lynch, we just baked the linch into the commitment scheme itself. And so now your the Pops in your snark only have to worry about row checks for nonlinear constraints which is what the the POPs are best at handling. And so we begin by defining

what an equal constraint is. A coefficient equality or an equicient constraint E is just a set of bases for polomials. And these polomials are set to satisfy the constraint if they're equal when expressed in their designated bases. So as you can see when ZA, ZB and ZC are expressed in the A, B and C bases they're just equal to Z. So here we just list three polomials but you can generalize it. So formally the EPC scheme consists of the following algorithms. First is EPC setup that samples public parameters given some maximum degree bound for the polinomials that we'll be committed to and the bound is just derived by the number of securities in the number of bits of security in your system. So if

you want more security, you make a higher bound. In the EPC specialized phase, you'll um you you will sample private random private randomness that's specific to each equal efficient constraint and then output committer, opener and verifier keys. The committer and opener keys are used by the sender to commit to polomials and then open their commitments at the query point sent by the receiver. And so to recap the diagram, the sender sends a commitment which is an equicient commitment to the polomials P1 to PT under the constraint specified by the committer key and specialize. Then the receiver sends R the query point and the committer then opens the commitment uh or at Z in this case opens a commitment and then sends back the opening proof

that the receiver can go ahead and check. And so EPC schemes satisfy standard notions of security namely completeness and knowledge soundness. And so then if you recall from the previous slide, one of the previous slides that the completeness property of a regular PC scheme says that the verifier accepts the evaluation proof if all of the evaluations are indeed correct. And so EBC scheme as a polinomial commitment scheme inherits this condition but has the additional property that the committed polomials satisfy the equition constraint and extractability extractability is also similar. Our analog is that if the verifier accepts then it must be the case that the provers polomials and also that they satisfy this equation

constraint. And so to give intuition behind our new primitive, we present a vanilla example of EPC that's based on KZG. And so the first step in KZG, the committer will take a committer key along with the coefficients of P and compute a dot product. And if you take this dot productduct, you end up with a linear combination of the powers of tow which is equal to P of TOA in the group exponent. And just using KZG, we can commit to the polinomials Z A, ZB, and ZC. And so the second step is that we actually want to enforce the equation constraint amongst the polinomials that we just committed to. And so the first step of doing this is to create a new commitment key that I'm going to call

the consistency key. And to actually make this consistency key, the first step is to start by constructing three new keys that are specific to the polinomial bases A, B, and C inside of the equation constraint. And so if you look at these keys, the ais, the bis and the cis are just polomials inside of the bases evaluated at toao in the group exponent. And so now we take the keys that we constructed in the previous slide and we compute a random linear combination of them to make the consistency key. And so notice here that the cka, ckb and ckc are exactly the same as in the previous slide except that we've scaled each of them by a random coefficient and then we've added them. And so in the actual protocol, the consistency key would be created in the

specialized phase using alpha, beta, and gamma as private randomness. And then the committer would invoke the commit algorithm to use this consistency key CK star and commit to Z which is purportedly the equal coefficient representation of ZA, ZB and ZC. So the upshot of this is that if the committer commits under this key CK star with anything other than Z, then the verifier is going to reject. And so the committer is forced to commit to this equal coefficient representation if it wants the verifier to end up accepting. And so to recap our our new commitment algorithm, you commit to each of these individual polomials and then you commit to Z under the consistency key CK star and you output all four of these commitments. And so in pari to get

a very short proof we make a number of optimizations that allow us to only output C star and not the three other commitments. The EPC evaluation proof is another group element which is why you see two group elements in the size of pari. Now that shouldn't be immediately obvious to you from this slide but it's more of just an FYI behind our construction. And so the final step is to actually do the EPC verification. And we can think of this as doing a standard KCG verification for the commitments to the polomials and then augmenting the KZG scheme with a consistency check. And I'm not going to dive into the math behind the consistency check, but the check is what ends up enforcing the equicient constraint while the KZG steps step ensures that the evaluation claims

of the polomials are all correct. And so remember that in prior work the common recipe for building snarks is taking a pop a polomial commitment scheme and compiling compiling them into a snark. And so in our work we show that we can also use this compiler but substitute the PC scheme with EPC as a drop in replacement. And so following this train of thought, we can take the previous slide where I showed you this the PIOP plus PC scheme diagram and just make a snark and replace PC with EPC. And so I'm not I'm not going to spend too much time on this slide because one of the earlier slides is extremely similar, but we've basically migrated the entire PC toolbox

like the setup algorithm, the commit algorithm, etc. to use EPC. And so if you remember from the beginning of the talk, all snarks have to satisfy completeness and knowledge soundness. And so while I'm not going to dive too deeply into the math proofs uh in this talk, completeness follows by the completeness of the individual components which are remember the POP and the EPC scheme. And for knowledge soundness, the general idea of these proofs is to proceed by contradiction. So if you construct an adversary that breaks the knowledge soundness of the snark, then you argue that you can construct one which either breaks the soundness of the POP or the knowledge soundness of the EPC scheme. And then you would argue that this leads to a contra contradiction if both the PIOP

and EPC are secure. On the efficiency side, the proof size is equal to the number of commitments, the evaluation proof, and the number of claimed evaluations from these commitments. The prover time is equal for the time of the PIOP prover plus the time that it takes to commit under EPC and plus the time that it takes to open the EPC commitments. And finally, the verifier time is just the time that it takes for the PIOP verifier to run plus for the EPC checks to occur. And so a big note is that our construction does not yet achieve ZK though this is something that we're working on adding. So for instantiations of our snark first with pari we instantiate it with a univariate row check pop and a univariate EPC scheme that's based on

kg. So pari is a snark for square r1 cs which is also an mpcomplete language. And so the trade-off to using square r1 cs as opposed to r1cs is now is that now the matrices double in the number of rows which means that the msms are roughly twice as large. But the upside of this again is that you can reduce the proof size by a by a single field element compared to if you had not had done this. So the proof size ends up being two field elements plus two group elements in G1. And the field operations in for the prover time are quasi linear due to lrange interpolation and FFTs.

But again note that this only scales with with the nonlinear constraints in the circuit and the additive constraints are free. In total, there are four MSMs for the prover and the verifier computes three pairings and also reads the public input. For Garuda, we instantiate it with a multivariate row check. So, a multi-linear sum check which incurs o field operations in the number of nonlinear constraints. We also use an EPC scheme that's based on the PST commitment scheme for multivariate polomials. We also introduced a new variant of customizable constraint systems which we call generalized R1Cs to handle the higher degree gates in our arithmetization.

We found GR1CS easier to work with though both CCS and GR1CS are functionally equivalent. And so on the prover time, Garuda computes O of T MSMs of size N of size N where again T is the error of the custom gates and N is just the nonlinear constraint count. And the verifier computes login pairings and the proof size is also logarithmic. And finally, as I mentioned, both of these snarks require a trusted setup and are circuit specific. So we implemented pari and garuda using the arcworks library and for garuda there is also a jaw1cs programming infrastructure to use custom gates.

There is also a solidity smart contract generator where if you run the pari verifier that's written in rust it'll just generate the corresponding solidity code for you. So we evaluated pari over verification time, gas cost, prover time and proof size compared to other popular snarks including fflunk groth 16 and polymath on the circuit which is a cascade of rescue hashes. And so let's analyze these plots from left to right for verification time. We find that pari and polymath are the quickest and groth 16 to grow linearly in the input size. And this is actually reasonable because groth 16 has to compute an MSM of size of the public input inside of the verifier whereas pari and polymath don't compute MSMs in the verifier. And so

compared to polymath we also see that par's verifier is roughly 15% faster. For gas price we should expect to see a similar behavior to verification time since the smart contract will just compute the snark verifications using various pre-ompiles. And in terms of prover size a prover time all the way to the right pari is roughly twice as slow as grot 16 and again the reason for this is because groth 16 groth 16's prover does 3 ms that scale with the multiplicative constraints but pari does four msms that are of double the size because remember pari uses square r1cs instead of r1 cs.

Um and so the trade-off of this is that it'll reduce the proof size but it increases the prover time. uh compared to polymath we see about a 30% improvement on proof size over various different curves we see that the size of pari is almost is always at most equal but otherwise always less than groth 16 and polymath with equality being achieved on the curve bn2x4 and pari being smaller for higher bits of security for this slide for the evaluation of garuda it makes sense to mainly focus on proving time since this is what Garuda is best at and this is a plot all the way to the right and so we see that Garuda is consistently the fastest prover and is about two times

faster than Hyperplunk and three times faster than Groth 16 and compared to Hyperplunk Garuda doesn't pay any cryptographic cost for additive constraints which is why you see the better performance and so the upshot of this is that you would want to use Garuda in scenarios when you want a blazing fast prover at the expense of having a circuit specific setup and larger proofs and so if you're using grot 16 which is circuit specific but want a much faster prover and don't care as much about proof size you can use Garuda for the proof size Garuda's in the middle Garuda scales logarithmically in the number of nonlinear constraints and scales with the erity of the custom gates and finally for the verifier Garuda computes a lot of pairings versus groth 16 which only computes constantly

many and we also found the verifier to be about twice twice as fast as hyperplunks and to conclude the talk we leave a couple of open questions. So the first one is that of all of our EPC constructions uh use a circuit specific setup and so the main question is can we actually use EPC schemes that achieve a universal setup. The second question is generally other applications of EPC that aren't in snarks and finally currently our snarks don't achieve ZK though this is something we're working on um and our question is is it actually possible to add ZK without increasing the proof size? Thank you.