ZK Whiteboard Sessions – Module Seven: Zero Knowledge Virtual Machines (zkVM) with grjte

Transcript

[Music] hello everyone we're here today um with another zk white board session and this one is going to be about uh zero knowledge virtual machines and i'm here with gersteff from polygon minden and my first question is so what are zero-knowledge virtual machines and what are the alternatives to them yeah so basically zero knowledge virtual machines give us a very convenient and easy way for somebody to write a high level program and then execute it and get both the output and a proof without actually having to know about zero knowledge um so to think about the different ways to create zero knowledge

proofs first the way that we've had around for a lot longer is to have a circuit that and gives us a proof in this context what exactly is the circuit yes so the circuit is going to be a representation of a computation that uh we're able to run a snark or a stark over and uh so it's a sound essentially like an asic it's especially optimized circuit for our zero knowledge proof so it's like an asic approach um and that means it's specific to each computation that we're doing so if we want to make this um more general and be able to run arbitrary programs this way you would want something like a

specialized language that you can compile into your program specific circuit and run so we would have some sort of program here written in a dsl so an example of this would be sircom or leo put some examples um and then it gets compiled into this circuit that is just a representation of this program that the snark can understand and then we run it and get our proof okay and this is like an algebraic circuit right where there are gates actually conditions multiplications exactly it's an algebraic circuit so it might be sort of represented like something like this where um we've got

some gates that are doing things maybe addition multiplication and then we've got our inputs coming in here at the bottom that's how you'll often see it drawn okay and you know the reason why we call it the circuit that's equivalent to i i guess we can see uh how it could be implemented hardware where you have gates which in in the case of hardware different types of gates exactly so it's sort of a way of thinking about um what would be a physical representation but we can think about it an algebraic circuit as the same sort of mental model um in the same setup of sending a signal down through a bunch of wires um so on the flip side what we can do is we can think about instead of having the circuit be equivalent to our program we can write a

circuit that knows how to take in and execute a program and so that would be our zk vm approach let's call this our you know zkbm and uh it's going to start out very much like a regular virtual machine so we've got some input here and we've got some program code some byte code that our vm knows how to interpret and execute and then we're going to get an output over here and um so this already this is just a normal vm and now what we add is our proof and over here we can have some secret inputs

that only are oh that's not how you spell witness but only the prover inside of our vm knows so these are secret inputs these are public inputs and the verifier is going to know this and the circuit that we're doing and then gets to see the proof on the output um but the prover knows these things okay and just to make it clear like the circuit also has like this uh inputs and weakness and output but the difference is that in here the program is also in the input but here the program is the circuit exactly so in here you're sending your um what was our input it was here it's going into your circuit and you're also getting your output and your proof but um this

equals this right this is we're compiling and so we can think of this as being equivalent to our to our program code whereas here it's an input to our program code makes sense make sense um so i mean why why there are two different approaches and like why would you use one versus the other yeah so um the first i'm going to put a label on this we'll call this kind of a cpu approach just so that we have a clear way of distinguishing between the two um so the benefit of this approach is that it's highly optimized your circuit is going to be exactly what's required for your program there's no extra stuff that needs to happen so often this is going to be the the most

efficient approach to running your computation in a zero knowledge context on the flip side you need more kind of user specialized knowledge in order to either write the circuit directly or even to use uh a language a dsl like circom or like leo uh in order to define the constraints correctly so it's harder for somebody who doesn't have zero knowledge to actually do this thing and another thing is that because this is specific for each program we need to have a verifier that knows each circuit so each time we do this we need to have a special verifier whereas this this part here is our circuit so we just define the verifier once and then we can get that verifier audited and we can

send in as many programs as we like forever makes sense um additionally this can be so right here this is the byte code that our zkvm knows right but we can have some like higher level language like solidity and we compile it into this um and so people can just write this without having to learn anything extra anything specialized the the downside of this is it's going to be a little bit less efficient as mentioned and that's because we have this sort of overhead where we need to decode and process this program we need to um we have to have memory so we have a few extra things that we need to do inside that that context how how would you handle a loop inside the circuit

yeah so a loop inside a circuit you have to unroll it all the way so you end up having a lot of extra gates to handle as many iterations of your loop as you're going to have whereas inside here we're going to define some op codes that know how to do loops and then um we'll be able to just run our set of constraints and everything over that so basically in a circuit approach you would you know basically incur the cost of a loop of the maximum number of iterations of the load but here you only pay for how many iterations you're gonna use yes yeah you just pay for as many rows in the execution trays which is something we'll be coming to next and you'll get to see how that ties in um one last thing that i think is is good to mention here is that this gives

you a pretty easy this can give you a pretty easy path to recursion because um verifying a proof is just going to be another program so we can write a program that in you know in our zkvm instruction set that can verify one of our zkvm proofs and then after we run our first program through here we can take this proof we can pass it in as an input we can run our verification program and we'll get another proof out proving that we've you know that our proof was correct so you can get recursion fairly easily this way very cool very nice right so you mentioned that the circuit approach is like fairly well known and i think zkvms or zkvms appeared fairly recently uh but

you know what is the background like people started using them did they exist before like when did they come about yeah so zkvms are really recent um in the past couple years there are a few different reasons for that there are a lot of costs um to running um zero knowledge running running things in a zero knowledge context inside of a vm which we'll get to in a little bit but the basic history of it the first sort of um system to be doing arbitrary computation inside of zero knowledge in a zero knowledge context was tinyram and they defined a way of handling random access memory that sort of gave us an idea of how we can do that inside of this context from there we got to cairo vm

and disk staff which was a precursor to maidan and now of course there are a lot of other vms you've got zk sync you've got all of the evm projects hermes and scroll and the consensus project so there's really been an explosion of it over the last couple years um and if we want to talk a little bit i just mentioned the handling of random access memory by tiny ram but we can just talk a little bit about what are the building blocks that all of these zero knowledge vms sort of share the things that everybody's using even if they're using different proof systems and targeting different instruction sets so just so the first thing

that we want as with any vm really is a cpu and the way that we model that inside of um well yeah the way that we model that will be with an execution trace as we mentioned earlier so before kind of showing the execution trace i think it's useful to talk about the difference between circuit and machine computation representations so we saw the circuit earlier um which looks the algebraic circuit and it's like a like a circuit in hardware where you have a signal going through a bunch of gates a machine computation is going to be represented as a state and a set of that is not a very straight line a state and a

bunch of steps and we do a transition function from one state to the next this is a really natural way to represent a computation it's a really useful way to look at it inside of a vm context so it's kind of the way that we'll look at things within most of these zkvm things it also fits really naturally with starks and mines is stark based so we'll see kind of how that comes into play later i think a lot of the virtual machines like in ezekiel vms or vms they're mostly start based probably because of this ease of using this repeated computation structure yes so a ton of them are stark based and do think about the execution trace in the same way you've got hermes and maiden and cairo and um the

consensus project as well and then even the ones i think as well risk zero of course yeah um targeting the risk five architecture and then even the ones that don't will use like a plonkish arithmetization that still you kind of look at it in this table like structure so um yes so the execution trace we're going to have right here actually i'll call this time this is going to be the cycles of our vm um so t for time and then we'll have sort of a program counter here and a bunch of registers and these are more columns um and this will just go from the beginning to you know our final

cycle that we run and then this is going to control everything that happens inside every every the state at every step at every cycle and over here between each pair of subsequent rows we're going to have a transition function that we run and this transition function will be exactly the same at each step and as long as that transition function is valid at each step then we know when we get to the end that the entire execution trace was valid so we're basically saying let's call this our you know basically say when we take our transition function of the state and the next state um then we're going to accept if

um if that's valid if that state goes to the next state so that's the execution trace it's how we can model the main processing inside of our vm yep makes sense and then you mentioned something about memory as well yes so memory we have to think about a little bit differently this is so this is a time ordered um execution trace and if we were to do that with memory we'd have to do something like uh store all of the memory addresses at each step and it would be just this massive thing that goes way past the end of the whiteboard and is very inefficient so what we want to think about instead is how can we store memory in a way that we can do a transition function at every step in the exact same way while doing this more efficiently and

the answer is to use kind of a space ordering instead of a time ordering so we're going to order it by address order it by address and then by time so we'll draw it out again like another as another execution trace and start here with address zero now um we can have as many sort of reads or writes as many axises as we want at address zero as long as the thing that comes next is the next address and then we can go you know lots of things that address two lots of memory accesses there and then we just order them by time next so maybe this happens at cycle one cycle eight cycle ten and this so just to clarify like

every one of these repeated things is a memory access and it could be a read or right is that correct yes so just to be very clear we're going to define the actual memory update whatever it is that's happening over here and um i'll just write update uh and that's actually where your memory model is going to be defined so this pattern of defining an address and time first does not determine the memory model we can have a read write memory model we can have um which we use at myden we could have a non-deterministic read-only model like they use in cairo and that's going to be down to how you define this section of it so i won't go into detail on that right now um but just to show this one correctly i think

in cairo it is right right one's memory or something like that it's not just read-only it's well non-deterministic read-only would be saying the prover gets to set it and then it never changes so we're sort of saying the same thing yeah and i think in the paper they express it both ways but yes you can also think of it as right once memory um so then yeah so so just to show this time ordering um this time the access memory address one can still be before we're done with with address uh zero right so we can do this at two three um whatever and it just goes on words like that and now what we have is a transition function that we define for our memory

at each at each row and again it's the exact same transition function defined at each row and if all of them pass then we accept and our execution trace for memory is is valid make sense so like okay um it seems like two separate execution traces how do we how do we get from here like i know here for example we want to access some memory here you know in the beginning of the trace and maybe later on we access it here and then but then again we go back to the beginning of the trace so we kind of jump all over the place how how can we tie them together yeah so um a really important thing that has i think i think since 2018 so very new is the idea of look up arguments and an

efficient way to do that inside of this context and so the idea of a lookup argument is basically to say everything that exists here um and you can think of each of these columns as a polynomial because that's how they're going to be when we go ahead and actually run our when we when we generate our proof so every point in this polynomial also exists inside wherever we're looking it up here and so we can use this lookup argument to tie these things together efficiently and an example of a very common one that's being used by for example hermes and scroll and a lot of projects is is pluck up so that's and i won't i won't again i won't go into the details of lookup here but that is how you can

connect two different separate execution traces together to ensure that they're they're actually valid the you know the look the accesses that we call to memory here match all the things that we prove in memory over here makes sense makes sense now um i think um so there are two components but you mentioned that there could be multiple building blocks is there anything else besides cpu and ram well um yeah so it it's really up to it's up to you you could do everything here but it would be expensive and um that's that's true even in a hardware context we like to have sort of specialized chiplets that might do specialized processing uh but especially in a zk context there are a few costs extra costs that we have to think about

so the first thing um the the reason we have to deal with these costs first of all is because everything we're doing here these are finite field elements um elements of a finite field and we whichever field we've chosen and that can vary depending on on the project on your proving system but we might for example want to do some operations on integers and so there's going to be a mismatch because our integers are going to be a different size different number of bits than what our finite field what our field elements are and so every time we do those operations we need to prove that we actually are using something that is a valid integer so to give an example from um with myden we have a 64-bit field that we use but we offer a lot of

32-bit operations and so for each of those operations we have to prove that the element that we have is actually just containing a 32-bit integer and to do this we have to do something called range checks and these happen all over the place and so it makes sense to have a specialized circuit that can do them efficiently so um i guess i shouldn't call it cost i'll call it overhead these are sort of things that you can do without specialized circuits but they're going to be more expensive um so range checks is one another thing that we get that's expensive because of the same the same situation well

actually it's expensive because in this context we have to prove every single thing that we do and every piece of data that we use and that's bitwise operations because again we've got a field element and if we want to do a bitwise and over it we have to break that field element down into its individual bits we have to prove that each of them actually is just a bit we have to prove that we decomposed it correctly then we do our operation and then we have to aggregate our the result of that operation back into a field element and doing that in the cpu itself would be very very expensive right so if we were to do that within that cpu that we draw it earlier it's going to be just a lot of cycles to do all of that work um so it makes sense to define a

specialized circuit that can do that efficiently and then use this lookup argument like we talked about to connect it to the the main execution trace the cpu and the final thing that's um i mean there are lots of things that you can do to optimize with this but the final big cost is is hashing and that's because um traditional primitives um like cryptographic hash functions that are in use are optimized for the hardware that we have which is which does bitwise operations really efficiently and so a lot of them use a lot of bitwise operations so the cost here sort of turns into this is also expensive and there are a few things that people have done to

improve the costs here one is zka friendly primitives um so that would be examples or like rescue rescue prime poseidon um so hash functions that are much cheaper inside of a zk context but the other thing that you can do even using these it can it will still be expensive so the other thing that you can do is to have a specialized processor to handle the hashing for something like sha so exactly exactly especially ketchup if you know if you're doing zk evm or if you're doing anything supporting ethereum then you've got to deal with a couple of hash functions that are just very expensive um and so people might also do specialized

circuits for signature verification or for anything else that they want to do exactly but these are the three that pretty much everybody does okay make sense okay so let's say we have these building blocks and we decided what to do like what other things do we need to care about before we let's say build a zero knowledge virtual machine yeah so um i'm gonna draw two things the first is just a summary of this sort of general model of a zk virtual machine that we just talked about and the second one is a picture of sort of what the what it what it looks like going from the user to to the proof and then we can use that to guide the decision points to look at the

decision points that we have so just to summarize our sort of general design model we have our main cpu that's our primary execution trace we add in our ram we add in specialized circuits and we connect all of this via lookup arguments and then to make this even more optimized we can actually add recursion on the end and so that's sort of a general model that we can think about for building us the next thing is what it looks like going from sort of top to bottom if

you're a user a developer and you don't know the zk stuff that's sort of the pitch of the zk virtual machine you don't have to and you can run all this anyway so we've got sort of the language level you can think about where we have you know solidity or whatever else rust some high-level language that we compile into some intermediate representation then we've got our byte code so we compile down to here and um this byte code can be something like evm um by code it could be say risk five

or wasn't something mainstream or we could target some zk friendly new instruction set that we that we design so bytecode is basically the instruction set architecture yeah so vm yes so we're going to have by code but this is this is sort of where you're thinking about the instruction set architecture that you're going to be feeding into down here or runtime and this is going to be just um we have our cpu we have ram we have all the other things we talked about and we also have our approver in here and then out comes are proof [Music]

so yeah so there are there are sort of two decision points from looking at this high level picture that you can think about the first one is the instruction set architecture as we were just talking about so you can decide to target something mainstream so for example the risk zero project is targeting risk five and a big benefit of doing that is a whole lot of language is already compiled to risk five and so you have all of this tooling available um on the other hand it might be less efficient inside here than something that is zk optimized that's a newly designed instruction set um you can also choose evm the evm architecture so uh projects doing this would be like hermes you've got scroll and a lot of benefits of that of course

you've got solidity and all the tooling for that and it's really targeted towards ethereum um and you're still gonna have to make different decisions when you get down here then for the zk friendly approach this would be sort of like cairo or what we're doing at maidan teams that are designing a whole new thing that should be the most optimal inside of our zero knowledge context uh the other decision point that you can sort of see from this so this is this is one um is this what's your proof system going to be and the proof system that you decide on maybe a stark or a snark and we talked about it a little bit earlier is going to determine the arithmetization that you have to design everything in here for so that's going to be the other sort of important

top level decision that you have to make and as we talked about earlier stark's especially well suited for this kind of like optimization where you have repeated computation or a computed computation with like repeated structure and that this is basically what the virtual machine that you drew up before yes exactly um partly because the arithmetization first arcs the air algebraic intermediate representation is basically just an execution trace like we looked at with a set of constraints that get applied to it it's sort of a very simple mental model for how that will work makes sense so but even with starks there's a lot of options that you can choose like you can choose a different field for example um like how how do yeah so let's um let's actually dive

into maidan a little bit and see some of the design choices that we've made and in the process of doing that we'll see sort of where some of these deeper decision points are okay sounds good all right well uh let's do a deep dive in mind and see how what choices did we make in on all of those decision points yeah great so let's talk about um the maiden we'll look at the mayan execution trace i will not write that whole thing out because it's long so starting here we have a couple of system columns and these are just for things that we need to keep track of everywhere so for

example our clock cycles um clock and a free memory pointer for for procedures so this is system then we have our decoder so this kind of brings us to the next decision point that i was referencing which is how you want to handle program initialization and what options do we have there so the first option is just to use public memory so the program would be one of your public inputs and you initialize your memory with it at the beginning of

just before you start execution and you point your program counter to it and then you go now the downside of this is as your program grows large your verifier has a lot more overhead because your verifier sees all of this as one of your public inputs but it is a sort of a simple straightforward option that you can use another option um would be to use a bootloader so you would bootload from hash so in this case instead of having the full program you as your public input you would have just a hash of your program as a public input the verifier sees that you have your full program as part of the witness and so then you have this bootloader that's going to it's like a mini program that's going to take your full program and hash it all together and prove that that matches the

hash that you provided to the verifier and then it will put it into memory and initialize your set your program counter and you run and it sort of goes the same way but instead of having the whole big program and your public inputs you have a shrunk down just a hash so that would be bootloading from hash and then another option would be what we do which is merkly's abstract syntax tree and this also is tied to our control flow which is another sort of choice that you want to make if you're designing your own instruction site is how you want your control flow to work so the mast it starts out a little bit similarly and that we provide a hash as a public input that the verifier sees but instead of um unhashing the whole thing and setting up

all our memory that way we can just unhash selectively as we go through because each node it's it's a binary tree and each node represents one control flow step and we'll look at this a little bit more in detail later so that we can draw it out but i have to like summarize it in in very high terms like the bootloader the simple bootloader approach you basically take the linear hash of the sequential hash of the entire program while in the must approach it is more structured harsh it's it's actually a miracle tree of sorts exactly yeah it's a structured hash which lets us sort of control a little bit more we don't have to unhash things that we're not executing and we can selectively reveal things to the verifier if we want to okay and so our decoder handles processing

that and we'll look at it in a little bit more detail the next thing that we have in our execution trays is our stack and this is another sort of decision point we chose to use a stack and have a stack based architecture but that's not the only option you could do a register based approach you could also do a memory memory machine which is what cairo is doing and memory actually is is quite cheap inside of a zk context there's no latency really you have it when you want it and as long as you can access it with very few constraints it can be very efficient to do a memory memory machine so that's another option there um but yes so we've done a stack-based machine so here's our stack the next thing that we do and i'm just going to

change colors for the sake of the markers but this color changes is not meaningful um would be our range checks as we talked about earlier we have a special section of our circuit to handle range check operations and then finally we have a section that we call our um chiplets and this is where we stack those specialized circuits that we talked about which are in our context it's not a circuit it's a specialized processor but we have our hasher then we have

bitwise underneath it then memory and finally we add some padding and what is this padding why do we need it yeah so basically the we need every column to be the same length for our execution trace that comes back to our transition function that we're going to apply to every pair of rows all the way down and so if we have somewhere the rows end early then we're going to have a problem with our transition function unless we do something special and deal

with it a different way which is possible but it's not the easier way to go about things um so so i guess you will need padding in all of them yeah so what what happens is based on whichever one is is longest which is probably going to be the sac but you never know um whichever one is longest we'll round it up to the next power of two because the length of the trace needs to be a power of two and then everything else will get padded until it matches and this one will get padded to the power of two as well and so the design idea here because we could have made each of these a separate set of its own columns the way that we did the range checks right but the the thinking is that we're going to do many fewer bitwise operations than

we're going to do stack operations because manipulating this hack is takes a lot of pushes and pops and so we can pile in a few processors here in the amount of time that it will take us to go through this and this reduces the number of columns exactly we can save columns okay make sense you draw them different sizes is there a meaning to that yes um there is and to explain it actually i want to take a step back and as i'll first say that these are selector columns um and then to explain what that means i want to go back to talking thinking about our execution trace and the transition function so as i said earlier in error it you can basically think of it as a big execution trace and a set of constraints and there

is algebraic intermediate representation um which is the arithmetization for starks okay so yes so we can think of it as this execution trace plus a set of constraints and the set of constraints are going to be applied at every step so they're basically equivalent to this transition function that we're talking about now we're gonna we're gonna apply them at every step but we don't actually necessarily want them all applied at every step we don't you know for example if we're doing an ad operation we have our operations defined inside our decoder because it's decoding from our mast so we'll do add and we have our stack here where we've got you know a and b let's say these are our

stack positions um up to you know we have the 16 16 columns for the stack so at this row we want to add a and b on the stack and at the next row we want to have c on the stack now which c is like a where c as well as a plus b yeah okay yeah so um so we want to have some sort of constraint that forces that enforces that c equals a plus b and in order to have that constraint it has to be part of our set of constraints of this transition function that's applied but maybe in the next row we're actually doing a multiplication and in that case we don't want to apply this add anymore

so we need some way to deal with that so what we can do are have flags so we'll say this is represented by a set of operation bits and we can turn those off bits into a flag so the op bits [Music] i'm just going to write it in here but we'll know that it's not actually a step so the outputs turn into an operation flag and now what we have we can have a flag for add and when this is a flag like what exactly this is going to be a binary value so we just it's going to be one or zero um and so when it's one we're applying the add constraint and when

it's zero we're not so we'll do um our ad flag a plus b minus c we want all our constraints to equal to zero so we'll multiply this times the enforcement of this and in this row when we have our ad flag is true it's gonna it's gonna enforce that a plus b minus c equals zero but in the next row our add flag is false this is zero already so this part won't be enforced so this is multiplication right doesn't look like a function yeah this is multiplication it's very confusing with the f yes um so yes this is this is the multiplication of let's do it like this um yes so this basically shows how we can

express um the transition function and apply the constraints for any specific operation that we want to run inside here there are also a set of things that we want to always apply that might not be operation specific so an example is our clock cycles we want this to always be increasing by one and so a very simple thing that we would add to our set of constraints here is to go clock prime will mean the next clock minus the current clock minus one equals zero and so this we don't need a flag here because we want to apply it for every single step all the way down but any specialized operation that we're running we do need a flag

so that basically brings us back to here in order to decide that we're going to run um these operations that we're going to select these sets of constraints to do the transition function here we need to know when we're in the hasher portion of the trace when we're in the bitwise so we define selector columns so this is at zero so when s0 equals zero we apply all the hasher constraints and then after that it's always equal one so then here it's one and we don't apply to hasher constraints but we apply the bitwise constraints and so this gives us a way to um to select for each one of these

specialized processes so i know that in starks or like in general when you write this type of lgbt constraints every time you do multiplication your degree grows so uh in this it would seem like the degree could grow pretty quickly like what is the well there's a degree here yeah so it's a really good point because um the degree of constraints is another design consideration that you want to be thinking about as you're doing this stuff for mine in we actually use degree 9 as our maximum and when we combine all the constraint functions later so this transition function as i said is sort of the set of constraints so when we finally do our start we're going to be applying something that's the combination of all of these and they all need to be the same degree at that point

so if we have a maximum of degree nine then sort of all of them can be degree nine but um it would be you know it's it's much cheaper to use lower degree constraints so for example cairo uses degree two constraints um but with degree two this type of stacking would be more you can't you can't do this kind of thing you'd have to yeah so so with cairo they use they do something different they have built-ins um to handle a lot of different things but it's it's the same sort of mental model of having separate something separate to address the hard things but they have to sort of do it and combine it differently from the way that we do it here makes sense makes sense all right um

i guess one of the interesting parts that you mentioned is how the decoder works like and the whole concept of mask should we go into that next yeah yeah so to talk about the decoder we first need to introduce the mast a little bit more deeply the mercalized abstract syntax tree that we use for representing our program and which also manages our control flow so let's look at how we would translate some program pseudocode into a mast and then we can look at how we interp how we work with that in the decoder sounds good so start with a sequence of instructions and each one of these you can think of as as a you know its own non-control flow instruction so this could be push pop add anything like that then we'll go to

an if statement and have some more instructions in here and else and then we'll do a loop and have some more instructions inside of our loop and then end our loop and our if else and we'll keep it like that and just keep it simple so to look at how this turns into a mask first we're going to take this block of instructions and we'll just make it its own leaf node and we call this

um we call this a span block to process this now we need this to execute and then this text execute and so the way that we do that is with a join so there's just a different type of node in the tree yes so this is a new node in the tree which is going to execute first this child first the left child and then the right child and in order to um when we put the program together this join is going to be the hash of this and of its right child um the right child now is going to be our if else so this is a not a switch split yes

um so this is going to be a split node and here we'll have our true as the left child and our are false as the right child so over here we're going to put in our [Music] j our b's and then as the right child we will have our loop which is another control flow node and then the loop has a leaf which is rc c 0 c1 2c i guess k [Music] so you can see here that the leaf nodes are all of the non-control flow instructions

and then these nodes in here are our control flow and and when we build i mean this is this is sort of the the translation from here to the mass but when we're actually building our mass to get that root hash that we need what we're going to do is here we're going to hash um well we'll hash our c's and then that's going to be our loop then here for split we're going to hash our b's and our um let me label this so we'll call this b zero so so the hash of this would be kind of just the sequential hash of all the uh instructions here and then you know you kind of aggregate it here right and same thing here but uh when you join them together how does that work um yeah so we're joining this

let me let me pull the decoder out at this point and we can sort of look at so the decoder is going to be some op bits that we talked about and i'm not going to go into that quite yet but then next to it we're going to have a section for hashing these are eight hasher columns and so we're going to put the things that we want to hash together into here so um let's say we have our what are we at we're at um let's say we have our split uh and we have this the bit representation of our split then we're

going to put our left child here i think join will go first or are you oh sorry i was just trying to address the point that you're done yes i mean if we if we're actually going to if we're actually going to take our tree from top to bottom which is the way that we should do it so what we're going to do is we'll take our join and then um the prover or non-deterministically puts in here the left child which takes up four field elements the hash of the left child takes up four field elements and the hash of the right child which takes up four field elements and then after that it's gonna recursively go through everything below this so we'll have a span

block that does the sequential hash of all of our everything that we need to do this is a lot more complicated how this happens but essentially when we end our span um we're gonna have the hash of the left child right here um and then after that we would do the right side so we would go for our split and split's going to have again left and right and um we go through it the same way and when we get down here after sort of recursively going through everything we get to the end and what we're going to have now here is the hash of our join um finally at the bottom and that's going to be our root

the root of our program the root hash is going to be right here okay does that answer your question yeah i think it makes sense but uh seems very complicated uh why why why would he do that yeah so there are um it is it is complicated and i've obviously skipped over a lot of detail but there are a few benefits here i have now erased our program so we'll have to just remember how it worked but this is an if else statement and so if it's true then we come over here and so we might say it's true if we have for example a one on the top of the stack if we have a zero on the top of the stack we would go over to our loop side so when we're actually executing it's going to be one of the two things we're not

going to have to execute both sides of this so let's say that it is a one on the stack that means we never execute this which means we don't have to unhash this and so that saves us this sort of a process here we have the loophash and we know about it but we never have to go through that last part to pull this out so like the hash of this is prover is going to provide non-deterministically as you mentioned yes exactly okay but the prover never has to provide this part not deterministically because we don't execute it so we can save on a whole lot of unhashing by only going through what we actually execute so for example you have complex program or like in the context of blockchain complex smart contract but you every specific you know transaction executes

just a small portion of it you don't unhash whatever is not executed exactly okay and so comparing that to our bootloader approach that we talked about where we had a sequential hash of the whole program you have to unhash everything in order to have your program there to run it makes sense so we save a lot that way there's another benefit to the mast um relating to what you just mentioned we can selectively reveal things so we said um the hash of our root node this is our you know root hash so we send we have that as a public input which means that the verifier sees it and the verifier doesn't have to see the rest of us now in the bootloading approach you either share the route and only the route or you share the entire program and the verifier sees the whole program so it's

an all or nothing thing but in our case with the mast we can actually selectively reveal parts of this because each of these each of these nodes is actually its own mast program its own sort of mini mast inside so we can choose to you know share this part um but not this part okay and so in a blockchain context again if you wanted to prove that no assets are created or destroyed during a transaction you could show something at the beginning of the program and show something at the end of the program to show that you are verifying those things inside your smart contract while still keeping the middle part of a smart contract secret makes sense but uh to make sure i understood fully so when you say share this part so

like the very the approver would reveal all of these a instructions yes but it would not reveal any of the boc instructions that would just reveal the hash of the yeah exactly okay make sense um now another question that comes to mind is that uh we have this hasher here like how does hashing actually happen in or like what do you do with it yeah so this all gets offloaded to the hasher trace that we were talking about the hasher circuit uh i mean it's a portion of our trace yeah but our specialized hasher chiplet that we were talking about earlier um and then we connect to it with a a special lookup column and so i would like to show how we do lookup arguments in our context i think the hasher lookup

argument is very complicated to show but i would like to maybe show the bitwise so the bitwise lookup happens between um between the stack and the bitwise uh well i should actually mention the op-eds i suppose a little bit because the the decoder is connected as well since the decoder um the decoder enforces which operations actually happening in the stack so we remember we talked about our flags before where we had our ad flag um that actually maps into the decoder

um the outfits here so we have seven bits that we turn into this flag and um we're representing it there so it's important when you say turn how how do you turn it on so um what we'll do is we'll say let's say we have um one zero one one zero zero one what we're going to do um this is going to be true when we evaluate this to true so in order to do that let's let's label these as s 6 s 5 down to s 0. and so we'll do s6 is already 1 we'll multiply it by 1 minus s5 we'll multiply it by s4 and s3 are both

1 as 4 times s3 then s2 and s1 we'll do 1 minus s2 times 1 minus s1 and then s0 is also already 1. so this is going to give us something that when this is our operation when these are the outputs representing our add instruction um this is going to equal one and that's going to turn our flag on and if anything else if it's not this it will be a zero right yes if any of these are different it's going to evaluate to zero here and that means all of these instructions are defined only only one of only the correct flag is going to be true at any given time and so we can rely on it to select correctly and so because we're multiplying seven

different hours i think the degree of this will be seven right yes so the degree is seven plus whatever else we need to actually enforce for our ad constraint though there are things that we can do to be more efficient we could for example sort of um define a specific limb that will apply for our you know arithmetic instructions or whatever and then we can maybe make things a little bit cheaper so there are tricks you can use but this is the basic way that you would go about it but even seven fits fine like for most um instructions you probably don't need more than degree one or two constraints exactly if we remember the constraint for add it was just a plus b minus c so it's just one degree so it's fine okay make sense

so um yeah so that's just to show how the decoder ties to the stack and now we can loop back to showing how the stack and the bitwise tie together for our lookups how we do our lookups between those different processors so um what's happening over here in the stack let's say that we have uh we have b and a and we want to do an and and so the next row we want it to look like z where z equals um a um bitwise and b all right so that's what we want to do on the stack and over in the bitwise processor

we have some way of proving this and i'm not going to go into the exact uh details of how we do it but basically it takes eight rows for us to do we start with our a and b as inputs and we get our z as an output down here and um we also during the course of this prove that um we actually decompose these but we prove that in the last row this is an aggregated element that equals our correct inputs and that this is the correct output so at this final row here we have a and we have b we have z and we proved that everything was correct and in internal you said we break it into bits and then do uh you know operations of individual bits and then we aggregate

it yes we decompose it we prove that everything we've decomposed to is actually a bit we then do the operations then we aggregate it back to get our output here and we prove that we aggregate it correctly so all of those things are constrained and this takes us um eight rows so zero to row 7. and so what we can do to connect these two things is have um a lookup column and let's call this we'll just call it p0 um and we're going to have it start at one and it's going to end at one and we'll enforce these with assertions that say you know at p0 at zero is at time zero is one and p0 at time n minus one is is also one and the assertion is

basically a boundary constraint yes it's a boundary constraint yeah um so so we'll say that these are true and the program will fail if they're not and then what we're gonna do is when we actually execute this in the sac we're gonna say um let's define a value x and we'll use some randomness from the verifier so we've got beta as a random value we've got um alpha and we'll multiply it by our a plus alpha do this a little bit lower down write it over here with our space so x equals beta plus alpha times a plus alpha squared times b plus

alpha cubed times z our output so we're we're including the three values that we need and um so just i understand where does this alpha and beta values come from like so this is randomness that we're getting from the verifier randomness that is very fire at which point does the very fire send this randomness after we've already committed to the i see so we basically build this trace and then we build this trace we commit to that and then the verifier sends the randomness and then we build this column yes so yes so we we have a way of doing these columns afterwards there's sort of a specialized way to deal with errors where you could do some extra stuff after and this auxiliary column is is part of that okay um so we do have to sort of commit to

our trace and say this is our trace first and then get this randomness and then we can do these lookup columns make sense um so we've got this value x and what we're going to do is when we call this in the stack we're going to um i'll do it from from this side we'll divide by x so then we get one over x here and then we'll keep it the same as long as nothing's happening and then whenever we're actually getting to the point of evaluating our bitwise operator because remember the stack sort of starts here and the bit y starts down here they're evaluated at different times then we're going to um multiply by x and that will give us our one and it will continue all the way down and we

make sure we enforce that it doesn't change um otherwise so it either it either performs this multiplication or this division or things stay the same and we can imagine let's look back at just i'll draw up here again our stack from our um from earlier so you can see our trace again where bitwise starts here in the middle right so let's say we call ours we call our and up here this is what this would look like our and is here and it gets divided out and then down here we actually process it in our bitwise processor and we multiply it back in now if instead we called our and down here

then it's actually going to be executed first on the bit y side so in that case our p0 column is going to look like it's going to look more like this we're going to have our multiplication come in first from the bitwise um and then it will stay x and then our stack you know comes in further down um and so we divide by x down here and then we're one all the way down so you can see how this will work in either case no matter where in the trace we called the bitwise processor or execute this sort of proof within the device so basically if we used up the same number of operations here as we did here and with same like result inputs and outputs then this will end up with one and one

and uh yeah awesome okay so and just to label this this is how we do our um look up argument inside of inside of mine and to connect things to talk to me make sense and um i'm just curious so we drew out that execution trace and then there are these columns like how many columns are in general there in the trace this is this is another one of those design choices um people you know minimize you can sort of make this trade-off between the number of columns you have and the number of rows you end up having if you have more columns you can define more specialized things and so maybe your trace will be shorter because you're doing more things across but if you have fewer columns then

probably your trace will end up being longer because it takes more cycles to process each thing so it's really an engineering decision how to do it now i know in cairo they have only about 20 columns or something it's very very small whereas in hermes they have like hundreds of columns in our case we've got somewhere around 80 i think um and for the auxiliary columns these ones that happen after we've committed to the rest of the trace we've got about three of those i think okay i think maybe a bit more than that but maybe yeah maybe we have five at this point but yeah yeah and there and there may be more as we find different things that we need to um actually so so just to specify we use this as a bus to connect these two

different areas and of those we have just a few but we can also use it to enforce constraints within a specific processor and we have more that do that too so there's really a lot of flexibility with all of these design elements awesome awesome well uh thank you very much i think uh it's it's very interesting how we can take the zero knowledge proofs and like build this virtual machines where um you know the same circuit can execute every every single program and then obviously these design choices are very interesting figuring out whether you want to use mast or you know boot loader or public inputs and a bunch of other things but yeah thank you so much this was my pleasure thank you [Music] you