Building Efficient zKVMs with Multi-Power Support | Leo Alt (September 2024)

hi everyone my name is Leo I work on Powder the yeah title ended up different from what was announced so initially I wanted to do like a high level sort of demo talk but a few meups ago Chris already did that um so I thought uh should probably talk about something different so today I'm going to talk about basically how we have um integrated many different provs in our compiler and what we want to do next for a little bit of context what exactly is powder so the whole idea behind powder is to be an SDK for SDK proofs what does that mean um how many people here know what Zer knowledge proofs are okay cool almost everyone so with Zer knowledge proofs what you want to do is basically prove that you know something about other something without necessarily prove without necessarily showing what that thing is and that can also be computation so you can prove that you've computed an logorithm successfully over some input and you got some output and you can make a proof for that that you can use to convince certain verifier that um that that's true and the way you can the way you could do this already a few years ago um in a programming uh perspective is you could write what's called zik circuits so there were languages like zores or circom where we have a DSL and you can write basically verifier so you can which is there's different abstractions you could use in these languages but you basically write a program and this program will be the verifier and it accepts a certain input or not and you make a proof for that or not and then the the real verifier that you want to convince um can that proof without the knowledge of some private data that you may have and this worked really well there's lots of applications out there that use this for of computation for scalability for privacy um but the the one thing it doesn't do is to scale to all types of of programs you may want to make proofs for which are let's say an ethereum client for example or even bigger programs and the next step on this timeline of tooling for ZK proofs is what's now called ZK VMS quite wrongly but yeah let's keep calling it that way at least for this talk meaning that you not only want a circuit that implements a specific functionality that you want to verify for example a hash function you want to you have a public hash Challenge and you want to prove that you the pre-image of that hash so you write one circuit that verifies one specific hashing algorithm instead of that we actually want to be able to make C proofs for any program out there and we can't simply rewrite all of these programs in Z circuits it does it simply doesn't scale so one alternative to that we can actually make one circuit that's going to summarize them all so we have one circuit the ZK VM and that circuit takes programs as input as well as the inputs to those programs and you make a zik proof for the execution of The Interpreter the VM over a certain input program and input so this is what a zvm does it basically allows you to make Z proofs for any program then that can run inside that zkm so if you make a ZK evm for example which that's basically how well that's not true that that's B how it started but in massive scale um ethereum a few ethereum l2s developed their own ZK EVMS which means they can make proofs for the execution of evm programs um without having to write circuits for each of those programs and by now there's lots of other VMS including um like non-blockchain related VMS like wasm or risk 5 that have ZK versions um to them so that's kind of like the summary of the background and so what does Powter do is basically another way to make Z proofs and similarly to how languages were used to describ circuits before we can use powder uh which is a compiler in a score to basically represent the VMS themselves as well as the programs so we go one level higher and instead of having just this one program you can represent we can actually we we will have a language where you can represent any VM that you want either existing VMS like Risk 5 or wasm or your own custom VM that you might want to come up with for whatever reason and next to that you have the program as well that uses instruction set from that VM and when you put those two together you give that to powder and you get a z proof basically of the execution of that program and some inputs in the VM that you've just built which is also one of the inputs and the reason for all this Machinery is that it basically abstracts away all the really low level ZK constraints that you have to write when building this type of systems and the pro complexity um in the sense of the finals they Pro that you have to call at the end so for example examples are like Halo 2 or plunky 2 plunky 3 these are Z provs where they're kind of what you Target in the end you give all the Z data already kind of massage and and then you just give it to the approver and it's going to spit out the ZK proof and um powder basically abstracts all the front end and the backend things so that um this works for basically NVM and from a program architecture perspective this allows for modular machines what does that even mean so you can basically build your VM or your program in ways that um we are already used to in software development so you make modules for different things you can reuse that code you can share with different people you can have a stand a library and this was so far not super possible in zik tooling and with that we have other things that we're also used to in the normal computer world like compile optimizations um static analysis security tooling or even form verification and different types of analysis you can do over the programs which are things that sound very basic and straightforward and things we're used to but that are not really present nowadays in the zik tooling world and the main goal that we have with pow is to basically maximize the developer experience give you give people all these features we already used to and enjoy every day when when building programs without compromising the performance which is what you usually lose when you go like a super high level um abstraction layer and for the user what you get in the end from these features is that the programs the circuits they become very easy to to write to test to audit and so on as opposed to writing like manual constraints in Rust and that no one can can read and this is like a basic diagram of what poter looks like so so this Square in the middle is the powder compiler where the input will be actually these things are also part of the input so we have different VMS that you can write in the in the IR language together the program and that's the input and this basically implies that for any VM that you can represent with P any language that compiles through that VM is automatically supported and from this point it compiles to another language called patter pill which stands for polinomial identity language which is a lowlevel constraint language there's no Notions of program anymore it's just constraints in polinomial and this the the program is basically compiled to this type of constraints and you can look at it you can optimize it manually if you want and you can understand what it does and then it finally together with the witness which is basically the trace of execution of the program that you want to make approve for it's given to approver um like Halo 2 or St plunky 3 in NOA and then you finally get a zig proof and you can give it to whoever you want to to verify that proof and there are a few things here that are very special um the first one is that it you can use multiple provs at the same time which is just not possible in the zvm world so if you look at the zvm out there um to the best of by to the best of my knowledge I don't think there's a single zvm except for PW that gives you different provs um in the zik circuit World there is um with zures you have access to different provs I think there's grath 16 Marlin don't remember what else but there are a couple maybe I think circom also has a couple um but in the ZM world you just can't pick and choose whatever prover you want to use but why would you have to choose which prover you want to use so different provs have different properties so hello 2 for example it comes from this from this Nar world and it is built in a way or at least the PSC Fork of Halo 2 not the original Z zash one it's built in a way that the proof is kind of slow and the proofs are big but you can verify directly on ethereum which is was a massive focus of BSC from inside the theum foundation when when they started working more on Halo 2 and this is one of the main properties of hillo 2 it's slow it's not the easiest to build but when you get a proof um you can arite a verifine on ethereum without having to do any compression or recursion or crazy crazy stuff um estar is used by the polygon Z KVM team also built by them and um yeah you get Stark proofs and these are very similar plunky 3 is also from polygon from the polygon zero team and wait yeah and it also supports stars but with different fields these two are actually very similar but this one is more optimized for evm where this is Fork proofs in general um using Starks and Nova is a folding scheme um that still doesn't have that much production usage because most of the l2s that drive a lot of this ZK proof um infrastructure they use Starks or snarks directly um but yeah with powder you basically from any program that goes through this pipeline you automatically have access to any of these provs actually not Nova it's not integrated but we actually integrated St which is also Stark Pro from the one that starkware uses and it's similar to these two in a way and yeah this is kind of the main thing we try to provide for people because there are new provs new techniques coming out all the time and if a ZM sticks to a approver they actually got vendor locked in it's it's pretty hard for them to migrate to a different Pro it's just a lot of manual work a lot of manually optimized Cod that has been written which going to have a really high um switching cost if you want to switch provs and they currently do have the best performance um but if you get to a point where this architecture can also deliver the same performance then you basically get the best of both worlds where when a new prover comes out say plunky 4 comes out and it's much faster than plun 3 you just switch you literally just switch and there are there's also the case is when there's completely different techniques coming out like gkr or Bas who everyone like everyone is talking about these two proof systems they're not quite in production level yet but there's a lot of Promise um and how do we know that they actually work for my system if it's not possible to experiment or integrate um there's just no way for me to make the decision so I end up getting stuck with my old prover and I don't even know if I should switch or not so the decision becomes kind of impossible and and that's again what becomes really easy here because you can just if bis comes out and there's approver we can just integrate it let's say in one two weeks and then basically every user of fter has immediate access to to that and the other uh main thing here is a front end because you can also write Implement one front end and make it very specific to one use case and build a whole pipeline from it let's say wasm um but if someone wants to use evm or risk 5 or so on um you'd have to rewrite it and here you can just write as much smaller program so for example our risk 5 implementation has about 300 fifth lines of code which is much smaller than building a whole implementation in say rust and compiling that to low level um constraints um so focusing a bit on the last part of the compiler part so there spill this language where it's started as a constraint language language uh very very basic with very basic Primitives just like constraints and columns which turn into binomials now um thanks mostly to Chris it's a full functional language and you can actually use the language itself as a matter constraint language in a way to build the constraints that will be used when implementing libraries or different functionalities and we have already used this internally to implement for example lookup and permutation arguments which is something that the provs some of the provs provide this as a primitive so these are like kind of ZK gadgets that make it really nice for the circuit so they're kind of like algorithmic Primitives that the provs some of the provs give you and you can you can use it to write optimized circuits in a way but not all provs come comes uh not all provs come with this functionality um but then if we want to support multip Prov how do we actually do it because if the front end uses this and we use it as a KVM how do we make sure that the pro that doesn't have that functionality how how how can we use it and the answer is basically that we can implemented in the language itself so that all these things that are specific to provs can simply go into standard library and then we only pick and choose whenever we we are going toose approver um so that these kind of tricks and optimizations that we make in the circuits that they just become generic they become a library and um implemented in the language itself which means they will work for any prover that we integrate automatically basically after we implement we integrate the very basics of the approver which is three things columns constraints and challenges when these three things are implemented everything else comes on top is automatically integrated as well and this was an attempt of a screenshot of one of these arguments implemented in pill itself um probably doesn't say much as just a screenshot but the main point here is that this is literally a 100 Line library code whereas if you were to implement this and this scales for any prover that we integrate whereas if you were to implement this for each prover you'd probably have hundreds of lines of rust code for every single prover that you want to integrate and the last thing we want to do with the provs and this is more of a of a future kind of thought that we really want to do and it's starting to become possible with um already having multiple provs that we can potentially use together is a combination of provs and whereas currently whenever we have a proof it's a proof in one proof system so here's a Halo 2 proof here is a star proof here is a Nova proof um but what if we can make proofs of proofs which we're already do in a recursive way but um what if we could use multiple proof systems in a single proof so this is also not done in production right now and it's something we're really interested in interested in um kind of like from a research perspective but we we do think it can turn into production optimizations because especially when building a zvm there's lots of different parts that have different pros and cons on the way you prove them so if you if you think about like hash functions they have a certain structure um that makes it suitable for say like folding schemes so cck has a lot of experiments when people prove I don't know how many cat hacks per second and but if you look into the contr flow structure of a VM star's actually pretty good um they have shown to be pretty good for for that so what if you identify like five or six things in your ckvm um that would benefit from different proof systems if you only pick one you were you're basically getting worse performance than the ideal just from the fact that you can't optimize each part of your proof with it it specific um with the proof system that would be best for that um for that part so this is something we want to do um the main sort of practical idea right now would be to use Starks with something circuit based um like gkr or some folding schemes for the hash functions or this kind of very like self-contained um repeated structure um algorithms so this is kind of like the main candidate right now in our heads um where where this is kind of like the overall thing where you can basically select different bits of the proof and say okay I think this can be a Nova proof and this can be bis proof this can be Stark proof and where yeah I guess the Ultimate Dream would be that these are just compiler options and you just say compiler pick the best one and somehow it knows how to do that and magically you end up with the ideal proof for your system um yeah that's basically what I just s so yeah where this would be the updated version where yeah in the end we don't end up with a single proof of a Kind where we have a proof where you can mix whatever you want inside um yeah getting to the end just wanted to kind of uh remind all these cool features that exists mostly because of having a compiler middleware handling all of this basically scales all these features to any front end and you connect any back end so it's not like it's one VM that is optimized to one prover um it's the fact that all of these features they apply to all the VMS so the VM itself is also just input to the compiler so whatever feature we're using here planky 3 the This research multi-prover stuff recursion continuations optimization and so on they are basically available and applied to any um any VM that comes as as input and this is um that's something pretty pretty novel that we're really excited about yeah thank you do we have questions anyone don't first here M yeah can you say how how do you split this proofs up into pieces I mean like an if if I get an eart proof it's not really modular it doesn't say insert Halo to here right so do you have a strategy for sort of putting those together breaking the proof apart so that you can Assemble Yeah the basic idea there's probably I mean for sure for different proof systems there's different ways to optimize it but the very basic idea in the architecture is let me see if this will make sense that basically so you can split the program in different parts and what this will look like before it goes to the appr is you're going to have sets of tables which turn into polinomial and instead of giving the whole table to one proof system you split your table in a bunch and then you give that to different provs and then you going to end up with n proofs separate for each proof system so let's say I have I don't know like nine star proofs and one gkr proof if you want to put all of that eventually you have to put them back together in a single proof is the basic idea and the way you would do it you would apply a recursion step where for each of these proofs in let's say the lowest level you verify them inside a piece of code that you then make a proof for again later so if I have let's say a plony 3 and Hisar proof I can write I can I can write another algorithm let's say also as an input program that reads an tar proof and the plunky 3 proof verifies them runs a verification algorithm for these proofs and then I make a proof for that program and let's say I get the output of that proof in Halo 2 so now I have a Halo 2 proof a single Halo 2 proof of two other proofs being verified inside that proof is it that just like a composition like that why why can't like I guess I didn't so this is very hand wavy no and there's lots of details that are missing here it just seem like if you just stick one inside the other then you don't have to go through this whole table I guess so the the table part you can you can fully abstract it's just the inputs to the prover so instead of getting your instead of making your whole program combined in a way that it becomes one input to one prover you can split it and say like 10 inputs of 10 provs and at the end of this you still have 10 proofs and it also depends a lot on on your verification environment if you're fine with 10 proofs as a verifier then that's it you're fine with 10 proof so you get the 10 proof to verify all of them so there's nuances like your verification environment how much time you want to spend in verification if you want to verify for example in ethereum then you can't just get these 10 sted because you cannot verify them on ethereum it's going to be very expensive so let's say you have yeah you have like five blanky 3 proofs because I split my program in different ways or two JKR proofs and three plunky 3 proofs but I want to verify them on ethereum and so the way one way would be I write a follow-up program that takes all of these proofs verifies them inside that program and then I make one proof for that program with Halo 2 and then it can go verified on ethereum so this is a recursive proof right that ultimately proves that I proved these other five proofs much earlier on and but one way of composing these proofs is usually for example um how do you solve the problem of um you want to verify you want to make a proof for the execution of a Ros program or a C++ program that has like a billion cycles so in practice you cannot fit this in a single proof because of Pol normals and all this kind of stuff one practical number is let's say 2 to 23 is something you can do how much do 23 it's a lot but it's not a billion so 2 to the 20 is a million so that's going to be 1 two 3 so it's going to be 8 million so you can make you can put 8 million Cycles in a single proof but what about the rest of the 1 billion minus 8 million Cycles you can't put that in the same proof so one way is to basically every 8 million Cycles you stop and make a proof right so you're going to have a bunch of these you're going to have yeah a thousand of these proofs and each proof is proving a segment of a million Cycles or eight million Cycles whatever this number is what you can do now you have one verification program which is say also a Ros program that does fed in 8 million Cycles I'm assuming here that takes two of these proofs and verifies the two of them so I'll take two of these proofs as input to my new program and this new program fits in 8 million Cycles let's say it has 500k Cycles now I make a proof for this program and so basically I've compressed two proofs in a single proof right so I took two segments out of my 1,000 segments that prove that combined prove my 1 billion cycle execution I take two of the segments compress it into one proof by also making a proof of another program smaller program that verifies two proofs so I I do this for all the 1,000 proofs so now I have 500 proofs right I do it again now I have 250 to proofs so you go up a binary tree so that after log amount of levels you end up with one proof so this is one common strategy for example where where you need this type of um composition recursion however you want to call it um whereas the basic idea is is the same just that instead of having two proofs that of the same kind and compressing into one proof I could have two proofs of different kinds and combining again into a proof that could be of a Third Kind right yeah hope that makes sense yes thank you yeah oh yeah yes uh have you explored the options of using different fields in different parts of computation so say some part of computation is good with like it's with small values so it's just Ms good with MSM so you want to work with curve fields and another one is like random value so you want to work with some like smaller Prime fields and then is it possible in your opinion to combine them in some like not naively as just like recursively maybe some more tricky combinations yeah that's what we need to find out because that's going to be a tricky thing when you mix provs right because some of them only even support a couple fields or only one right so currently we only do one field in the whole thing thing um so it's either yeah BN everywhere if you're going Halo 2 or goldilock 64 bits or baby bear 31 bits merine 31 31 bits if you're going to plunky 3 and that's that's applied everywhere and yeah it's pretty good for some parts pretty bad for other parts um and I guess it's even if you do it combining recursively it still run out into the problem that exactly very fire circuit it will some part it will be like non nature for exactly so that's the part that we did have some like we we've thought about what you asked but not from the direction that that you asked we thought about from the perspective of it being a problem when you try to do recursion because if you want to verify a 31 bit fry Stark and put that together with a I don't know gkr using whatever field it is BN or whatnot because you want to do curve stuff then how do you even verify the two together because the field arithmatic is going to be all wrong and you don't want to pay for a bunch of wrong field stuff um yeah to solve this problem can also be a fure yeah I guess a similar differentiation factor is multivariate and univarate pols you also mention in gkr combining with with Starks um is it a problem I mean some current techniques just switch back to the in so say Val or sp1 they do gkr but then in aop they make it univariate conversion uh you're considering something similar or for the gkr case I'm not too familiar how we implementing it do you know Chris I don't think we use yeah that I don't think so either but I'm not sure if there's plans yeah the main reason we haven't spend much time on multivar pols is uh because there are no goods yet as far as I know hyper could be next in the Todo list but you have L of there yeah most yeah we have a yeah so Lots like so these lasso benos and Nova or I guess cycle fold those like things we just think about would be cool they realist what it's a wish list yeah it's a wish list though what we do have now like a basic integration this St the new Pro from starware though it's a basic star Pro they do have um Circle Starks um which blun 3 is integrating I think or they already have it they have it is it cuz I've heard it wasn't like fully optimized yet and stuff I think they just use different qu deep quing strategy okay like from original paper and then two users slightly newer so maybe that yeah but uh yeah and one thing we would of course really like to try to use binus but there's no practical um yeah scholing for it yet um and yeah that would be I mean not exactly what you asked before but would be related to having different fields for different things it also seems like some of these are like different parts of the proas is a lookup argument being us is a bit more of a a commitment scheme um does it make sense to combine them as a full on proof systems like two and three I don't know that's why you have to integrate all of them first and then and then try it out um I get I get yeah yeah very excited I thank you yeah thank you last question maybe all righty then thanks so much again cool thank you [Applause]