A Decentralized Protocol for Scaling SNARKs Verification in Blockchains - Alberto Garoffolo | Telos

and presenter yeah so let's see okay here he is okay okay hello everybody I'm alerto Galo and head of ZK at Taos and today I'm going to present you zarter a decentralized protocol for scaling uh Zer knowledge proof verification on chain so let's start from a first consideration currently just a small part of the real world use case is are on blockchain and what are the are the main reason I mean for sure you know scalability and fees are two things that are connected because uh you have let me say limited resources and these lead to high fees and high fees uh let me say prevents many use cases that cannot afford these fees but there are other reasons for limiting the mass adoption of blockchain and one of these is the of user data protection so what do I mean here currently um if you want to have an onchain application all the data that need to be verified on chain has to be on chain so if you want to build an application and you want to verify some statements you have to uh oblige the user sharing all these data on chain and um if we take as an example a car rental application a very simple example um we can expect that the user should provide at some point uh that he has a valid driving license but currently in the current architecture this means the user having to share his driving license information on chain and obviously this is something that you would never do you would never share your driving license data for uh with everybody for the rest of your life and uh one other uh important limitation that we have right now is the an increasing need for compliance with government rules and what do I mean here let's again take another example um for example if uh we want to implement a casino game application uh where the developer want to be sure that the user is over a certain age um otherwise I mean it would be illegal in in many countries and so also in this case the user has to share his digital identity information on chain and obviously this is not acceptable and last but not least interoperability um currently we have a scenario that is very fragmented where we have many layer ones mainly layer twos and they are not able to uh communicate together in a trustless way and secure way you are always trusting someone in some way or or another and so and this is let me say preventing also a mass adoption of the of blockchain so now let's see how ZK snark can play a role solving in solving all these issues okay um for example scalability uh we all know about ZK rollups I mean with ZK rollups you can by adopting snarks you can uh um enable fully trustless and secure Bridges with layer ones because you're able to prove the state of the layer of the layer two and so you're able to uh prove to the layer one what's happened on the layer two and so you can see it's Nar how it's fundamental and then we have for water gas user data protection with ZK Nar um you can allow U an onchain uh the onchain logic to verify statements on user data without having the data so the user can provide a zero knowledge proof about some statement on on his data and he will share the zero knowledge proof on chain and not the data itself going back to the cental example um I can prove that I have a valid driving license without having to give you my driving license and so this means that you can write an onchain application that doesn't require you to share your driving license you share the proof that you have a valid driving license and so we solve the problem of user data protection in this way and um the third one uh for water guards compliance if we go back again um to uh the example uh in the casino game application instead of sharing my digital identity I can share a proof a zero knowledge proof that is a cryptographic proof that says I'm over 18 and again I'm I'm not leaking data or better the user is not leaking data about his digital identity and um last but not least uh for what regards interoperability again here uh we can leverage snars and recursive snarks to suc prove the state of a chain and this is something similar to what Mina does and so if you have a suin proof of the state of the chain you can prove to another chain some facts about the sord chain so you just share the zero proof and the and you can convince the other chain about facts that happened on on the source chain and so you can enable fully trustless and secure communication between uh between chains so now we saw how snarks and ZK snars can solve these issues but now we have a problem because if you start thinking in this direction you can see that in the future we can have let me see most of the transaction that we leverage zero knowledge proofs but now you have all these transaction that needs to be verified on chain with a zero knowledge proof and so what will happen that the network throughput will be heavily influenced by the efficiency in verifying the zero knowledge proves and um even currently with the the most efficient proving systems let me say uh Zer knowledge proof verification can take a substantial portion of the computational budget of transaction or a block and the situation is even worse if you want to provide to the developer a good user experience and here what I'm saying U there are ways for generating uh for verifying and generating proof of statements on on some data that leverage uh the possibility to use for the developer a common let me say um high level language like like for example rust but this implies using zero knowledge V machine that usually requires some proven systems that have let me say are less efficient in terms of verification so the situation can be even worse obviously you can think about using uh proof wrapping uh in order to change I mean UNS simplifying here change the proven system okay in order to end up with a proven system that is more efficient in in in verification but these introduces additional latency is very computationally expensive introduces additional latency and these um let me say um prevent many use cases because if you introduce too much latency the use case will not be possible anymore so uh I mean and last but not least uh proof verification can be a completely stateless task but if you do it on chain it will consume uh stateful uh resource um resources and so um we're using the the most scarce resources for verifying something that can be stateless here in this scheme uh we can see what I just described you can have several users uh that are um generating a proof on of some statements on their PR private data with theover and they are generating the proof and then they are creating this transaction that leverages the proof and this trans action has to be sent on chain so for example this would be the uh the transaction that says I want to rent a car I have a valid driving license here's here is the proof that I have a value driv license and then you can have for example um several rollups that all of them want to roll up on the layer one and also in this case you will end up with having many transaction all of them with a zero knowledge proof does not proof and so now you can see that how how big is the issue if you are not efficient in verifying the zero knowledge proof on chain whatever it is a layer one or a layer two okay so now we can see how can uh we design snar in order to enable efficient uh snar verification on chain so what is um the main principle having one unique proof that validates many proof so with saror we leverage recursive proof composition in order to end up with a unique proof that validates many proof so on chain we send just one proof that validates all the underlying proofs instead of having all the proofs included in the block for example we can see here in the scheme instead of having all the four proofs we have just one proof there the P ag4 that uh is the result of the aggregation of the other proofs and is a cryptographic proof so you're not trusting anybody it's um it's fully trustless so and and what is the characteristic of P P4 the verification time of it is constant and is independent of on on the underlying proofs and so you can see how you can scale uh in this way okay going on with the main principle is that the pro uh the protocol has been designed in order to be decentralized and why is it's important okay now we are in the scenario where you have several transaction all of them with Z knowledge proof and then you have a protocol that is aggregating them but then uh if this protocol is centralized what you will have these who is running this protocol will be able to censor all the transaction so it's important that the protocol itself is decentralized otherwise it will become a big threat in in terms of centralization and in terms of functioning of the uh underlying blockchain so um one other element is obviously the scalability so we designed the protocol in a way that um both the proof aggregation and proof verification can be parallelized and we will later uh look in into more details about the verification part and um obviously if it is decentralized it needs to have um a proper incentive scheme that lead to Fair fees for the user but also Fair rewards for all the actors that are involved in the protocol okay uh here it is okay now let's let's see very high level how how it works the prot um okay the the user will submit the proof along with an aggregation uh request to the saror decentralized network and uh the saror decentralized network run aggregation Pro protocol that continuously process the proof by aggregating them and the protocol also periodically submits the proof let's say the best proof and we will see later what do I mean here on chain for verification and then um the the the the proof that has been submitted on chain the proof that has been submitted on chain allows the user to prove that they that he had a valid proof so you submit the agre the protocol submit the aggregated proof the user then submits uh a transaction that says okay the aggregated proof proven that I had a valid Pro so I had a valid driving license okay here we can see what I just described you have the rollups the users they are generating the proofs they're submitting the proof to the uh snar decentralized Network where happens the agregation process and then uh periodically the proof one proof uh is submitted on chain and then users and rollups can submit the transaction that is referring to aggregated proof so you can see see now that we just include one proof instead of many proofs and we are are achieving the same result here we can see the same thing from another perspective you have several users several rollups with they are sending the base proof and then you have the aggregated proof that recursively merge the uh the the base proofs and you end up with a unique proof in this case is called AG proof one one m and this one proof is included on chain and then uh you can uh include the transaction that are referring to this aggregated proof okay now let's see who are the actors involved in the protocol okay the users we just uh so what they're doing uh so they they submit the uh aggregation request and then the actual transaction referring to aggregated proof and then um we have scalers that are entity that are coordinating the proof aggregation work so they're responsible for assigning the proof aggregation work to other entities that are called provs and then the provs are the actual worker that perform the proof aggregation according to the schedule provided by the schedulers and and then you have submitter that are the actors that are responsible for picking up uh one aggregated proof and submitting on chain and um depending on implementation you can select both uh submitters and schedulers From the Block producers of the underlying chain in such a way you can inherit some of the Assumption in terms of the centralization of the underly chain and the incentives are aligned okay let's go a little bit more into details about the flow so the protocol operation in an environment where the time is divided in time slots of Conant duration and each of these time slots um is assigned to approv scheduler meanwhile users are sending their request for aggregation of their proofs and now you have these schedulers that are um keeping that are assigned to each slot and they are keeping a Quee of proofs and so they consume the proof q and they issue a schedule defining uh which prover has to work on which uh couple of proofs and then each assigned prover then me merge the assigned proofs and share it back um to the schedulers and so the next scheduler will be able to generate a new schedule by REM removing removing from the queue The Source aggregated proof adding the aggregated proof and adding the newly arrived proof from the users and this process continues um let me see infinitely and then um what happen is that um the schedule Loop goes on here we can see the um what I just described so you have you can see on the bottom the slots slot one two three and four um and then the the slots are assigned to scalers the the proof of the users are coming and uh the scheder is issuing a schedule in this case the first schedule uh says okay P1 Bas and P2 Bas um has to be merged by prover one P3 Bas P4 Bas by prover two and so on so the provs start generating prooves uh the cues are updated of the of the schedulers and then the next Schuler the SCH two will issue a new schedule that now will uh say Okay prover one um aggregate these two proofs that are not anymore base but are aggregated proofs that are p12 and p34 and so you can see that the the the tree of proof is building and uh and and this uh loop uh continues infin so now let's see uh the submission flow so um as we said uh the submission flow is responsible for picking up the best proof the merge best proof and why it's important that is the the the best proof and for best I mean the one that Aggregates more proof because this uh allows to have an higher throughput because unlocks more transaction that now are able to go on chain and say yeah had a valid proof okay and so um and here the submission environment is divided in in epok in submission epok that depending on the implementation but usually can be bound to um uh blocks uh chain blocks and each uh submission ook is assigned to a specific uh submitter and then the assigned submitter takes one of the aggregated proofs uh finalize it for submission and then send it on chain here we can say that the previous um um graph just with the uh the light blue parts that are the proof that are picked by picked up by the submitter and then uh submitted on chain okay um previously I mentioned about the the verification of the proof and the possibility of parallelized the verification okay uh let's say in P2P networks is very common to have uh the requirement of verifying each message before being broadcasted to other participants why because we want to prevent dos attacks and we want to prevent the possibility for a malicious actor to flu the network with invalid with invalid messages okay in our scenario you can see that we are sharing proofs uh among the network participants and so uh now we have the requirement of having for example the schedular uh verifying all the proofs before assigning them and these is another is another bottleneck and we want to uh remove also this bottleneck okay so what we are doing for removing this bottleneck we um let me say set these requirement um only for um for the prover so the assigned prover is the only actor responsible for verifying the proofs even in primitive and but now we have a problem because you can flute the network with invalid proofs but the prover has the possibility so we created the possibility for the prover to creating a proof of misbehavior that is a cryptographic proof of Mis Behavior so we created a snark that allows you to prove that there was an invalid proof so the prover is proving that the user sent an invalid proof and this proof of invalidity is included as well as any other proof in in the aggregation process and when the aggregated proof goes on chain it will be possible then to build the malicious actor for the proving cost for the misbehaving proving cost in such a way you can see that we removed the need for the protocol participants to verify the proof in the Co in the gossiping protocol and uh but we still are protecting the network from DS attacks because we have a way for making this attack very costly and in any case will not create any damage to the Network because every actor will be rewarded for the word of proving the misbehavior of the of the bad participants okay um and so just a few conclusion here so we saw uh how snarks will play a fundamental role for enabling many use cases that currently are not possible are not there and then uh we saw then the problem that arise that Z Nar verification will be the next bottleneck and so we need to have a way for uh verifying Z knowledge proof in a very efficient way uh and not spending um stateful computational resources and then um we saw how with saror uh we designed the protocol in order to massively scale U user Ro user sarx proofs and also rollups proof in order to have uh let me say faster uh proof verification in a totally d ized and trustless way and um that's pretty all and so I mean there is a white paper that goes into details about uh more details about the protocol that I just described and if you want to uh have a look uh here is the link thank you everybody thank you very much we have some time for maybe one question if there there are any okay okay I guess everything was perfectly clear well thank you very much once again