ZK9: Speeding up SNARKs with cached quotients - Ariel Gabizon (Zeta Function Technologies)

Transcript

foreign [Music] is going to be talking about speeding up stocks with cash quotients welcome into the stage please thank you [Applause] uh yeah so uh so so like the title says the focus of the talk is a technique called cached quotients uh but I I want to start by sort of casting that work in uh in zooming out in sort

of a description of what's been going on with pairing based snarks in the last decade or so so uh we can think of it as the the pairing based triology uh where uh the first episode A New Hope was Yen Squad saying look we've got these cool things called pairings and we can get proofs like with constant number of group elements without all the complications of what what was What's called the PCP theorem then uh that snarks were based on back then uh and then the pivotal moment in this sort of chapter was a ggpr that introduced qaps that then were dubbed are when cs's and and that work sort of said look you know

this can really be practical and grad 16 which we all know sort of optimized this approach so this was sort of a chapter where we said let's basically do everything with with pairings uh the second chapter the polynomial commitment scheme Strikes Back was uh saying yeah pairings are great but actually if we sort of restrict our use of pairings to just this one cryptographic component uh what probably ever most people here are familiar familiar with a polynomial commitment scheme we can suddenly get a lot of flexibility and this is what gave us snarks with a universal setup instead of

setup for circuit which was a logistical nightmare uh this was what helped us get custom Gates that we all like uh so yeah so this is this this is all pretty good uh and the sort of the third chapter which which we're sort of starting late recently we've started Return of the pairing uh started with this work called caulk and you could think of it as just sort of going back to a middle ground where okay we don't have to do everything with the pairing when it's not convenient but maybe there's places besides the polynomial commitment scheme where we

can get some power out of the pairing and caulk and and other you know started is this work that started showing yes we definitely can uh so before starting to describe this this sort of third chapter of this Trilogy Let's uh do a short kzg uh recap so the the kzg polynomial commitment scheme which I imagine most of you are familiar with uh the basic idea is we have this is what's called The Trusted setup we have some we generate somehow in a protocol a string of group elements where in the exponent or in the scalar we have the

powers of some secret X and then this gives us a way to com get a short commitment to a degree D polynomial what is the commitment of a the degree D polynomial it's simply F it's simply F of the secret X encoded in the exponent or in the scalar so kcg commitment scheme uh probably most of you know incredibly useful uh but really for the talk if you're not too comfortable with it the two cool features of kzg that we'll need are the following so these two features you try to engrave them in your mind uh the first one is linearity

if I the commitment of the polynomial f plus G is the commitment of f plus the commitment of G the second more fancy property is that using the pairing we can do product checks directly between commitments so say now I have commitments to four polynomials F1 F2 G1 and G2 then I directly from the commitments I can check whether the polynomial F1 times F2 is equal to the polynomial G1

times G2 and the thing that may confuse you if you're familiar with pairings is like okay I can see how you compare the commitments using a pairing but you're saying that means the polynomials that are identical as polynomials and here we use this strong assumption the algebraic group model which lets us conclude that that yes if if we can actually conclude from this check that the polynomials are are identical uh so those are the two nice features of kzg as a polynomial commitment scheme the linearity and the ability to perform uh product checks

all right so now that we did that recap we can describe the the first chapter of uh the first part of this third chapter of pairing based snark so uh from from caulk so we can think of the following question we have a Vanishing polynomial of some subset some subset t and we're giving we have some polynomial f the verifier has the commitment to this Vanishing polynomial ZT and the commitment to f and now the prover wants to convince the

verifier that this F is actually the vanishing polynomial of some subset s that is contained in t so if you've you know played around with quotients uh you know kzg you can probably think of how you would do this uh and the natural way to do this would require uh an amount of approver operations that it depends on the size of t or let's say T minus s and the uh the the the the cool thing that happened with caulk is

they can do this with only order s operations right so think of s being much smaller than t uh caulk was able to do this in order s operations uh so right so how does this work I won't go uh I'll only sketch this because I want to save your brain power for uh the cached quotients method that I want to explain

which is something a bit different um so so actually let me uh let me I'm going to skip uh uh I'm gonna skip how how this thing works and if there's time or someone asks me it will get to it in the end but again the cool thing that started this new chapter of pairing base based narcs is that this requires only order of s not order of T operations all right so now let's talk for one second about uh sparse polynomials what do I mean by sparse polynomials so for

the rest of the talk keep in your uh head we always have two parameters little n and big n and little n is naturally much smaller um so what do we mean by sparse polynomials so think that we always have some fixed set of polynomials like capital N polynomials B1 to b n uh and you know what do we mean by a polynomial a being little n sparse in the base B right we simply mean that we can write it as a combination of at most little n of these bis right so we can write it like in in this

way where only little nais will be non-zero okay so that's that's sparse polynomials and you know most of the time but not all of the time as we're going to see in this talk what is this B it's going to be just the LaGrange base of some subgroup right so the sparsity corresponds to the polynomial being mostly zero and some subgroup so sparse polynomials interact nicely with kzg why because we can pre-compute

the kzg commitments of the basis elements and later during a protocol when the prover has some little n sparse polynomial a from the linearity of kzg they can compute the commitment to a in just little n operations right because they're just going to combine the commitments of the bis that are used in a all right and now we finally come to the

this cache potions method so what what is the scenario generally we're going to look at you know concrete applications like lookups later but what is the general scenario we're looking at with cash quotients so the scenario is like this we have some predeter prefixed uh pre-process polynomials T and z uh where the degree of Z is this capital is Big N and think also the degree of t as something of that order something big and so and now the prover has an input a n an N sparse little n sparse polynomial

a and some polynomial R of degrees smaller than than big n and the verifier has the has the commitments of these polynomials and okay and now what do we want to do the prover wants to convince the verifier that a times T So a is the sparse proverb polynomial again T is the pre-processed polynomial that a times T is equal to R mod Z

and you know the punch line is that we want this to be an O of little n operations okay so so all of these polynomials in this equation they're of degree typically big n and we want to do this the punch line the point is we we want to do this in O of little n operations all right so what's the natural way we

prove things like this right we we use quotients so we know that a times T is equal to R mod Z if and only if there exists some quotient polynomial Q such that a times T is equal to z cubed plus r and again we don't Q is going to be of degree something like lar begin typically the point is we're going to be able to compute the commitment to Q in only little n operations so how do we do this

first we're going to have a pre-processing stage where for each eye we're going to compute the commitment to a polynomial qi what is what is the polynomial qi it is the the quotient that comes up when for the if basis element that a is sparse in uh we multiply by D and divide with remainder by Z so right so B1 to b b Big N that was the basis in which a was sparse and q i is the polynomial such that for the if basis element B I times T equals

q i times Z plus plus sum remainder all right and and here is where the name cache quotients comes from so the cached quotients are the commitments to the these qis where again what are these qis they're exactly the quotients when you divide with remainder

uh the the basis elements in which you are your input polynomial is going to be sparse thank you and yeah we're also going to pre-compute the the commitment to this z and d that t that we're multiplying and then uh dividing by right remember Z and T

this method works when Z and T are predetermined uh so basically right the reason we we can do this is that uh a technical way to say it is like division is a linear operation or a consequence of that or another way to say it is that Q is going to inherit a sparseness if A's sparshness was in the this bi basis Q sparseness sparsity is going to be in this Qi basis

right so so more precisely if to remind you again a is this sum a i b i where most of the AIS are zero so so Q you can check just from the linearity of division is going to be sum a i q i and therefore after we've pre-processed the commitments to the qis the prover can compute now the commitment to Q uh in only little n operations right this AI not equal to zero is a little redundant because uh well

obviously it's redundant because the zeros wouldn't change the sum okay and now so now we come all right so what what the situ what's the situation we're in we want to check that a times T is equal to Q times C plus r where we don't actually have q we only have the commitment to Q actually Computing Q would be too expensive for us but here's where the second nice property of kcg comes in

that we you know went over in the beginning that if degree we have an equation of degree at most two we can directly check it on the commitments with parents so given only the commitment to a T Q Z and r uh uh we can uh the verify can check that that this this equation holds which uh whoops what happened like my monitor okay uh which exactly uh uh right exactly implies what we wanted that a times T is

equal to R mod Z so right so that that's basically the cached quotients method and like an abstract General setting and now let's look at two concrete uh concrete cases where this has been used so the first time this was used uh was in a paper called CQ which just stands for cash quotients uh with Dario Fiora and uh Liam Egan uh so so what's the lookup problem you're probably familiar uh we have some pre-process table T of size big n

we have some witness F of size little n and we want to check that all the elements of the witness are in the table we want to prove that and and the very interesting uh you know result of this this line of works that started with call can culminated at least currently in CQ is that we can do this in prover time little end time login so we can we can do lookups improver time that after pre-processing doesn't depend

on the table size so for big tables this is a this is a huge this is a pretty big improvement over pluck up that required capital N log n uh operations uh so I'm going to concentrate on a second application so the very sketchy sketch of of of this uh of this why this works is that if we use the log derivative lookup that there was a very nice talk

by Ulrich about it uh earlier this morning um if it ends up being that what you're doing there is multiplying some sparse polynomial that's sort of representing what values are actually used from the table uh times uh pre-process polynomial a polynomial representing the table and and right and this is exactly a good fit for this cached quotient methods right if we multiplying a sparse polynomial by a pre-process polynomial this the cache quotients method allows us to do this where the number of prover operations only depends on the sparsity

right so this this proof sketch is is what what appears in the CQ paper in greater length and now application two from a more uh recent paper uh with again with with Liam Egan uh called cqlin uh what is the time situation five minutes okay uh so so I'm gonna I'm gonna uh you know I'm actually gonna I'm gonna get a little technical now

so apologies if this part is going to be uh not totally followable uh so what what is the Lynn check problem so we have some predetermined fixed end times n Matrix uh we have some prover polynomial the verifier has the commitment to it and let's call a just the vector of values of this polynomial on some subgroup of size n so from now on the big n is going to be little N squared and it won't won't be explicitly on the on the slides in some sense uh

and what do we want to do we we want the program wants to show that M times a is zero and the again the punch line is he wants to do it in O of n operations even though the Matrix could have N squared uh non-zero entries and for for the next slide let's let's let L1 to Ln be a LaGrange basis for for h uh so so

I'm going to reduce this problem to the sort of cash quotient I'm going to massage it into the cache quotients uh uh setting uh so this will be a little technical apologies we're going to represent the matrix by a polynomial of degree roughly N squared uh so it's the polynomial mij where uh you know the sort of the row is going to be multiplied by the LaGrange but with X to the N inside times LJ of X so so this is this is the polynomial uh representing the The Matrix uh

think of the X to n it might help to think of the X to the N uh as y it's just another variable Y and then right this expression maybe looks is easier to digest and really in earlier early drafts of the paper it was why uh and now let's let's C be the the polynomial x to the N squared minus one um and let a be uh sort of our input polynomial but with a raised to the power n inside so a is like f of x to the n and now finally let R be like a times m UD Z

so so the idea is sort this a times m is sort of a polynomial representation of the vector matrix multiplication uh and you know if you sit with a a paper in in the in pen you can see that R is going to have this form and of course it's a lot to digest what I want to highlight is that if you look at the inner sum that is right that's sort of the expression you want that's like the the ifro of the Matrix times the vector a it's almost what you want but it has

this annoying Li uh of of x to the n right so if we didn't have that annoying l i of x to the N this R would be and would be zero right in the case that the prover is honest and the Matrix times a is zero that this this R would all be zero right so like I said so M times a okay okay but right we could get rid of this l i of x to the N if we if we mod It Out by x to the N the this Li of x to the N would become some constant would

come like one just the constant one over n so we have that M times n is zero if and only if this R is zero mod x to the n uh okay and now we wanna show that the the you know this is a fit for the cash quotients method so the first thing to notice is that this a is sparse in what in like the basis of the LaGrange polynomials but but uh but applied on X to the N right because again a was a was just f of x to the N so right it's gonna it's gonna be this it's just this polynomial of n Powers so it's going to be sparse in this base

so basically we're going to use the cache quotients method twice one wants to show that the the remainder we committed to is really correct that a times m m is equal to R and the second time to show that R is zero mod x to the n uh and an important point right sort of what we said was like we can use this method when are then the not fixed polynomial is sparse and again the point is because of the linearity of division uh if we start off with a sparse a R is going to be sparse in an

appropriate base of uh remainders uh that you know when when you multiply remainder is like in multiplication of M uh mod Z uh yeah so I'm like more or less on zero all right so yeah so anyway I'll stop here and thanks and I'm I guess open for questions if there's time yeah [Applause] can take one question for good measure at the rest just hook up with Ariel afterwards

uh what do you use the Lin check protocol for uh we haven't used it yet uh I think it it would could be good for a zkml applications where you have a lot of multiplication by matrixes that are potentially dense like as opposed to matrices you get from r1cs that are very sparse so zkml in one word thanks right we have to rush to the next talk but please feel free to talk with the real afterwards thank you very much Adrian thank you