ZK8: How to build a zk-VM - Ferdinand Sauer - Neptune

Transcript

foreign [Applause] high-level introductory talk so if you already know if you're working on a zika VM like um this might not be for you but if you want to build your own zkvm or like a bunch of them or just getting into it like this is for you so welcome right so what do you need to build a zqvm basically you only need two things the first thing is you need a VM and the second thing is a stark engine or at least that's how we do our zkvm you can do it in different ways but we're going to look at Starks

today so we're going to jump right into it and we're going to build a like maybe you can't even call it a VM but we're going to see so first level my first ZK VM what do we need well we need some sort of program memory I guess and we want to keep it as simple as possible for now um and so the program is read-only it is stored in a dedicated memory part and at any given address there's either an instruction or possibly an argument to an instruction then the next thing we have is a processor right that is actually

performing the computation and this right here is the process of design that my first dkvm uses these are all the registers we have available so there's one that counts the number of cycles that have already happened clock there is an instruction pointer that points into program memory instruction pointer IP there's a register for the current extraction the instruction that is about to be executed CI there's a register for the argument and then in terms of memory we're a little bit Limited in that my first dkvm only has two memory cells and the memory

pointer that selects which of the one is cardioactive and that's it so is it a VM you know you'd be the judge all right and we need an instruction set like what are the instructions that this processor can execute and there's only four of them increase you know plus one uh toggle the memory pointer point to the other memory cell jump to a given address if as an argument if the currently pointed to memory cell is zero and gracefully shut down the VM halt that's it right that was part one step one the VM so now we need to figure out how to

decayify that and I mentioned that we're going to go with Starks and um so we need two very important ingredients a the algebraic execution tables and B the arithmetic intermediate representation and once we have those we just do the rest of the Stark and that's not going to be part of this talk um there's links to resources at the end of this license you're you should check them out if you're interested it's really cool oh yeah this is what the rest of the Stark looks like yes you know a little involved and not part of this

talk right okay so uh here's an example program it is in the program table um there's an address the instruction sometimes it's an argument and yeah that is our first AET that's it right there the somewhat more interesting one I guess is the one for the processor so it is also a table hence the name and these are the registers if we have as we have already seen and we just initialize everything to zero except where that doesn't make sense and then we load the instructions into that and now we start executing um and

processor just records every stage it ever sees so we execute instruction increment and what happens is well the clock cycle increments by one the instruction pointer this is not control flows data increments by one reload the next instructions and the pointed to memory cell increments by one no big surprise is there and this is the next row in our table and then we toggle the memory pointer and we fill in the next row in our AET for the processor and like that we build up the entire processor table and that is the AET that's it

so that's step a done I was rather fast um let's move on to B the air okay the air goes hand in hand with the aat and the air makes sure that whatever lives in the at is consistent with the rules that we specify by virtue of the air um so these are what we want to have here is a bunch of multivariate polynomials that evaluate to zero if and only if our a t is consistent with our spec which we don't have but we all kind of know what the VM is supposed to do so there's four types of constraints

initial what's the value in the first row consistency a row has to be consistent with itself transition how do you move from one row to the next end terminal what's the last row and most of them are pretty straightforward for example memory is not initialized to zero consistency the memory pointer can only point to one of the two existing memory cells and it cannot have any other value the transition constraints those are usually the things where the meat is at so that one is rather simple oh yeah the notation here the prime and clock that means now we're comparing two rows in

our a t and the prime means we're looking at the second of those rows so it's like whatever the next value of that register is supposed to be so that one's pretty straightforward but the instructions themselves there are you know a bit more complex but not too much because my first dkvm is pretty simple so for example if the current instruction is Jump is zero then the stuff that you would expect to happen should happen for example the instruction pointer is set to whatever the argument is and memory consistency we need to take care of that right if the memory doesn't magically change

and then in our in my first DP VM what I want is that you can only generate a valid proof if you actually shut down the VM gracefully so you shouldn't be able to generate a proof If you crashed it if you just ran out of instructions or anything like that so the last instruction that you execute has to be halt that's my requirement right but these are not polynomials of course I expressed them because it's convenient as Boolean logic so how do we turn them into multivariate polynomials that evaluate to zero if and only if um the 80 is consistent well for most of them that's really really easy for

example the first one that's it that's the polynomial the second one well an or is just multiplication in polynomial speak so that's it what was for the third the fourth one is a little more tricky but by turning it into a disjunctive normal form maybe applying some of the Morgan's laws which I'm not going to run through um you have to turn this one into four polynomials because there's a bunch of ands in there and then you end up with this the last one again is pretty easy right that's it we have a consistent

processor nice I guess that means that my first dkvm is oh right no one's checking whether the program that we're executing is actually the one that the programmer wants us to execute right so we have a consistent processor but memory loading a program loading is not taken care of and there's two challenges with this little triangle here one is the program sorry the processor executes the instructions in a different order than they are stored in program memory right we do have some sort of control flow and secondly it executes them more often than they are written down in the program table because you can do loops

and um yeah so one neat way to get rid of this one little triangle is to just create two more but luckily enough now the problems are smaller size and by introducing this instruction table here we can overcome the two problems that I've just mentioned like the multiplicity and the order so I'm just going to throw the instruction table at you this is it we fill it in by first copying over the entire program thing and like we need to fill in we have a new column here next instruction or argument which is just copied over from the program and if the instruction is

the last one we just fill in a zero and we fill in Additionally the entire trace of the processor you just copy it over and then we sort that entire thing by address and now we can very easily in terms of air talk about what does it mean for this guy to be correct so here's our error for that table there's no initial constraint no consistency no terminal constraints because other tables are taken care of that but the transition constraint what we need to check that is that if the address stays the same so does everything else because the program is

read only it cannot change throughout the run of the VM and the second thing we want to check is that if the address changes increments by one that's the only change that is allowed then we sort of do a diagonal copy because yeah the next instruction should actually beat the next instruction and again these are expressed as Boolean logic right but it's kind of straightforward to just turn them into multiple multivariate polynomials and now we have a consistent instruction table that's pretty neat so now we need to only take care of the links between tables and for that we

modify the Stark engine yeah a bit in that we are taking in verifier challenges and we extend using these verifier challenges our algebraic execution tables to get well extended 80s for lack of a better name if you have one hit me up let's see how that goes I'm gonna brush over it a little bit for reasons that I will say in just a minute so by taking in verifier challenges what we can do now we have more columns that we can build and these green things there those are challenges by the

verifier and we can like sort of build a random linear combination of every value that we have in our row and that is I call that a compressed row and then you can feed that in to for example in this case a running product and using that if you feed that all the way through you can make a permutation argument just like in Planck for example the p and plonk right that's the permutation that's the permutation part and yeah the terminal down here that is then the integral part of the permutation argument and just like the AET in the air go hand

in hand so does the extended AET need a counterpart and that is the wrap the randomized air with pre-processing there's not a lot of pre-pricing processing going on in our case um but that's the term that is established and it means like the specify box here is a partial evaluation off the air because we need to supply the actual values of the verifier challenges partially evaluate our multivariate polynomials and get new ones which are then the wrap and the reason I'm not talking about

this in great detail is because Gerta will do that um at two o'clock on the main stage where she will talk about the power of multi-set checks in Stark based VMS so if you're interested in that part and you should be go check that out and thanks to her we now have solved our cross table linking problems and we actually have verifiable program loading so that means that my first right it's your knowledge we wanted to build a zero knowledge VM I remember okay um so what can we do to turn these things your knowledge well there's one

easy trick we just use a zero modern starch and we're set right well almost unfortunately the terminals that we have computed for our x80s they leak a little bit of information because they are sent to the verifier directly in the clear and that's not gonna fly in a zero knowledge protocol and the way we get around this is that the prover supplies random initials so now the running product starts at a random point and if you want to check it then you do not know anything like anything is

explainable by that random value this introduces a slight new problem in that how does the verifier know that the running product that was computed in two separate tables actually started at the same value because the very the prover now otherwise would have the opportunity to pick that initial value such that a actually incorrect running product or running evaluation or whatever you're using evaluates to the same thing even though it shouldn't and we for that we need a new type of constraint so far the four type of constraints that we've looked at they are per table right every table has some

of them potentially zero but you know in principle and the new type of constraint that we're introducing is one that links to tables or more if you want but for us it's just two and so concretely in this case we want to make sure that in one table the running product starts with the same value as in another table the random product starts with and that's it we have achieved their knowledge awesome let's take stock what is my first dkvm good for is it usable nah

is it fast how do you decrement again it's not fast is it useful can you recursively verify it how would you even go about that is it cool it's a zero knowledge VM of course it's cool so I give this one Stark out of five let's try and you know see what the users actually want apparently they want to somehow communicate with the with the VM so they want to have in and output let's tack that on level two ZK VM with IO

back to the drawing board two steps first build a VM then make a decay so we already have a VM this is it that's the same thing you saw you've seen before now we just say well there's a couple more instructions available to you now read write and read Secret right how does that change our Stark engine part well this is what we have so far and this is what we have now we have a new table for input a new table for output that's it all the other tools are already in place so just like that we've upgraded our VM of course you need to take care of the

air but I mean we're designing the things let the engineers take care of that okay is it usable yeah is it fast is it useful I would say there is an argument to be made and it might be somewhat involved that Yes actually now it is useful you still can't recursively verify that and of course it's still cool so this gives it to start out of five I talked about recursive verification here twice now what do we actually need for recursive verification so one part is we need to read

the proof for which we need IO which we now have perfect we need to do some future mirroring for which we need hashing we need to do some fry verification which means verifying Merkle tree membership which means hashing we need to check some commitments which means checking Mercury membership and which means hashing and then we need to do some native field arithmetic which our VM currently can't do but that's easy to fix later so apparently hashing is a really really big part of it let's try and tackle that level three fast hash zkvm back to the drawing board we need the VM

so let's use the one that we already have and hashing just two memory cells is kind of like that's not very useful so I decided to give it more memory it still lives in the processor because otherwise it gets a little more complex and we want to focus on the hashing part so now we have 16 memory cells available to us and the instruction set has grown a little bit we now have the instruction hash just like that but how does it work how is it implemented well first up we're going to tack on a new table the hash table

this is where the hash co-processor stores its intermediate values in the following way this is if you want to produce compute just a single hash usually your hash functions are round based and for these kind of ZK VMS you really want to use something that is um nice to arithmetize I know that not everybody's doing that but then you need quite you need to spend quite a lot of time engineering to make this really fast if you use something like rescue prime or Poseidon which is very nice to put into polynomials then you have a somewhat

easier time right so this is somewhat like the processor in that you just record every the result of every round of your hash function and then since this is an extended a t you can compress the road just like before and we want a different type of table linking argument here but the principle is still the same and unlike before we don't want to prove a permutation of all the rows I mean it's not a permutation anyway it's an evaluation but we want to have this conditional so most of the time you just copy over the value right for feeding in

uh you can you can see this running evaluation as a sort of bus so the processor sends 16 State elements to the corporate coprocessor via this evaluation argument then it does its thing where it doesn't update the bus and at the very end it does update the bus again which is the results of the hash and sends it back to the processor and that is it we just designed a co-processor and a bus between them and now we have fast hashing let's take stock I think it's still kind of difficult but possibly you might be able to verify this thing recursively now just because

you have hashing as a primitive as a native instruction available so three Starks out of five all right final level Triton VM which is the thing that I'm working on I'm just going to brush over it mention a few changes um right what else do we have in Triton VM right we have a coprocessor for fiddling if you want to do a bitwise xor that's difficult to arithmetize unless you have a native co-processor for it I mean there's other ways but that's how we do it we actually do have Ram so you're not limited in the amount of memory that you can use

um in fact we also have a stack we're not limited to 16 elements but you can like just keep pushing to it popping from it multiply two elements on it but that's pretty straightforward and I think like almost everybody here could probably just like get that working give them the tools that you now have and there's the jump stack also so you can make functions calls you can actually call return and not care about where you were being called from and all that stuff and of course the processor changes a bit you know but not not much you have a few more registers something that deals with the jump stack something just deals with the op stack something that deals with ram

and you know a bunch more instructions because after all we do want it to be usable and fast so now this gets a perfect five out of seven Starks yeah as I mentioned there is some further reading if you want to brush up on your Stark or get a deep dive into it um yeah feel free to take a photo of that or hopefully you can find them in the description below whatever that means and that's the talk thank you very much [Applause] Question Time are there microphones private one question only one question

I'm sorry about that very nice talk uh just regarding a political processor there's nothing to do to do this job correctly how do you check the computer and doing that check isn't it then slow again slow because you have to do it within your slow VM so the question is how just because you Outsource your hash I'm not sure the microphone was working thus I'm repeating it um just because you're doing you're Outsourcing the harsh doesn't mean it's fast and how do you check that it is actually a hash and doesn't that make it

slow again so yes you're all right you do need an air for the hash table which does the checking are you actually Computing the thing that you are supposed to compute and isn't that slow well that depends on the type of hash function that you're implementing so there are these fairly recent uh arithmetic uh algebraically optimized ciphers AOC or hash functions or whatever and if you use one of those then the polynomials with which you check but the harsh was computed correctly they are not of a very high degree which is really all that matters in terms of performance of your ZK VM so if you use one of those then no it's not super slow

I mean you still have to do the Stark part for that so you need to spend something some time on it some resources but it's not super slow if you want to do a traditional um like bit wise hash function you're going to have a harder time I know that there's people who are doing that and I think they spend considerable amount of engineering on that and I'm not sure what the performance is after that yeah thank you very much