ZK10: Analysis of zkVM Designs - Wei Dai & Terry Chung

Transcript

foreign [Music] hey guys my name is Terry and Wei we're from 1kx an early stage crypto Venture fund uh we're here to present analysis of zkvm designs there's been a lot of iterations on Works in ZK VMS with different design choices each with its own trade-offs and so we wanted to examine them their concrete efficiency and just sort of give you a higher level overview as well as the design decisions involved as well we're going to start off with what they are why we need them we're going to go into efficiency analysis in three parts including ice efficiency arithmetization efficiency improved system efficiency and then we're going to go into open

questions so what are ZK VMS and why do we need them the common comparison that a lot of people make between a zkvm and a circuit is that of a general purpose processor and use case specific Hardware a circuit is generally tends to be faster because you have constraints that are tailor written for the specific computation at hand in a ZK VM you're off improving computation or execution of a general purpose VM one that's widely used in practice so you do get the advantages of taking advantage of existing infrastructure like like compilers or you know using higher level languages but then the downside is at the moment they're about 10 to 100x slower um circuits have been getting easier to

use with custom dsls new dsls and the core question that we have to ask then is can we make ZK VMS faster as well there's a rich history in the development of ZK VMS um started with tiny Ram in 2013 and then the first commercial work in 2021 as far as we know in the past two years there's especially been a lot of new ZK VMS tailored towards proving execution of existing and popular VMS today like the evm Wasim or risk 5. in the context of a ZK VM you can think of represent like a abstraction of what a machine is it's specified by its memory its instruction set architecture as well as its internal machine state

the ISA of a machine is basically a finite list of instructions with fixed semantics think about like the evm set of op codes risk 5 wasm a program is a sequence of such instructions the job of the machine is to read through each instruction at a time and then do one of five things including things like reading and writing from memory or changing its internal machine state so the ZK of the zkvm um the job of it is to prove valid execution of the machine of the above machine given initial program initial inputs as well as an initial internal machine State and you can roughly divide this into four parts first you have the setup which includes parameters of the zkvm things

like Max Trace rows fixed columns hash functions and creates a proven key in the verification key in witness generation you have an Executor which takes the program and the input and then is responsible for creating this array of the execution Trace Matrix execution Trace which includes the the execution of the program and you know also includes additional information that helps constrain the validity of the execution this is also where you have the splitting of the program into many different parts for parallel approving in the proving phase the prover takes the execution trace the proven key generates a proof and then the verifier verifies this um

within a traditional machine right the core idea of efficiency is roughly correlated to the number of instructions in a program times the time it takes to actually execute the instruction roughly uh this translated into the context of a zkvm we say this is the number of instructions in the program times you know the the constrained complexity per instruction uh and so this is kind of like because we're we're um developing something that's proof system agnostic uh think of it as kind of like the number of r1cs Gates or the cells in a plunker circuit um and then times the time it takes uh to prove per constraint and so we divide these three things into

um three different parts one we call ISO efficiency to arithmetician efficiency number three is proof system efficiency so let's dive a little bit deeper into the iso efficiency um so traditional Isis and zki says they optimize for different things so traditional processors they're memory bound but zki says you have generally speaking um one cycle per instruction so they tend to be instruction bound another design decision that you can make is between a Harvard and a Von Neumann machine in a Harvard machine you have program and memory in separate locations and so in this case in the context of a zkvm you'll have something like a pre-processed lookup table and or a lookup table generator witness time

and then the main execution Trace looks up into that table and then in a volumen machine you have the program in memory in the same location uh here it's generally closer to Modern CPUs but the cons is that as you fetch instructions you do need to constrain correct instruction Fetch and at the um initial phases of the program you need to load the program into the memory so there are more cycles that you use here another choice you make is between the internal State uh the internal machine state memory model which uh you know there's like three options that a lot of ZK VMS are using today the stack machine the register machine and the direct memory model in the stack machine you generally have a lot of data movement

operations to access the top of the stack on the other hand you get these simpler instructions in a register machine your instructions tend to be shorter but more complex but there are much less data movement operations there still are between the stack and the registers but you'll see later that it's much less than stack machines and then in direct memory you have zero data movement operations but you do have a lot more read and write operations so this is the current categorization landscape today um it's going to come back up later so try to remember it but yeah so um if you look at the actual instruction counts uh per the different types of uh machines

um we took one round of shot 256 compression compiled it there are obviously uh caveats here in terms of like implementation efficiency or compiler efficiency but as you can see the first three stack based machines has significantly larger local data movement operations compared to say like Risk 5 or llvmir which has virtual registers and therefore zero percent local data movement operations um so like here you can see uh in the actual assembly the data movement operation specified here um yeah if we're specifically comparing um risk 5 and Wasim across shot 256 and ketchak you'll see that there's significantly less data movement

operations in Risk 5 compared to Wasim but then once you get to Kit check because you need to maintain a little more like internal State there are equivalently a lot more data movement operations between the stack and the register for risk 5 there as well so the core takeaway here is that stack machines have a lot of data movement Ops up to 50 to 60 for solidity registered machines meanwhile they have good efficiency when register pressure is low but when register pressure is high they still have a lot of data movement operations while direct memory machines they have zero local data movements um but you know they they do have a bit more complex arithmetization as well so next up Let us look at the efficiency

of resignation or basically how much uh how many constraints we need to express one instruction so if you were to plot the complexity of the constraints as a function of number of Cycles or instructions executed you'll get a graph roughly like this which is piecewise linear and where the graphs divided into segments and the length of the x-axis for each segment is uh what we call the segment cycle counts and the reason why most existing implications do this is two volts one is there's this economy of scale for proving meaning the memory usage is usually linear in these instant size and the protein time is usually super linear uh in in the instant size so therefore

it is more efficient to keep a smart instance meaning a smaller segment and secondly these segments can then be proved in parallel meaning that if you have a lot of processors a lot of computers you can actually have a lower delay if you break them into segments and however breaking them down to segments it is now free and we incur in some overheads if we want to prove that the machine State between segments are consistent and moreover if we want to compress all the proofs down to a single 16 proof we need to do recursion and for some rough numbers here for stock VMS the number of Cycles in the segments is usually on the order of million Cycles but for something that's for example

Nova based the segment could be you know as low as one single instruction so let us dive into the uh you know what happens in the segment in more detail and first let us recall the notion of polynomial interactive vocal proofs or poly poly IOP for short um in in this type of protocols we generally have a set of polynomials derived from the execution trace and they are then additional constraints placed on these polynomials in terms of semantic checks such as a permutation check lookups so for example a permutation check will check that the value of a polynomial is a permutation of the

values of another polynomial and these checks are then further turned into uh zero checks and product checks which are then turned into quotient checks in the universe setting or some checks in the Multiverse setting and everything up to this point are information theoretic and incur minimal computation in the form of mathematical fund fee operations to turn this into a existing snork usually what we do is we have to add on a polynomial commitment scheme and for that it incurs a lot of fun of your operations in the form of ffts as well as multi-linear extensions and most importantly of course polymer commitments which amounts to

multi-scaler multiplications in a group or for example Merkel hashes if we're working with fry and so to put this into context of a ckvm what happens is that while the executor which takes a piece of program some input will split out a list of execution traces and each of the execution Trace is then turned into a sequence of polynomials which are then committed to and then opened and set at random points and the commitments and the openings constitute the proof and if you were to look at the complexity of the operations here it turns out these the steps labeled uh you know currently in purple are the the most heavy operations and Barrel rough

counts up to 80 of proving time could be spent in these two stages uh which consists consists of mostly ffts uh and and poly comments and so for for us to look at the second category of realization efficiency we need to look at uh this metric which is basically how many polynomial uh are derived or are there for the proof system and how many polynomial polynomial evaluation points uh do we need to additionally do for each instruction so keep that in mind that's the method we're going to be looking for for these systems uh and roughly we'll have two categories uh that we look at look at one is Stark VMS so Cairo really

started uh you know building systems uh you have this architecture and there's a lot of many projects that have follow suit such as root zero maiden and so on and on the other side we have algebraic Stark VMS which are actually currently mostly based on Halo 2. so I'll have to worry a little bit the next next slide is going to be very dense with numbers and we're going to be walking through it uh step by step so here is a spec sheet for stock VM so we've collected and the most important column here is the last two columns which denotes uh the bytes committed per instruction to be executed

and the flight expansion rate so for stock VMS it turns out there's this tunnel parameter called the fry expansion rate that dictates the trade-off between proving speed and proof size and it's mostly a tunable parameter meaning uh we we have the numbers on in this column and we can pick a free expansion rate and we get roughly the total amount of bytes to be completed per instruction and and that's if you pick the you know the third step which is polymer commitment scheme you you get roughly your your time per instruction and um next up let's look at how we derive this number the first thing is uh we have to fix a field and it turns out for most dark VMS with the exception of Cairo I have chosen to either use a

64-bit field which is Goldilocks or 31 bit Fields such as baby bear or Mercedes or 31. and there's always a set of Base columns which are usually simple functions of that solution Trace and then there are a set of columns which we call the randomized extension columns these columns usually results in the semantic checks such as permutation arguments lookups and copies and we can see that these VMS are generally using a small number of these operations uh with the exception of uh I guess polygon the evm here uh and

the reason why these checks are expensive is that there because of the randomization needed we need to move to extension Fields uh since if we're in a small field setting and this incurs a blow up of the extension field degree factor which is you know undesirable compared to base columns um yeah so here are the rough numbers that we have derived using this framework and one caveat here is that this number is not supposed to be uh you know a comparison metric for for these VMS because we're comparing Apple's oranges these are different ISO uh different isos with different efficiency and underlying PCS could also be different so but the

takeaway message here is that even for the most efficient VMS such as Maiden Cairo or valida the amount of buys to be committed uh is at least about like 1.5 to 2 kilobytes if you pick a fry expansion factor of two and uh so for example for Maiden if if you pick a phrase ventral factor of eight then you could even have up to like you know five or six kilobytes committed um but you know roughly they're all within one order of magnitude which is two to ten um so keep that memory Minds you'll come in handy and the second thing to notice is that the operations uh were buys to be committed per instruction differs depending on the type of operation they're doing in particular for 32-bits binary operations there are some VMS

that are optimized for this and some other VMS there are not and this additionally could incur uh order two blood or up to like order 30. on the number of buys to be committed per instruction and a little bit of uh uh caveat here when I was talking about the frag expansion factor is that uh for a lot of VMS there's actually optimization that can be made where the fry expansion rates can be closely uh you know related to the max degree where you can eliminate uh one of the you know one set of ffts but I'm not going to be going to that in detail so let's look at uh Halo 2 VMS here the story is roughly the same we want to

derive a number that is number of bytes committed per instruction and uh here we have to use some very very rough estimates here so let me actually start on the left here for Halo 2 based VMS we actually got some more granular numbers in terms of the number of lookups permutations and copy checks that are done uh in these three VMS and we can see that Halo 2 based VMS currently use a lot more lookups than uh in the Stockland and we suspect that you know it's because we we could stay in the same field so you know intuitively speaking there should shouldn't be any efficient difference between base columns and randomized columns but however actually

this might not be the case because uh the base columns could have low Heming rates uh Heming weight so therefore committing to base columns could be potentially more efficient than um randomized essential columns or randomized columns in this case and for us here we had picked a number of four bytes per base column and 32 bytes for a randomized column to derive these numbers and roughly speaking they're again on the same order magnitude but maybe slightly more kilobytes coming in per instruction than start VMS so uh what are some learnings that we can take away here well one is to minimize this number we have to minimize the number of cells committed super instruction and a lot of

times there are certain cells that's carried over repeated across different Cycles such as registers which are essentially unnecessary uh you know to do as a column and secondly there are some techniques that for example improvements in lookup protocols that can be applicable for all VMS and so for example a lot of Hello to VM still use the Halo 2 lookup arguments which can be directly replaced by more uh you know recent and faster lookup arguments so next up let's look at briefly at the recursion complexity of uh starts in general actually so

recall the reason why we need recursion uh well the reason why we need to look at how to aggregate the segments because we need to make sure that they're consistent between segments and we want to derive a single succinct proof and it turns out the the way that you would tie the segments together it could incur up to around 50 percent uh blow up in the number of cycles and we took this number from risk zero and this could differ you know depending on the the strategy that you would prove that memory is consistent and the next big contributor to complexity will be um the complexity of verifying recursor proof and for that we have looked at

three categories uh direct start recursion voting schemes and start based recursion um and for the reason for the interest of time here I would just skip to the number slide here where we're going to plug in the numbers for um you know for everything and so direct start recursion is definitely very inefficient uh compared to Starks or folding schemes and it is clear that folding schemes if operated over a native uh field have clear Advantage however Stark based recursion could be efficient enough uh you know as is for some practical systems so finally let us look at the final metric uh which is actually independent

of ckvms which is the time that it takes to uh you know per per gate or per cell and for this we have we'll just have you know two short size on this because we couldn't really find good data and this is independent of ckvms here is a benchmark by Remco showing the PCS commitment throughput for uh as a function of instance size and we can see that Stark condition schemes are actually well fine it's faster than msm's uh answer uncertain machines and however if you normalize a number by the fuel size the number actually gets really close and in some cases MSM

actually wins out uh over fry for for these implementations and the second uh data point that we have is from Ellie slides from SBC which lists the Cycles it costs to commit to a 32 bytes value or 32-bit value and the number was given for for fry with Blake fry with Poseidon hash and MSN based commitment schemes and there was kind of a reply to you from Zach correcting the numbers for msms uh bringing it down significantly and so the the story here is really that we don't we don't really have good grasp of which one is faster per byte and the highly depends on the configuration the hash that you use and uh you know the

the MSM algorithm that you use however for fry it is clear that with more Stark efficient hashes we can significantly bring this number down um so let me actually go back to this slide and conclude so in this talk we have presented this metric of analyzing the efficiency of the kvms into three different efficiency metrics ISO efficiency originalization efficiency proof system efficiency the last one is independent of dkvms and there's improvements to be made on all three categories so let me conclude with perhaps a little bit of uh of questioning you know but open questions that that we can uh try

to solve so for the eyesight front is it clear that there's efficiency to be gained if we eliminate local data movements on organizations it is clear that with more efficient snark-based hash functions fry can gain a lot of uh efficiency in in terms of the recursive complexity and finally for PCs we should have better Benchmark Frameworks to be able to compare these and moreover there should be actual libraries that uh you know a lot of for instance can depend on instead of the current landscape which is every single uh start library or every single stock Library having their

own having to call up their own uh polymer women's games so with that uh I'll conclude the talk and take questions oh and we thank this list of individuals who have given a great insights to these systems many of you are you know sitting in the audience today foreign so do we have any questions so um I have a very quick question about whether you have an intuition about the trade-off between uh stack and register machines because so in it featured in in both of the first two segments in that

it it features in instruction complexity but also in how many instructions you have because of uh data movement did you get a feeling of an overall winner or is it not clear from the data you have so this is subjective I think my my feeling is that uh direct memory so operating on the call stack directly uh could be could be like more efficient than you know having registers or having too many bit of the stack uh because you have less instructions and it only incurs more memory reason rights more memories and we we know how to do those very efficiently as a permutation argument all right thanks any other questions

hey thanks for the joke so what's your take on the lookup singularity uh oh so one thing is we didn't really compare Jordan lasso here um and and you'd be nice to kind of put them into the same framework and I think uh based on the you know preliminary numbers that they're giving out there's definitely Improvement that have made um you know bytes committed per instruction so yeah I mean I think it's a nice good step in in the right direction but I'm not sure if you know we'll have like a single lookup for everything anytime soon anyone else we have a couple more minutes cool

thank you last minute entry did you do any benchmarking comparison between development of similar circuits uh as dsls versus their implementation in a virtual machine oh it's a really good question so um yeah so actually if you look at our shot numbers you can actually kind of derive uh there's a slide that I didn't show which was uh the complexity for Sean um and so you know it takes about like 40 to 60k constraints in in plunkish and if you look at if you were to implement Shaw in like Risk five or wasn't well in

Rust more compiled to risk and wasn't and then going through the calculations um I think you get yeah something like 10 to 100 times so that's that's how we got like 10 to 100 times slow down number for one of the slides uh um yeah so so you know there's definitely inefficiencies like with going through you know a a computation that's like expressing software and then going through a VM compared to like just directly to nine circuits thank you cool anyone else all right thank you so much Dan thank you [Applause]