ZK Paris: Frank Laub - Continuations and Parallel Proving

Transcript

okay so up next we have continuations and parallel proving by Frank laub at risk zero thank you all right hey everyone I'm Frank laube CTO co-founder at risero I want to talk to you today about continuations which is a way for us to make uh ZK scaling ZK proof scale and make them run in parallel so so yeah if we look back it's sort of like how we got here um we found that we could do verifiable Computing by having sort of an economic incentive model to basically get lots of

uh parties to you know run a bunch of uh computation and very you know it's not really verifiable but it is sort of trusted in the sense that you could you could get lots of parties to agree on on doing these computations together but there's some problems with this approach um you know you can't do really simple computations uh there they lack high frequency it's kind of slow it doesn't it's not doesn't scale very well um it doesn't deal with private data very well so okay here comes your knowledge proofs great um wonderful except that they have a whole bunch of problems in terms of writing circuits it's very difficult to do only certain people in the world can can kind

of do that uh they have a lot of overhead um uh and they don't really you know they're not super powerful without a whole lot of work so if we look at kind of what's been successful out there open source has taken over the world uh consumer Hardware is really um uh useful it's it beats Big Iron um the when you want to optimize for programmer productivity over run time usually it's the program or productivity that kind of wins overall you can get your things to Market faster you can you know you can develop faster um

and standards are good generality is usually better than specific over the long haul you know I kind of look at Asic versus CPU at first there was lots of Asics in order to solve problems but it's sort of we've moved towards the generic sort of CPU is now powerful enough to actually solve lots of the problems that only Asics could have done in the past uh scale matters so if we look at like what it takes to scale these proving systems um you know the major constraint seems to be around the number of constraints in the system um uh the cryptographic foundations themselves are actually hard to to make

run fast as we've kind of seen and so you know we've been looking a lot into using recursion to kind of solve these kinds of problems but we have a different kind of approach which is not really at the prover system level it's more of an engineering kind of approach where we can basically take a big long execution Trace split it up into different chunks we call segments and then each segment is its own proof you just run each segment as its own proof it can run in parallel and then when you're all done you can roll up the result using recursion that's the basic idea behind continuations um

so in RC KVM we can basically determine where those splits ought to go automatically the segment size is basically configurable has to be a power of two because we're using sort of an NTT it's a stark based system so um we do have to have certain limitations there but the the segment size is something that you can pick and that is important if you're running on low memory devices or if you have more memory you can turn up the segment size um and what this gives us is the ability to run each one of these proofs in parallel there's also this interesting feature where users can actually pause the execution of a program and then kind of continue it later on and that's kind

of useful one thing I like to think about for that is sort of like for ZK and ml use cases where let's say I wanted to load all of my weights in as sort of one one program and then pause that and then have lots of other users continue that program doing their own inferences from all those weights that have already been loaded into the program so you kind of amortize the cost of this computation across lots of different users this is kind of an example of the code that we have for the the rust API or to to be able to interact with the zkvm you construct and you know you could add

your inputs to the program you give it an elf binary which is basically just risk 5 code anything that compiles into risk five the zkvm should be able to execute um and then you can basically say okay now go and create me a session which then returns you know internally constructs a bunch of segments and then we ask the session to prove you get back a receipt and that receipt you can verify so yeah there's basically two phases to the system one is the execution phase where essentially you take your execution trace and we're going to basically interpret all of the risk 5

instructions and generate the execution trace and as we're doing that we're going to find out where the splits should go and then the second phase is the proving phase where okay now I've got all these segments and I can treat each segment as a totally independent proof and they can be run in parallel um yeah and then at the very end uh you can optionally do a roll-up where you take all of the different segments and make a succinct proof out of it so the the key thing here is to figure out how to make sure that our memory images are have integrity that they're not getting um you know they're not getting fooled by the the host isn't sort of like

making modifications so we want to have a miracleized memory image that basically checks that the pre and the post states are valid and so this is kind of an example of what that looks like so again there's the the PreFlight which is sort of this execution phase where we want to go through and just run the program sequentially and generate all of the different segments then once I have my segments I've got the different image the states of memory a and b and c and d and e and I at the end I want to basically show that I'm going from the very first state that I know of a and reaching the E State and so yeah we have these Leaf proofs here at the bottom in this case it's at the top and

then we run these join recursive circuits and at the end we get a final a final so synced proof uh so we're borrowing some ideas from operating systems uh the idea is that you can use paging in order to kind of summarize the what's going on for an entire memory image and so take you know take my user memory and some system register information and split that up into one kilobyte chunks one kilobyte Pages what I can then do is Hash each one of the pages and I end up getting an array of pages a page table and I can keep doing that until I get a

final entry at the end and what that ends up being is a Merkle tree with you know however many hashes I can fit into a single page I think it's about 64. so it's a kind of a very branching Miracle tree it's not binary but in effect you get a mortal tree and at the end of the day I can then use this image ID to sort of compare different memory States and the nice thing is that I only have to um when I'm when I'm Computing this new image ID I only need to do it for all the dirty pages I don't need to do it for every single page in the entire memory image I only need to keep track of sort of which Pages were touched in the in that given segment so it's kind of a nice performance

feature there so what are the kinds of things we can do with this we already have a zkevm demo so for us we can just take ref which is a rust implementation of the evm it compiles into risk five uh it took us about I don't know two or three weeks to basically get an evm implementation running with an RZ KVM same thing with wasm we have a wasm interpreter that can basically just run all the wasm code inside the ckvm we've also built a central limit order book application there's multiplayer games we've done one idea that we haven't yet gotten to but I think we're getting closer to being able to do which is running basically all of GCC or whatever

compiler you want inside of the zkvm and that kind of gives you a solution for software supply chain sort of verification so so that's basically what our continuations system is about we have we've just launched Bonsai which is basically a prover service that makes use of continuations and Roll-Ups so we now have API keys that we're handing out to developers that want to go try it out we're just kind of doing a slow rollout of the system and so here's various links that you can go and get more information about that

and with that um that's it [Applause] hi hello thank you for that it's super interesting and very relevant and helpful for me um I saw a tweet go out that there's like two megahertz something was clocked for risk zero can you talk more like what about that Benchmark sure yeah so recently we've been able to run um I think this is on a like a that evm example that I talked about we can run an entire block uh in about 30 minutes basically the idea is that we have the

execution uh that runs at around 30 megahertz right now the execution phase that's kind of like has to be done sequentially so you have to wait until that's done but after that's done we have about 100 gpus that we have in uh in the cloud that we can basically just run all the different proofs proofs on and when you add up the numbers you get yeah two and a half megahertz is basically where we're at right now we think we can get about another 10x or so there's a whole bunch of different places where we think we can do better optimizations um we have a bunch of GPU acceleration currently and we think that we can yeah improve that quite a bit we have the recursion circuit takes about um four seconds right now so

hey thank you so much um I'm curious what are some of the risks of breaking up the execution and proving in parallel um the risks well I mean the the as long as the memory is so yeah like the host can't really that the image the memory image ID guarantees that the memory isn't can't be tampered if between segments um uh so yeah I can't really think are you think do you have any uh ideas in mind that you're yeah um not particularly I imagine it would have something to do with the image

maybe not being done correctly um but I noticed you mentioned that for certain parts of the evm you have to prove sequentially and not in parallel right well yeah I mean the execution phase runs all sequentially um so yes I there there's you know when you're interacting with the host the host could lie to you and basically give you bad bad information uh so you need to basically verify that that information is correct inside of the zvm um but that's kind of a a basic sort of constraint of ckvms in general I would say yeah hi thanks for the talk

um can you speak a bit to the verifiable GCC compilation that you mentioned before in particular like um how you're dealing with all of the randomness that's that's happening because from like from what I'm aware in like reproducible builds right this is often like the big problem and how are you dealing with that here thanks yes so I think the idea here would be that you know I've got so assume that you start with a memory image that contains say your source file right you've somehow loaded your source file into memory um let's say that you've got a hash of that source file or something everybody

agrees on before you start on what that source file is and we all agree that we're starting from there then the idea would be okay now I'm going to run GCC I'm just going to compile GCC for risk 5. I'm going to run that inside the zkvm so now you know you you're testing that there's a translation that went from source source code to some sort of whatever output you know whatever you're compiling into it doesn't even have to be compiling direct risk you could be compiling to whatever whatever Target you want and at the end of the day you get this elf binary or whatever you know whatever the output is you can now attest to this elf binary and say okay because I ran the entire build process

within the zkvm you've now verified you're now attesting to that that now maybe there's bugs in the compiler you know we can't really necessarily say that that isn't the case but at least from the reproducible build point of view if somebody gets a binary along with a proof that says hey this by you know this source file was transformed using this compiler and it turned into this binary and here's a proof for all of that now everybody can just rely on say the hash of that proof or you know something like that and that's yeah that's the basic idea and then you can just kind of build up your whole you could do libraries at a time and eventually build a whole application out of all the components and all that kind

of stuff so we're not quite there yet because the the ckvm only has a about 192 Megs of guest memory that's available I think if we wanted to run GC like simple programs you could probably fit within that but larger programs um you know we have a future version of our circuit that should allow for the full like four gigabytes of RAM kind of thing but okay awesome thank you thanks foreign