ZK Hack Lisbon: Hacking on Polygon's Zero Knowledge Virtual Machines

Transcript

foreign [Music] I'm I'm Dominic from polygon I'm product manager of polygon maiden and we are here today actually with two zero knowledge virtual machines most of you have probably heard of the zkevm and ignazi and Jesus will later talk about the ZK VM and for when it comes to Virtual Machine the ZK VM we should use when you want to have great usability

um whereas we also have mine the product I come from and modern is a highly performant zero knowledge virtual machine that I want to show you today so basically with my VM you can write arbitrary programs on one of the fastest ZK VMS out there like we have some benchmarks comparing it with risk zero for example let me explain the goal of the Mind VM at the moment our goal is that we want to build a roll up which the Mind VM is the heart of and this roll-up extends ethereum's feature set

whereas this is the ZK VM scales ethereum obviously so it mimics its features one to one and with the maiden VM we can build a roll up that um it has different features than ethereum still secured by ethereum and so we want to provide an enabled novel and useful applications on ethereum using the maiden VM but today only the VM so I'm run very quickly on zero knowledge virtual machines most of you probably know that please excuse me but some might not so a normal virtual machine has inputs like an initial State and a program

and outputs a final state and the zero knowledge virtual machine like the maiden VM does exactly the same we have an initial State as an input we call it stack and like we have programs that we can input to the modern VM we get a final State plus we get a proof we're gonna prove that the mind we am computed with this initial state that program exactly that output and we can add a witness like a secret input that only the prover knows the verifier does not need to have access to the witness so I can add secret data or data I don't want to show to to the verifier

this is a zero knowledge virtual machine uh the proof is very fast to be verified might be might take longer to be produced and yeah the witness is only known to the program okay it was a very quick rundown but um yeah like compared to writing circuits our goal is that the Mind VM it should be easier to use easier to write programs in our Turing complete language modern assembly um it's yeah that's why we also have like the universality so you should be able to write any program on a roll-up also any smart contract that can then be

proven with the Mind VM it should be relatively simple when it comes to the constraints so a small set of constraints should be able to uh uh serve the Mind VM and um obviously we also want to enable recursion and we have a branch already that where you can play around with recursion I show it to you later um so when you want to use the Mind VM you have to write in mining assembly for now and it's an basically you write programs in writing assembly and they get compiled into something that we call the program must I will explain in a second

and the program masts then gets executed on the maiden VM so for you my assembly is a turing complete loan level language for writing instructions so this here on the bottom you see a completely valid model assembly program it adds one to the stack it adds two to the stack it adds them together and then a program ends and this you can prove and this program basically gets translated or compiled into what we call the localized abstract syntax tree or basically raw mindvm instructions operations and um yeah and these operations then

can be directly read but I will show it in a second how it looks like um yeah so far with the theory but because this is a workshop I don't only want to show uh stuff but I want you to play around with it so if you want you can open this playground of it's easier on the laptop I also have the link handy just switch to the link the laptop it might be a bit easier here's the link so it's Xerox polygon Maiden Dot github.io slash examples

and you should see something like that yes you see it yes okay so this is exactly um yeah this is our mind VM running in the browser and I just want to show you how it works such that you can maybe hack about it or hack on it so um we have here the input files or the inputs like what I said before like we have the init the the stack in it and uh like our witness which is here called

advice stack uh we have outputs none so far um and we have the code like exactly the code that I showed you before right so we have one and two being pushed to our stack based uh system here and then we add the two top elements of the stack so let's check it out when I run it I get three this is the stack that I get back right okay so then I can prove it so it proves in 300 milliseconds I also get three and something which is called an overflow address

which I will explain later but then so nowadays the proof let's look at the proof okay it's not very helpful but it's super large right but this is to prove how it looks like um okay and this now I can verify foreign like here select another program one second can you execute the sample program

does it work with whom does it work yeah nice can you proof and verify the computation of the one to 1200 Fibonacci number there is an example program called Fibonacci and see if you can proof and verify the computational outputs of the 1200 does it work nice that's cool and can you look for the program like the collapse sequence program and maybe at a break point right before the while loop starts

and try to go with the debugger exactly to that breakpoint I think it's just right break point as a minor assembly instruction thanks I can also show you maybe it works anyway because you're does it who with whom does it work debugger I just also do it here then you can see it so we have this collets program which looks like this

and I can add a break point for riding breakpoint and then it's a bit too big I can click the debugger whoop starts the debugger and I can basically fast forward to the break point which would be here you see I'm now at the breakpoint the assembly instruction at clock cycle 11. does it work for you yeah nice cool um yeah like maybe one other concept is the concept of what clock Cycles in the VM

but maybe you know that already this is how we measure you know like this is how we measure how expensive a program is like the smaller the clocks it's like all the trades land of the program the better it is to prove it like the faster it goes or less resources we need um cool so this is our playground but I also want to show you our CLI um and maybe this I just show you but you can basically clone the mine repo and I will send the links later um so and here again we can

so here I have the Fibonacci program which I can show you so in modern assembly second like this here it was hard to show code and this is our Maiden assembly basically how we can compute the Fibonacci number and you've seen that before right when you calculated 1200 number um and using it in CLI basically looks like this and I can so I yeah this is the executable here and I give the command so I say prove it please my my assembly file and then it proves quite quickly

and this is now the 1000 Fibonacci number um and I can also here I have the debugger so instead of proof I now say debug one second I just make it make it way bigger and um so okay one second reading program file fail to compile program Source cannot be

an empty because I deleted the program also good okay now here we can also have a debugger uh like um and you don't need to know rust like the Mind VM is written in Rust but uh you can with the simple debugger and these input files you can just also create a maiden program and prove it and here you can also have like different commands next always steps another clock cycle I can again add break points and go exactly to that or I can do like show where the memory is like whatever you need to debug and also please provide feedback if there's something

missing that you need to debug that we don't show here and um yeah what I also wanted to show you is our newest feature recursive verification and recursive verification that we need especially in the blockchain case to compress um many proofs um is yeah something that we just built and what it actually is is um when you recursively verify something then you prove that you verify approve correctly right so I know like we have the

verifier that basically when we think of this playground when we click verify then we send there the proof the outputs and the inputs and the verifier gives us a one or two if everything is correct and like I can also run this verifier within the Mind VM and create a proof for it and this then is requested verification most of you probably know that um so but that is quite complicated to build and um so I want to show you the program basically so we had this initial program like um we repeat 32 times that we swap every swap a one and added so it adds

yeah okay and um and then like this like the outputs and the proof of this program basically together with the inputs are then the inputs of my recursive verification proof and this basically of my workers verification program and this program actually is super small it just looks like this and I can run it and I will show it to you always good to show live demos um let's check

right it takes quite a long time so it's around 2 to the power of 22 Cycles I guess try to push it yeah here it is a recursive verification proof that you can also hack on I know who of you already or who viewers considering hacking on the Mind VM we can talk about bounties everyone already has a hack or you don't you don't hack at all yeah we'd like to hear about Matthew nice so incentivize

um well our challenge you get you could get two thousand five hundred dollars if you build an awesome application using the Mind VM and an awesome application could be an incomplete information game like Stratego or ZK Mafia but it could also be something in the realm of D5 so a private order book auction um or something that makes the world a better place or whatever you can come up with that would be really cool like more applications and a little bit easier maybe might be

to help us to improve the mind and standard Library like for these modern assembly programs we have a standard library and that you can simply import that you don't need to write every uh everything from scratch and there are still some things missing so elliptic craft cryptography for example could be a cool project floating point or arithmetic um yeah or decoding encoding or P strings which we will need when we will build our role up to ethereum are there any questions to that yes

the stack in memory like the initial stack like or the stack in theory can be very big the initial stack is bound to 16 elements but you have the advice provider but you can add like um like local stores and spasmaker trees so lots of data compressed in form of a Merkel tree yeah and but the like this would be the the witness that the secret input where you can add lots of data I can show you maybe uh [Music] that came you see like this is the initial

um input the second Port which is bound to 16. um but here you see a whole Market store and Spas Market tree like still a small one with only two lists that you can add but it can be as big as I don't know if there's a pound sale bound bro 64 64. okay [Music] so you can let it get as deep as you would need it to be I'm happy to talk to her

any more questions cool I think we are exactly 20. so now uh our colleagues from the zika evm you can just click okay so hi everybody I'm Jesus I'm working on the polygon dbm project and what I want to explain you basically wrong that it's a Assembly Language that we use to build the KVM so this DK room is an assembly like

language like we see like now in Miami that will Define the program for our GK JK machine basically it was with resistors that here you can see a bunch of them and it also can use a build defined estate machines so what I'm going to explain a little bit is a quick over on a higher review on how it works and how you can interact in an easy model and then as you will continue the with a little demo thank you so [Music] um basically you can interact with it with the resistors the resistors are refined with every resistor has eight slots

every slot is an element of an old Deluxe field and basically these resistor is what we use to basically like do most of the operations or interact with the plastic machines that you will see later as you see we have the generic resistors that it will be a b c d and e and also we have like a special resistors like it will be like the state route that also has eight Fields eight goldilock element fields and another resistors to like very tricky Special Operations but with this to start I think it's more than enough and since we are doing as a KVM we build the Ziggy Roman the tooling of the city room to be friendly with the evm so for example to perform 256

operations which is the field that the ABM Works basically we divide these numbers in in eight chunks of 32 bits that's why we have eight Escalade a test load for every resistor and then we can we can do the operations so now I will I will start to the basic operations that you can do with the registers basically what we can do what you can do with the resistor is assign it a value so here we have an example that I want to sign a 1000 to the a what we are doing here is like first we assign 1000 to what we call op the op is an intermediate resistor that we use like for do operations that you will see a lot so you have to take a man like the

left side of the way of the of a line of an assembly it's always assigning the op so in this case we assign 1000 to the op and then we put an arrow to the a so this basically means that the in the next step of the operation the a we take the value of the op that in this case is 1000 so basically we are assigning 1000 to 8 but I want to explain it all the flow because then you will understand more things uh also you can you can Define bigger numbers like a more more than a Goldilocks field if you put an N then then when the compiler will understand that it's a big number and you can like fulfill all the of this equation right in the a761 all the all these lots of the register

okay the second thing that you can do with registration basically you consume for example a plus b and assign the result to the C uh in this case as you see when you zoom two resistors in fact what you are doing is like suing like individually every like a slot of the resistors so the op 0 will be equal to b0 plus a0 and and so on uh take a you have a ticker but every of these resistors can overflow around the flow and it always will overflow and underflow in the Goldilocks frame field so you have to take in account this to to your operations and in this case because we put the arrow we are we're saying that in the next step the C will

take the value of the op that it will be the result of this sum um yeah basically you can do the same with the subtraction it works the same way I will go to the multiplication so in this language you cannot multiply two resistors like a a multiple day but you can do it with a constant basically if you multiply a register by a for a constant you are multiplying all the slots and one more time you have a underflow and overflow in every single slot so you must take in account that and there is things that you can do you can like a add and subtract and multiply in the same line of assembly multiple resistors but what you cannot do is like multiply

I yes multiply by a constant sorry multiple resistors but you cannot multiply to resistor by each other or you cannot use more than one constant for line in assembly for example a multiply 2 plus b multiplying seven you cannot do this so I try to put the restrictions here that you can do and what you cannot do and well I will pass this slide quickly what I will just show you is like the typical registers that we use to perform the the most common operations but we also have defined it uh one slot resistor that it's just one called Deluxe Prime that we use both for very specific operations maybe for interacting with some plastic machine or to keep tracks um to some value for

example we have a basically contest we have a resistor that basically for example counts how many binaries or how many pickaxe we use in this execution and we use this number to like um to make a safer execution you will see more on this later but basically like let's say special resistors to keep track of um then very specific operations okay what you can do also is Define labels basically to Define level you have to put a name and two points and basically it is this is good for redness of the code and also you can use it as a jump destination instruction that you can jump to some

levels and also some Commissioners that you will see okay okay we have also variables uh basically the variable variables is is used by the memory steam machine that I will show later and basically there are two type of variables are the global ones and the context one the global ones can be accessed always and read it always and the context one it depends on one of the special resistors that I said before that it's called context basically this helps us to separate a memory regions and this is very useful for example when you are working with ABM because every time you do a call to a contact you open a new context with a new variables so you can you can use these to like

separate completely the memory regions and and work with them and here's an example of defining a global variable which could be the chain ID that this doesn't attend in all execution or for example the destination address that can change in the middle of this execution it's very common to use it as a context variable okay now I will explain how to use the S3 machines um basically what we see from now is like basically using the resistors and with the with the zika ROM you cannot use the resistors but also use the pill SD machines that you you can Define before and basically we Define the state machines to work with the AVM so for example we'd find a binary State machine

that basically it's prepared to work with 256 bits to do like the the like most common operations like adding subtracting doing operations and stuff and basically this like more useful than what it was before because for example in the example we can see that you we can we can add I A and B and we will add this number in the whole 256 56 bits so this operation will not underflow in the Goldilocks Prime but in the 256 bits that will do it also in the evm so let's say we we with USD machine to do like the arithmetic operations that you could do it in the evm in a more frame

machines you can you must always use the same resistors in this case for the binary listening machine we always use the A and B so in order to use it you basically have to define a number in layer where we assign a number then we assign another number to the B and then we add the number and assign the result to the C okay and now it will explain basically using this in binary there is something that we call Curry basically a curry appears when you do a compression or you are I can do a comparison and your compression is true for example you put an equal and the four resistors are equal so you have a carry and also when you have like when you do an additional

subtraction and you have overflow and underflow respectively so you can handle this type of system of operations with a DMC jumps is a special operations and basically it takes the carry of the state machine in the same line and in this case MC is like jump carry so if there is curry and those reaction that in this case is jumping so this code that you see here basically compared to non-personal and if they are equal that it's the case we will jump to a level that is called read code it's like a very common operation okay and one another steam machine that we use a lot is like the memory one

basically what we allow us to do is like low out and store uh things and do a lot of extra resistor values basically and it does not need any resistor in particular like the binary that it needs the A and the B basically it just needs like a variable uh that we that I explained before what what they are and basically you can store values and lower values using like the same variable as you see in the in the example let's say like the most common ones and to have an overview we have more for example we have a Kika casting machine we have a positive honesty machine and so on and you can check in the cheat

sheet I think if more or less you understand the the behavior of these ones and that you have to use always the same resistors and what is the op you will like the other ones are more or less straightforward but if you have any questions you can always ask us for sure okay the early testing machines basically we use it to to verify multiplications because as you see since now we don't we do not have anything to verify multiplication basically to the Overflow of the operation plus the op so how to use this I got an example code

here basically we Define the a b and c and d and at the end you call the added to the result uh as you see there is a like another operation that you can explain that it's like in in this case basically what we can Define here is like executor functions you can call a JavaScript like an arbitrary function or basically operations as you see here like musically multiplications exponentizations whatever you want there's like a free input like an input that an Executor puts directly and the idea of this operation is like you like pre-calculate the multiplication of the two numbers and then you verify them using the array testing machine so I hope this gives us give gives you a little bit of overview on how we use our

zika ROM and now ignacy will continue with um an example thank you so much do you have any questions foreign okay first of all um my name is ignacia

I work at the ckbn team at polygon with with Jesus I'm going to explain briefly what's the workshop about um well first of all the Bounty it's like a 5 000 matics that will be splitted in the 10 best proposals of optimization of the code of the secret ROM or the smart contracts from the smart contract side I think that more or less most of the people know about their gas contribution so we are talking about and gas optimization but but the secret ROM probably it's something more new so now I'm going to focus and to explain a little bit about um the room optimizations and how does

it work and how we measure the performance of the secret room and I'll give you some some examples to measure this first of all how we measure the performance of the GK Ram well well this the repository here there's a readme with everything that I'm going to explain now explain it step by step and this if you really want to participate in this Workshop you should definitely look at it and to find it Well you just want to search for my name on GitHub and repository it's called this one so how we measure the performance of The Secret ROM of a part of the goat of the

sigurum to do this we use a metric called counters and what are counters when we create a batch of transactions that have to be processed by an Executor this executor has a limited resources executor is the like the service that runs the complete code of the secret ROM this um these resources are measured with one metric that we call counters there are different kind of counters that they are spent when you do certain operations of the secret room some of the operations that Jesus has explained for example there's a counter called binaries that is spent when you do a binary operation or

um there's another one called kickex that is a spend when you do a cooperation so what I'm going to show now it's just some example about how can I measure the performance Encounters of a part of the code of the secret room to do this I will do a very simple example with the code of at in in this readme at the bottom you will see some useful links that will definitely help you to to do this Workshop one of them we actually have to use a lot in my day-to-day work it's the evm dot codes first of all

let's check what the ad op code does most of you probably already know but this is a very simple up code of the ethereum virtual machine that what it does is the addition of 256 bit integers that are in the stack and it outputs the the addition so let's see how is this logic how is this reflected in um it's really good okay so this is the code of the ad

operation first of all we have to check if we have enough Contours to do this operation to do this we take first of all the steps the steps is one of the counters and each line of code execution it spends one step and the other one are the binaries the binaries is the one I said about that it's a spent when you do for example another operation we can see that operation here at the bottom yes okay so after checking the steps we do another check which is the stack underflow we need to have at least two

numbers in the stack before doing this operation because this operation will waste will spend to two positions so in case we don't have two numbers on the stack the stack point that is pointing to the current size of the stack we have to go to the stack underflow logic another tick as this is an ethereum virtual machine we have to check if we have enough gas to perform this op code this is done here gas is a registry where where we store the current gas of the execution and this this level gets fastest step that has a percent at the beginning it means

that it's a constant you can check the values of the constant in the constant file and take us I will gas faster step has a value of free because 3 is the cost of the op code at so we put this the reduction of the gas faster step to the gas to a and then we put we update the address history with the a value and in this term N means the negative this text that gas is not negative so that we have enough gas to continue with the execution else we will jump to the out of gas finally

well not finally but we go to the um to retrieve the values of the stack to do the operation we put on a the value at the top of the stack and OMB the the evaluate juice before the top one and finally now yes we do the addition operation and we store this operation threshold to the stack and we jump to the next of code execution which is this logic it's done in the in the read code function okay so

an example of optimization here that I've put on purpose will be of the musician of steps here in the tech out of gas we are doing you are we are using two steps because we are using two execution lines to do this logic but it could be done directly and setting the result of this operation directly to the registry of gas and then jumping and we can do it just this way this way you we don't need the the

following line and we are doing exactly the same logic but just with one step less but going back let me show you how to know how much steps is we are using for this op code we have some tests here in the folder counters for each one of the opcodes well there are some missing but most of them and the op ad this is a test I'm not going to go deep in the logic of that test but you can use them with everything this is splitting it in the renewable just to to show it here we have a script that's also in the content folder called

counters executor.javascript where you can run a test a unit test of an OP code and see the output the output will be the number of counters that are used for this step for this opcode so if I want to run the code of the up at I just run this this script and it outputs me how many steps how many sorry how many counters um I've spent to do this this logic with this one binary and 15 Steps with the optimization I did before if I run the script again

you see now that the number of steps has been reduced by one this could be considered like a possible from optimization it's just to give you a novel idea of some proposition that you can submit for for this Workshop you have the code of the secret room available to check for optimization simple like this one or some more complex optimization as I said you have everything here in the in the readme of the Repository also there's a big explanation of every one of the of the counters that can be optimized

there's also an example of how to put logs in the ROM in case you want to well I think if I can put just to show it you can put here for example if you want to know the value of a log and when you run the test you will see at the top the value of a which is two on a scalar do two and X and last well to submit it it's explained here but it's doing a it's you have to do up here to the repository with your proposal and this will be reviewed by us here you have some useful links about

the Audi reports we had recently in the different repositories and also the audit of the smart contracts and here you have also if you want to go for the optimization of the smart contracts you have the repository of the solidity code of of the bridge and fine I I wanted also to mention ah this one um in case you I mean this is like very easy for you we are also open and we encourage you to if you find some vulnerability issues in the code of the room or in the smart contracts you can apply to immunify which we have

a position in there where you can earn up to one million dollars if you find a critical a critical back but there's also medium box with low earnings but also very interesting and well we're going to do this if you well if you find yourself like you can find some possible bug about it so that will be everything from my site and from you you participate on our on our challenges we are waiting for you thank you very much and if you have any question to us now it's a moment no sure maybe later if you want sorry

people what the yes okay so that's all thank you very much [Applause]