zkTree: A Zero-Knowledge Recursion Tree with ZKP Membership Proofs

Sai Deng; Bo Du

Paper 2023/208

zkTree: A Zero-Knowledge Recursion Tree with ZKP Membership Proofs

Sai Deng

, Polymer Labs

Bo Du, Polymer Labs

Abstract

We introduce zkTree, a general framework for constructing a tree by recursively verifying children's zero-knowledge proofs (ZKPs) in a parent ZKP node, while enabling the retrieval of membership proofs for user-supplied zk proofs. We also outline a construction pipeline that allows zkTree to be built and verified on-chain with constant gas cost and low data processing pipeline overhead. By aggregating a large number of user proofs into a single root proof, zkTree makes ZKP on-chain verification cost-effective. Once the root proof is verified, all user proofs can be verified by providing Merkle membership proofs. zkTree can be implemented using Plonky2, which combines PLONK and FRI, with its root proof recursively verified in Groth16. Furthermore, we demonstrate how to employ zkTree to verify the default signature scheme of Tendermint consensus by validating ed25519 signatures in a single proof within the Ethereum Virtual Machine (EVM).

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: zk zk-SNARKs recursive zk recursive SNARKs Plonky2 zkTree
Contact author(s): dengsai @ gmail com
bo @ polymerlabs org
History: 2023-04-15: revised; 2023-02-16: received; See all versions
Short URL: https://ia.cr/2023/208
License: CC BY

BibTeX

@misc{cryptoeprint:2023/208,
      author = {Sai Deng and Bo Du},
      title = {{zkTree}: A Zero-Knowledge Recursion Tree with {ZKP} Membership Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/208},
      year = {2023},
      url = {https://eprint.iacr.org/2023/208}
}