DappCon 2023: Improving The zkEVM Prover Performance - Jordi Baylina

Transcript

well hello everybody uh I'm Jina I'm the technical lead at polygon zkm for you that you don't know polygon ckvm is mainly a layer two uh Roll Up is compatible fully equivalent with ethereum so you can have a solidity you deploy a smart contract you use just hat you use EXA exactly the same tooling instead of deploying to ethereum you can or polygon you can deploy it to the ckvm and everything should work exactly the same the only thing is it should be cheaper and faster throughput okay before start before getting deep a little bit to the content that that I want to talk about just want to give you a bit of the rad map of what we are

doing right now in the polygon ZN team main we're working in in in different fronts here um we have uh for example the force transactions this is for sensor ship resistance we want to enable that as soon as possible we're working really hard on that uh very soon you will hear some news from sbak bounties uh for this is um I mean from the security perspective it's a little bit risky because this opens a lot of uh Vector attacks and and we want to be very sure on that but we are working hard on that direction there is also others work other other types of work a lot of them related to optimization optimizations optimizations on the pro that we will talk later but also optimizations in the client side uh uh and so on then there is U the biggest

bottleneck right now in the rollups in general and especially in the Z well in the Z rollups too not an exception is a data availability so here uh we're also working a lot in the four in the EIP 4844 to integrate that uh when it's available this will give uh 10x at least in capacity in ethereum that we'll see if this is equivalent to 10x in in cost too and we're also working in the compression so that the data uh we expect to have a compression rate of 67x that's going to be on top of this 10x so we expect that in the few the upcoming month uh uh we probably will have an increase of the throughput or reduction of the price if you want more or less of

about 50 60 70 x in the upcoming year so that's an an important Improvement that we will see in the upcoming in the upcoming months okay but let's let me explain that's what I wanted to explain especially in this in this uh talk it's about the I want to talk about the the new proving system that we are working on okay so if we see the the current Pro which is quite efficient it's a monolithic proof it's a proof that it takes it can more or less uh approve a 10 million gas uh uh block mean 3 million gas of execution and it takes about 1 minute and a half

to minutes depending on the in a in a huge server in a server in 128 cores with half terab of memory it's a huge server it takes about this one 1 minute and a half okay but the the problem of this proof one of the one of the problems that is is that it's a monolitic structure okay and we have the number of operations that that we can put in this um proof is limited for example the num the number of arithmetic operations is limited the number of cets is limited even the number of execution so the the complexity of the transactions is limited I mean it's it's it's a uh bone a bone there so system is an an L2 uh mainly so and just to be this is not really exactly

the same on ethereum I mean normal users should not see a problem if they are not doing extrange things but if you for example do a a loop of cets or a loop of just arithmetic operations and you extend these places then this transaction will be executed but will be considered like a no operation transaction so that's why we always we are always able to prove everything but maybe there are some transactions very very stct transactions that go out of this counters and then and this a little bit of difference between What's um ethereum one what's ethereum and and what's a a layer two uh Layer Two roll up so in order to solve that we are changing a little bit the architecture of the proof and instead of having a single proof a monolitic proof the idea

is that here we are using a lot of recursion so we are taking advantage of recursion to uh uh so instead of having a single proof we have like different sub proofs maybe one proof of binary one proof arithmetics one proof of main on the main stain machine and then we aggregate all this proof in a single proof actually it's not really independent proof we call it parallel proof because these proof are generated at at at the same time okay but uh we have like a one level of recursion where we can uh Aggregate and the cool thing of this is that for example we can um I mean if we are using a lot lot of arithmetic operations we can put a big proof uh with big arithmetic or if you are using not many arithmetic operations we can have a smaller proof a proof that

can be computed much uh much faster okay so we optimize much better the resources that we have in the monolitic in the monolitic proof uh in the monolitic proof uh sometimes I mean if if there are if the transactions don't use many cets there is some place there is a lot of a big part of the proof that we are paying anyway that's maybe unused okay so with this system we can we can optimize much better the resources that we are using and not only that we can also do uh for example if we have a lot of binary um operations one thing that we can do is we can generate as many binary sub proofs and then aggregate them all together and in this subproof aggregate them together so this allows

us so this structure allows us to do as many um operations as as many operations that we need in order to solve the the the in order in in order to execute in order to prove any transaction no matter uh how complex or how difficult is okay and this has a a lot a lot of a lot of advantages regarding this okay so this is the the the the advantages of the proof but um but in order to do that here is when we see the the this structure um the problem here is that because there are different machines

that there are different sub proofs and they even have different sizes they this how we connect one each other in a monolitic proof is relatively easy because we do a normal plup a normal plup structure that with the two polinomial of the same degree but when with this B Cs I mean we have and and and and what I want to explain now is a little bit what's this technique because this is very powerful and this can be used for doing this huge proof and proof that can proof uh uh they can you can prove as whatever you want I mean you can extend this proof with the resources that you you need to compute any proof okay so first of all uh I'm going to start now a little bit the technical discussion on

how we are doing that uh first of all I want to do a little bit remaining of uh what a polinomial commitment is all these proofs are based on uh polinomial commitments the idea so the proof idea is that we are um setting up a set of Pol nomials pols uh for people don't know is POL is a normal polinomial instead of working with a normal real numbers we are working with finite field uh numbers but they follow exactly the same polinomial and the idea here is when we are saying a polinomial mainly you can understand this as a as a an Ari of points for example if we do a line a line is defined with two two evaluations there two pointsan if you do a degree of uh polinomial of degree uh 1,000 that

means that it's defined with 1,000 with 1,000 points so it's the same that saying that committing to an array of values okay so the idea is that we commit to a set of polinomial okay uh set of the verifier sends just a random number and then we just do an opening so we prove that those polinomial that we committed when you open a certain point is given a value okay and then the verifier can check the polinomial equations but they check just in a single point and if this number is and the field is big enough and this number is big enough then the the the you you can be sure that these polinomial are that this so that this polinomial are okay and that follows these uh

constraints these identities okay these polinomial the cool thing of these polinomial is that you can have relationship between one row and the next row so this these relationships of polinomial mainly what they do is the straight transition so you can do a state transitions so you can generate polinomial these polinomial can be a state transitions if you have a state transitions you have processors if you have processors you can execute programs if you can execute programs you can prove whatever you want okay there's a little bit the full stack of a of a pro Al together so that's little bit the the the important part okay so here for example you see a polinomial that the next step so the next value of a polinomial should be for example the the the the the previous value okay well this is a mistake here okay so um how we

do one of the things here is that when we have two polinomial one of the important parties because we want to connect like two State machines we want to uh do a kind of a we want to do a a permutation check okay so permutation check what means so I have two polinomial and I want to check meing the polinomial F and the polinomial T and I want to prove that the polinomial f is evaluations in the polinomial f are exactly the same that the Pol the devaluations in in in the polinomial T but uh with different with a different permutation I mean it's it's a different different order but I want to prove that I don't it can be any order but are actually uh the same the same the same numbers W 's this is the where you

evaluate the polinomial it can be any number in general we are taking what is called root of unit but these are different numbers uh just random I mean it's kind of a they are not random but there are specific numbers in there so this is the evaluations this polinomial can be identified with this evaluations the polinomial can get defined this evaluation and then the question is how we prove how we can prove that these polinomial one is a permutation to the other okay so the the main here the the the the main so how would it work well it it's a two steps so it's actually well it's actually two steps uh uh Pro so in the first we commit to the F and polinomial so ones that we want to check

the permutation we uh the verifier sends vaa here you see that's an interactive protocol okay all these interactive protocols they can be converted to a non-interactive it's a FIA Shamir uh method and the idea is that this beta can be the just the hash of what s before okay and then because hash is reversible then you cannot you cannot detect better so you can convert everything to a to a normal uh normal proof and non- interactive proof but it's a good way to see it this way okay so we we come to the polinomial we get this random beta here we the the Prov generates a new polinomial is a polom new a z polinomial it com to the Z polinomial and then the idea is we do the same once we have these three

polinomial committed then we do a normal opening so the same that we did before uh the verifier sense random number here we open all these polinomial at the different places and then we check some equations okay so going back actually what's this Z polinomial what this Z polinomial meain is what we say is is the grand product okay so the idea is um uh what we do is in the first one we put you see here is uh three is the F so so you see the F uh we we we do add f plus beta and and and and in the in the in the this in the numerator and the in the denominator we put the t plus beta okay in the next step actually we accumulate

we do a grand product we take the the previous one and we multiply in the numerator the F and in denominator the T but uh with a with a with a beta with added with added beta okay so you see uh once we do all the steps you see that the the 3 plus beta 2 plus beta four plus beta 1 plus beta all of them are going to are going to pair if you see here in the last the last row here you all of them are going to appear in the numerator okay but because I'm adding also the T these are going to appear in the denom in the denominator but if it's a if it's a permutation everything that's numerator should be the denominator maybe in different order but everything should be in the nominator

denominator so the result must be this to one okay so how I Express that in uh polinomial equations well in the first the first equation here it just says uh just says that uh um uh the last line must be one L4 is another polinomial that's zero everywhere except the last line so L4 if it's in the first three columns is zero so 0 times whatever is zero is going to follow whatever it happens but when L4 is one this is in the last line then zit must be one so in order this to be zero Z must be one okay so I'm for see that this is uh one okay and in the next and the next one here what I'm saying is z prime prime is the next row so the the next uh the the next

value must be the current value times well the next Value Plus beta the next Value Plus plus it okay so this is just the two equations that I'm checking okay so as we saw before the full protocol is just do the commit send the this beta random I commit to zit and then I just do the openings which openings I do well I just need uh F Prime f w is f Prime is evoluation in one one later one point so in the next uh in The Next Step uh T Prime Z Prime and Z so we have this openings I'm uh saying the opening is this this point is this I proof so this this openings goes with a proof so I'm sure that these

openings are this and if uh these evaluations matches this uh these equations that means that uh all all the qus matches the polinomial and if this happens means that this polinomial the only way for this to happen is that this polinomial one is permutation on the other okay so this is the basic this is the basic permutation check that is very much how how it works okay here there is a new and need something is like here what we are doing you see is you see the trick here is that in the numerator we are adding the F so we adding the two polinomial in the numerator we're adding one polinomial in numerator we are subtracting one polinomial well there is a way that instead of multiplying in the numerator and denominator I can do is

well instead of multiplying I'm just adding so I'm adding instead of this will be I'm adding the the F in the numerator and uh subtracting then the the the the the the the T polinomial okay so you see here okay but the the difference here of course I cannot put it in the I need to do this um inverse for the protocol to work but the cool thing here is that no this this this way is additive it's not a grand product it would be more a grand sum okay so I can do this things for adding the idea is exactly the same the thing is that of course the last number is not going to be one it's going to be zero because at the end everything needs to add up sum up to to to zero so this this this this

equation are also change but Thea is exactly this is exactly the same this is what we call a look up okay and this is kind of a new new thing okay what uh for these permutations if we sophisticate a little bit we are we are uh doing a permutation until now we do a permutation of two polinomial but we can do also the same with various polinomial you have three po three polinomial uh instead of having F I have F1 F2 F3 and I have uh T1 T2 T3 I just can um I can do exactly so I can like the idea is to do the same but instead of putting F Prime I can just do a random linear combination Alpha this is a um a challenge number set instead of like

beta mean this is like another challenge sent by the verifier and I can add a l i can do a linear combination here of uh F and the protocol works exactly the same so I'm adding this part this F I want this F need to be permutation check of T okay so I can do this adding this is a a linear equation so I can prove exactly the same way that we did before okay um this is yeah another another important interesting thing right now we have check what what we did until now is a

permutation check okay so we are checking that one polinomial is exactly the same that the other but sometimes what I want to do is check that it's a an inclusion so that whatever is in here for example here is 3221 it's included in it's included in 1 to 3 four okay so this for example would be a kind of a range check somehow okay so 3 to to one is so two is two times but I want this to also happen Okay so one thing that I can do is I can add this extra column here we call it C and that says how many times this value appears there so if if I saying this is one this is two this is one I can put this I can just change the questions instead of adding this one time I adding c times okay so that's the

same that multiplying by c times and the and this the same so here I just converted one thing that's a normal permutation check to a normal plup so this uh the fact that this uh adding this allows us to do this um uh plaps very very easily if we do it in the multiplication this C in the set of V multiplication would be an exponent and then exponent in the polinomial this is much more difficult to to prove but because we have this structure that we can do this with adding with this uh uh Grand Zoom way then doing per mutation doing um uh um plaps then it's much much much easier okay so we have this structure is we adding here and here the we are adding n times c times the thing

here so we have the uh with this we solve what we C the the plaps okay between two pols okay okay what happened when I have right now F and T are the same are the same uh are in the same proof proof and then this is relatively easy because I can do this uh polinomial checks uh so I can do this this this this polinomial identities when the polinomial are the same degree are in the same proof okay but what happen when I have for example the f is in one sub proofs and uh uh the t's are in another subproof maybe with different uh degree I mean maybe this is degree four this is degree eight okay so what I can do here is okay I have a

state machine here I can have a state machine that's doing exactly the same but just adding up so I'm just adding the fime polinomial so at the end it's not going to be zero this is going to give some number okay and in the other side I just can do the same but I'm just substracting so when I'm substracting I'm subtracting this uh Su here so I have one output here one output here so I have subproof two subproof that have one output and one output so if this output I can put it as a public input of as a public output of this proofs then what I can do is in the in the bigger proof I can check that this number is exactly the same or if you want that these numbers adds uh Su UPS uh uh zero

okay so the idea of this sum is that I can have this call it uh this column I mean I I can compute this sum in one side I can compute the the other sum the substraction in the other side and then in the in the in the proof that Aggregates the two proofs I can check that this public uh output is exactly the same so this allows us to do permutation checks or PL ups between different sub proofs okay but this is um even more this is even more powerful okay so imagine that I have different sub proofs okay what I can do is I can have this in each of the subproof I can have this U zit column we can call it the bus column it's a bus where the each

proof is adding or substracting things I mean if I for example if in the main machine I'm assuming that one multiplication is uh is valid I'm assuming that in the same machine I'm adding that to the boss and in the Artic State machine that I'm proving so something that in the main State machine was assuming but needs to be proved somewhere when in the arithmetic State machine they can uh prove that this arithmetic is valid so they do the actual multiplication they prove that's valid and what they do is they subtract that in the Boost okay and this can be in a different proof itself okay so and this and and I can also add uh so I can also add U uh I mean any function I mean binary operation maybe it's a different

thing that I'm adding to the bus um um uh KET I'm adding that to the bus okay or you want a you want a um Range check so whatever I I'm doing I can add to the bus or subract it to the Boost when I provide or when I require okay and I just need one column where I add all these things okay and at the end I'm just taking all the bosses and I'm adding and just checking that the addition is zero okay so yeah this is the idea okay for example this is the in the main estate machine I can have the the here would be for example the the the arithmetic State machine I'm assuming that a times B is C so I'm adding here A B and C this is a one this one is the operation uh one means the

operation arithmetic for example and two means the operation store okay so I'm adding to the Boost an arithmetic operation so one plus one alpha so this is this is a selector of what I'm adding to the boss because it's Alpha it's going to be random Somehow Here you see that they can have even different size of parameters okay I'm adding this because I'm assuming and then for example in the arithmetic State machine I'm substracting because here I'm proving that a * B is C and in the store machine I'm just uh proving that the the store of A and B is is is correct okay but you can extend that I mean the fullprof has like a lot of assumptions and uh you're adding a lot a lot of things to the bus subtracting a lot of things to the bus you can add uh a lot

of things to the bus at the same time because at the end you are adding and you you you this is this is very I mean this is very powerful okay another thing is that you can do is uh assuming these things to the bus of course you can have different state machines adding and uh subtracting things to the BS but you can also have what we call it public tables also the verifier because the verifier they need to compute the transcript somehow say they have Alpha and beta so they can um so they can also add for example uh include some transactions for example he can the verifier can um uh write things in memory okay and if a Brite is a is an instruction they can compute the the addition of all the bright so they

compute a value and then this can be like a an input to the circuit and this input is added to the sums of all the bosses and this is what needs to be zero so you can delegate part of this uh uh uh operations to the to the verifier okay so this is for example it's a way to save uh a lot of public inputs in general what we do is we hash it and we hash it inside but with this technique the the verifier can just do this linear combination I mean these multiplications I me these additions these special additions and then just uh uh pass it as a public input and and check inside the verifier that's in in here okay so this is another another trick

so with these techniques you see that first we are saving a lot we are saving a lot of uh a lot of uh polinomial in the proof so we expect a huge Improvement just because we are reducing like uh oneir uh about one3 of the polinomial okay so this is going to be a good improve but the most important part well the most important part here is that we we expect a very a lot of sales because we uh we don't need to have U State Machines of exactly the same size sides we can grow that we can have this Dynamic size that we can grow and so we are just paying the pro what we are really what we are really using and it's another Advantage is that the design of

these estate machines um they not don't need to be constrained by these sides okay you can do for example State machines that are very white I mean that the for example you can do a ketak in one line okay but with a lot of polinomial very horizontal okay uh or you can do uh KET with I mean with a very few polinomial but lots of lots of rows okay so right now we we cannot we don't have we we are a little bit constrained because at the end we want to uh at the end what we have is a fixed number but with this system with a variable degree you can do whatever you want uh and you have this flexibility so this will allow also to redesign some of the pieces uh some of the pieces uh in a

uh that's going to be much much more optimal itself so all this winning we expect that we haven't seen the numbers we need to check but at least a 3X in the improvements of the pr for sure are going to come okay um for this New Concept the idea we are expanding pill uh to pill two and we are uh pill two will have a a lot of new things the most important thing is that we support this bad cup so we will be able to design this we call it Hardware I mean it's this polinomial but it's this low layer this arithmetization uh with2 there is a lot of new um uh I mean a lot of new things that are added in in in P2 like I mean it's more functional Library it's a lot of

for example of the constants that right now are site scripts they're going to be embedded inside the the pill2 so it's going to be even easier to to audit and to verify uh you will be able also to also access different rows I mean there is a lot of new you will you will Define right now the pill one is very I mean the constraints that so what you can do permutation checks you can do uh PL UPS the things that you can do are very specific with P to IDE is that you can extend I mean you can add new protocols and all these uh I mean the permutation checks they are um programmed in pill two itself so these a more flexible and more it's the I mean the language is easier uh but it's more it's more flexible I mean you can write pill one

in pill two somehow okay so this is going to be very flexible and all at the end the idea is uh the idea is to be able to build a kind of a library of this uh components we call it Hardware components but actually it's not Hardware it's a polinomial these are proof so proofs these are polinomial identities somehow okay so the idea is that we can have a library of ketak arithmetic maybe a patrici tri or smts whatever libraries that are very specific okay you can have processors processors here can be ZK specific processors or can be for example a r r five or some uh of the things of these processors uh and the idea is that at the end you will

be able to run uh a code ideally you can have for example uh a code written in in in in rust or in golang and then you can compile for these processors uh if you just have a processor this is not going to be optimal uh but if you have some of the pieces like an like Artic ex machine the kcks that uh or some specific things that the program will need maybe in the program site they will they will be as a normal uh software library but then they will end up using this like specific hardware and this specific piece that they can plug all to plug all together so we will be able to generate uh proofs uh faster and maybe not using a Special Assembly maybe using even high level

language okay so this is the the main goal of this uh uh P2 and uh what we are building uh as P to and yeah that's very much it uh just to for you the people that don't know about the the about that don't know about the zkm just uh uh give a ask them to to try it uh Saturday I think we have a polygon connect uh somewhere I'm going to be there if anybody will have dopes or want to talk about uh the the polygon what we're doing in polygon ckvm I'm fully available here on on Saturday so that's my presentation thank you not sure if there is

questions does anyone have any question that they would like to ask I'm sure you all have a math question or a lot of numbers it can be they can be no technical if you want no oh here sorry thank you for the presentation definitely not a math related question but um just curious from your perspective um these optimizations um what kind of new possibilities does it unlock in terms of like new new business models or more like decentralization or is it part of like a bigger road map that would

uh yeah allow for new innovation on top of polygon yeah so these optimizations uh I mean they will for first of all they will allow they will allow uh first is they will allow to do what we call it type one uh type one uh rollups that means that rollups that are closer to ethereum okay so without I mean we will be able to prove exact the same the exactly the same block that happened in ethereum okay uh so we are getting much closer to that okay this flexibility of uh having a proof that's variable sides I mean that you can prove whatever you want by extending okay this is one thing that's uh uh important the second is optimization is uh I mean building these

proofs you require it requires a lot of Hardware computation okay with this we are getting better I mean the idea is to to get closer to to to to to to prove uh to prove things okay the other thing that I mentioned a little bit here the low is like uh the the holy gra somehow would be that uh you just take a a client an ethereum client I mean you take Aron or you take U re or or G and and you just you don't need to audit that the idea is that you can take that code and then compile but uh but compil for the the ZK processor so you will be able to prove whatever you want just by recompiling the the the final thing okay right now this is not possible because

it's very ineffective but when you build this when you put this um specific components that do some specific Parts very efficiently then you remove that from the main processor and then this is what will make it uh what we make imposs from the decentralization perspective I mean this is a different this is a different topic but uh what's important here is in the force transactions uh when the force transactions the the important part of the force transactions is that in in in in rollup uh if you have a centralized sequencer uh this centralized sequencer can censor you I mean they can say okay this transaction uh don't like it so uh I'm not going to include that transaction so and then may if you don't do anything else then your

your funds could be a stock in inside the inside the inside the r up okay so there is a mechanism that's called Force transactions that the idea is if I'm locking you I mean if I'm not forcing transaction if I'm not if I'm not sending sending your transaction because I'm censoring you you can take this L2 transaction and send it to L1 okay and then in the sequencer I'm forced to include that transaction actually you will be able the way not I'm forced you will be able at some point to take that transaction if I don't include it you will be able to include and to sequence that transaction in the chain so these transactions you have the warrantee that this transaction is is going to happen whatever happen so there is no way for sensorship resistance it's not actually it's not really true because uh it's a

sensorship resistant in the sense that I cannot lock you but effectively I can't kick you out of the network okay because I'm not censoring you probably you will you will do is an exit uh that's why it's important the centralite sequencers okay but just the the thing is because we want to build uh systems that are Universal okay that anybody can use it here uh the centralized sequencer can decide uh somehow um who can use the system or not okay so that's why it's not perfect uh centralite sequencers are not perfect but it's probably the word centralite sequencer is not is not uh the best words I mean it's it's very good I mean means it's a sensorship it's a system with sensorship resistance that works well that that the sequencer

cannot do uh anything but uh decide who can be in the network uh uh they can take you out in the network okay uh well I mean there a lot of things but this is uh it's different topics but this is the the main work is for working in in in in that direction okay so unfortunately we don't have more time for questions but I'm sure you can ask him outside and more than happy to answer the question so big Applause for Jordy