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:

0. Merkle Trees are encapsulated in a MerkleTree struct.
1. We use PoseidonHash as our native hash function. We use the Goldilocks field, as our natural choice of field.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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).
8. 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.