zkEVM #02 - Devconnect AMS'22

[Music] i'm going to be also very quickly because i've been giving many presentations in the last so if you want an overview and generic but i think here the crowd everybody is quite familiar with the concept with sdk vm just easy just taking transactions the important thing is that we want these transactions to be ethereum compatible so this transaction should be able to be created for example with metamask or with any ethereum client so here you expect that the input to the circuit we are handling here is not a special transaction it's an ethereum transaction and this is the compatibility that we want here can be a deployment transaction uh an execution transaction normal transfer transaction so any valid tethering transaction should be valid also in the zka ebm that's the most important thing go from all the state to new state we need to refrigerate this state i think this is quite familiar for all of you okay so the way the project we are following is uh we're also creating these polynomials but the thing is that um within we can do it but in general we don't work that much with uh the concept of custom gates we work more in the concept of uh uh state state transitions like a normal like you have a clock so you have a state machines you have a registers and then you have a trace you have state machines we can also include because at the end we have polynomial polynomial identity language and we can have more things we can have circuits and together with uh state machines actually for example kecko is a specific circuit that we are implementing that way here is the the big map uh that we have we have a main processor you know it's a state machine that actually is a processor with registers with a program counter with a rom that is executing a program a specific program fixed program a program that cannot variate it's a specific program that you are executing and then we have a ram we have uh operations like arithmetics like binaries comparisons shifts and then we have this important we have a storage we are at this point we are not following the the patricia trees model we are having a sparse merkle tree with uh with a poseidon function uh naturally we are using the goldilocks small prime so this is quite is the most efficient for the for the storage that we are having as far as i know in the ibm specification itself does not it's not it's not stick to a specific format of the vm this should be quite transparent uh but we know that there are some some programs that uh that this uh relies on that maybe just to do some queries on the on the tree and so on but this is the probably the biggest concession that we are uh that we are doing and uh yeah and also the for example the the well let me let me just go a little bit for all this and just give you like the main idea how we are solving all that stuff if we start from from the ram the ram is the same concept that barry was explaining we are sorting the all the access by uh address and then by uh the step so instead of accessing to so the reads and writes i'll read some rights to a specific register so with a single permutation check we can we can verify all the we can verify all the memory um binary operations this includes ants or shores add soup uh most of the most of the opcodes uh uh less than greater than so all these things is doing with a single uh plug-up uh plug-up table by the byte and this is done in this state machine so you have an operation which operation you want to do and the result so with a block up then we just solve all most of the operations here for multiplications and even for example for elliptic curve operations and for more complex arithmetic we have a specific machine which is we call it arithmetic maybe we can explain it later how we are doing but the idea is that you can put an equation you can have a complex equation where you have a let's say a set of multiplica so an addition of many multiplications and we can solve that in just in 32 cycles and and with this we are implementing their you know basic arithmetic for multiplication and uh but we we are also adding there the basic operations for uh the ac dsa so maybe for the elliptic core operations so in the case of the cdsa here you wouldn't have a specific we don't have a specific uh machine for cdsa but we have this arithmetic where we solve the the biggest part and then in the main we do the main loop uh you know checking that the point is not zero and all that stuff we already have a state machine so we can do it with uh up codes in the uh with within the rom in the same program for verifying that um what else uh well storage as i mentioned it's a sparse mercury very optimal we have actually the the storage is like a supercessor it's a it's a processor that is very similar to this it has like it it already has it's uh it already has a rom uh it does not has a ram because it works in in registers but have specific registers it has specific uh instructions it has their own assembly so it's like a processor itself that actually what it sits off all these the complexity of the of the of the of the sparse mercury the sparse marker tree you need to you need to do extreme things you need to add nodes remove nodes so all this logic which is a little bit complex is inverting this subprogram on this uh storage we can also talk about that later but that's very optimal uh altogether and other things for example all the programs uh we are hashing them with uh so we're hashing them with uh for the execution purpose we're hashing them with uh the this poseidon too to go fast and retrieve them then fast the idea of the for the hashing we have these two state machines these two this is it's it's separated the padding with the actual function you know the actual function is cac f or the inner function of position and the other thing is the padding and and it looks a little bit like memory uh the idea is that you can have a hash and then you can read positions on that hash if i have a specific hash that's with a specific number then i can do a read of the position three of length so much and this must must match all together and with these operations we can in the main code we can verify all the programs uh we can for recovering the program for example we just need to check so in the in the in this cac padding we do the the padding but then with a single reads on this on this padding state machine we just execute the opcode in a very very very efficient efficient way one of the for example one of the difficult just some details but for example one of the things is that just to give you some numbers we are considering more or less the numbers that we are considering and this is just an average but the idea is that we have an average of 16 cycles so 16 micro codes if you want to call it that way per uh per a gas unit in ethereum this is an average there are objects that are less there are codes that are more but this is a little bit the numbers that we are that we are considering and with this approach we can implement everything at this point we don't have we don't have any anything in the ethereum machine that we don't know how to implement it even for example for example uh paintings which is one of the things that for example is quite difficult to implement we can do it so it's hard but that actually we can do it because we have this arithmetic this arithmetic state machine that's very powerful and so we can define here specific functions with specific fields that we want to manage and they are going to be also 32 so it's going to be a very concrete operation there and then we can do the program to calculate the painting which is going to take well some cycles in the main state machine and this is actually uh we do the numbers it's actually possible i'm not going to say that we are going to implement it maybe in the first first version that's definitively possible um create two well at the end is uh is exactly the same we are managing the memory it's an op code that's actually implementing if we see let's see just here is some snippet of the assembly how it looks like for example in the left side we can see the uh how we parse the transactions with rlp okay so actually we are getting the first byte of therapy we are um of course we are hashing uh we are hashing all them together so that it match depending on the number of rlp as well we read more bytes or or we read the next whites so we are actually all doing all this parsing storing that on memory we have memory each membranes and we are processing all the transactions the other thing is well here in the right side you can see for example some examples do not take it as a it's just an example but this is for example uh one of the different opcodes at the end is a subroutine that you are uh that you are implementing and here you can implement any logic you know we can do checks in the stack we can do uh gas additions and all that all the tricky things in ethereum they are encoded in a in an assembly which is much easy to implement that with a specific uh gate also the quantity of gates that we are implementing that can the quantity of uh polynomials is big but it's not that much where our heart limit is uh one i want to be under 1000 polynomials we probably around 700 800 but that's the the thing there are small polynomials let me just go a little bit in the just this is how we do block apps within tables so all the basic polynomials so we have the synthetizer the synthetics generate this set of polynomials these polynomials are small field polynomials with these small field polynomials we generate a stark start generation in this small field is really fast and then on top of that we have you know a set of recursive recursive steps in order to first uh aggregate many uh aggregate many op codes some many blocks or many sub blocks uh of these but there is another thing that's important you know and yes dn is reduce the complexity of the proof so that at the end we are verifying so the last stark is verified with a growth 16 circuit or growth 16 or plonk circuit so that's very cheap to verify at the end in the main in the mainstream machine i'm done two minutes well mainly that's what more or less what i wanted to say uh here we are open we are open to a new discussion and if anything we just ask i think they just cover a little bit all the overview questions yeah well actually we are doing the two things at the same time so we are in uh importing the bites and we need in some way to accumulate in a hush and at the same time parsing and we are doing that in in in the scene yeah this hash is just uh we checked that yeah exactly so yeah that's but that's that's just a program we do it this way because it's more optimal we're already having the register so we can save some clocks but we could do it separately we can put it in memory and then do the hashing later my other question so like the main difference between like our two approaches are that like on your approach you separate things out into separate circuits more and that brings like a little bit more work to the aggregator but otherwise we're pretty similar yes here is um yeah the probably this is uh yeah this is probably one of the things we don't we probably have more uh polynomials uh we don't need to deal with these selectors stuff and uh the idea is that if we recycle polynomials or not this is the difference between a little bit the main difference between hollow two and the project we're following we are uh so we cannot put like millions of polynomials but we can put maybe one order of magnitude more number of polynomials and avoiding the complexity of having to uh wrote and you know dealing with these selectors and and trying to put probably there is a an automatic way to to join it but uh because we have this uh proving system uh uh on the top of starks which is generating these polynomial commitments is really fast and negating them is really fast we don't care uh that much and uh uh and it's much much more easy to do a specific state machine you know you do an animatic expression machine you can it's one person can do an arithmetic state machine and you have inputs outputs and it's very clear and you don't have to you don't need to worry about how it's going to be fitted uh somewhere else and how it's going to be matched with other things so this splits a lot the operations and we don't have one [Music] custom gate for each opcode we have like different state machines and then we are implementing each so the custom gate is a set of op codes if you want and and this is doing this is maybe the big difference yeah that's here it's i'm not saying one is better than the other is it's just a different approach for us this is working very well it allows us modularity uh very much uh at the number of state machines is limited well you you saw the you saw the uh we don't have much more than that maybe we have here i avoided some intermediate state machines but this is very much the state machines we have uh geordi's um there is maybe fewer circuits overall but then they're composed together to uh to basically emulate all clothes right at the under this boot right like there are micro offs that you use to anyway like to use my site is more or less correct maybe you can so what we do is and binary operations basically okay like we kind of feel like we're flexible now we can do some more outsourcing we're kind of investigating different kinds of complicated so my question is how many different micro cups do you have and do you have numbers for each evm of code how many micro of course does it take to run we don't have numbers yet but here can give you an idea of this is four five six seven maybe two of uh parsing this is normal opera normal operations are gonna be eight nine up codes all together in average i said before 16 this is the number maybe it's gonna make crop costs per gas points and an op code maybe a multiplication i think is two gas or three gas so we have like 32 margin of 32 micro up codes but just if we can do it with less we are going to do it with less it's just a number that's number is very much because we are working with polynomials of at this point we are working with polynomials to 2 to the 23 and we do a blow up in the in the stark of two because we want to go fast in this first layer uh we can go farther but two to the 23 this is a millions if you divided by 16 it gives you 500k it's so we need to block we can in this first version we can handle 400k in this case if instead of going to 23 um op codes so instead of going to 223 polynomials we go to 2 to the 27 then you just multiply okay all right we gotta stop [Music] you