ZK Whiteboard Sessions – Module Ten: zkEVM with Jordi Baylina

Transcript

foreign [Music] I'm bobbin and we're here today recording another session of the ZK whiteboard sessions and today I'm here with Jordy who is the technical lead of political Hermes and our topic today is ZK evm so Jordan the first question what is zkavm exactly Emmy is is well his name is evm which is ethereum virtual machine okay but ZK if his means for zero knowledge okay but actually we are not interested in the

zero knowledge we are interested in the in the computational proving of the ebm okay zero knowledge have these properties so that's why we use this term of zero knowledge but actually you know we are not hiding anything we are just Computing we want to prove that let's let's see what we want to do actually okay let's just start maybe what's uh actually Define the problem okay what's what problem we want to solve why why do we want why do we need it yeah okay why would we need it okay so the idea is that we want to prove that um some ethereum transactions are okay and are valid yeah but without having to

process or doesn't know that transactions actually we want to process the transactions and create a proof that anybody can verify that those transactions are valid without having to run to all the transactions and and you know one test them again this is what makes a scalability you know in the consensus layer if nobody uh you know if if you have to just check this proof instead of having to check all the transactions that means that uh well you can check many transactions at the same time so the consensus are faster and and that's why everything is scarce of course there is that availability and there is other things that you need to to be aware to

scale but this is the important this is one of the important pieces in order to escape and I'm imagining also because you would have this proof you can pose this proof on like ethereum L1 and exactly so this is when we're saying we want to consensus mainly what we are doing is just sending this this proof to a Smart contract in ethereum and ethereum has this you can verify this smart this uh proof in ethereum okay okay so and when we are building a zero uh a proof a zero knowledge proof if you want um what it is so actually is what you need to Define is what we call it a deterministic circuit the deterministic program sometimes a deterministic circuit again is the same stagman maybe if we go to the a more traditional zero knowledge uh literature yeah but but at

the end is like the way the best way that you can understand is just the single program of this let's check this one just a single program has it's a deterministic problem it has some inputs and some outputs specific inputs you get that the specific outputs okay so actually and and then so you need to build that this is the first the first thing that you need to build but the problem is that when you want to prove that it's not just taking C and okay let's write a program the domestic program in C you you and the program here what exactly is the program it's evm byte code is that right yes well the program actually yeah exactly let's see

what the program is it is okay so mainly the inputs of this program is uh the current state of this video okay let's say it say I okay this should be a a miracle root of a full State okay but actually it's the the state okay okay you have a set of transactions let's put the X1 yeah I can probably make those boxes a bit bigger so that yeah that's yeah yes I like to just put here DX one maybe DX a set of transactions and the output

would be state in box which describe the state I plus one yep so this is you want to prove that if you have this state and you have this instructions you get this new estate and you you don't get others so you are proving that these transactions will go to this state from this state makes sense so this is a deterministic program actually here this problem what you are doing what you are checking the doctrines such as solvale that you have there have the valid signature that they then do a double span you know if if it's an evm well if they are deployed in a smart contract that means that they are putting this smart contract in the state if you are actually doing a smart contract that means that you would run to the op code so this can be this is ethereum you know

this is this is this is State transition function is the ethereum state transition function okay this is the part of the the part of the IBM makes sense yeah so this is so the definition is that this is the the circuit uh circuit deterministic program UI so this is what we want to Define but you can see this this circuit is complex circuit so it's not a it's not that you are adding to adding two inputs and I think evm instruction set is pretty complicated and it's also not very zero knowledge friendly or exactly so it was not designed it at that so this is a really complex system okay yeah so the difficulty here is how you build this

this this circuits in the zero knowledge base okay why can we don't use uh C plus or python to break these circuits this is important because in general we need a relationship a mathematical relationship between the inputs and the outputs okay that's why we call it uh circuits or sometimes a constrained systems you have here that so let's let's start with a simple circuit okay so if I if I if I start for example single circuit that just takes two inputs and just multiply them and you get the output let's call this input a this input B and the output C okay yep okay this you you have a way to compute a plus b and then you compute C but actually what you want is a relationship

between the output and the input in this case would be quite easy you just see see must be equal to a times B okay this is the relationship of this uh Circle okay but imagine uh you know uh thousands millions of uh multiplications additions and and I think this is this is complex okay and this is the but we need to convert so we need to write circuits that that fulfill this kind of relationships and also in general knowledge proof systems we usually work A B and C are not just numbers they're field elements and that adds another layer of complexity exactly yeah exactly yeah that's uh that yeah exactly we we

see we I like the word circuits because this comes from the electronics uh works but it has a lot of similarities in electronics we are working with binary binary binary signals which are also filled by the way yes that's um you know it's binary and you're doing you're working with real hard work and and so on here um we have a little bit more flexibility because we can work with this finite Fields so we can work with three four in general we work with bigger much much bigger prime numbers yep yep okay but we need to build this sort of relationships yeah okay so this is I I would this is like the first section it's important to understand what we want to to build we

are trying to build this circuit and we are trying to to to to to to do this okay here um well we can go maybe to hit this later okay but the problem is that this is big you know sometimes a lot of time we have a lot of transactions and and this is uh huge so what we call the public input because so here we need we can distinguish between the public inputs and the private inputs yeah okay let's talk about that let's talk about that a little bit okay for example for for the state the state is support clearly it's a public input okay but um you cannot put the full state in as an input okay you just want to a specific pieces uh you want to put some specific pieces

uh of the state and you probably want to make the public inputs as small as possible as well exactly that's we want to be the public inputs more because um some whole all this public part it needs to be uh checked by the verifier so you need to be used by the verifier so if you have a lot of public inputs then the verifier is going to be quite complex just to process these public inputs yeah and in the context of L2 system that actually in place a lot of costs on L1 if you need to put a bunch of public input there so the the technique that we are using here is uh we are like hashing all the inputs we're just taking a hash so we create like again we're doing we're doing um we are doing a circuit where actually

let's put this bigger okay so the circle with this here here what we do is all this we come with with this we compute we this is our private what we call it private inputs but here what we do is we compute the hash of all these together so we hash all the all the inputs of the state input okay and then we just have a single public input which is which a single input which is the hash of all these inputs okay and then in the circuit we just check that these two are are the same so we are competing Computing the hash inside the circuit from private inputs which are free or cheap or are Partners like unlike

intermediary signals so it's just uh you can very cheap for the daily file right the prover still needs to do that exactly yeah but you don't need to use it in the verifier yeah this is like this is here in in this circuit the private inputs and the intermediary signal so the intermediate values that you need to build here are more or less the same at the end you because you have a full system and then the only thing you want to prove is that you have a set of variables that fulfill these constraints Etc okay and this is like you can think about this as you're inverting the hash or doing unhashing of the uh so with a single public input there's a single hash is what I want to prove that this hash is uh is uh okay yes and that's it okay so it's a circuit

that has a single public input and then you you verify all that together but this is all this is a public input if you want okay it's just that we are doing this trick of uh or everything inside okay so yeah so the first part is unhashing the in the public input to get this set of inputs into this uh and this is like the this is the logic of the zkevm which absolutely Okay Okay Okay but well if if I explain that with just put a cache it's difficult to to see well this catch is that like the hash of the public input makes sense makes sense Okay so let's um deep what is it how we build the circuit yeah I imagine it's a very complex task so you need to break it

down and uh in multiple ways yeah we'll start with the low level so and we will start with the very basic things what's the circuit and then how we are doing that with uh um um clock like you know this uh the IOP I think it's called model which is yep start model and we will start building small circuits and then we will end up building the zik area Okay so this is the this is the path for today okay let's do it so let's start from the from from this from this beginning okay so in traditional circuits you know if you if you when we started to do zero knowledge you know well start people already did this IOP but the the the this narc the snark

World they work mainly with circuits and arithmetic circuits that's what we were talking a little bit with the multiplication we put before maybe I can delete that can we can erase this yeah so this is the circuit that we find before it's a very simple circuit okay just imagine just a multiplication okay and you just get a b and here's C okay this circle can be much bigger okay so it can be I don't know maybe three signals two of them they go that get added this and this one one let's get multiplied by this one let's just put it

this way you can you you it can be a complex circuit but this circuits you see that the the you know the relationship is always with with value so where we have an output we have an input and we have uh a value this is like gates in electronics we have many gates like the signal propagates to the circuit and you get the result exactly that's that's what that's what you have when we go to the I IOP it's a little bit like when we are adding a clock to the to the system so we are it's like imagine a circuit like this okay but um we have like uh uh this in this output just gets back to the input maybe with a latch or something like that okay

and then you get back to the input and maybe you have some also some inputs that enters directly okay so here is you see this is a state transition function so it's like we have a circuit that but what we're but we repeat it many times you repeat it many times the same the same uh the same the same circuit yeah and kind of the as you like draw here the outputs become the inputs into the next uh iteration the outputs can become to the into the inputs in the next state okay this is the basic of the state machine okay so here actually we don't have one value actually we have one value for every clock okay so we have many it's um we compute the witness you know doing this here is just these values a is this

B is this and C is this but here if we do that it's like we have a b and c and maybe in in the first clock this may be one one zero but maybe in the second clock this is zero one zero and then the third log this is uh one one one what whatever you know this is but you see there is not it's not a single value for for for a single you know it's it's called has um has a value okay and we have a state transition function in this case is this circuit this program that actually from from the current state and maybe some inputs attributes the it computes a new state this is the basic

this is the basic of um Electronics processors processors are done this way yeah okay so of course this is algebraic this is not the way we're building circuits we we are building algebraic we were trying to build this uh relationship yeah so in our case these are not zeros and ones it's like much bigger numbers exactly yeah so in a state of building a constrained system where where you have signals actually what we do is we have a constraint system where we have polynomials why polynomials because polynomial is the same it's the same thing the same signals okay yep just to a reminder I think this was explained

somewhere else but you know in a polynomials we can represent the polynomial in what we call the evaluation way so we can select some uh specific domain you know some specific uh values yep and then this is V1 this is B2 the evaluation so we can the the evaluation of this polynomial so in this case we have five values that means that would be a polynomial of degree four so degree less than five and this is because like basically you need um n minus one points to uniquely determine exactly at two two points determine a line three points as a parabola and you know and so forth

exactly and and now it represent so a polynomial is a synonym of an array of values yeah the thing is that if I'm adding two polynomials is like I'm adding all the the value the the values so imagine the polynomial this and I have another polynomial and I can add all the values at the same at the same time so I'm I'm adding in parallel so so instead of working with signals I'm working with polynomials so then I I do operations in in batch you know in and the relationships are should be fulfilled because you have one state transition coach so in this case this would be like evaluations of one polynomial this would be a violations of another polynomial exactly

so you have this state this is the state transcription so we are moving and of course we have the the the the the the the the evaluations of the polynomials this this will be a polynomial it will be a polynomial this will be a polynomial and this will be the evaluations of this polynomial at this point that these roots of unity just for for naming but this is just a specific specific uh points in the domain where we evaluate okay here is a detail because you know we the relationship here we can say that c is a b times a but no we don't want to say that we want to say that uh the next state so how we Define this uh State yes so imagine that this is we have well

this if we see if we find this function this is State transition function if these were signals this would be we call it this A this will call it B and this we call it C okay this would be uh well the next state okay let's let's put imagine that this way we just put it here to see just to put okay this is just three inputs okay just to put something that we can say okay so here the this is C okay so this is C I'm going to put C Prime here okay just to say that's the next state the next the next state here is uh because this would be a plus b times C okay okay so basically this is

how we compute the next C this we do this this is the current value of C okay okay but before we put that in polynomial in a polynomial form this is we are putting here in like a signal form okay but how what's the relationship in polynomials that that we we put you here okay here is the the next one so actually it's uh here we put uh doubly wax okay and this is let me put the Formula First a of X plus b of x um this is times C of x okay yep so you see what is the W the W that w means that you are shifting the polynomial okay so it actually um just maybe just to understand because

this is important so let's let's maybe just dip a little bit on that okay so when I say that the polynomial is evaluated to a specific uh specific uh elements okay we we are using what we call it roots of unity okay roots of unity are well square roots of one it's 1 minus one okay um Squid's Roots uh Square thirds of one one is one so one is a one time so one times one times one is one so one is a um a root a third root uh cubic root of uh one there are two more okay there are complex numbers yep okay but they are

also when you multiply by themselves three times they give you one okay if if I if I ask you for the uh 30 root of unity of one and there are there are 30 possible values in the complex numbers yep we are working here in the finite Fields but the ideas apply exactly the same okay so basically they Define kind of the domain am I think about it right yeah they Define they Define uh domain which is these roots of unity um we are the fields the way that we're building the fields and the weather the construction is that a way that it works exactly the same way that works with the complex numbers okay so it's just there's a mathematical theory on the on

the background but the idea is that everything that works in complex because it's a it's a field then it also you can have the polynomials you can have roots and the roots of unity and actually we are working in generally in uh roots of a power of two so roots of four so uh fourth root the eighth root the 16th root or two to the 28th root okay so if you are working with the two to the 28th rule that means that we have 2 to the 28 a W's points yep so this is going to be W this is going to be W Squared it's going to be W to the third okay and the last one is going to be W to 2 to the 28 which is actually one

okay yeah and and because of the properties of the field they kind of like cycle around yeah or the roots of unity for example in the complex if you if you find that in the in the complex numbers uh this is they are in the circle okay so the the the square the yep now the fourth square is that is is clearly these systems okay but we go to the eighth square is these numbers okay and when you multiply them together it's like adding the angle so it's this you have this uh makes sense rotation thing if you get this and you uh put a weight to the eight then you get one okay so this is just wait so you you can build all the all the all the

other numbers okay so that means that if I hear you know the the the the roots of unity are are built just by uh um just multiplying by themselves so I can I can generate all the square roots by just getting one and just multiplying by it and getting all of them makes sense okay yep so if I'm evaluating um so if this is if if I'm in a point of end but if I'm if I if if f of x is this okay if I evaluate let me just put get another color family evaluate F of uh double w x that means that um when um so um

in in in in in when X is W this is it's going to give the value of w Square so that means that I'm just shifting this polynomial okay okay so I'm just shifting the polynomial some way so this is the polynomial of f w x is the same polynomial but shifted one double makes sense because X is here are just like some values of w here so like if you multiply by another W you just shift it so I'm just taking the next value and shifting to the current value okay so that's why when I want to work with the next value then instead of working with the the C of X polynomial I'm just working with

the Sea of WX which because I'm taking like the the next value make sense okay so now now I think this expression makes total sense to me okay so that's that's the the way that we express um um well relationships uh of many values in parallel uh uh inside the inside the service so as you said this is a fairly simple example and I'm assuming in ZK VM there is hundreds maybe thousands of such polynomials exactly so um I'm assuming like writing them out is super tedious and difficult so well this is why we in order to build that is we built all this tooling for for doing these things in an

easier way okay so for this tooling what we are going to do now maybe is start with what we could say the hello world uh uh of of the story okay uh the hello world here traditionally and this comes very much from the Stark literature uh the hello world it has it's standardized to the to the to the fibonaccis to the fibonaccis area so I think it's a good it's a good point to to to to to start maybe just okay how we would be the Fibonacci service in just to give you a little bit of the just to not lose the track okay we have a statement we have we have a state transition so we have a state state machines okay if we have a

state machines that means that we have processors if we have processors we can we can build a program that runs on the processors and actually what we will do is build a program that emulates uh ethereum in order to process the transactions okay so that's the path that we are running here okay awesome let's start with uh let's start with uh fibonaccially sequence okay boys let's let's start doing this example this Fibonacci series okay so we are going we need to Define what variables uh we have what's this and what's this state machine at this state function this state transition function for this state for this state

machine okay so I'm going to keep well let's let's let's let's we can probably get rid of this part yeah yes we can delete that this one okay here well I can keep maybe the circuit here okay because at the end of you are not too serious it looks like something like this so actually it's even easier than what we painted here okay so if these are the two values what we want is the next value is going to be the addition of the last values it's the definition of the Fibonacci Fibonacci series so here is some here but here what I want to put here is actually the addition I'm gonna put to to to a okay but also I'm gonna put a

to be okay okay so let me write the formulas here okay so I want I want that b Prime so I won't set the prime yeah uh B Prime is equal to a plus b okay and a is equal to a prime is equal to B okay okay so we're using two variables here right here we're using we Define two variables okay let's write here how we would uh write it in P in in peel okay so let's so well what is pill exactly because people may not have heard yeah bill is okay or we are writing this um relationships okay it's going to be relationship of of polynomials here we

are writing this estate transition function the relationship of this polynomial so we need to express uh uh this uh polynomial entities some way we could write I don't know there are many ways to Define it we can have a I don't know our rust piece of code that somehow do that okay but it's good to have a language where you have all the identities in the same place with the exact relationship and this is what spill and it's very useful because once you have the pill when you have this relationship then from the pill we will be able to automatically generate the Stark or generate the the proof and without uh having uh in order to generate the proof you need which identity what you

want to verify so what you need to do what identities what program identities you want to verify so basically pill is a language of sorts that you guys developed to make writing these constraints out simpler and like exactly when you are developing in pill mainly you need to write three things okay we call it the polynomial identity language this is what we are writing here and then you need to write the code that well it's two pieces of code one that computes what we call the pre-compute uh the pre-compute polynomials the constant polynomials if you want some polynomials that are fixed and the the execution trades actually the polynomials and the other is that computable polynomials for a specific instance of this uh circuit actually executes all the values uh so

and then this polynomial identities enforce those relationships on the execution trace and those columns exactly so that's only three pieces you know the pill which is the relationship and then as a um a piece of software to write the constant polynomials or the precompute polynomials and a piece of software the bright polynomials for a specific for a specific proof okay so that's it and once you have that when you have this the constants that you do that once for specifically that this constant polynomials of these pre-complete polynomials you compute you you have this piece and you have the pill and then with that automatically you will generate the you will generate the proof pillow Stark mainly it does that you know it just takes a pill it just takes

this um computed uh computed polynomials and it generates everything you know the the proverb the verifier the circles for verify so all the other Machinery on that okay but we need to Define that you know it it we need this is the language you know it's what we want to prove okay so before we Define the in this case we want to prove a Fibonacci serious okay so that's let's let's write a pill to write the Fibonacci that's good okay so um well in the beginning we in build we first we say name well this is maybe it's going to be very small let me put it I put eight eight this eight means that

uh we will have eight clocks okay maybe we can put here um 2048 or we can put uh some power of two in general Okay so we Define this state machine so this is namespace maybe we could put the name same machine but we use namespace okay um then uh we need to define the committed uh uh the the committed the the committed polynomials in this case are this A and B okay so here is going to be a whole polynomial comment here we have a and b okay so actually I think it's uh I want to mess this up with this okay

and um now we need to write the this uh relationship okay so we just write this relationship very much as it is you know this is actually this is pure you know this is B Prime equal a plus b and a prime equals B okay that was simple enough simple right so we we we're done okay so well at least it looks like we are done okay so um well we Define it this um here we Define the state transition function so that's it okay looks easy right I mean I'm sure there is much more complexity to it and let's let's see

what complexities but we're done so this is actually uh if that's unique if you are able to build something that fulfills this you will be able to generate a start that verifies that and that's all everything we need okay and and by the way to clarify like to generate the verifier uh not the approver but the verifier you actually all you need is this Expressions you don't need the you need expressions in this case there is no pre-compute polynomials okay we will have to know someone okay but uh and but you need to build so piece of code that writes a set of a on B is actually a piece of code that brights the specific values okay so imagine here let me put here here that piece of code we only need for the

approver not for the verifier only for the proverb yeah yeah but verifier is basically defined by these Expressions the verifier just verifies that what you are building that that you that you hold some polynomials that fulfill these Expressions yep okay okay so but here well yeah you are able your you are proving that you have some polynomials that uh fulfill the Expressions what what are the public inputs you know what what what what are what values are you proving you are it's it's um it's a very stupid proof this okay so you you need to prove at least I don't know let's say I prove that you now imagine that you want to prove that you now uh two numbers that when you do

the Fibonacci series eight times uh it gives you a specific number okay that's that's a more uh thing okay so let's imagine that we have a here two numbers imagine here we have one two and then we know well we can do the the Fibonacci just following the size in this case says the a p m a prime minister means that this is two and and here is the addition of two of them so this is going to be three so this is going to be a h saying yes yes this is three and this is going to be five this is five and this is going to be eight okay so let's put four here's just two KP it's just short word okay so actually it's imagine that the result is this one

okay yep so this is what would be the public input okay and you want to prove that well that you know two numbers that way when you do the Fibonacci series of these two numbers you get eight yep and you could also say like this is your public input as well so you can prove that exactly and you can Define whatever you want we just Define it a random a random problem just for for this okay so here actually it's this we call it this uh public uh uh this is a public uh public input okay and this is going to be the the private do you write public input as part of the pill or is it yes let's write this uh public input actually

um okay so let's define this um public input okay so in this case so let's let's call this in public input so this is what I'm going to Define here is public it's called this public input r okay and this is gonna be what's r r is B at position four right so here is just B and position four uh this is sorry so position four okay so this is we Define r here okay so is it zero based or no so should it be three actually or should it should be

three yeah yeah you're absolutely right yeah okay okay so we Define it that these are but we didn't Define any relationship yet so this is where you are taking this we are saying this that this is uh is going to be a public input okay but we are not uh forcing uh anything yet okay okay so we need to force uh something okay so we need to force that R is eight uh uh so that that b is uh r that these are at at eight some point okay makes sense so we need to add this um another relationship another polynomial relationship uh let me write the the expression and then we

talk so actually what I want to say is that um this is say a one let me just L1 times um hello let's call it LL times um uh um this is B minus r is equal to zero okay okay so what does LL LL actually it's not defined LL is one of those pre-computed polynomials okay okay so what I'm doing in this case I'm just defining here this uh I could here in the top I'm defining here at the

bottom could be in the top but this is pull constant LL okay so this is a in from the perspective this is a constant it's a pre-computed it's a precomputed polynomial what's the value of this pre-computed polynomial okay where it's going to be fixed it's going to be 0 for everything except for well actually it's going to be uh yeah zero for everything but one in the last one okay and uh does the verifier needs to know this polynomial as well right yes but this is what why I'm telling you that uh when you're writing a circle like that you

need two pieces one that one that's like a setup you know that actually what it does is pre-computes all these polynomials yeah in this case just generate the file with all the custom polynomials where you fill everything with zero you said the one that's one that's it's very easy code uh to write okay so that's yeah and and here is the definition of the uh of the bill okay okay so that means that when LL is zero then of course there's a question so for all the values is fulfilled because if this is zero this is going to be zero but when this is one here I'm forcing when this allow is one so that means in the last line I'm forcing that that b must be equal to R in order for this to

be zero this happen okay that makes sense so with this we Define like the last piece that we miss it that's how we just uh forcing this okay it makes sense so one question I have is that we've kind of hard-coded these numbers here is it possible until to like make them parametric so sometimes I can say it's four sometimes I can say it's eight yeah absolutely so sometimes you put it here I think you call it constant n okay equals four okay and then here you can put n and here you can put n minus one and minus one okay

and this just changing one place or maybe you can even include files so you can put maybe in a configuration file and then you just include the configuration file you can you can play and actually we are um evolving this language and yeah generating very cool yeah yeah so you can you can and and well uh let's see so we just generated uh this is the hello world okay and but you can see how we can Define and estate machines when we have a fibonacistic machine we can Define any State machines yeah okay so actually we can build processors and and and this is the next step is okay because this Fibonacci is quite easy you

know that's what what happen if I want to build a real processor yeah well let's go into that let's go into let's go here and see what pieces let's go to the processor okay okay let's now that we know how to build um um steak machines basic estate machines let's build a little bit more complex instead machine Let's Do It Let's do a processor yeah okay but let's erase this okay well actually you know processor is this piece but you know bigger okay yes that's defined let's define a processor if you know who a processor in an

electronic processor Works in general what there are different kinds of processors but typical processors they used to have registers okay they used to have instructions okay instructions they read it from some ROM or some Ram you know Regional processors they they would read from a ROM okay and they used to have a ram of course and but there is a processor the state machine the idea of the state machine of the pressure you have the registered state and the instruction some whole the registration States together with instruction you get the next uh then then you get the next state of the registers okay so if you find the processor here we have uh we

have registers let's do a processor of two registers just to make it easy at the beginning okay so we have register a and let's have register B okay yep all the processors they have one thing that's important it's the program counter I'm going to put here PC it's actually it's image which line of code are you executing okay so that means that this will point to some ROM okay so this is M1 paint it let me find it this is so this sprung Contour so here we put the ROM

this will not point to some place on the run to the actual instruction that you will get here in the room you have some instruction that somehow you are loaded okay so here we let's put here instruction that's another register right well it's CI it's just a set of resistors in general but it's uh all together it's the instruction that so what what are you executing here so what what are you doing in this step okay so that's a thing okay and um yeah that's that's very much that okay and this you need this to define the spread transition for the net resistor so here I'm gonna put

a prime which is the same resistor but in the next uh in the next clock okay so here is B Prime okay so this is what uh so this is a little bit the structure that uh what we have okay so and we need to Define this in pill this state transition that goes from a from from one state resistor to another resistors to some set of instructions okay okay so let's just start with these instructions which is just move uh instruction so just just let's say how we Okay so

um here we have a um here we we're going to Define two polynomials two actually to to specific polynomials the same two committed polynomials the same way that we have a and b in the Fibonacci cell it will have two polynomials that are going to be part of the instruction so instruction so the the polynomial I'm going to call it here in a let's call this indie okay and I'm going to find also two of two more then that's going to be let's say let's say old a or set a would set a and Center

okay this is a so we have for we mentioned that the uh the instruction if we find the we should find some place let me find the the instruction but let me let me just extend the instruction okay so again the instruction actually the instruction is going to be let's take a blue one level one works better so no until now the the instruction have let's say in let me put it in lower case just in a we have in b and we have a set a and set B okay I'm gonna just Reserve because we

will need another and these are basically kind of like binary values right it's zero one yes well it actually will see that there can be any value but we can force them to zero one just to start okay okay if I want to imagine that I want to impale I want to force this to to be one zero or one I can always put in a times uh a minus 1 equals zero okay so if I add this to the bill then I'm forcing that in a can only be zero or one okay because this will evaluate to zero only under this conditions exactly so in peel here I can commit so Bill

commit in a in B in sorry set a and suddenly okay yep of course also I will have a and b okay as a register so I can Define already Just A and B okay and different so the one thing are the registers other is the instruction actually well we will see how we match that with the ROM okay but this is just uh let's assume at the beginning at the at the beginning that in this state machine in each step the instructions are are fixed actually if

this instead of being committed polynomials these are constant polynomials let me put constant here you're kind of hard coding the problem you can't code the problem okay okay cool yep that makes sense okay just to just to realize actually it's committed because you will you will want jumps okay and then you cannot hard code that yeah but let's let's move let's move let's move let's let's move this way okay so okay so um the idea here is um next setup is that I'm gonna Define here I want to Define like something like an intermediary value here okay which is a selected value okay so here let's define here it's a poll

I'm not putting nothing else so I'm not it's not neither government nor constant I'm just saying Paul op so it's a this intermediary value okay and this is it's going to be equal to in a times a plus in B times B okay okay so if the instruction is this is one and this is zero then uh op e is going to be a make sense and if uh in the other way around so if this is 0 and this one then or B is going to be B makes sense okay if I don't if I remove this here I could have maybe a linear combination of A and B the instruction

would be just put here something in a combination to element makes sense and the next thing that I'm gonna and I'm gonna let me just delete this okay just to make it a little bit even more flexible okay yep and um uh the next thing is okay what's the a prime okay so this case I would put that a prime is equal to op times set a okay I'm forcing that a prime is if it's set it's a set a okay and I'm going to say also that b Prime is op times set

d okay so how I if I have an instruction where in a is one and set B is one and in B and set a is zero then okay we'll select the A and we'll set it to be make sense make sense okay but now so uh set anzb are defined by estimated polynomials if our committed polynomials then I can do a set of instructions okay it makes sense but now so how is each instruction represented I'm curious because here you have multiple values due somehow like if you say there is a move instruction is it is it decoded into this value somehow or the instruction is a set of values I

could encode to a single value okay but we actually we don't you just have like many values and you know that all these values they compose the instruction okay we already have it in the decoded uh it's it's better you know we will see why okay okay but this is you see that here I Define it a state machine that actually is doing you can do moves you can even do a little bit more because you can even do additions here because you know just if you see just different things one one okay you can set the addition to to a so you can yeah we're going to start being able but this starts looking like uh very much like uh start looking very much as a processor yes okay let's add here another part of the instruction

okay I'm going to call it here const let me put this part of the destruction so here peel constant because we are at this at this point we are working with programs that do not have jumps okay so programs that are just previously constant Define it okay so it's const and I'm going to call it here const okay and the idea is that here is in eight times a plus in me time D Plus const okay because this part of the instruction so this is what is called the mediate value if you want to put for example a four uh in register a okay you just the Constable before and

then set a is going to be uh one the other resistors are going to be zero and this will force that the next step is going to be a four it can register a yeah okay so here we have another we are adding functionality yeah so yeah now we have we are now having where we can move registers and we can do this immediate uh immediate uh values nice nice so it's very extensible this way yeah yeah you can you with this this is and this is the basic this is the basic of of a of a of a in real evm how many of such values do we decodage instruction into real there is I need to check but something like about 30 30 or 40 yeah that's some but yeah yeah here you know

in the in the real ebm a you know we need to work with 256 bits so actually it's a one two at eight where we're working with chunks of uh 32 uh bits okay um you know and and we have we don't have two registers we have five and we have some other special registers for specific uh ethereum uh evm stuff but but they did basically this exactly it's exactly is exactly the same should we um should we go into more specifics about like the evm implementation that you've built or should is there more stuff we want to cover here well I would like to cover maybe the the the whole because this is concerned so I think it's interesting to see how we do conditional

jumps yeah and and and then we can move to the let's do this to the specific idea okay so here of course you know this is uh instructions okay okay you have instructions we can do additions here okay we no no not very much but it's additions okay but I want to cover these two things hey it's like okay how I'm forcing um well first is can we do a conditional jump okay actually yes because we have this PC we forget about this program counter in this in our case in this case the PC is going to be PC it's going to be PC Plus One okay so you're just this one should be a prime right exactly okay okay so the the next quarter is the next line so you're actually going to program

you in general you could one after the other okay makes sense what happened that sometimes um you want to do a conditional jump sometimes you don't want to go to the next line you want to go to another line or another line According to some uh um do some condition yeah okay so actually we can code that inside the inside the inside the AVM okay how do we do it okay so um first trick um the first the first trick is um we need to detect for example let's do a conditional let's do a conditional or let's let's start with a with a basic jump okay basic jump would be here we

can have like an instruction we call it jump that can be zero or one and here I can have let's say an offset okay okay so then this program counter instead of being the next one it's going to be well if it's going to be the next one if it's uh if the jump is zero okay but if the jump is one I want to be offset okay okay so how I would encode this in in pill well it's quite easy let me just well I'm here what I do is uh PC Prime is equal to the jump instruction when one jump when I want to jump this is going to be offset

if it's not offset it's going to be it's c plus one okay so minus PC plus one okay and this is plus BC plus one okay you see this equation that if offset is zero then this term is going to be zero so then we have the the expression we have before so if you don't have a jump we just go to the next the next instruction if jump is one then this this is this is going to be canceled with this so This the the next one is going to be the offset the next the next value okay and this is basically an absolute offset right absolutely in this case it's a single it's a single it's a single jump make sense okay yeah what happen if you want

to do a conditional jump well first we need to the what how we compute this condition so what's this condition could be okay one condition could be okay maybe if a is zero okay that should be for example on a normal way to to to do this jump yep okay in order to do this conditional jumps we need to compute we need to know uh if op is zero so we need to calculate it for p is zero we will jump okay in this case is uh condition yeah it's we are we are checking so we want to do a jump if op is uh zero and if not we'll continue with the same way so we need to compute some whole in a polynomial way that something that is one if it's not Z

if if so if it's zero and and zero if it's not zero okay so let's write here to be clear the the two tables Let's see we have op let's define this variable is zero okay so we have we have here uh zero one two so for zero this one's to be one and if it's different than zero then this why we want this to be zero okay the three zero one and so on yep okay so hope we will how would we do that in polynomial equation simple okay let me write the questions and then we check that they are okay so that's good so so here is Paul let's here is is zero equals to 1 minus o p times in in it's

another polynomial let's define it here or commit in we'll see that the same should be the inverse of op in case that op is different than zero but that's right for the questions and then we have that uh is zero times o p equals zero okay let's check let's check if this works okay in the case that op is 0 okay then or p is zero then uh or P zero times whatever is going to be 0 so 1 minus zero is one so if zero is one okay so this fulfills actually the second question because so P0 it's also it also works okay okay let's go to a different value we

mentioned that OB is two or three or different value okay if if op is two or three that means that is 0 must be must be zero okay so we are okay okay but what happened with the first equation well the first equation is okay zero is zero okay or p is different than zero so this this means that zero is equal to 1 minus this so that means that this third means we needs to be one so that means that inverse needs to be the inverse of o p okay thanks and we we can we will avoid uh be able to find an uh a numbers that fulfills this okay so with this we have a this is a polynomial that's called e0 make sense how we put that

into our system well in this case we have this jump okay but imagine that this jump instead of being uh let's call this uh do jump okay and do jump is uh so when we have to do a jump okay so here we can have a another polynomial uh do jump it is a calculated polynomial that's actually so when we have to do jump if it's a job or it's a conditional jump or if it's a conditional jump and uh and the polynomial is zero so that we can put it

here if it's a jump or it's a conditional jump conditional jump uh times is zero okay okay so that means that do jump one will have to jump if it's a jump okay here of course we'll have two instructions jump and jump conditional okay so we have to do instructions yep okay so if it's jump we will have to jump if it's a conditional Jump Then and this is zero then we will jump okay so here and if and if we jump then we go we'll go to the offset okay so here you see that we can do a conditional jump okay

yeah when you do a conditional jump then that means that you are moving the you are moving the the program counter so we cannot you know this program cannot be constant anymore so this goes actually this we need to Define what we call it a ROM okay so let's define let's define the ROM and let's see how we connect that okay so in in in in in our case this instruction okay so we call it we the idea is that this is the this is the name space like name the main processor okay I don't know what this is

2 times 23 just to put something okay one two two thirty three clocks okay 10 times into the power right yeah this is a double it's a double last risk okay okay um and now let's define another it's like another state machine actually we put it in the same state machine but just to just to be more similar for what dbm works is a namespace ROM it's different namespace okay it's like imagine Namaste it just as a we could be in the same name space with different names okay yeah but here so this is going to be it's not going to be constant this is

going to be committed committed okay okay and in this ROM we are gonna to mimic that so we are going to have the instructions so actually what's the instruction well we have a bill come meet a in B uh set a set B we have uh well we have a jump we have the jump conditional okay or jump if zeros yep

whatever uh what else we have uh um well that's it right I think that well the constant the instruction somehow okay and this is in this case this is going to be constant [Music] okay so we will have a ROM which means the polynomials where we have the lights actually here we will add the line okay um polynomial but in the first line so this is line zero and imagine imagine that's a jump uh it's a jump between A and B then it's going to be was one in a one in in so this is if this is in in a this

is in in B well maybe it's 0 1 uh set a set B this is one zero and the other zeros could you explain the line again is it like a free input or uh line is just uh it's just it's just the number of the counter it's just the column the program line you know without it so the next one is going to be the line one line two line three line four and three half the program okay but the program of course maybe there is here we have some jump conditioner where the jump is going to be one here the offset is going to be maybe just jump to two Okay so this is going to be a two but here we have the the program embedded in the polynomials

so here with what we call it the ROM is pre-compiled so it's a pre-computed thing makes sense makes sense so and now we have in the main we have equivalent okay it gives the rom.na and this is the main.net this this polynomial is different polynomial that the wrong one is actually what we are executing okay so it is the problem but and in this case because it's committed that means that's free you can put any value you want okay but we want this program to be so we don't want this state machine to that you can put any instruction you want you want to to that if you if the program counter says that you are in the

line three that you are actually executing the line three of the ROM okay so you need to link this somehow to that you need to link that with with that okay how you do that and this is the the the trick and one of the most powerful things that we have uh in pill okay so we do it via a block up little cup okay you look up so how we do that actually what we are doing is let me just move this from here and let me write the line of code of pill that's gonna be in that state machine well you can put it in both sides but you can put that in state machine okay okay so actually what you could what you want to do is um

well you want to link that the instruction so in a in B set a set B const uh all attraction jump jump C okay and the program content okay I'm continuing here in so in is kind of like a keyword right it's a keyword but here is ROM dot in a drum

Dot B wrong dot set a till ROM whatever just let me just write down all of them so from not set B here is from Dot const comma from dot jump dot jump C comma the line okay so basically this PC is equal yeah okay we want so here is it

must match yeah okay so you must match what's saying is that it must match what's it must match the line that I'm executing with the line that's in the Rope if I'm executing if the if the steam machine is selling Dynamic Security in the line five that means that the instruction not all these polynomials all the instruction polynomials are forced to be what's in the wrong why because there is only one line five here yep okay in what it means is that this number must be included in this polynomial okay this is a blue cup the pillow cap function and basically you like you express it like this and like the pill compiler will automatically yeah okay awesome this is

very cool yeah exactly so this is you you this is a single you know this is how we force so this is how we are forced to execute a specific program a problem that have jumps you don't have jumps you can do it with constant as we did before but if you want to do a real program that you need conditional jumps and do things then you go you go to you go to this way makes sense very cool okay so here we have a processor here we already have a processor where we have a specific program that's executing we can put whatever program and it's going to be fixed okay yeah uh and what you have the system it all everything put it in pill you know I mean these are all the building pieces that you need to build

uh yeah we don't need many more pieces but we will need some of them so let's let's move to the maybe a couple of more pieces and okay and then we we move forward sounds good okay perfect okay so um now that we have uh the note that we have a processor okay let's let's let's let's let's go let's do a zoom out okay so and and see all the pieces okay so we have the processor which is ROM okay but you know with this we are some here we have some missing pieces okay so we have uh for example we have a you know binary operations arithmetic operations we even have a ram you know processor used to have a it's good to have a Ram

or you can store intermediate values okay so let's find a little bit the you know the the components the devices that are around the processor okay yeah we have to hear the main processor okay here if you want to have the ROM we're very corporate okay it's like different Stig machine okay here we can have we need a ram okay here we can have I'm just pointing here in the the KVM we have the binary Opera the binary State machine which means one question why do you need this binary State machine why can't we just do everything in the main processor uh well because um uh while this binary we'll see that this binary are are expensive if you

want to do in the main processor this would take like many uh many clocks and and a lot of a lot of logic and a lot of polynomial that in general you are not going to use because not all instructions are going to be binary so you want to have it's better to have a specific processor that it's just Computing all the all the binary operations okay and in the in the processor in the processor just uh uh check that the so just check or connect this binary processor with the processor so you are consuming only one clock in the main thing machine and all the clocks in the secondary stay machine are fully used and are Compact and fully

used for that specific for that specific basically it's a way to accelerate certain operations uh kind of like in in regular CPUs we also sometimes accelerate certain operations by creating specialized circuits so this is like this is the purpose exactly so you are building things like in panel if if we want to put the same processor imagine I could have all the possible instructions that I can do for a single clock should be repeated many many times and it's going to be wasted most of the times because you are you can do only one thing in the instruction in this thing we we just we we can do like so we are not wasting all this all this value we can pack that on the other side okay so that's why it's interesting this concept of having different estate

machines here what we have binary we have arithmetic we have some crushing stuff I'm not gonna cover now today but here it's you know we cannot and we can add you know catch up you know that there is there is uh we cannot order uh stain machines here it makes sense but the let's let's focus on the maybe the most important the most important one okay so let's deep a little bit in in this binary in this binary in in this binary State machine I don't want to go deep no but the idea is that we have a state machine where we are when we are Computing this and an xor so at some point so we'll have a state machine where at some point of this estate machine we will have the

results we will have the results of this uh and uh of this A and B okay so and the idea is so okay so and how we do that we do mainly with pillow cap tables so if an end is very easy to do it in a lookup table so you have I have two inputs half an input a I have an input B imagine that they have all the options for a so imagine that can be something from 0 0 to 1 1 1 in binary so if you go from 0 to 256 55 okay and B are the possible values from 0 to 255 so okay so I can easily Define a constant constant polynomial which is the and of both right so I can compute

buy to byte okay so I can set up easily a state machine where at some point so I have the the tables okay and at some points at a specific point I will have that here because I don't know a specific number uh one two three and uh zero it's gonna be zero yep okay so basically for each combination of these two values you have a result and I guess the table here will be like 2 to the 16 in size exactly okay do the 16. if you want to do ants in eight bits of course if we want to do ants in 16 bits then maybe we can split in two steps and have a state machine that computes that in two steps

but at some point I'm gonna have like results of the numbers which numbers the ones that I choose that which are you going to choose the ones that I'm gonna use in the in the in the in the in the main same machine makes sense okay so and then who I do the block up well it would do something the blue cap would look like something like um the instruction bin so this is over Half-Life one instruction the same way that I had jump or jump C I will have an instruction that's going to be bin binary okay and it's going to need bin and then I want to do from um well here is uh binary here is going to take a

a sorry this says a B I'm going to put a register C with just definitely two registers but here for doing ternary operations is good to have three registers okay um okay E1 and this must be in and this is the binary State machine dot selector or latch if you want sometimes we call it large yeah latches no this is large is going to be one when when when we have a result that's we can have some in some intentionally yeah that are not there okay so this is good latch and then here we will have been dot a Bean

dot b and Bin let's see okay so we have a block up so we have a program that so at some point we warranty so if this beam we guarantee that whatever is in C must be a uh and B makes sense and like this is pre-computed uh table that you use in exactly and but well it's it's the this is a pre-computed so here at some point we'll have something in the binary this is the Mainstay machine if you go to the binary State machine at some point I will have something like uh a uh b c uh in this is the pre-computed table

it's k k a k b k e c k a k v a separate computer table so a b and c can be any value but must fulfill this okay and if this will fill this then you you you it must match the make sense and this again this works on like single bytes and then um this gets aggregated when you single advice but you know you can you in the sustained machine you can do it like multiple maybe multiple lines multiple by so you hear that's why you have the latch maybe you have like four steps before where you are doing bite to bite I see and then in the last one you latch it and you have the the final result of actually what you want to compute got it yeah so basically this is you you use pre-computed values on a byte level but

then you have this logic here in this table that Aggregates them and computes because you need to in evm you need to do it on 32 byte values right uh in the in the evm in the game is 32 bytes yes yes exactly but okay but this is the idea here is that we can we can compute that in the separately in the existing machine and then be a plookup we we do uh we do uh we we do this we do this much okay okay and you mentioned in your case the uh this binary does uh X source and and you also mentioned it does comparisons as well yeah here is on this we have like a kind of a country so we are doing well decomposing in bytes then we have a curry and we can do an addition actually in the EDM it's 32

steps and we are doing buy to buy because this is what we are doing and here we do additions multiplications less than greater than exorced or and what does arithmetic do that arithmetic is more for multiplications many is for multi for doing 256 multiplications we're also using the arithmetic for the elliptic curve uh operations embed it in there okay so basically we have this tape machine that handles most of the logic and the American binary or bitwise functions yeah and then this one handles multiplications and like additionally like elliptic curve uh something that helps with that's very specific for the cdsa but actually you can add there more operations that are you know for example

for paintings we could that you know the the the operations in the in the BN in the BN Corp and makes sense and then hashing I'm guessing it's ketchak mainly ketchak we are also using here we have uh also for example storage we have not talked about the storage this important thing here okay that we are using positan just because much more efficient okay to write a on that okay got it so storage hashing any other big state machines that are missing from overall I think this is the main this is these are the main one there are some you know some specifics for the ABM but main this is our the the big the big you know the the big ones at

least okay okay so awesome yeah this is so clearly yeah just to summarize a little bit there we have this with this pillow cap we connect uh one uh to the other important to see why this works it's a and another important one is who we set C in the in the main estate machine okay we here we are checking that c is is is is is is is okay but who we said see uh if you want this to be a and b actually what we do is uh we have like a special so when when we had the the processor remember that you had the register a the register D the sustain machine will have the register C okay here we had the in a

instruction so the part of instruction in a in B and in C okay here actually what we have if we have another register we call it free it's not really a register it's just a free input so it's a value that you in each instruction you can put whatever you want there so it's a free input it's a free input but here we have in three I think in like terminology this is called non-deterministic input exactly okay so actually you can put a non-determination so there are some instructions that allows you to put a non-deterministic input in this case if you are doing a a uh so and then actually you can this is not what they see this maybe would be

the op okay and actually you can put bs3 input you can put whatever value you are checking that this value that you put actually is then and then you store okay whatever you want okay but this is a free input actually it's you use this for input in this specific instruction to put whatever you want you put whatever you want because later on you are going to check via this program that what you are putting is not what you wanted it's what the result but actually that actually it is makes sense makes sense so this of course Ram is um also you know a full story you know inside the ram but the idea is that you can in one clock you can you can read some writes the big idea just to to mention here is that uh

data is that we are we have like another steam machine we call it drum that's all the reads and bright that we do it in the in the ram but the idea is that we resort we we we we we we we resorted we put it in a different order we couldn't order that we ordered by address instead of ordering by appearance we order them by address and that appearance that means that all the reads and writes that you are doing to a specific address you are packed them together so you can do it in a register so you're doing all the registers and then and then and then here we are a lookup actually it's not a lookup is uh is a it's a permutation check okay so which is more restrictive Imperial instead of being in is is

so yeah basically this is ordered by uh kind of like Spain like uh space ordered while this is like time ordered yeah exactly okay okay and with this of course you need to force how you force that are ordered that way that well that means we we use this kind of increasing things will be uh be a a um be a rain check so it's like uh if you are increasing so you are increasing the address so you cannot go box okay of course you at the end you there is exception you go to the end but yeah but that's it's you can you can check in the code in the in the rhyme it's not a difficult uh it's not a difficult thing machine to follow if you understand this idea and by the way

um we mentioned something about range checks is there a separate State machine to do range checks or is it because a rain check is just if you want to have a rain check at the end is uh it's a pillow cap okay so you have a set of a kind of pre-computed uh columns that enforce zero one two three four and then you are checking that these are in zero one two three four got it uh I know that there is uh there is some techniques to it you know to optimize so a little bit these rain checks when they are some specific uh maybe in the future we detect that or we do something special for that but at this point it's just a normal pillow cap if you have Pillow cap you have much more than uh rain checks yep makes sense uh so this is a you know this is a basic

estate machine we we just cover the the basics of the steam machine and in order to build a zkvm well we have all the pizzas so it's mainly this what what we are doing of course we have more registers these registers are wider we have some extra registers for kind of some we have some register for uh for for the gas uh on the VM and for counters and for you know some some specific ebm uh things okay so that we don't uh just to go fast um we have a you know a bunch of operations we have some you know some other stick machines for doing some

specific things of the VM for example the alignment of the memory uh you know sometimes in the memory industry in the evm um it's uh byte alignment but uh so you can read bytes alignments but actually are you're reading words so how you structure the memory well you need to do some extreme things there okay of course all the hashing or the padding the Storage storage is an important part that uh in there we then cover here but it's like a full steam machines in the storage okay but at the end we have a processor that's uh running a program which program well it's a huge problem but actually is ethereum that's mainly it's like it just takes us these three inputs that we say in these three inputs we are putting the

transactions with the code on the with the code that rlp we get all the of the values we check that the signator is valid uh if it's a call we we recover from the ROM and the hash uh the program which acute and we the code or the op codes uh and we can at the end we end up Computing the we end up Computing the new hash value so the new state machine and with this we have the full this is how we built the full evm all the code is available all the gold is free so you are free to to check there to go to contribute there so it's uh it's uh it's a huge effort but yes it's uh what

that's uh that's the work that we are doing and that's why we are able this is how we are able to build going to the origin you know going to the beginning where this is how we are able to build this uh program this deterministic program this circuit that takes some transactions as an input the Texan State and computes this new estate so it checks that the new state is forced to is forced to this one it's you know it's a full stack but it's a full stack but but you know it works it's it's uh we can prove that another very efficient way it's very cool and the the fact that you have this pill construction that does a lot of work for you automatically is exactly this was you know you have to build this

like you can build this uh just uh directly in this case the approach is build this Tooling in this case is the pill and the assembly mainly uh these tools uh actually it's two assemblies because we have the storage is uh it's a processor itself with a Roman with the same instructions all together okay so we built you can we can build that quite fast and quite easily once you we have the the the this tooling okay and then and then of course this connected to all these uh logic you know once we have this pill and automatically we go to this uh Stark you know we generate all these Stark and and generate this proof and then we'll go to the recursive star

to reduce this Stark and aggregate these proofs in you know in many so we here is all the all the other there is a lot of complexity and a lot of well yeah it's a lot of it's a lot of layers and it's a lot of fast but it's it's Slayer it's quite clear what does and here we just cover well this this this part which is probably the most specific in in the for for breaking it up in this way like it's the the only way to do it you can do it in everything in one go it's too complex so like breaking up into logical piece is that you can handle on its own I think is the way to go exactly yeah all right well uh thank you so much this was awesome and I I I'm sure we all learned a lot and thank you well you're welcome

and yeah just you see it's this is uh this is amazing it's it's it's very cool it's very cool stuff thank you thank you [Music]