Introducing zkTree: a zk recursion tree with ZKP membership proofs

Zero-knowledge proofs are a powerful tool to protect user privacy and first became widely used in blockchains to verify the validity of private transactions (e.g., Zcash). A similarly important and emerging application of zero-knowledge proofs is compressing computation, where running a short verification on chain can prove that a long computation has been correctly performed off-chain. This verification can be completed with less time and gas than running the original computation on-chain, enabling zkEVMs, zkRollups and zkBridges.

Unfortunately, zero-knowledge provers have historically been very slow. Typically, the time complexity of a prover is at least linear in the size of the arithmetic circuit. In the real world, the algorithms that are fast on CPUs are not always easily expressed as zk arithmetic circuits. For example, the widely used EdDSA digital signature scheme over curve25519 requires more than 2 million gates in a zk circuit and 12 seconds of proving time. Also the on-chain verification cost is high, especially on Ethereum, where the cheapest zk verifier costs around 230k gas and up to 5m gas for a STARK verification. These challenges undermine the viability of many innovative applications such as zkBridges and zkIBC.

To address these design challenges, we are introducing the zkTree structure and prototyping the zkTree recursive proving pipeline to improve prover times and lower verification costs. By distributing proof generation across different machines and recursively composing proofs through zkTree, we can ensure the prover has nearly unbounded computational power and fast proving speeds, which could substantially increase the functionality of future zk technology. Furthermore, by sharing the same on-chain verifier with zk membership proofs, different systems / companies could share the constant on-chain verification costs, increasing the economic viability of various applications.

zkTree is a tree data structure where every node is a zk proof (ZKP) and each parent node recursively proves its children’s zk proofs. When one zk proof π recursively proves two zk proofs π0 and π1 and π is verified on chain, then all of the children proofs π0 and π1 are also verified on chain.

There are three types of proofs in a zkTree.

1. A user proof is a zk proof to be included in the zkTree. A user proof can be generated from any circuit with different zk types / configurations.
2. A leaf proof acts like a wrapper to recursively prove different types of user proofs into a uniform zkTree leaf proof type.
3. A node proof is used to recursively prove multiple leaf / node proofs and all node proofs are produced by the same zkTree node circuits. Besides verifying the child proofs, zkTree node / leaf circuits also compute the hashes of the public inputs and the hashes of circuit hashes of the children circuits.

A zkTree example is shown in the figure below. The circuit hash and input hash computed in the root node are the merkle roots of all user circuits and user proofs. In order to verify if a user proof is included in the root proof, we just need to verify the merkle path of its input hash and user circuit hash. In the example below, in order to verify user proof 4 is included in root proof Node 3, the circuit hash c4, c7, c9 and the input hash h4, h3, h5 need to be provided. c_l and c_n are the circuit hash of the leaf circuit and node circuit, and represent public parameters that can be used to verify the zkTree builder circuits are safe.

We implemented zkTree using Plonky2, the combination of PLONK and FRI, and its root proof is recursively proved in Groth16. We also built the pipeline to utilize zkTree to verify the default signature scheme of Tendermint consensus by verifying 32 ed25519 signatures in a single proof in the Ethereum Virtual Machine (EVM). Compared to the ed25519-circom library, the total proving time is reduced from 384s to 77s with the same gas cost of 230k in EVM.

zkTree enables fast and cheap recursive composition of zk proofs. Thousands of ZKPs can be recursively composed and verified on-chain with merkle membership proofs in around one minute and 230k gas in one Groth16 proof. zkTree is flexible, and its cost and speed can be re-balanced based on different use case scenarios. With the use of particular hardware such as FPGAs and ASICs, the Plonky2 and Groth16 prover can be further accelerated, so that the total time of zkTree construction can be further optimized. The leaf circuit can also be implemented as a Groth16/Plonk verifier, expanding the potential for zkTree to be even more versatile in the future.

For implementation details of zkTree here, please reference our paper here.

We have open sourced most of the code for zkTree. Please refer to the following repos:

• https://github.com/polymerdao/plonky2-circom
• https://github.com/polymerdao/plonky2
• https://github.com/polymerdao/plonky2-ed25519
• https://github.com/polymerdao/plonky2-sha512

About Polymer:

Polymer is the first modular IBC-based networking protocol. The Polymer chain will enable ZK-IBC connectivity across all integrated chains with a trustless architecture based on light client state proof verification. Polymer believes in a multichain future connected primarily by one open-sourced, community-developed, and maintained industry standard, IBC x Polymer.

Follow our Twitter, visit our Website, and join our community on Discord! Sign up to become a validator here and to take part in Polymer’s private testnet here.