zkEVM #05 - Devconnect AMS'22

[Music] uh hello everyone my name is yeah today i'd like to talk about the the proving course of vicky evm so it's it's actually like has two goals one is that you know there are there are two goals one is that to get you a better sense of uh like what's the approval cost so like you know because you know you can figure out you know because generating proof for the qm really suffers so you need to figure out what's the dominant computation model improver and theoretically like how many ffts and how many muscular modifications you need for generating this proof and then you can figure out you know how fast and how parallel your approval can really be and secondly they're talking about you know because you know like you know when you are writing custom case and look up arguments you know like what's happening in the back end then you will know like you know how to optimize this circuit layout so like whether you use more custom gates or more lookups you use a higher degree custom case or lower degree custom case but more with more like allocated internal sales and also like if you use a wider or shorter circuit but a thinner or taller circuit and lastly i just want to bring bring stuff some some discussion around like uh around this leak event like community efforts key um like uh some problems we met and some possible solutions uh so first like just assume that everyone expert has a k and z key um so just a quick overview like you got this already code you got the bad code and you you need to fill up this those witnesses in your tables and when you are writing up codes you need to write a lot of custom gates like whenever you add you need to constrain that it's the selector of add is open so each each selector each cell you write like different like you know whether it's zero or one to two constraint that is a selector and the last line like you know considering that there is only one opened and also like you need to do some like add specific constraints and you also do some context check and those stuff so those are the first kind of uh custom case you are adding to this zig em circuit and second kind of constraint you are adding is lookup arguments for example like there are some operands you are operating in this add up code for example you pop two and you push one so for each operand you need to look up in a ram table and there will be a separate ram circuit constraining that this ram table is cracked so that's basically like you know two ways like how you are writing writing writing a circuit one is customer relationships secondly look up arguments and so so the the question is that what's the cost of writing those constraints and what's happening in the backend and that's the point of this this topic so let's look at the record of adding a custom gate so for example like you want to constrain that the the cells within that region has some relationship you write some way five times maybe five times basis minus sub minus maybe a b6 equal to zero so why one is backhand you just you generate those polynomial relationships so like a1 is for the first column a2 is for the second column a3 for the third column and a2 is a2 omega s is means the second column but it's in the next rotation and it's not enough because you you only want to constrain that a certain position so what you do is that you have actual selector column and so like in your in your you know polynomial like you also need to multiply with a selector cylinder polynomial so basically when you are writing each custom gate you result in one polynomial identities and each of polynomial identities are polynomial with some rotations so basically dj is like how many classmates customer gates you have like in your circuit and so like for each cupcake you will result in one polynomial and let's look at the cause of adding a lookup so basically what you usually do like in when writing circuit is that you you have a tuple and each two point is actually some extraction to simplify or just write v5 vb5 and you look up this entry in some lookup tables like whether this entry belongs to that table or not so let's look at the what what kind of polynomials it's generating so basically like a traditional pillowcap or the local argument define relationship between two columns for example like a1 column belong to t1 p1 column so let's just firstly like understand this so i will give you a concrete example like firstly you fill up the first column with one two one two three one one two one two and then it belongs to the table like only have one two three so what you do like when you are proving for this argument is that firstly you need to sort the the so basically what i'm describing is the lookup using hello 2 it's different from blue cup so in pillow cup what you do is that you compare two to two vectors and you sort sort something and then you randomize the differences and you generate some some some constraints some polynomials so what what halo 2 is doing is that instead of concocting together so for each column it will generate some some some permutated columns for example it's just some sorting of your initial column for example your e1 after permute after some sorting like you get this a1 prime and these are the the new columns you generated and for the table you also need to like using some sorting algorithm to generate those those tables and those those new columns and you need to prove that those two generated columns actually permuted from previously uh like your input and output so what you do is that you have two two two checks one is that some like green check for four boundaries and you you start with one and second is some like you know you generate some running sum for for zx and it's a separate polynomial so if you don't understand too much about the the crypto side you just need to remember that for multiside check you need two polynomials and uh like after you're permuting this to to to column what you which what you still need to do is that this two-part permutated polynomial has this like you know membership relationship so what you do is that so so this is like new in hello too so what does it do is that firstly the check that all those two columns start with the same element so they all start start with one and then like you know for for the elements in a1 prime it's either equal to the previous value or it's equal to some new entries in this table so those are the two two two constraints you add like the first one is like you you multiply with some lagrange polynomial which means you it is constraining your starting point and second polynomial is that it this this this this new column whether it's equal to the previous value or it's equal to some entries in this in this table table value so so this is a bit more technical but you know like if you don't want to understand so much you just need to remember that if you want to prove that one column belongs to the other column it needs four polynomial constraints and so if you have dj cosmic gates so sorry i read some tables so there is like dt like lookup tables and then it will result in four dt like polynomial densities those four four times you know equations and now let's look at you know like because you you want to you want to oh so sorry more so because as i mentioned previously you need to permutate columns in the middle right so you need to also to commit to those two columns so you actually also have two two additional two dj like additional polynomials for for a prime x and t prime x is which is a permutated column for for the for input polynomial so let's look at because you know what we are looking at one writing lookup we just look up certain entries right so we need to only look up you know we if i belong to t1 so similarly you can write some some selectors there and open only open at this entry and then you still generate some new like inter internal like you know columns and then prove that this and this has this relationship so the only difference is that you generate a one prime in a different way because you are you are actually multiplying s column with a i column and so this like you know your polynomial becomes as x times ax and now like you know like after all like you know if you want to prove that some cell belong to a table you need those those constraints still like you know four times and uh even more flexible like you if you want to look up a two-point whether it belongs to some table or not you just use some linear combination and multiply all those stuff and you need a selector to open at a certain point and then you need those linear combinations and prove that whether they belong to to the polynomials combined from from those tables or not so it's still like four times you know larger than custom gates so that's the only thing like you need to care about and for this new because you know like you you need to generate new new permutated polynomials and and new new columns so you need like you know your new polynomial is actually some linear combination of your a1 a2 and a3 column so that's basically like you know the overhead for adding a lookup tables and like moreover you can write some expressions there and you just need to like you know combine your columns using those expressions so at the end of the day what you have is that you have a lot of polynomial identities that you need to prove like you know for each cascade it will result in one for each lookup argument it will result in four and then what you do is that you you need to commit to all different polynomials and open those polynomials at at a random point to prove that this relationship holds at all the column all the columns like so usually what you do is this is that you you you need to divide by some vanishing polynomial so the differential polynomial defines like you know which which show you you vanish and then like because you have so many polynomial densities and you can linear combine them together hx and this hx is actually super hard to compute and this is actually uh the biggest overhead for for for for the approver because you know i will give a concrete example like for com to compute hx you need to linear combine all those polynomial identities right so it's high degree because each custom gate maybe have maybe degree four or even higher so to compute the hx you need to do a lot of high degree polynomial computations and that's also a reason why you need fft over a different field because if you are doing fft like for for polynomial multiplication if you are just doing like for example like your input two polynomials are just in degree times in degree you so you will result in some 20 degree polynomial but if you are just doing doing f of t like you know size and f of t so what you do is that you result in endpoints which can't interpret to get your like degree 2 and polynomial so that's the reason why you need higher degree fft and larger set f of t because you need to coordinate with those high degree polynomial identities and then like after you get this you need to random that at a random point and uh to get all those evaluations for those polynomial identities you need to open each polynomial at a random point and then you run some open open multi-open argument for this part so like it's more technical but let's look at the workflow so there are like so many polynomial identities from your constraint system but so for for cosmegate each will introduce one for requirements it each will introduce actually three because you know uh the previously your input or your input polynomial so here i'm talking about new polynomials that you introduce so basically your input polynomial comes from some linear combination of your your columns so the polynomial actually comes from some linear combination of those you already have the column polynomials so that's for lookup arguments and for openness you need to commit to hx and this is a overall workflow so the plural need to commit to some polynomial the verifier need to generate some randomness and then like prover commit to those those lookup tables and those low polynomials and then like you know you calculate some hx and then finally you open hx now let's look at the proving cost to commit to ix and ax which is a the instance column and the advice column you need to do those two operations firstly because to get the the instance or advice polynomial what so basically what you get after filling up the witness table is that you get you get a table full of weakness and then like to get the polynomial you need some fft to interpret to get your polynomial and and so basically you need that your like how many of mi is the number of your instance problem and m a is your the number of your your device column so you need that number of fc and then you also need the similar number of of multi-examination to doing the kg commitment and also like for for doing for doing like lookup you also need that number of multi-resonation to commit to those intermediate like polynomials and then like when you're open you need to do polynomial evaluations on your chord point so that's a third dominant part like polynomial evaluations evaluating at some random queries and then when you are doing the the computing this hx you need you you need to compute like some some extended fft which is a larger size which is basically your row number times your your largest degree of custom gates and then you need the number of rfts and multiple initiations so basically you need those two to component those components that you're you're proving so there is fft and there is fft and fft is over a large large domain and you also need polynomial evaluations so here is a overall large like cost i will because i'm like you know like a time i just go real quickly so basically if you add one custom gate it will just add one term in your hx it doesn't introduce extra commitment because only if you you introduce new columns you need to commit to that and but for look up arguments you introduce actual commitment because you need those intermediate polynomials and the vanishing the various in different arguments so like some potential improvements to our circuit layout is that first you can reuse lookup across the the whole circuit because lookup really introduced a large overhead like because you can open like use one selector problem and also those are some potential like improvement like you know you can also some expensive copy circuit to outside because you don't want to do the all the constraints in the sim circuit and also like you can change the whole layout to some wider one like whether even the widest one i just say start air because you do some raw transitions and also like you can lower the degree to some extent so that it can lower your your your maximum degree of your custom case so that you can doing a smaller size fft and so this is like you know maybe you can you can also select each row to do some other circuits and uh so like finally just one quick mention like you know in our in our usb circuit another heavily used operation is lookups so basically in evm circuit you need to look up some column belong to some some other tables right some other cable are also constrained by some some other circuit for example this one so to look up such you know to build such relationships that several solutions one is that you can pad this table to exactly the same length of your input uh circuit so which and then you you do some lookup like whether this entry belong to that one and also you do some permutation because you know there there might be some like you know different order the or the other you know initial column might be different from this one and another way that you just put everything in the same circuit and you just directly reuse the same column and third way is that you do some cross circuit look up like you do some pure cup stuff because you know ultra plank or hilo 2 implementation naturally requires you to pad the two columns into the same one to do that argument but pure cup the initial one doesn't require you the input and output to be the same so maybe you can do some cross circuit lookup and add some feature to hello too because you know one advantage you can bring that you can run some lower degree custom gates over those tables because they have a smaller number of rows it's not only the lookup relationship but also like other constraints over this circuit can be at a smaller degree yeah so that's basically some optimizations and some print cost analysis and thanks for [Applause] [Music] you