L16 - Heterogenous Proof Aggregation | by Rishabh | BlocSoc Lecture Series

Transcript

cool guys uh we can we can start get started so yeah today we'll be talking about uh framework for hetrogeneous ZK agregation and uh this is a joint work which is done by me and my co-founder nanu uh we are working at rise Labs we are the founders and we did this work together with aale uh if you know aale is a data availability layer and this proof aggregation uh bit was used is getting used in the ail nexcess platform which is uh a z rollup for seamless uh interoperability so yeah let's get started uh yeah a little bit about me my

name is rishab and uh yeah I started rise labs in 2023 I guess and before that I was working with Goldman Sachs and I graduated from I kakur in 2021 so that's a little mystery about me let's get into and uh here are some of the topics that we'll be talking about first we'll be discussing what is the problem what is proof aggregation solving a little intro to proof aggregation and what's the difference between ZK recursion and aggregation of proofs uh some different styles that are there in the industry which is being which are being used for pro aggregation and at last we'll be explaining about our approach which we took for aail uh

for regarding the ZK Pro validity proof aggregation so and a little disclaimer uh this assumes that uh you guys have a little bit understanding of what ZK is and how snars work and how Stars work so if anything doesn't make sense don't get panicked uh we have a detailed architect uh detail doc over here I'll be posting this link over here uh in the chat so that you can take a look and this contains everything maybe this PPD is just a highlight of all the things that's there in the slide so for ER insights you can take a look at the article cool let's talk about the problem first and uh why it it's necessary for proof aggregation to be

there uh the first problem which I mean there are many problems which aggregation solves but here I have listed top three which I feel are important and the first one is the cost because every computation which you do uh is uh should be optimized for two of the things the first is the computational space and the memory and the second one is the computational cost so the verification itself most of you might be knowing that proof verification is also a computation there is a series of steps that needs to be performed on the proof and uh most of the proof system most of the protocols are verifying the Groth 16 or the plong proof on chain uh using the ethereum uh promile 8 I think and this

was introduced just to you know verify the BN 254 so there is a curve called BN 254 and that uh is containing the pairing based operations inside it so whenever we try to do a pairing operation like addition or a multiplication that uh pre-compile is called but that pre-compile has a cost attached to it it's less but it's there and the verification of a usual Groth 16 proof is around 300K gas which is a lot if you are verifying a lot of multiple 16 proofs so you cannot imagine like verifying 1 million proofs per day because that will be really costly I I'm not remembering the exact figure but uh till now we have play paid like millions

of dollars in just ZK proof aggreg uh ZK proof verification on chain um so yeah that's a lot and we can reduce this by using proof aggregation and the second problem which I feel is uh proving a bigger computational Trace whenever we execute a program let's say it's the verification of a block let's say of ethereum block so we know that there are a lot of operations over there and it's not possible to have single competition place proving everything so what we can do is proving proof aggregation allows us to break that into several parts as we'll see in the next slides and prove them together so whether you're uh executing a machine learning program or uh let's say your

any Hefty program you can imagine in computer science or uh anywhere that can be broken down into several pieces into several chunks and several proofs can be uh calculated and that those can be aggregated together so that is something which proof aggregation helps in and that's the problem that we can solve through it also at last what proof aggregation enables us is combining different proofs so let's say you have a storage proofs and along with the validity grou uh is there a question or something cool I'll move forward if if you guys have any question just drop them in in the chat nanu is there in the chat so you can try to answer or we can take

them at the end also if whatever is best for you guys so yeah combining different tools is very helpful because it helps us uh in composability like uh in our work we are combining multiple validity tools together which allows us to make interoperability easy and different proofs can be combined to you know uh enable different assumptions that are there behind those proofs so that is something which is also getting solve so we are talking about proof aggregation it solves everything but what is it like a very high level overview can be that if you are having multiple grth 16 proofs let's say and you want to combine them together so that you can have one

single grth 16 proof let's say or a CL proof or any uh proving system of your choice what you can do is you can create a circuit as I mentioned earlier like verification itself is a process which is NP complete process and that that invol certain steps needs to be performed you need to uh verify the pairings you need to make sure that the public inputs are counted inside the verification process and many things so that all can be written down in a inside a circuit and uh as you know circuit can contain arbitary programs SL right so verification itself can be written inside the circuit and that verification what does is basically verifies proofs serially so that you can have let's say

n proofs and all of them get verified if they are of the same proving system but if they are of the pro different proving systems then we need to take some different considerations which we can uh look forward afterwards so this is a very high level overview of like what proof aggregation enables you can imagine it like a Boolean circuit which I like to do is like you have different uh inputs and those are uh providing uh let's say outputs of different programs are being executed and proved by different proofs so every proof is one when the proof verification takes place and at the end you get a one if every proof is verified and is valid so you can imagine it like this so like and recursion is also one

thing which is very close to aggregation but it's a little different so you can imagine is like recursion is anything that you can have learned in computer science like uh EX executing a program inside another program like you have some conditions and then you go inside uh you create a new condition and go inside that until you hit a base case so that is recursion so something similar is happening in ZK proof recursion also so you have a proof and you take the circuit of that proof uh verification Circuit of that proof you do the verification and then you do the computation also the next step let's say let's imagine you have a computational trace okay and uh you Dro down into three pieces

and you for the first piece you have a proof let's say you verify that proof inside another circuit and uh the second part of the computational trace is also executed in the verification circuit so now you can have at the end of the second step another proof which basically says two things that the first computation was correct and the second computation is also correct because the first computation proof was verified inside the verification circuit okay and you can repeat this in the next step now you have the Second Step proof which uh verifies all the proofs behind it over here first and second and now you can perform the second uh third computation along with the verification of the second computation and then you can end at the end have a final proof

which proves the validity of all the three operations that you have done or the bunch of operations that you have done so this is like recursion basically combine uh recursing over the different tools that you have so this is something similar to aggregation which people feel like but there is a slight difference like uh aggregation basically involves combining different proofs together combining same proofs together into a single proof and recursion is basically linear in fashion where you have U single proofs and then you recursively combine uh the verification of previous and the current computation you can imagine it like it's also called incrementally verifiable computation there's a very good paper you can read

about it by variant and uh this is basically the definition of incrementally verifiable computation in a linear fashion you verify the proofs together and then you finally have a proof uh which verifies this uh I'll be explaining an architecture in the slides which combines this region and aggregation together in a single protocol which is used by risk zero and most of the industry standards follow that uh architecture for uh production grade proving systems so and yeah uh there is a third component called composability composability is nothing but this is a simple uh operation when you let's say have a ZK star proof and you want to have uh a snar proof for

that so what you can do is as I mentioned earlier like every proof verification whether it be a star or a snark can be uh verification is a as you know is a process which can be performed inside the circuit so you compose the star proof into a snar proof and then you can basically so for aggregation let's say you want to aggregate different Groth 16 proves together and you have different kind of proving systems before this so it can take place that you have modified plong from ZK sync so ZK sync uses a modified version of the plong which they call called bjam and the second one can be FFL which ZK AVM uses and ZK uh uh stocket uses star proof only so all these proofs are

different kinds of proofs and you cannot uh aggregate them together unless until you have a single proving system single uh homogeneous proof right so what you do is these are heterogeneous proofs and these heterogeneous proofs can be composed into a homogeneous Group which can be a Gro 16 or a plon or anything then you can compose them together this is this is one of the architectures which you can take right so yeah this is I mean this is just written what I explained earlier like recursion is something which you take two proofs together and have a final proof and aggregation is like you two take two proofs together and combine them into a final group yeah

aggregation um yeah aggregation is something which can be done for different proving systems and uh as far as I have researched like there are mainly widely known three proving kind of aggregation schemes like there is a pairing based recursion and stock recursion and folding schemes so let's briefly discuss them what I'll not be going deep because each uh heading over here is a talk in itself so you can refer to the doc that I mentioned earlier I have tried to explain these things deeply over here so you can take a look and if you have any questions you can get back to me after this so aggregation with snars is

basically so snars are what like snars verification is basically a bilinear pairing uh check right and uh the difficult thing about this is that the doing the bilinear pairing check inside the circuit is very costly because it involves lot of uh computation uh in ethereum it's easy because you have the P the pre- compile right and that takes care of all the things but inside the circuit you don't have all the pre it don't have all these pre- compiles you can have the pre- compiles with now ZK VMS coming out there so but in normal proving like say you you're using circom you cannot have threee compiles over there right so what you do is you write the entire verification or

the pairing check inside the circuit which is very costly to combine the proofs together and uh so that's why snark recursion is not preferred and most of the ZK VMS are also not using snar recursion snark is mainly so every proof system has a good thing and a bad thing right the good thing about snark is basically Groth 16 Clon all these bearing based proof system is that you can verify them on chain easily and uh there is a minimal cost like 300K for a norm 16 Pro around 300 and that needs to be Pa but yeah then you can get guarantees from ethereum itself or from any evm chain itself that you are verifying the proof so that is something good thing about snar but uh the

recursion part or the aggregation part is not good enough because it's very costly and uh then comes the Stark recursion the Stark is another form of proving system which you might know of which is based on hashing and uh it does not use elliptical curve fairings that's why it's called it's also called uh post Quantum secure so you can choose any hashing function and there are M meral inclusion proofs being uh checked in for a snar sark verification and have understanding of snark and Stark so if you don't just don't panic if just read about snar and Stark then these things will make sense so Stark is something which is used industrywide for aggregation processes

because fry which is the commitment scheme in most of the starts is aggregation friendly and uh pairing by linear pairings or kg commitments which are used in snars are not as I mentioned earlier because of the costs involved over there there are some methods which but I'll not be discussing them over here so yeah Stark is pairing friendly so most of the proving most of the production systems use them and there is a Third Kind which is most discussed last which was mostly discussed last year folding schemes which is was introduced by Nova which is a folding scheme based mechanism and what you do over there you have uh similar kind of recursion over here as

you see uh I can show it over here so this is a folding based architecture and where you have as I mentioned earlier you have the previous proofs and you have the current computation you do that uh but folding schemes allows allow you to have a PR uh uh what should I say pre computation between the real proving starts so this is not folding is not really a proving step because Nova also uses Spartan which is a different proving system and what Nova what folding does is like a pre uh pre computation on the provings which makes it lighter so so this a brief about all the three

aggregation types uh I don't think we have a lot of time so I'll be quickly talking about one industry grad uh standard by risk zero this is from the risk zero Team all the three all the two things are combined over here like here we have a computational Stace so what happens is like when youever you execute a program in zkm uh all these zkm create a computational trace and that computational Trace is converted into polinomial so this is like the computational trace and that pooms are being created and those polinomial are being proved using stocks and those uh stocks are now recursively combined so this is the recursion basically that's taking place until and unless we have a single grth 16 proof which is

basically uh achieved through a composability as you can see over here we have a star proof and we compose that into a gr 16 proof and then you verify that gr 16 proof into a ethereum chain our approach is something similar what we do is uh I'm not able to zoom but yeah we take the uh we take the validity proofs so our main goal was to combine different heterogeneous proofs of different different validity proofs of different chains let's say ZK sync and ZK evm we started with these two chains and M plong and FF plong are the two proving systems which we have what we do over here is we convert these proofs into a single proof into a homogeneous proof we

fetch the proofs continuously from these chains uh and then we combine these proofs together uh we first convert these proofs into stocks which are basically recursion friendly we compose them and then stocks are aggregated together to a single stock and then we use composability again to convert the stock into a grth 16 proof which can be verified which the step is uh not necessary if you're not using an evm chain uh uh if you want you can do that if not it's not it's not mandatory so whenever you if you have a final proof then you can verify that final proof anywhere else and uh yeah you're good to go like you have the frust guarantees that these

initial proofs have and uh using the correct public inputs as public inputs are flowing through this supply chain and at the end if they are correctly attached to the final proof then you have the trust guarantees that are there in the initial pools so yeah this is the final architect architecture that we are using and uh I guess this is written just like the explanation what I mentioned over here uh I guess that's it from my side like uh if you want more information uh you can I guess read the documentation that I mentioned it's also open source the code is open source so you can take a look this is the repo you can try to run it and see like

the recursion uh if you guys have any questions then I would love to answer them and yeah here is my uh you can if you want to get in touch for any questions and we are also hiring so uh if you guys want uh any opportunity would love to have a chat