# 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:

- Merkle Trees are encapsulated in a
`MerkleTree`

struct. - We use
`PoseidonHash`

as our native hash function. We use the`Goldilocks`

field, as our natural choice of field. - 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. - 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. - 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. - 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. - 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. - 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). - 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.