ZK7: Verifying STARKs with SNARKs - Jordi Baylina – Polygon Hermez

Transcript

[Music] and now we're going to hear from jordy talking about verifying starks with snarks [Applause] hello everybody sorry for my boys the week is long i'm i'm george melina i'm the technical lead at polygon nermis well i'm what i want to explain now is i'm going to zoom in in one of specific piece that we are using in polygonermis

is verifying verifying a stark with a snark so just to to mark where we where we are is mainly if we see the approver the prover what we want to do mainly is taking a set of transactions ethereum transactions we are code compatible so this is our stereo transactions we are getting a state route and when we are proving that we have a new state route for this we generate a bunch of polynomials that's all those polynomials needs to fulfill specific uh identities a bunch of identities in the prover for example we have around 1 000 polynomials maybe a little less but surround that number

order of magnitudes and the well and constraints maybe twice as that it's just a lot of a lot of constraints and a lot of polynomials and well we have a synthetizer or if you want that actually takes these transactions and generates these generates i don't know if this work oh yeah good uh it generates this this this proofs uh so these polynomials this array of polynomials that will fill this this this okay what do we do with this well the first thing we do is we generate a proof and we generate a stark proof actually we are working with a small field small field uh elements so the star proof generation is uh

well it's quite fast to generate we are using a small blow up so we don't care as we will say because we have other things later we don't care about the size of the stark because later we want to at the end it's going to be a snark so what we care is in the full proof generation so that you don't have many constraints later on and so on so once we have this proof that maybe big but you know just a proof that has been computated quite quite fast then we can well we can have this optionally we can have this tree of proof so we can aggregate many many transactions or many blocks of transactions in a single proof and finally in the last step once we aggregate all this proof maybe with a

kind of a tree then in the last element we uh have a prover that proof uh this this start this stark proof and generates a snark as an r proof this is an r can be plonk or growth 16 at the end it's a normal r1cs circuit or long circuit just the standard plong here we're not even talking well we will talk a little bit about possibilities there okay but and what i'm going to focus in my presentation is mainly in this part of here so we scroll actually seen this how we generate this gros16 proof that we generate uh this so in order to understand that is okay what means verifying who

what means verifying a stark what are the computations what needs to do because all all these computations are the things that we need to put in a circuit actually we're using circum circum is going to be a circuit that you have as an input as an input private input it's going to be the it's going to be the the the proof the stark that comes from the low low low side of course it also will have the public input that hashes all the all the public inputs is just single we are working with a single public input it's going to come here and this is going to be like part of the verifier of the start so it's going to be one piece uh in there so

the if we if we just zoom in here what what what pieces what we have to do here well in the first in the first the first this is very common in in these polynomial commitments we have a transcript and we need to compute about this transcript we need to compute this randomness through this transcript this is this is quite easy but at the end when you knew this mainly hashing that's the main operations that we need to do here okay the second part is actually checking those identities we need we have a lot of polynomials we have probably an evaluation an evaluation of those polynomials at some specific point or points and then we check at that specific point and if the

random number if the random number is uh if a random number is uh okay then uh then that means for some math theory that you know for probability that this is going to be okay this is a little bit more tricky when you are talking when you are working with small field elements because you need to work with some extensions but the idea is exactly so the day is exactly the same so these are here we see that we have a lot of operations on that next step is we need to do queries actually a stark mainly is a it's a miracle tree of some localization of some evaluations so we need to do queries and queries are mainly hashes

here okay the other thing we need to do is uh calculate uh well we need to verify that these evaluations are right so we need to uh calculate the calculate the opening polynomials okay uh we need to do we need to do that for each query so uh if we have a lot of queries we'll have to do these evaluations of the of the of the of the opening of the opening polynomial many times and then we have the fry the fry we have uh when we go up upwards and downwards we have different queries also to the mercury so we have here a lot of hushing and we have also we need to do this

we need to check so the idea is that we need to do evaluations so the idea is we have a polynomial of degree n or the degree less than n we have endpoints and then we need to evaluate that a specific point and check that this match with the downside polynomial and we need to do that in each so recursively until you know the polynomial is going with a low degree until we are at the end and at the end the remaining polynomial will be to do maybe some check there so this is a structure of a verifier more or less and we have to put that in a circuit okay so how we do that in a way that's cheap that means with small constraints here the difference so in general with people that's designing

starks if they try to reduce the size of the size of the proof here what we are trying to do is trying to reduce actually is the number of constraints for the verifier side but also the the general the the proof generation so everything then what we are trying to minimize is the full process of the of the final proof computation time okay so what's a naive way well the easiest way is if we just generate the start with the same field we want to use bn128 because this is the the one that's easy to write growth 16 or plonk in ethereum right now i hope that some point b bls one

381 come it's available but this is what we have right now so it's 256 bits so we can work with these polynomials generate all the state machines with these 256 bit fields but then this is this is well this is expensive from the generation of the proof but uh it's more cheap in the it's it's straight forward the for of course uh for the for the for the hash functions you can also use uh uh some uh plonk uh some some uh circuits you know some zika hash functions like position in order to uh save constraints in the

in the in in the circuit but what happened if we have a mix you know in this case we have a mix of uh prime fields so we have uh we there are parts of this for example the hash functions we can still use position and we can store these freely uh circuit friendly or grow 16 friendly functions to build the the the stark so this is does not change but in the for the specific you know when we when we need to do for example we need to check the operations in the polynomials we need to work with these uh small small prime field here so so

how we do these cross prime cross prime multiplications what's the cost of doing a cross cross prime multiplications inside the circuit well actually what uh what but mainly you do is well we imagine that we want to do a multiplication so a times v mod pp is 64 bits number must be equals to r okay we can put exactly the same equation but in mod q so a times b here it can be some some some multiple of the prime number minus c this must be equal to zero this equation is okay but might be overflow because we are in a prime field so what we add is we have two range x mainly so we guarantee that c is less

than two to the 64 and r is less than two to the 64. we guarantee well then then we are done we have only have two solutions but we know that these solutions are small enough are only 64 bits and this is enough for what we for what we need okay and this is a total each range check is uh if it's 64 bits it's more or less it's 64 constraints here if you have a carries maybe it's a little bit more maybe it's 129 or 130 for the car is all together we are working sorry we are working with uh we are working with uh extension fields so actually uh well when you do an extension field you do

maybe six if you are doing an extension field for example of uh of two is uh maybe you need to do four multiplications if you're an extension three or an extension field of three maybe you need to do six nine six seven multiplications depending but let's out of the stitch so uh so um you need to well you need to do these uh different multiplications but you can actually do a trick and actually you can put this this equation a little bit more longer and you only need at the end you don't need that many uh you can pack them together so at the end you just need uh like three times if it's an extension three for example you just need three times this rain check so for

doing an extension field of 64 bits we just need less than 400 uh constraints okay so let's do some numbers here okay is it possible to build that well let's start with the first example imagine that what we want to be what we want to do is uh well for hash functions normal hash if we are doing hash of uh we are doing trees of 16 16 elements per per slot and the hash of actually is t17 so uh 16 inputs and you just hash with a single hash if this is impossed on is 612 constraints which is very low compared to uh say a shot of

256 which could be like 30 000 or something around that so it's a it's a good hash on that and uh yeah so if we have a query then a query of uh 2 to the 24 so this is our six six steps so this is going to be 300 so let's let's start with a simple example is what happened if we want to validate this just strike forward so we want to take uh directly one of those uh proof systems so one of the that are proving ebm transactions and we would just we just want to prove that directly uh just directly to the to the ethereum so you would we just

want to generate this growth 16 out of this well in this case we have uh around 1000 polynomials we have a blow up factor of 2 that means that we have to do a lot of queries in this case 128 queries the polynomial sister the polynomial size after blow up we take 2 to 24. this is just some example numbers so that you see where where we are just take it as a take it as a just as a reference as a rough numbers of where we are okay so number of constraints uh well if this is if we have 100 polynomials maybe it's 2 000 polynomials let's put two multiplications uh per constraint just as a

rough number okay so we have a total for well this is what we have so what would be the numbers okay was when then we need to go like a step by step and check uh what are the what are the the the numbers here okay the first step which is the transcript this is quite constant and it's just uh some some uh some hashes which is quite low and this is could be i put it it's gonna be below five five k just rough numbers it'd be this depends very much on the circuit if you have many interactions you need more primes and can depend but in this case it's quite low and quite insignificant uh in the full system um checking the polynomial constraints here

in this case we have a lot of these uh cross prime fields this is uh when you see a 300 390 where it is um the the 390 here this is the the cost of the multiplications so we have 2 000 constraints times two this is at the end is 1.6 uh one to six constraints okay uh you see here that uh we are using deep fry so we are we are only checking once this so we have single opening in the full system so we only need to check once this is one of the advantages of using the fry here so the next step and this is you see an end here so this in this case we need to do this for each

query the next step is we need to do the we need to check the the the the evaluation the we need to check that the the evaluations the openings are correct okay and we need to evaluate this opening this opening protocol there so in this case this is well it's quite important mainly because we have with this 128 here so this is about 5.3 million constraints which is quite quite a lot if you go to the different to the different steps calculate the opening uh polynomials uh and uh but no sorry this is the well well we need to do this this is the

the this is the this is the opening of all the all the all the points although all the of the of the valuation points so this is the 612 this is the hash the hash cost so this is in total 5.3 megahertz and the evaluation of the pollion the polynomials is 0.8 megahertz is 300 and this 390. okay so in this part so in this part here is what we need to do every time so this is the fry part in the fry part this is a six five four three two one this is because we are we are in each

one we are reducing 16 uh we divide by 16 so we are reducing four bits each time so this is what we need to do that uh four times this is uh uh this this this gives us 2.1 uh million constraints this is our hash functions these end queries are also hash functions for the upper polynomial the bottom polynomial uh on that side here we have an extra cost because here we if we we need 16 points we need to hash these 16 points all together and at the end here is the part that we need to do this cross cross prime field that's quite closely it's six me six million constraints as you can see these uh

these parts are important because these are the the ones that are cursed field and that one makes uh all together and in the last one of course the last polynomial if you go quite low this is insignificant maybe it's one constraint or or something like that or very few constraints so in total this is about 17 million constraints which is an important circuit actually with uh rapid snark this circuit it can take about 25 seconds in a 64 course machine to generate so it's doable but it's a little bit costly this is in gros16 if we go to to to plonk

then uh if you go to planck then of course we can do these wrenches in a in a custom gate these lows a little bit this can be lows you can lower a little bit the the the number of constraints but then the very fire uh in plum it's a little bit more expensive uh because you need to do some extra things in the in the very fire and the problem by itself is a little bit more expensive that gross 16. i know that the aztec people is improving it and getting very close to growth 16 but it's implant is a little bit more expensive and the other thing is that because the structure of plonk uh well the gates you cannot do some

optimizations that you can uh that you can do in r1 cs systems so you have more more more gates so you have an extra cost of the more gates uh here and also you have some limitations and because you need to uh in the plan you need to increase the degree like four times so here we are very much in the in the limit in the limit of the curve here with um 7.4 so that yeah yeah so if we are just get lost so yeah we were talking about blanc so

because we need you need to ex you need to go um when you need to you work with uh four times the degree of the polynomial this gets uh this gets worse in the curve and we are reaching we're reaching the limit of the corp here the it's uh this is this would be in the 32 million constraints the next power of two if we multiply by that four this is 128 million constraints which is 2 to 27 and the limit is uh and the limit is 2 to 28. that's a question there let's just i don't know it's i'm i'm fin i'm finishing i'm fin let me finish the other and then we do questions if yeah

okay so just to to finish i will put another example it's like what happened if uh instead of verifying this proof system we just verify this recursive uh star system so if we go back to the to the schema we verify um this um this this circuit this circuit is already a circuit that's verifying a stark this is much simple not verifying uh that verifying uh uh not verifying a zika abm so you have much less polynomials and here i put let's see here so just instead of 1000 polynomials i just put 100 polynomials instead of

well we have a blow up factor instead of two i put two to the four so we can only do in in this case we only need to do 16 queries um we can do it uh uh on that and uh just here um we keep the same size of the we keep the same size of the of the polynomial because there is a flow factor actually is one million steps so this should be more than enough to do uh to verify a stark and number of constraints we keep exactly the same rule that before maybe two times the number of polynomials and multiplications times two if we do exactly the same numbers and we do the computations then what we have is a

circuit that's uh below two million constraints and this is a circuit that uh can be generated this proof can be generated in less than two seconds in a 64 course uh machine so satan in other words is that this uh this uh last part of this verifying a stark in snark um if you compare to the total cost of generating the proof uh this is i'm not gonna say that's insignificant but at least is really really low and it's not the the bottleneck in the in the prover and no yes we can do the questions all right well thank you for

the talk maybe we'd give a hand all right so there was a question right here all right um thank you for a great talk jordy uh the question is you say the plonk is not particularly convenient because you have more constraints but did you actually consider using custom gates for plong because if all of the constraints you're doing are just hashing like all the way and you don't need to engineer definitely you know actually uh these all these at least these all these you can have custom constraints for the hash functions for sure and you can have also constant constraints for the range

checks the rank you can reduce instead if you do this multiplication well it doesn't work stop working stop working this well well if you saw the multiplication for each multiplication you had uh 64 for each range check you had 128 uh 128 constraints in the extension was 390 constraints you can avoid you can compare these 390 constraints with a single custom gate block up

range check on all that so in this you can reduce a lot uh the number of constraints we need to do the numbers and we need to see if this works the problem is that the the big limitation is not in the proving it's not it's not even approving it's more in the verifying the the verifying cost of plong is slightly more that uh growth 16. but of course splunk has a lot of advantages for example you have trusted setup which is a pain to run so i'm just taking this as glove 16 which is very straightforward and you don't need to do like any things and of course there is margin for improvement what i wanted to explain is a little bit what are the what are the pieces in there and just

show that this is something that's definitely possible and it's not expensive in the context in the context of verifying uh the kvm jordy i think your slides are working now by the way you there is something on there yeah yeah and this is this part here okay but also that you know the in the plonk you can put this you know you can put parts of the plonking but the problem also the problem is that the these custom gates if they have a if they increment the the degree of the polynomial you're also limited by the by the by the curve you in the in the bn you can only go to the 2 to the 28 and we are especially in the first circuit

we are very much we are very much in the limit if you multiply that by 8 we go above the 2 to the 28. of course you reduce in one side but then you increase because you don't have multiplications so we need to check but we are it's not clear so you need to do the work what's definitively possible is in the second circuit in the recursive uh part this can be for sure done in plank and this is probably how we are going to we are going to work on that direction you mentioned that one of the big motivations for using planck is that you can do these custom gates um if we could do a similar thing in grot 16 would that be useful or would it

be your long-term goal to move to something like planck because of the universal set up anyway i think it would be a very at this point very interesting but my feeling is my feeling is that plonk in the short run everything is going to run in plonk mainly because running a trusted trusses setup for a specific circuit is a pain for most applications so yes it's useful but i have doped that in the practical so that the practical people that's doing uh a snark application is gonna use google 16 because running a

trusted setup i run once and i don't want to run much more i think we don't have time i think unfortunately we don't have more time for questions but you're sticking around right folks can talk to you i'm a room okay very good thanks so much [Applause] [Music] [Applause]