ZKM: Implementing a Modular zkVM Using Lookups | Jerone van de Graaf - ZKM

[Music] hi my name is Jerome um we are pleased to present zkm is here in Denver we are pleased to to present our implementation of a modular zerge virtual machine using lookups my name is Jerome um stefen is on my left Lucas also helped prepare the presentation but he isn't here um let's start with the concept of a proof proof of knowledge for some computational problem a proof of knowledge um is a protocol that allows aover to convince some verifier that it knows a valid solution for some specific problem instance so an example is if you have uh the Hamil Onan cycle problem you have a graph and you want to know um if there exists a cycle if there exist a path that will visit each vertex of the graph exactly once um so the context that we have is we have aover we have a verifier and the Prov says well I know a solution for this instance of a hematon cycle and it provides the proof now um there for for every proof of knowledge there exist the trivial proof which is just the answer the full answer but for some um some context some applications this is not a good uh a good idea because there are two two contexts the Prov might prefer to keep the solution a secret so maybe the pro if we have a a larger example um the pro uh might pref prer to not reveal exactly what the secret is um and another context is that the the resulting proof may be too long for the verifier to check so these are two different different um different extensions of the proof of knowledge um the first one are called as are really called the zero knowledge proofs so the Zer knowledge proof is the property that uh um you have a proof that does not reveal information about the solution for a given problem uh and this is often implemented by performing a randomization a verifiable randomization over the problem instance and then show that you know the solution for it so in in the example here you we have permuted the the original instance and we show in the Premed instance that um cycle exists so so this would be an example of uh zero knowledge proof on the other hand we can have a different uh criteria we we may want that um the proof is short because in in some context we have that uh the pro is much more powerful than the verifier and so the verifier uh doesn't have the the computational capacity to to process the proof and to verify it so what we want is we want what are called suin proofs in which the verifier only has to flip random coins perform some checks on the on the proof that the that the verifier sent and then accept or reject so what what we are doing in the case of a succin proof is we are simplifying the work of the verifier at the cost of putting the burden on the approver it's so so um it's a setting in which we have maybe um on on the the ver the excuse me the the pro is is a strong cluster and the verifier can be a cell phone or we can have a context in which the prover is off offchain and the the verifier is is layer one um now the the context that we are applying these uh this proof of knowledge is the context of verifiable computation so in verifiable computation there is one step before the proof of knowledge because it's the the the verifier who is now the the weak user and is asking to the prover I have this function X um excuse me I have this function f I have this entry X please compute F of fact from me uh resulting in y so the idea in verifiable computation is that the approver will uh compute Y which is the F ofx and in addition to giving the result it will also produce a proof W which which shows that the uh the value of y is indeed correct and so important is that um we want this proof to be short because we want the the verifier should be should have very little work to do um now in the context of of blockchains this this proof of knowledge they they should be succinct as I said they should be non interactive we want to avoid interaction between the approver and verifier for a couple of Reason um and they can be zero knowledge so they can be they can provide privacy but they don't have to provide privacy um and so the the the problems to which we we apply these proofs of knowledge they can be um the the transaction transition function for Layer Two um which are so sort of Z rollups the execution of smart contracts which is the the Z evm so the smart contracts are then uh written in solidity and we have the evm that uh verifies the the execution of the contract and um we can have other programs which are the zvm so we have a program in our case it's a mips program and we want to verify the execution of the mips program and um the the technology that's being used for this are are snarks which stand for succinct non-interactive arguments of knowledge which optionally can be can be zero knowledge or not so how do snarks work um well this is this is a little bit high level but it gives it gives a little bit of the flavor a snark does something very surprising a snark will translate everything every computation into a pol IAL and this polom is expressed modul some some large prime number maybe a prime number with 64 bits um because I don't know that there's a lot of mathematics behind this but if you have a prime number you can add and you can multiply and that means that you can Define uh have a meaningful definition of what a polinomial is um so so having a finite field well it's easy to to add to multiply or to to exponentiate modulo this prime number for um bit operations things are a little bit more more difficult um so the first line that you see there the bitwise operation is is a test to see that the element in modulo modulo the prime number is zero or one and then we have expressions for the or operation the ant operation and exclusive or operations and we also have um a way to to combine to batch a lot of uh pols together without increasing the degree this is important aspect because what we do if we want to verify that P of X is equal to A and P of Y is equal to B then we we make a linear combination um of this well so the linear combination is of uh PX - A * Alpha and then pyus B * Beta And so this value should be zero if this condition is satisfied um so that means that um using this encoding this dising is also called a ization uh it guarantees that any any knowledge can be proven it it we can do the succinctness and the verifiable randomness we can make the proof non interactive using Fiat chir transform um nevertheless some properties are difficult to verify just using pols and this is why we use uh lookup tables so how does the snark work we have the original problem problem we transform it into a myips execution Trace we we then the execution Trace we have the the register we put it into a polinomial and the op codes we put this into a polinomial we combine the two and this we will giv us polinomial commitments and lead to random polinomial commitment evaluation and now Steven is going to give all the details okay thank you let's let me go through all the details with any example okay uh given that um the golum or the the high level language can compare it into mips and we got a sequence of the mips instructions like the uh the add instruction would be add register five reg six and write the value back to the reg seven okay and uh for the the right table it's uh when we execute each uh instruction we got the value of each register uh yeah and uh we go through all the instructions we finally got a TR table including all the values we I mean we we we we go through okay after we got this uh TR table then we need to apply some kind of tech uh technology like the continuation that means we um split the whole instructions or the whole table into different segments okay so each segment may have uh fixed uh instructions and then um here we actually we need to because we we uh have a trest table we need to apply the constraints on the each RW or cross the different R uh they meet so first is we um converts the I mean the each RW into a constraint polinomial like the see like the for the s for the low I the c i R5 R 6 r s equals to R7 minus R6 and uh minus R5 okay it's we cre it's constant polinomial so uh so along with the uh instruction sequence we have different uh constr nomial and then on the other hand we also have a trace polinomial that means uh the r1x r2x that we want to commit uh for the trace for the ex execution Trace okay as I mentioned we need to apply the constraints on the execution Trace so because the different instruction have different constraints so we uh I mean splits the instruction uh as put that t into different modu like we have arithmetic model uh CPU modu logic modu and memory module so different module uh has a different constraints okay and uh and of course we also need to make sure that the value they shared like the uh the different uh columns are identical okay um so after we uh got the uh models and we have the trace table we begin to prove each model okay we so for the pling uh we just use a stack that means we commit the trace by um FL and then we actually got different uh stock proof Okay so because finally we need to you know verify the final proof on L one so we need to join the different modeles proof by kind of proof composition uh okay so yeah okay I think I would go this quickly because it's uh just saying that we have different uh models and we produce different the proof for each modeles by the stock so for the stock I think I will not go through the details it just you know it's kind of the moer proof moer commitments or each we we we uh we mapping they trace polomia into the Moocher proof moocher tree leaf and then calculates uh the M roots and of course we uh use the M query to uh samper the uh to to to open the uh some points okay uh okay so that's what say We join the different proof into one that's we use the proof composition yeah for the proof composition actually we uh have different segments we first we generat this stock proof for each segments and then we um yeah so why we say the loot proof here because we have different uh table different TR table so we actually have different uh have multiple multiple uh stock proof for even one uh in instructions so first we need to you know combine we need uh combine the different uh Stacks into one proof okay so that's what I said the loot proof is the proof of loot circuits of the all the uh stocks and then we agregate the loot proof okay the so the active proof would be the aggregation soet over the two different root proof and finally we uh as all we know the stock proof is quite large it's maybe reach up to uh four megabytes so we need use some other uh you know SN uh algorism to compress the pro so that's here we use a group 16 and we can uh achieve a constant proof size about it's about um 200 BS and uh that's demo for all proof composition so uh yeah so it's quite easy if you can write a a good now program then use say go componer to compare it into the meeps it's quite simple and then you can use our examples in our GitHub rapper to split uh the mips into different uh segments and then uh generates the finess proof for all the segments Okay so okay so that's all okay so we we'll take any questions off offline okay thank you very much for your attention thank you very