'zkEVM' - Alex Gluchowski

without further ado i'd like to kick us off with alex's talk welcome to the talk about zika vm the technology that will extend zika roll-ups from application specific functionality to generic programmability um this has been considered a very difficult task uh and it was in in fact impossible up till this year and many people thought that it will not arrive up to a few years from now but i am uh ceo and co-founder of metalabs uh the company behind the zika sync protocol and i can attest that zika vm is coming to ethereum this may on the test net and uh in summer hopefully to production and in this talk i'm gonna go into the history of the ideas uh behind generic computation as your knowledge proofs and we will demonstrate why it was not possible what changed what would breakthroughs actually make it available for us today and hopefully i'll be able to give you a good intuitive understanding of its design i will assume that you have some basic zero knowledge proofs understanding if not please watch other videos we don't have time in this 20 minutes talk let's start by recapping quickly how zika roll-ups work we have a state of our blockchain or a rollup with some accounts they have some balances some some data uh they are packed in the merkle tree we have a root hash of this mercury serving as cryptographic commitment to the state and whenever the state changes because we're applying one one or more transactions to it the root hash will also change and we can define this the the transition with a so-called state transition function so whenever we have a block uh the new root hash will be result of the state transition function from the previous route hash the transactions uh data that are involved in this block the accounts that are modified by those transactions and the merkle proof miracle proofs for for for this accounts and this is all information we need to to construct a new root hash this is in fact which you would place in a stateless client to verify a block uh so if we only could implement the state transition function as a zero knowledge proof uh this would allow us to implement uh a any type of zika role and uh this uh we actually have this so zika sync is live on mainnet since june it's been used for payments very actively and we have the uh the very efficient provers very efficient uh argumentization techniques uh that is frameworks that that convert the algorithms in the state transition function into the form which is uh digestible for zero knowledge proofs we have all the servers for infrastructure around it the smart contracts so all we need to uh to do in order to support generic computability is to make sure that this the the generic smart contracts can be efficiently arithmetized and this is a big challenge the arithmetization is a process of converting the function into uh what we call an arithmetic circuit uh it's a directed acyclic graph where the inputs of your function are the initial nodes and then you you go through a sequence of friend network of gates each of the gates represents an operation of addition or multiplication in a finite field and eventually you you you keep accumulating your results and you get to the final output and you can imagine it can be pretty complex uh if you have a big algorithm so something like uh simple arithmetic operations are very cheap you can do them with one gate logical operations will take more gates uh hash such as shutter 5 6 or even k chuck will take a lot more of those gates but that would be doable the problem we have or the challenge we have is how to make it generic why is this a challenge if you're familiar with your knowledge proofs you know that the verifier which in our case is a smart contract on ethereum must know in advance uh the circuit so the circuit must be fixed you know you can't uh you can change it on the go you define it once then you make some computations to generate a verification key and then you use this verification key to check the proofs now uh with generic smart contracts we want the users to be able to define the contracts and deploy them on on this chain permissionlessly which means we cannot rely on a single static rigid arithmetization of one one like fixed state transition function so we need to find a way how to uh have multiple contracts coexist uh so let's let's go through the history of ideas that that were tried in this area we will start with uh an approach called tinyram which is already eight years old and uh this is a a really fantastic idea it solves the problem by saying let's create a circuit which verifies not an execution of a single like a single algorithm but let's make a circuit that can verify any algorithm by verifying the execution trace of the program the way we do it is uh we assume that we will have n steps of execution you can think of them as the cycles in in the processor and at each of these steps what we're going to do is we will read the inputs and the op code from the program counter and we will uh we will do all of our operations and then we will select the result of only the or the one operation which actually is supposed to be executed at this step so um this gives us a quadratic complexity or like number of steps multiplied by the number of operations and the number of operations must be relatively small so we we we would go for something like risk architecture with a small number of opcodes uh which must be relatively equal in cost um and we could then prove anything how it works to give you a better more intuitive understanding i made this model in a spreadsheet let me show it imagine that i want to write a program so i want to turn this spreadsheet into a universal interpreter of a program i will provide my program here in the yellow columns with the type of operation at each step and the operand and i want this program to be executed every time sequentially so like each step must be applied to the result of the previous computation we will start with accumulator uh with the value zero for example and then i'm going to add 13 uh subtract five uh multiply this by three and so on so we're going to support three operations add stop and move um and as you can see when i change something here the the all of the computation changes starting from this step and finally in this cell we will have the uh the result of our computation of the application of all of this program so the interesting thing is i can modify the program and i can modify the inputs but the um the the spreadsheets itself the formulas or essentially the circuit which i use to produce this final outcome remains the same and if you look at how i constructed this circuit um at each step i do a simple computation and it's the same computation for for for all of them and it's just a simple formula which does the execution of all three of our operations addition subtraction and multiplication and i use this simple naive approach to to select just one of them right so like if if the operator is add then i will just take this result right because i will multiply it by one and not by zero uh if the operation is sub i will take this result small this result and i just add all of them and i get only one uh outcome uh so like this is how tiny ram works so in this example we have here only uh like static problem without jumps without comparisons without memory access but all of them are possible to implement we have some very efficient models that could be used uh for tinyram the problem is that it's gonna be pretty expensive if you compare a program written like handwritten as a circuit uh to a program which runs in a tiny ram circuit the tiny ram must be approximately thousand times larger in the in terms of the number of gates in order to uh accommodate this program and for some simpler cases for some just for simple computations this will work and even for some yeah uh yeah actually even even for simple hashes that will be already too expensive but for hashes that are uh required for evm that would be prohibitively expensive like we won't be able to support it the cost will blow up immensely so this doesn't work uh it's been there for eight years but it remained a very theoretic approach uh until recently because like not usable so we looked at this uh two years ago and we thought okay what if we use the recursive aggregation uh so we it's possible with your knowledge proofs to construct a circuit which verifies the proof of a different circuit and we can dynamically load the verification keys we can verify circuits of different types um and there were approaches to this uh the main problem was was the cost of constructing such a circuit which was solvable by using cycles of elliptic curves so we could uh we could have like each user will define their own circuit or like each each developer of a smart contract will define their own circuit publish it on um on the roll-up and then the users will take the circuit provide the proofs and then the the aggregator will take all of them in the block and produce the the proofs of intermediate results it can be nested many times in a tree-like structure until we get to the final proof of the entire execution of the block the problem was that cycles of elliptic curves were not available for efficient computation on ethereum because we lack the precompiles we only have a pre-compile of bn256 on ethereum this is the name of a curve we use and bls is coming soon but uh but like nothing that that supports the cycles of of course so our first solution to this was two years ago to come up with eap 1962 we implemented it at metalabs with like two we we produced two different independent implementations one in rust one in c plus plus we made a lot of testing uh fuzzy testing uh a lot of discussions with core devs uh but eventually the community deemed this to be too risky back then and like too big to be compiled to include and it never got adopted and i can understand that uh for a project like ethereum being more on the conservative side with regard to what what's going on on the mainnet uh is perfectly justifiable so okay we thought what can we do else um and last year the aztec team came up with a number of interesting uh ideas on how you can structure elliptic curve arithmetics in a plonk circuit in a more efficient way we looked at that and we thought this is the perfect candidate for us so we went ahead and implemented the first recursive snark on ethereum using plonk we submitted it last summer in august for the reddit skating challenge and we actually implemented it in production in and launched it in january this year uh for our zika sync um rollout for payments which made the roll-ups this roll-up indefinitely scalable so we are we are now only limited by ethereum block size for data availability but not by uh by the zero knowledge proof computations because we can construct this tree uh with as many blocks like smaller blocks of roll-up as we need to submit on ethereum in in verifying one single one single check um the problem with this solution is it's not turing complete it required us to implement a new programming language we called it zinc it was rust-based and it you would need to to rewrite your programs in a certain way you would need to avoid unbounded loops avoid recursion and also think about how you structure your branching because if you if you have too many nested branches all of them would have to be executed and it could blow up the complexity a lot we thought okay for most d5 applications this is probably not going to be a problem they are not as complex they do not require that many computations a lot of programs are written in viper which are which is also a non-tiering complete language uh but then we realized that people actually really really want turn completeness people wanted to have uh evm like we got this market signals that people really wanted to take existing programs written in solidity reuse the tooling they have reuse the audits they already invested heavily into and just like not need to learn a new language and rewrite stuff so we thought okay what can can we so can can we embrace this challenge and actually implement them uh so we looked at the third approach which would be um what if we could optimize tiny ram to make it more efficient for for this specific use case and what brought us to this idea is this observation if you write a smart contract in zinc like manually handwrite a circuit for it then the smart contract logic itself would take a very small fraction of the prover cost structure and the bulk of the approval costs will go towards access to memory access to storage signatures hashes other heavy operations so if we could apply tiny ram to this small fraction to the actual contractual logic then even thousand times overhead would not be a problem because overall it will not make a big impact on the uh prover costs for this transaction like maybe it will just increase it twice or maybe by 30 by 50 uh and the heavy operations we could write specialized circuits for them and and we what we could do is like take our tiny ram circuit and split it in parts i have one part for actually tiny ram with with the implement with execution of arbitrary trace of op codes and then have signatures and hashes done as separate parts of the circuit which can be addressed by by the by this operations now the problem with this approach is you can't really have too many of this specialized operations like you you have to you like maybe you need to pick one or two because otherwise it's an impossible um optimization problem to pick like what fraction of the circuit should be reserved for each of the operations because if you if you just reserve equally equal uh number of gates for you know like for storage access and for k hash and fascia to f6 then it would be very inefficient if some block does not utilize all of it because the blocks and transactions are very heterogeneous you know like one transaction might require a lot of storage accesses uh another transaction does a lot of uh ddsa signature checks so you need a lot of catch-up hashes and yet another transaction uses shatter 56 for some reason so like it's not clear how to how to like dispose it and this is why it's not suitable for a gk avm it is suitable for generic programmability so you could write a separate language and force developers to think about it and make certain trade-offs and like only have hashes for example and build everything on top of cryptographic hashes you know like not okay shocked not sha 256 not ethereum compatible uh and i think this is the only approach which you can do with starks and this is very efficient with starks for for the reasons of how starks are structured uh but it doesn't allow us to make zika vm and this was the goal so we we could not go for this and this brings us to the final approach which we actually implement in zk sync 2.0 which is a combination of tiny ram optimized circuits for specific heavy operations and the recursive aggregation of all of it and the way it looks like is this we have transactions um like users submit transactions in form of uh or smart contracts in form of byte codes we have separate circuits of different length struct structured by powers of two for the execution of the tiny ram part of those contracts and then we delegate all the heavy operations to specialized circuits uh which are then aggregated recursively along with all the proofs for the transactions and if we need more of ketchup hashes then we just add more of these circuits to the mix if we need more storage we just add more storage if we need more eddssa signatures we add more more of those circuits uh and we can efficiently aggregate any number of them the way i described before to get the proof of the execution of the entire block and uh we also uh heavily optimized the the specialized parts over the course of the last year so we added specific things for two five six bits arithmetics for we have very efficient snack friendly hashes we have pretty efficient non-snark friendly hashes as well because we we take advantage of the plonks custom gates and lookup tables and this gives us a boost of 10x uh or or even more in some cases uh so we we can do it very efficiently um the way things work with zkvm is you take your code written in solidity for example like the language you know you compile it with your normal compiler into you and from there you we have an llvm based compiler using a lot of optimizations from llvm it's a great platform for compilers uh to produce the zkvm byte code which you can then permissionlessly deploy on the smart on on the zika roll up and execute and we actually have done a simulation on we took the transactions from l1 for some uh frequent defy use cases we fetched the execution trace and we looked at what the prover cost will be in this case for us like with overall costs with recursion with the heavy operations with the tiny ram part of it and the we we came to the prover costs of like one to two cents for for any transaction we analyzed uh which is very doable and on top of that you will have to pay the cost of data availability which depends on the on the guest price uh if you use zika roll up if you use something like zk porter our alternative approach to data availability that's going to be a lot less so you will overall pay only like two three cents for a transaction on a zk porter uh but this is your base cost and uh uh yeah uh we we like this scales a lot so as i said this is coming to test net in may and hopefully to production in summer and we have a few minutes left i'm happy to answer any questions thank you all right minor technical difficulties um alex that was an awesome talk i'm uh i was really impressed with like how visually explainable everything was in terms of how you went through tinyram and thanks also for sharing uh the actual spreadsheet on on the chat so this is awesome um i think we're getting a couple questions in and the one kind of question which i feel like may have been slightly answered uh later on in the talk but i'll ask it again in general is uh this is from aureus and the question is um when you were talking about the the size of the circuit why was uh catch ax so much worse than shot two two fifty six and um is that a difference in interpretation or like what's kind of the background on that it's a different algorithm it's it uses broader state with more bits and it it has more rotations more manipulations of those bits uh i'm not the the best person by the way to answer the the deep topics in the crypto um implementation side it's it's more uh we have a big separate team for that but i'll just do my best to explain yeah so like it's just a different algorithm which is less stock friendly than uh 206 and both are way less friendly than um algebraic caches hopefully that answered uh your question maurice um a couple more questions coming in um the first one will be are there any op codes that are not supported by zkvm uh we transpile the ethereum of codes into the kvm so we we we need to support not only the op codes but also the pre-compiles and we will definitely not support all the pre-compiles from the beginning uh so there will be some limitations but they will be very rare i think most contracts should work without difficulties got it uh another question is a tinyram can handle data dependent control flow or can timing ram handle data dependent control flow or do you still execute all branches right it's fully handling the um [Music] data control flow because you have a problem counter and you read the next comment from the problem counter which is controlled by by the program itself so you can make jumps you can make conditional jumps and you only execute one step at a time and your cost is the total length of the execution trades got it hopefully that question uh was also uh clear if there's any follow-ups from uh you ali i'm happy to answer that as well uh i think this is more of like a slightly technical one and it's referencing a particular slide so i'll uh i'll repeat that and uh the question is for the slide that refers to the mixing of hydrogen circuits are all the functions in the uh the pi uh function there different or or are they part of the same circuit um yeah i feel like uh so i think this is referring to the slide that you had at the end where you talked about you're mixing the storage one and you're mixing the tiny ram all in the same circuit and um maybe maybe this will help you better if you want to see that on the chat are you able to look at uh i i remember this slide i don't i don't quite get the question uh so all the functions oh well the tiny ram is the same circuit so we have multiple tiner and circuits for different lengths um they are there structured by power sub two so we have a circuit of length let's say one thousand and two thousand four thousand and so on and you pick each of them depending on what's the execution trace for a particular contract called is uh now the uh circuits for heavy operations they also have different sizes and we pick them uh um yeah like we just use as many of them as necessary yeah so i'm not sure and it's not the question well yeah in case we get a clarification on that question we'll ask that but if not it's great i guess my other question would be actually we got a new question which is where does the recursion actually happen um in the intermediate circuits so we have special circuits that aggregate other circuits they're they're actually they're sold purposes to take multiple proofs and produce an aggregate proof uh of those and to connect the inputs in a proper way so it's a separate circuit dedicated for exclusion awesome and i think um there's another question that i got from the other chats we have a handful of places where people are watching this i aggregate all that um maybe one last kind of question will be from our end is uh just generally kind of seems like you you've talked about that this is actually fully uh touring complete and uh and evm compatible um is there any other gotcha at all involved here or or kind of what's the level of completeness uh to what we understand on the evm right now that can be mapped onto zkvm well it's it's not going to be 100 exactly bitwise compatible with the the bytecode so like what what what we mean when we say it's evm compatible is you can take your existing contracts written in solidity for example and transcompile them to this thing you might require some minor modifications we expect that for most d5 protocols for example you don't have to change anything for some contracts make some assumptions about the specifics of evms for example you you might depend on the specific uh costs of gas consumption in in the transaction which will of course be different in l2 the gas matter is differently than you know you actually only pay for storage chances right so like such things necessarily will change uh and this affects all uh laritu protocols uh probably like if they if they try to simulate it at some great costs like maybe some some of them will uh but it will not reflect the actual cost structure so you will be just wasting some gas in such cases the more small questions coming in let's repeat them for for the video so we got a clarification on the the slide question again which is are all the functions label pi the same and it appears that they are different circuits but uh but in the same form or are they different sizes they give the question um all right i'm i i'm still not sure um like the um well you can recursively combine different circuits if that's the question so like you you will have completely different circuits you will in the circuit itself you can load the verification key from either from some set of predefined constants or maybe even from storage and then you can verify the proof against these verification keys so the groups can be different types and different lengths and the the circuits which were very fine will be of different types of different types i hope this answers the question otherwise inhibitor on the chat and i feel like you can clarify that at the end and we'll just do two quick uh questions before we uh uh wrap it up and uh the second question the second last question is uh what is the block latency for sdk vm uh here and uh and i'll ask the last one as well which is what are the curves that you're using for your circuits we're using vm 2.6 for now which is the the only network we have on ethereum currently compiles and the latency it depends on the pathway you use the our provers are very well paralyzable especially with this recursive nested navigation so the let's say we also have a hardware accelerator placed in fpga and we can produce a proof for a single transaction like a single layer of recursion i think within a second like maybe three seconds like this the range i'm not sure about the latest numbers so you can imagine that you have uh if you want to aggregate 1000 transactions you have with 10 layers oh no necessarily not done because we can aggregate up to i think 20 or or 40 circuits in a single block again i'm not sure which number but let's let's say 20. uh so that means you only need three a full layer four layers of recursion so like the block could be um could be produced within 12 15 seconds maximum so like if we use the yeah the fpga accelerator if we use cpus then it depends on how many cpus we we have given this and so on but the more we add the faster computers awesome well thanks again for uh clarifying that and i think there now there's a bit more discussion on the the other question about the slide so hopefully you're able to hop on and answer those live but uh thanks again for making this work uh with live uh coming on here live and uh thanks for the presentation thanks everyone for watching