ZK10: FRI-based recursion with a Groth16 Wrapper - Paul Gafni

Transcript

[Music] hi everybody oh that's in my face okay uh my name is Paul I work at risk zero and I'm excited to talk to you today about the sort of architecture of our proving system at risk zero which happens to be very very similar to the sort of proof system architecture across a number of other kind of mature zkm systems um so if you look at the details of the risk zero architecture the polygon ZK evm architecture and the ZK sync's new bam architecture all of them have really quite a similar pattern um and I just sort of wanted today unpack what does that pattern look like and

what are some of the kind of considerations that drive the choice of that pattern and drive the conversation about whether we might want to Pivot away from that pattern at some point in the future so um brief overview we're going to talk about what is this emerging pattern and what metrics are relevant in considering alternatives to this pattern so I think probably the people in this room are relatively aware of zkm so I'm going to sort of like speed through this relatively quickly but general purpose zero knowledge virtual machines are here and we think they're going to continue to be quite important moving forward um so let me just unpack what I mean by a zvm I'll make it quick in a typical virtual machine you feed in some program

and you feed in some inputs to that program and you get out some output in a zero knowledge virtual machine you have a very similar setup you feed in some program you feed in some inputs you get out some output but in addition you get out a proof that the output actually corresponds to the program and the inputs that you specified uh at risk zero we package this output and proof into one object that we call a receipt and at this point we can sort of get into the main question of like okay yeah we want to make proofs for zkm execution how should we make these proofs should we use fry should we use 16 should we use some sort of folding based approach

should we use some sort of lasso based approach and what we see right now across these platforms that I'm discussing today is a pattern that looks something like this so we're going to unpack this picture quite a bit as we go but I just wanted to give you a brief sort of preview of the architecture here so these orange objects here are receipts and this is like the the stack for a single proof of a risk five execution so we generate a bunch of receipts and then we use recursion to compress those into a single receipt and then finally at the end risk zero is using a grath 16 circuit to compress this into something small enough for onchain verification the other two platforms or polygon and ZK syn are both using kzg for this so we'll dive into

this in quite a bit more detail as we go but you can see here there's a few kind of layers of proving here and initially we run provs to generate these six receipts shown here and we're using fry for those proofs and then we do recursion and we're using fry for those proofs also and then finally we wrap it up to make it small and this is in our case gr 16 in the other platforms kzg so let's talk a little bit more about recursive proving because there's kind of two separate applications of recursive proving that are relevant in this stack and I want to kind of decouple them a little bit so we can

consider whether we want to use the same proof system for both of these kind of contexts so the the basic motivation for recursive proving is to take a bunch of proofs and compress them into a single proof so I have a picture here we have four receipts four proofs we feed two of them we feed pairs of them into a recursion circuit and they each spit out a single proof and and we feed those into another recursion circuit and they spit out another proof so we can use recursion to compress a bunch of proofs into a single proof I want to call out here that there's uh these initial receipts here I'm imagining they came from the zero

knowledge virtual machine they came from a risk 5 execution and there's actually two Stark circuits in this picture here there's the initial risk 5 circuit which is used to generate our proofs of risk 5 execution and then there's a separate recursion circuit which is used to compress those and I want to just call this out in order to sort of invite the question of it might be that we want to use a different proof system for the risk five execution from the recursion right now we are using a stark based system for both of these but I think it's important to call out that it might be the case that there's a reason to stick with fry for one of these but switch away from fry for another so let's talk a little bit more about

recursion we just discussed one purpose of recursion which is to aggregate a bunch of proofs but at risk zero we're also using recursion as a mechanism for incrementally verifiable computation so I'm not going to unpack what I mean by incrementally verifiable computation I apologize if you're not familiar with the term um let's take a like closer look here about what I mean in inside the zkm this is basically the picture that I showed you before but zoomed in and we have an object called an Executor and approver inside the zkm and there's this notion of an execution trace and in order to generate a proof for uh the correct execution we need to

sort of do something with this execution Trace so just to sort of highlight the the public outputs of your proof here can be um kind of arbitrary parts of the ex tion choice so a few months ago we introduced this feature called continuations and I want to sort of unpack the connection between continuations and recursion before we had continuations we were able to generate proofs at Max of 16 million execution Cycles 16 million it's not exactly 16 million risk five instructions there's sort of not every risk five instruction is exactly one zkm cycle but uh roughly speaking you can

think of this as 16 million machine instructions after continuations we don't really have a limit here anymore we can generate proofs for arbitrarily large um risk 5 executions so far I think the biggest that we've done is something like 10 billion um and our like napkin math for our theoretical Max here is something like 100 trillion um we'll see whether that theoretical Max is I mean I don't think it's going to happen anytime soon but so I want to sort of Connect the Dots here of how this comes back to recursion so this is the picture that I showed you before and what we do at risk zero is we split our execution Trace

into a bunch of segments and we prove each of those segments in parallel so rather than proving uh like Stark for a billion cycles we typically are splitting our execution Trace into sections that are each a million Cycles long so if you're looking at billion cycle computation I guess that's a thousand segments each of or a thousand segments each a million cycles Long so we get a receipt for each of those segments a proof for each of those segments uh and then we feed this into recursion in order to compress this into a single proof so in some sense this is still using recursion for proof aggregation but I want to kind of call it out as

separate because it's proof aggregation for the purpose of increment verifiable computation so in particular uh this is not the slide I expected oh yes okay so we get to discuss this question of how should we make the proofs and I want to just call out that we need to be more specific about like which proofs are we talking about making here we need to make proofs for risk five execution we need to make proofs to aggregate those risk five proofs for IVC purposes and we need to make proofs to aggregate the full risk five proofs in our system we're using a risk 5 circuit for this first part and we're using a recursion circuit for the second

part but we might decide at some point to switch one of those to something other than a recursion circuit so for example it might be plausible to use a sort of folding based approach for the second item on this list but still decide to use a fry based appro approach for the third item on this list so we're using Starks for all of these and the problem is that Starks are too big for use on chain the proof size for Starks in our system is about 250 kilobytes the like gas costs are too large to make it feasible to ver to verify on chain I don't even think the I think the call data limits are a barrier here so we add one more proof to our stack which is this kind of snark

wrapper so this was the picture I showed you a second ago we have one more circuit in our system and this spits out a little teeny tiny proof so this was this pattern that I showed you in the first slide again these are fry base proofs here fry base proofs here and in our case grath 16 here and the other systems kcg so let's expand that a little bit this is that picture that I just showed you this is one full proof of a risk five execution including segmenting and recursion here's another one here's another one and here's another one and then we could aggregate all of those as we did before using a recursion circuit and finally at the end here we're going

to only worry about the Groth 16 wrapper at the very last step so in the picture I showed you before there was a Groth 16 step after these steps um but in the full like with proof amortization with the full proof aggregation this is the architecture that we're working with and if you look across ZK evm like the polygon ZK evm has a very similar diagram on the website and I think bam does as well okay so our approach is Starks for the zkm circuit Starks for the recursion circuit and then we're using a Gro 16 snark to make the proof small that's ours polygons and bams so now we get to the interesting

part is this a design that is good is this a design that we should stick with um our thesis for now is yes and we remain open to sort of exploring other options as they come in front of us at this point we don't see an immediate cause to switch but I want to just sort of outline some of the considerations that would drive these sorts of decisions so the one that or I guess the two that are really kind of obvious is proof size and proving time we definitely want proofs to be fast and we would like the final proof at least if we want to put it on chain to be small and when you see new papers it's easy to get excited about look this paper is clearly like we should switch

to this because the proving time is better but it turns out that there's actually quite a lot more complexity in choosing a proof system than just proving time and proof size we also might be interested in the hardware requirements we are interested in whether this is something that you can run on a consumer machine or whether you need a sort of giant epic supercomputer to run we are interested in how paralyzable this is the difference between a system that runs fast on a single Machine versus A system that is easy to horizontally scale to a cluster of 100 or a thousand machines not necessarily super obvious it might be the case that one system is optimized if you're not

trying to horizontally scale and another is preferable if you are trying to horizontally scale we're also interested in whether this could be decentralized is it possible to ask a bunch of nodes to each participate in a collaborative proving process and we're also interested in security and auditability and privacy and I could expand this list further but I just sort of want to highlight that there's a number of axes that we need to consider in comparing these proof systems and what I want to do for the remainder of the talk is sort of outline some of the details I'm going to focus on these top five um and we'll discuss a little bit of how this looks in the emergent pattern that I just described and

discuss a little bit of how some of the Alternatives May um be offer some challenges on in terms of some of these axes so let's first just talk proof size this is I think the like simplest one the Starks that we're using are about 250 kilobytes the snarks that we're using are under 100 bytes so it's a pretty substantial difference between the size of a stark proof versus the size of a kzg or Groth 16 based proof the pro time here I'm giving these numbers here this is 11 seconds for a segment proof so this is

one this is for proving one segment of one million Cycles takes 11 seconds on a MacBook M2 this is actually a M2 Pro I realized after I made the slides the recursion is faster and the grth 16 is actually kind of a substantial portion of the proving time here so this description here is worth unpacking a little bit here if you're running this on a single machine you're going to have to do six of these for the example that I have shown here but oh I'll get to that a little bit later um so for right now let's just

sort of I'll just highlight if you're running this on a single machine you do need to do that once for each segment there's a sort of uh foreshadowing I guess of discussion of parallelization here can we run these on regular computers can we run these on your laptop um this is a sort of like real kind of consideration if you look at the details for a lot of proof systems and you're like oh what what's the hardware that you're running this on there's systems that are like requiring over 100 gigabytes of RAM in order to be able to run it which is like okay cool if you have a supercomputer you want to like pay for one great but it's nice to be able to generate this on a standard laptop this 12 GB number here is based

on the size of these segments so right now our default segment size is 1 million Cycles which means that in order to generate a proof we need to do uh number theoretic transform or fft on 1 million cycles and the hardware requirements here translates to about 12 GB we can tune this down if we just sort of set the segments size to something smaller then the hardware requirements drop accordingly so this is like a configurable setting if you have a desire to be able to run this on a uh lower power machine we can sort of dial that back a little bit the grass 16 circuit here we have substantially less control over tuning um but fortunately

it can also run on a consumer laptop okay let's get into the more interesting stuff how well can we pair parize these systems and how well can we decentralize these systems this initial production of the execution Trace is happening on a single machine this is our current kind of uh a big effort is uh can we easily parallelize this initial construction of the execution Trace um so far it's just running on a single machine these ones though the segment proof here of which in the example I have here this is like a 6 million

instruction proof so there's six of these we can delegate these to a cluster so if we have six machines on our cluster we can ask each of them to prove one of these segments and send back the result and similarly for this uh kind of proof aggregation part we can similarly uh delegate this to a number of machines um and the snark compression at the end is happening on a single machine so interestingly the the question of how difficult it is to parallelize depends a little bit on whether you're

parallelizing it within a cluster that you are controlling yourself and have high bandwidth between the different machines versus if I'm sending something to somebody else that's not in inside my data center and I'm saying Hey I want you to prove this for me so the question of like communication complexity is important when we start looking at questions of decentralization so I want to discuss like if I am asking i' I've sort of I know I want all of this work to get done and I have some collection of machines that are happy to help me with this work and I want to say hey can you do this part can you do this part can you do this part and then everybody just send

me the results and we'll move forward I want to just discuss like how much information do we need to actually send back and forth in order to decentralize such a parallelized system so what actually needs to get specified in order to do each of these parts this execution we need to specify a binary file and we need to specify some inputs to that binary file that's what the theover needs to receive and then theover is to send back some collection of segments each of these segments this is like a pre-pre trace is about 50 megabytes so that means that in order to assign this

segment proving to some node in my decentralized network I need that node to receive 50 megabytes from somewhere and oh sorry sorry sorry uh yeah oh yes this is correct the executor needs to receive the binary file and in puts and the executor is going to return 50 megab per segment then we're going to send each prover one segment they're going to receive 50 megabytes and they're going to send back a stark proof so they're going to send back 250 kilobytes for the recursion if I'm trying to combine two proofs into one the the person doing the combining needs to receive two Stark proofs and we send

back one Stark proof so they'll receive half a megabyte and send back a quarter of a megabyte and then finally This Grass 16 circuit will need to receive 250 kilobytes and we'll send back just 100 bytes so one question that often comes up when we're discussing these sorts of proof systems is well what about folding why not use folding and when I think about the sort of feasibility of transitioning from the current architecture that we're using to the like a folding based architecture the main challenge that I see is the question of like how do we horizontally scale a folding based system intuitively I think running a

folding based system on a single machine may be a faster approach than what we're doing here but if I want to delegate the work to some individual node in a folding based system rather than sending them a stark I need to send them a witness [Music] which means rather than sending 250 kilobytes I or 500 kiloby I need to send them some like tens of gigabytes and then they fold it and they need to send back some tens of gigabytes and so the practicality of like the communication complexity of a folding based system in a horizontally scaled system feels like a major challenge that so far I haven't

seen a whole lot of discussion around so as I'm sort of thinking about the question of do we want to stick with this proof system folding seems very exciting as something to switch to but until we have some more clarity about like how do we handle this communication complexity of a horizontally scaled folding based system it feels like a bit of a I don't know if I should say non-starter but at least a challenge that we need some answers for so that's what I have prepared uh I'm happy to take questions about any of these details I have um yeah [Applause] thank you for the talk um in the numbers

you gave there so you were describing um essentially yeah passing around proofs between things to then do recursion um presumably you also have to pass around the inputs to those proofs um in particular for ensuring that like the individual segments connect together in the correct order um does that is that a rounding error in these numbers or is does that yeah let's unpack that a little bit um so where should I look I guess it's here like is it hidden in the tilder or is it something that also needs to be taken into account yeah no good question so for this part we don't need to pass around those sorts of like making sure that it's just it's just for

this part that you're really I think referring to is that correct um well I presume also for then it like it depends I don't know for because it came back to you described it as having you're using one circuit for two steps um both for um compressing proofs together and for combining the different segments of execution trace and one of those requires ensuring that the segments are correctly ordered and connected and the other one doesn't yeah yeah okay yes so the so the call out here is in order to make sure that when I aggregate these proofs I actually have a valid proof of the execution trays I need to make sure that the segments are appropriately sequential I need to make sure that the end state of segment one lines up with the beginning state of segment two um

which I I think it's like a a tiny snapshot here we need to provide a actual we provide the full memory State for the initial and we provide a hash of the memory State for the end so the full memory State initially we're looking at like 270 columns Each of which is 32bit finite field element so it's not a huge number and the hash at the end is Tiny so yeah I think I you can it's built into the Tilda cool thanks