ZK10: Degree tricks in DEEP STARKs - Shahar Papini

Transcript

[Music] on this stage we have Shahar papini hi there and from stockar and yeah welcome to the stage thank you very much hey yeah so the title of my talk is not deep Stark tricks like I said I lied sorry and um it's about lookup with Starks or the recent small work me and from a polygon did so here it is all right so I'm going to explain a

bit of preliminaries about Starks and and lookups and uh and products and the gkr and some checks like to give you background so I hope most of you will understand understand what's going on and and I want to say that most of the things I'm going to show here are not anything we did or like known things things smarter people did but I'll present them anyway so you'll see okay so uh in very high level what's a PO polinomial commitment scheme uh there are two uh sides in this proof system the prover and the verifier the prover

gives some kind of Oracle access to a polinomial of is's choosing he chooses a polinomial and kind of gives it to verifier and the verifier can sample this Pol at some point and uh know it's the right value all right so in our context we are talking about two Pol nomials as you can see from the right P of x and q of X and we're interesting interested only in some subset of of the points some domain D and not all of the points like you see here I don't have a laser point but yeah H okay so Starks are a tool that let lets us prove some kind of local

relations on a polinomial h something for example some relation on the current row or one row in the row after or something local but we want to prove some kind of global relation and for that we are going to use a a lookup okay so uh I'll start with a simple one permutation argument well imagine I have these two polinomial and their values on the domain and I want to show that all the values of p on this domain are exactly the same as the values of Q on this domain as a multiset or one is a pration of the other as you

can see this example Le p is 5 4 3 2 1 and Q is 1 2 5 3 4 these are permutations it's the same multi set so this should work out and the way we do this is by checking H basically the product of all the values but H we don't want the prover to be able to cheat so we first shift this point we compute the product of Zed minus the value and okay so we want to show this product is the same for p and for Q to do this we will add another column we call the cumulative product polinomial and this polinomial would be

the H product of of the values of P until this row and the values of Q until this Row the shifted values and to verify that this polinomial is true it's is just involving local relationships so we can do it with Stark for example uh one cell of the cumulative sum is equal to the cell above it times Q over P something like that so it's a local relation that at each step we multiply and divide by another thing and okay so H after we do this we basically need to verify that the last

cell is one because it's the product of of the one column over the product of the other column should be one if they're are the same and the cost of this uh proof is a cost of using two polinomial commitment schemes for p and Q for input vales and one for the cumulative uh sum cumulative product column which is an extension field polinomial because know if we talking in the realm of small field pin Q can have a small field value but the Zed shift we have for the column needs to be from a large field so uh

this column over the the right is might be a big H field column an extension field column so this might be kind of expensive and we would very much like to avoid it if possible but this is the regular peration argument okay so uh Now log up and okay log up is another uh lookup argument it doesn't uh want to show that the vales of p and Q are the same as multisets it want wants to show that the vales of P are contain the values of Q there's a type over there over the right it's supposed to be Q so here's an example if you can see p its vales are 1

2 1 1 42 and there're a subset of the Val of the table over the right 1 2 3 4 if I said Q it's supposed to be T there po p and t for table all right so I want to show that all the values on P appear in the Val of T so we are going to do something kind of similar instead of comparing the product of all the values we're going to compute the sum of one over the value shifted you know it's pretty clear that H if the H okay if we have two column that are permutations the sum of one over the values is the same as the sum

of one over the vales on the right side because we can just swap the order because it's a um symmetric so basically we take all the vales on the left like 1 2 1 1 42 and we group them group them into three instances of one two instances of two zero instances of develop three and one instance of develop four and and on on the table side instead of H duplicating all the values and writing one three times we only allocate one row for the value one and add another column for the multiplicity for how many times it appears on the

left so if we compute the sum of one over the values of p and show the same as the sum of M over the value t on the right meaning 3 * 1 over 1 and 2 * 1/ two Etc then it should show that these are the same Val of permutation or that every value on the left actually appears H in the table on the right and we shift the values H so the Prov can cheat all right and what is the c of this thing and like previously we have this uh one commitment on P we have an

extension field commitment of one over the values because we need to one over the values to be able to sum them and we have the same thing on the right side we have two columns T and M and one extension field R but usually these columns on the right they are smaller so I call it small number of m-sized polinomial commitments so note here that we also have a this extension field column which also is kind of expensive and we would like to avoid it if possible okay so this is log up uh lookup argument

um all right so yeah like I said the both Primitives require extra commitments and to the cumulative product and the one over the value for the log up and there are extension for commitments and we don't want that and an observation from the lasso paper if you were the lasso lecture earlier is uh to use gkr for this okay so nice letters gkr but what do they mean and I'll try to explain what gkr means and hopefully I can H yeah you won't get lost too much all right so Su Check N

gkr so I'll start by describing Su Che maybe some of you know Su Che it's a protocol that proves the sum of the values of p over D it works on multivariate polinomial though not univariant multivariant means polinomial with a a few variable and the sum is all always the sum over the hyper Cube hyper Cube basically means that for every X you put either zero or one so you have two to the end values 0 0 1 0 1 1 1 1 0 0 Etc okay so Pro this sum check protocol lets us

prove that the sum of the values of p over the hyper cube is something okay how this protocol Works in it's a it's pry simple but uh yeah simple okay H so first of all p uh send the value he claims is the sum this is a z and now he he wants to show that this is indeed a sum so he he computes another sum where instead of summing over the first coordinate b0 he replaces it with a variable X so comput this sum below P F0 there it's a

sum only on the coordinates that are not the first coordinates and the first coordinates we put this variable X now this is a polinomial in x a pol of low degree like let's say h is of degree five in every variable so f is just a pol of single variable of degree five so P can just the prover can just send all the coefficients of this polinomial it's really Su synct okay now that the pro sent this f0o V needs to do two things the refer needs to do two two things to make sure that everything is correct one he can use it to uh and put instead of X he can

substitute 0 and one and compute that he indeed gets a z for the sum you know because supposedly H if you put F0 at Z and F0 at1 and you sum you get the all the sum of the hyper Cube so F0 needs to be consistent with a z the other thing it needs to see is that F0 is indeed as the prover claims that it's indeed this sum over H so what he can do is substitute a random Point instead of our X random point R in and let's say it's in a big domain a very big domain an extension field and uh it is known that if we have

two univariant pooms and they're equal this bigger random point from Big Space then they're probably the same polinomial so if we can show this uh formula for the formula when we put r instead of X then it's probably the correct polinomial F0 okay but this new problem we need we need to show to the verifier is again a sum check a sum check with one less Dimensions so we repeat P this rounds login times you get login rounds and at the end H the verifier says okay so now we need to uh I get that h on an r0 R1 R2

R3 I I got the The Proven need to show me this point when I take H and substitute some random point that got from all the rounds and and this is where we we need some polinomial commitment scheme for the polinomial p h h p is the same as H okay it's po commitment scheme for the PO H where I need to uh the Prov needs to show that to the verifier that h on these random values are are what expected from the S protocol so I repeat it's log and rounds each time one coordinates gets set to

random number and at the end I need the prover needs to prove that h of one r0 R1 R2 R3 Etc is something and this is just a polinomial commitment scheme all right let see okay so now to have some check what about gkr how does gkr work well gkr is a is a protocol based on some checks that can prove that an arithmetic circuit H evales to something imagine that you have one of these columns let's say it's p polinomial i Envision it right right now is a row but it was a

column before and I look at all of its values and I build this arithmetic circuit on top of it h i create this layer of outputs and each output is some gate let's say a addition of two values in the input layer or multiplication of two values in the input layer and I repeat this uh and get an arithmetic circuit that built on on with multiple layers and at the end I have this one value and I want to show with the prover that the value when I put in as input my polinomial P I want to show that the value at the end is something let's say 15 so how can I do this I'm going to do

this with some check now it's important to to note that H while p is given as a poal commitment scheme um none of the other layers are ever committed on there are just a yeah they're not not not committed on prove just just needs to compute them but not has them not doal commitment scheme nothing and this is where we are supposed to gain all right so let's start with an observation about multilinear Pol polinomial which will help us for the gkr okay given some f f is multi linear polinomial which means it's poal of a a

lot of variables x0 X1 X2 X3 X4 but the degree in each variable is at most one okay and now look at this specific polinomial I just showed it's called e for equal e x XB H this polinomial okay it's a complicated expression but let's look at specific example for a 0 1 0 if I put instead of B 0 1 0 how does polinomial look like looks like 1 - x0 * X1 * 1 - X2 what this actually means it means that if x0 is one then this PO will be

zero because the first term term will will Zero out if X1 is zero again this zero is out and if X2 is one then this zero is out basically the only time when I put for instead of x uh binary values and it's not zero is only if x zero it's not one it must be zero X1 must be one X2 must be zero so this polinomial is actually the PO that gives one one on B and zero everywhere else on the hyper Cube which means it's the lrange polinomial basically we can use this to interpolate every

polinomial and represent it as sum as lrange polinomial so basically the thing we see below any f of x is the sum of the hyper cube of the value at this at point B times the lrange polinomial at B this is a polom that is one b and zero everywhere else so in multilinear pols the lrange polinomial is very nice it's very succinct and we can use this to do nice things like gkr all right okay so how gkr Works uh like I said we we have an

arithmetic circuit and it has layers where the input layer are called w0 the next lay is W1 the next L W2 Etc and and each one is a multi linear Pol polinomial and yeah represent the entire Val of of the layer and the idea of gkr is to reduce a query to a low layer into a query to a a layer above it so imagine I have this circuit that ends with a single value and I do a quiry to the single value which is just the value itself and reduce it to the quiry to the layer before before before

before before until I get to query to the input layer and then then I use uh my polinomial commitment scheme to compute this query at the input layer all right so how does this reduction work let's say I have this random query to layer L1 l+1 so I need to compute the polom w l +1 at R remember w l +1 is a a multi-linear polinomial that has all the values of this layer in the arithmetic circuit so what can I do H first I'll represent it using our

trick H as you can see here WL + one at R is a the sum of the Gran pooms at r or the sum of all the positions o on the hyper cube of the value of this layer at o time gr Pol at given it the query R okay now we need to see that WL +1 at o it's just a value it's not we don't really need to think about it as a polinomial anything it's it's simply the value of this layer at o and this value has a representation as Gates as Gates of the input layer because a okay it's

an arithmatic circuit and it means that every uh value in this layer is an output of some gate which means either some addition of two inputs or a multiplication of two inputs in the input layer in the previous layer so I can just open this expression w l plus one to H and generally I'm okay this is a general formula I'll get some more specific for formulas later but generally uh we we say the w l plus o is actually just a sum on the on two input indices times this is a selector that is one if H there is an a multiplication gate here and zero otherwise so if there

is a multiplication gate here from i z and i1 to O then it's just a multiplication of the values on the previous layer and there's a sum here because there is the same thing for addition Gates so imagine there is the same sum but with a selector for addition Gates and the sum of the two input values all right okay now that I have this uh expression I I know that uh proving the value to the right is just a sum check I have the sum of some kind of polinomial after the summation and this

polinomial is basically a description of the AR atic circuit and this is the previous layer and this is LR polinomial and for the sum check want to be able to query each polinomial at a random point and we can do this for a more because the verif should be able to know that this is simple and when in the Su check we actually need to sample WL the previous layer we get stuck but actually it's this is the reduction to compute the Su check we need to to compute the query to the previous layer so we started with trying to compute a query to layer l+ one and

got we need to compute the query for for l so we repeat this reduction until we reduce query to the to the last layer which has no variables to the first layer and then we use our polinomial commitment scheme all right okay so this is a an application of the gkr for the grand product and iing grand grand product is just being able to compute the multiplication of the entire column H so the arithmetic circuit we're going to choose here is simple binary tree every two uh aligned values are going to into a multiplication gate and

have one output so basically this a binary tree compet the multiplication of everything in this column and for every reduction uh from a layer to the previous layer I need to do a sum check this size of the sum check here is one previous two 3 four five and until get to the very first layer which is log n so H the total number of rounds is 1 plus 2 plus BL plus log n which is log squ n so this is the number of rounds we have for the gkr the degrees are degree two and in this case we have an even simpler

formula for for the sum check at each layer we can see that the layer it's l + one is the sum over all indices B here over the hyper Cube and each value is just a multiplication of two values is above at the value at B is multiplication of the input the previous layer at B 0 time B1 so it's like a really simple simple formula that we can use for the gkr for the grand product all right so what's nice here is is that we actually save we don't need the

cumulative product column at all like we had at the beginning H this saves the need for an extension field poal commitment saves a lot of commitment pressure we do have extra rounds need to pay attention for that and this requires a multi-linear pol polinomial commitment scheme because like we said before at the end we reduce everything to query to P of of X at multi-linear point so yeah this is a caveat but we'll address it later last point okay now uh we would like to do the same thing for the other lookup argument the log up okay so here here start the the

thing that me and did other stuff we didn't do anything this is just an observation we had pretty simple one just add might add and basically we want to do the same thing for the log up now a log up is not product of a column instead it's a sum of reciprocal of The Columns of one over the value and gkr can't really do divisions because at each step he we need to get this polinomial and multiplication is polinomial addition is polinomial but division is not so the observation here is to use projective coordinates which just means

look at the representation of the number as a fraction and keep this and never do the division itself so like in school we have If We Had A over B plus C over D it equals a D+ BC over BD so we just compute the numerator and denominator and don't do the division ever or until the end and now we have this kind of circuit that the input to the circuit has the numerators and denominators of the input and and the binary tree takes two pairs and outputs one pair of numerator denominator and now this is this is a a

gkr problem H because we don't have divisions everything is multiplication and addition right these are the for [Music] formulas H yeah basically you can see here imagine that we have a lot of pairs numerator denominator for the input layer so the next layer has have as many values the denominator is just the multiplication of the previous denominators as you can see above the numerator is kind of a a a product of the numerator and the other denominator and the other numerator and this

denominator so yeah it's we have a bit more multiplication than had we had at the previous example at the Grand product and also have more values twice as many values but we can still do it um yeah here I present this as if it was two uh different pooms n n and D for like different layers you can do it like that you can also H batch batch them together or maybe represent the layer as interl values

all of these are applicable and these are the formula formulas we get for the sum checks all right okay we get here 2 N degree to two gates instead of just n because I have numerator and denominator it's a bit more expensive twice the gates three times the multiplications and again this requires a multi-linear polom commitment scheme okay okay so this was the log up gkr I don't have a lot of time maybe I'll through it but this is a way to compute the multilinear poal commitment

scheme in a univariate case h yeah g is great requires multilinear Pol commitment there are known constructions to prove a a multilinear commitment over univariant and this is just another one it plays well if you're doing a lot of Lookout cups and universe STS so H how does this look like uh okay H the idea is that I can look at a column okay look at it's a column in two ways imagine this is a a polinomial these are also the evaluations of it as a univariant polinomial but I can also

think about it as a evaluations of another multi-linear Pol on the hyper Cube there is this a a duality and I can try to evaluate uh the value of this multilinear polinomial with the trick we saw before this is the trick up here that every multilinear polinomial at R can be computed as a sum of its interplant using the lran pooms it's the sum of its values times the polinomial and we can do the sum over the

univariant Starks with a just cumulative sum or just a sum um but the thing we are missing here is the interpolant uh column in the multilinear case it was easy it was aingle expression but when we actually do it in univariant Star this expression two bits of I is hard because H the x is a univariant point it's not multi linear point so how we do it by introducing a new column which is the um lrange

polinomial evaluated at the random query r h and we can see that it has a a nice structure and we can use a a very low number of constraint to just make sure it's correct H for example if you look at an even an odd Row the ratio is just r0 to r 1 minus r0 and we can say things about row 0 and two for the next bit so we can create these log and constraints to make sure that the uh this column is correct With Your gran pooms and then we can do

a a cumulative sum or ER column or just the multiplication of the GR in the pooms so we can bch multiple a lot of a columns that we want to sample each one at a point and do all of these with just two extra columns um yeah so yeah it's true that these are two extension field columns but we do it them for all the lookups and all the all the stocks just need to so let's say we have I don't know 20 lookups instead of adding extension field for every lookup

we just add two columns all right I I'm out of time I guess so no questions yeah [Applause]