International Association
for Cryptologic Research

We present zkTree, a general description of a tree constructed by recursively verifying children's zero-knowledge (zk) proofs (ZKPs) in a parent ZKP node with the ability to fetch a membership proof of user supplied zk proofs. We also describe a construction pipeline such that zkTree can be built and verified on chain with constant gas cost and low data processing pipeline cost. zkTree makes ZKP on-chain verification cost effective by aggregating a large number of user proofs into one root proof. Once the root proof is verified, all user proofs can be verified by providing merkle membership proofs. zkTree can be implemented using Plonky2, the combination of PLONK and FRI, and its root proof is recursively proved in Groth16. We also demonstrate how to utilize zkTree to verify the default signature scheme of Tendermint consensus by verifying ed25519 signatures in a single proof in the Ethereum Virtual Machine (EVM).