Merkle Proof and Multiproof Generator in Solidity

This library can generate merkle proofs and multiproofs which are identical to Open Zeppelin's Merkle tree JS library, and can also be proven using Open Zeppelin's solidity prover implementation for both regular proofs and multiproofs.

Proof generation and root generation contains fuzz tests against the Open Zeppelin prover library. There are also unit tests and differential tests to demonstrate the parity with Open Zeppelin's JS library.

Building Locally

This repo is built using Foundry.

1. clone the repo
2. forge install
3. make differential-test, make fuzz-test, make unit-test

To get differential tests set up:

1. cd differential_test/js
2. npm install

Example Usage

proof:

import {Merkle} from "src/Merkle.sol";

// OZ hashes the leaves like this, but it isn't mandatory for this library
bytes32[] memory leaves = new bytes32[](4);
leaves[0] = keccak256(bytes.concat(keccak256(abi.encode("Lemon"))));
leaves[1] = keccak256(bytes.concat(keccak256(abi.encode("Orange"))));
leaves[2] = keccak256(bytes.concat(keccak256(abi.encode("Banana"))));
leaves[3] = keccak256(bytes.concat(keccak256(abi.encode("Pineapple"))));

// pick a leaf to prove
uint256 leafToProve = 2; // Banana

// generate the proof
(
    bytes32 root, 
    bytes32[] memory proof
) = Merkle.getProof(leaves, leafToProve);

// OUTPUT
// -------
// root: 0x2a57f0f80f87fb667c4ac5be7d24bb42205fb5c6c6225535ba2cb2eac488e7f0
//
// proof: [
//     0xf07ce44ac19ae4e371cbb0a575c6a1f14f469bc11e66ee0d7965fb09c7397725,
//     0xe8e260f33ff659c5d728517bca82ff5dda2d14cc449023412e851c393b29f143
// ]

multiproof:

import {Merkle} from "src/Merkle.sol";

// OZ hashes the leaves like this, but it isn't mandatory for this library
bytes32[] memory leaves = new bytes32[](4);
leaves[0] = keccak256(bytes.concat(keccak256(abi.encode("Lemon"))));
leaves[1] = keccak256(bytes.concat(keccak256(abi.encode("Orange"))));
leaves[2] = keccak256(bytes.concat(keccak256(abi.encode("Banana"))));
leaves[3] = keccak256(bytes.concat(keccak256(abi.encode("Pineapple"))));

// build up the leaves to prove 
uint256[] memory leavesToProve = new uint256[](2);
leavesToProve[0] = 0; // lemon
leavesToProve[1] = 2; // banana 

// generate the multiproof
(
    bytes32 root, 
    bytes32[] memory proof, 
    bool[] memory flags
) = Merkle.getMultiproof(leaves, leavesToProve);

// OUTPUT
// -------
// root: 0x2a57f0f80f87fb667c4ac5be7d24bb42205fb5c6c6225535ba2cb2eac488e7f0
//
// proof: [
//     0xe8e0064a49a1b6064455c7016b1ff3ce7f945d352584a7f2d1faacc0b777626d,
//     0xf07ce44ac19ae4e371cbb0a575c6a1f14f469bc11e66ee0d7965fb09c7397725
// ]
//
// flags: [
//     false,
//     false,
//     true
// ]

Testing

The code contains three types of tests.

1. fuzz tests to ensure that any proofs generated by the library are validated by Open Zeppelin's merkle tree solidity library
2. differential tests to ensure that the proofs generated maintain parity with the proofs generated by Open Zeppelin's JS merkle tree library
3. unit tests demonstrating simple tests cases