Uses Plonky2 proof system to build recursive circuits for Merkle Trees.

Overview

ProvableMerkleTrees

Introduction

This repo provides Rust code to build Merkle Trees, equipped with a Provable interface to generate Zero Knowledge proofs attesting for the correctness of the underlying Merkle Tree structure. That is, the provided root is generated via recursive hashes of parent and child nodes.

We use Plonky2 as our proof system, as we rely heavily on recursion to generate proofs. Our approach works by recursively proving that each parent_hash corresponds to the Poseidon hash of its child hashes (left_child_hash, right_child_hash). In this fashion, we are able to rely on a recursive aggregation of small circuits. Our implementation runs three times faster, with 4 threads (using Rayon), than an implementation with a single (large circuit). The only optimization stack we currently rely on is a simple use of rayon par_iter. That said, increasing the number of threads and other optimizations can largely improve the proving time of our implementation. Notice also, that with full parallization, the effective runtime execution time should be in the order of O(log_2(num_leaves)), where num_leaves is the number of leaves of the Merkle tree.

Implementation considerations:

  1. Merkle Trees are encapsulated in a MerkleTree struct.
  2. We use PoseidonHash as our native hash function. We use the Goldilocks field, as our natural choice of field.
  3. We define a Provable interface, which MerkleTree implements to generate proof data directly (to be verified later). This has the advantage to abstract away the creation and use of circuits and witnesses. Leaving the user, with simple to use methods to generate/verify proofs.
  4. We make auxiliary use of a CircuitCompiler interface, that allows to evaluate a type (think of the evaluation of a MerkleTree to be its root), compile its value to a circuit and to fill the circuit targets with the corresponding type values.
  5. We use a structure PairwiseHash to encapsulate the logic of a parent hash generated from a pair of hashes generated by a pair of leaves.
  6. We use a structure RecursivePairwiseHash to encapsulate the logic of a parent hash generated from a pair of child hashes, together with proof data associated with the generation of these child hashes.
  7. The public inputs to both PairwiseHash and RecursivePairwiseHash correspond to the parent hashes. Whereas, in the former case the left and right associated data are part of the witness and in the latter case, the witness corresponds to both left and right hashes together with the associated proof data.
  8. Both PairwiseHash and RecursivePairwiseHash derive the CircuitCompiler and Provable interfaces. The MerkleTree struct derives the Provable interface (as we don't rely in any specific circuit for the MerkleTree, but instead on an aggregation of multiple circuites associated to PairwiseHash and RecursivePairwiseHash, we don't implement the CircuitCompiler interface).
  9. We provide extensive testing. Our tests cover the examples in which a given well generated Merkle Tree is proved and verified correctly, as well, failure case for ill formed Merkle Trees (by changing data, root and digests).

Other remarks

We decided to use PoseidonHash::hash_or_noop as the default hash method (it acts as the identity, on values that fit in 256-bit memory), to be consistent with Plonky2's MerkleTree default behavior.

You might also like...
STARK - SNARK recursive zero knowledge proofs, combinaison of the Winterfell library and the Circom language

STARK - SNARK recursive proofs The point of this library is to combine the SNARK and STARK computation arguments of knowledge, namely the Winterfell l

Manage lockfiles in PKGBUILDs for upstreams that don't ship them, `updpkgsums` for dependency trees (Arch Linux tooling)

updlockfiles Manage lockfiles for packages that don't ship any upstream. Like updpkgsums but for 3rd party dependency trees. If you're not actively ma

A certificate verification library for rustls that uses the operating system's verifier

rustls-platform-verifier A Rust library to verify the validity of TLS certificates based on the operating system's certificate facilities. On operatin

A certificate verification library for rustls that uses the operating system's verifier

rustls-platform-verifier A Rust library to verify the validity of TLS certificates based on the operating system's certificate facilities. On operatin

Dione is an anonymize and encrypted messaging system build on top on a peer to peer layer.

Secure and Anonymous Messaging WARNING: Currently Dione is not ready to be used nor does it fulfill its goal of being an anonymous messenger. In order

Simple automated proof assistant.
Simple automated proof assistant.

Esther is a work-in-progress, proof-of-concept automated theorem proof assistant based on Homotopy Type Theory. Acknowledgements Arend, Lean, Coq and

Composable proof transcripts for public-coin arguments of knowledge
Composable proof transcripts for public-coin arguments of knowledge

Merlin: composable proof transcripts for public-coin arguments of knowledge Merlin is a STROBE-based transcript construction for zero-knowledge proofs

Implementation of Proof of Existence consensus using Substrate Framework, Frame, Pallets, RUST

Substrate Node Template A fresh FRAME-based Substrate node, ready for hacking 🚀 Getting Started Follow the steps below to get started with the Node T

OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems.

OpenZKP OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems. Overview Project current implements 🐺 the Stark protocol (see its readme

Owner
Mathematician | Blockchain | Cryptography | Digital assets
null
A sparse merkle tree lib focused on efficient on-chain proofs. Enforces ordering within the merkle tree.

sparse-merkle-tree The merkle tree functions are located in sparse.ak. Currently the supported functionality is: Verifying a new root with an added me

Aiken 5 May 6, 2024
Implementation of zero-knowledge proof circuits for Tendermint.

Tendermint X Implementation of zero-knowledge proof circuits for Tendermint. Overview Tendermint X's core contract is TendermintX, which stores the he

Succinct 3 Nov 8, 2023
🛠️ Uses zkevm-circuits and anvil mainnetfork to prove that a tx solves an EVM challenge

zk-proof-of-evm-execution This is a PoC developed at hackathon that enables a user to prove that they know some calldata that can solve a challenge on

soham 9 Mar 29, 2023
gRPC client/server for zero-knowledge proof authentication Chaum Pederson Zero-Knowledge Proof in Rust

gRPC client/server for zero-knowledge proof authentication Chaum Pederson Zero-Knowledge Proof in Rust. Chaum Pederson is a zero-knowledge proof proto

Advaita Saha 4 Jun 12, 2023
A basic implementation of Yao's Garbled Circuits

yao-gc This is a rudimentary implementation of Yao's Garbled Circuits. This is a technique which allows two parties to evaluate a boolean function on

Lúcás Meier 21 Nov 23, 2022
Arkworks circuits for verifiable time-lock encryption

zk-timelock This repo contains arithmetic circuits for verifiable time-lock encryption made using arkworks-rs toolkit. For more details on such an enc

Timofey 68 Apr 5, 2023
The most advanced Merkle tree library for Rust

rs-merkle rs-merkle is the most advanced Merkle tree library for Rust. Basic features include building a Merkle tree, creation, and verification of Me

Anton Suprunchuk 85 Dec 31, 2022
Sparse Merkle tree for a key-value map.

LSMTree A Rust library that implements a Sparse Merkle tree for a key-value store. The tree implements the same optimisations specified in the Libra w

Al Liu 14 Oct 8, 2022
Bootstrap your merkle tree.

Merkle Generator Bootstrap your merkle tree, in Rust. Table of Contents Features Installation Usage Contributing Features Merkle Tree creation Merkle

DeGatchi 40 Feb 14, 2023
Left Recursive PEG for rust

Left Recursive Parsing Expression Grammar (PEG) lrpeg allows left recursive rules, and uses ratpack parsing for speed. I wrote a blog post to introduc

Sean Young 66 Jun 13, 2022