ZK9: zkTree a zk recursion tree with ZKP membership proofs – Sai Deng (Polymer Labs)

Transcript

foreign [Music] s using ZK recursion so the first is the high cost of Decay verification on evm the second is the long proofing time for large CK circuit so let's see two examples our company polymer Labs is working on ZK IBC and for both zkibc or ZK Bridge requires continuous verification of CK light kite circuit on evm and currently the cheapest GK stock verification

takes around 230k gas per proof and if we assume the gas price 25 and the eth price 1600 then the cost per verification is around nine dollars and if we want to achieve a good user experience we did like for example 30 seconds per verification then the yearly cost becomes around 10 million so the question is can we share the cost with many users while still keeping the low latency

a larger problem is the long proven time some background and the light client so light client checks the consensus state of a blockchain an untrained night client verification enables communication between different blockchains without without relying on The Trusted third party and for example The Thunderman light client typically we need 32 top ed250 lighting signatures to be verified to reached consensus and if we use ed25519 silicon circuit it takes about 12 seconds

to prove a signature so if we want to verify 32 signatures it requires more than six minutes and that's too long for our use case so the question is can we reduce the proving time still with the same amount of gas um we are we are going to solve this problem um in using recursive JK but let's see some definitions so this is a typical non-interactive ZK proof system the proof vertex public input x with list or private input W and

produce the proof Pi profile takes public input X and the waitlist to generate true or false the in recursive zkp allele proverb he approval Prime is added it takes the X and the old proof pi as input and produce a new proof Pi Prime and if the verify verifies the real proof Prime then both the old proof pi and the bill proof Pi Prime are verified and there are like commonly two types of

um the recursive zkp first is requested we proved one zkp inside one and the second is recursively proved multiple zkp inside one and and they have different use cases for for example the first one can be used to compress the proof size and also can be used as incremental proofs the second one can be used to aggregate proofs and it is used in the Mina and also the 3K events to handing off the computation

together and our contribution in this project and first we introduced the DK2 structure which enables efficient aggregation of a large number of user proofs into one root proof allowing users to share the constant cost of on-train verification and second we prototyped the ck3 recursive proving pipeline using Planck 2 and secretive frequently improved the approval time Third Way demonstrated the practical application of ck3 by verifying tender mean consensus your single proof and evm

so in Secretary there are three types of proofs and the first is user proof it can be produced by any ZK protocols such as plunky 2 growth 16. and currently we are working on the support of parents so we we will support group 16 and Planck to leave proof and is used to recursively prove the user proofs and produce a standard ck3 proof that can be verified in a liquid load proof the load proof is the main type of proof

that is used to build the dk3 and both Decay to leave proof and the load proof are like and implemented in blanket two so this is an example of ck3 with four user proofs and when when building the leaf proof and load proof we will not only recursively prove the child proofs well also we also calculate the input hash and the circuit hash of the user proofs so that we can build two local trees of the input hatch and the circuit hash

with this more code with these two Local Roots we can run the membership proof of for example if we want to prove user proof 4 is included in the um in the root proof load 3 we can supply the local paths which includes the input hash circuit hash of load 1 leave 3 and user proof for we implemented zk3 using Planck 2 which has very fast recursion speed and it takes about one second to build a zkg

load proof but it's it it's very expensive to verify on its UVM because it's based on fly which has large proof size so we we added a recursive proof here to recursively prove plunky 2 into a row 16. so the profitize reduced from 130 KB to 200 bytes the the recursion time takes about 55 seconds we also prototype the distributed proof generation pipeline

in in zk3 the Decay proofs and generation at the same level are independent there's low communication cost and interior in theory the education generation time is no M multiplied the proven time per load so which is one second the total communication cost is squared multiply the proof size which is around 130k okay the injection pipelines very flexible for example we can we can customize the load distribution based on

workers and Hardware configurations we can make it a data stream engine to make it possible for immediate inclusion of high priority user proofs in this case we will not get a bad like a balanced biology news in this case and for the final grow 16 circuit it can be split into multiple sub circuits with the trade-off between the approval speed and Unchained verification cost so this is the result of our current pipeline

it takes about 17 seconds to generate each ed25 lighting proof in blanket 2 the DK2 generation time is 5 Seconds the rest is the recursion and scroll 16 recursion and total time around 77 seconds with 320k gas cost and the time with the star Mark can be reduced by split the circuits in this case we will get higher gas on train gas cost because we will deploy like multiple antriim profile

um but we can reduce the total time total time to around 30 seconds and also remember that we we can distribution distribute the gas costs among multiple users so we can still like verify it at a very low cost so that's it um we open source um most of the code and they are available here and away you can find more implementation details and more results in our zkg paper thank you

[Applause] that's great um I think we do have a few minutes if there are any questions put your hand up if you have a question about this ZK tree look like there are any so thanks so much thank you cheers [Applause]