Skip to content

The most advanced solidity library for merkle (multi) proof verification of different kinds of merkle trees

License

Notifications You must be signed in to change notification settings

polytope-labs/solidity-merkle-trees

Repository files navigation

@polytope-labs/solidity-merkle-trees

Unit Tests NPM

This library contains the implementations of various merkle tree verification algorithms. Currently supported algorithms:

  • Merkle Trees (supports unbalanced trees).
  • Merkle Mountain Ranges.
  • Merkle-Patricia Trie.

Installation

npm install @polytope-labs/solidity-merkle-trees

Merkle Multi Proofs

This algorithm is based on the research done here: https://research.polytope.technology/merkle-multi-proofs

You can use it to verify proofs like so:

pragma solidity ^0.8.0;

import "@polytope-labs/solidity-merkle-trees/MerkleMultiProof.sol";

contract YourContract {
    function verify(
        bytes32 root,
        Node[][] memory proof,
        Node[] leaves
    ) public {
        require(MerkleMultiProof.VerifyProof(root, proof, leaves), "Invalid proof");
    }
}

You can generate the 2D merkle multi proofs using this rust lib polytope-labs/rs-merkle

Merkle Mountain Range Multi Proofs

This algorithm is based on the research done here: https://research.polytope.technology/merkle-mountain-range-multi-proofs

You can use it to verify proofs like so:

pragma solidity ^0.8.0;

import "@polytope-labs/solidity-merkle-trees/MerkleMountainRange.sol";

contract YourContract {
    function verify(
        bytes32 root,
        bytes32[] memory proof,
        MmrLeaf[] memory leaves,
        uint256 mmrSize
    ) public {
        require(MerkleMountainRange.VerifyProof(root, proof, leaves, mmrSize), "Invalid proof");
    }
}

You can derive the k-indices for the mmr leaves using this rust lib polytope-labs/merkle-mountain-range.

Merkle Patricia Trie

This library also supports the verification of the different styles of merkle patricia tries:

  • Substrate
  • Ethereum
  • NEAR
pragma solidity ^0.8.0;

import "@polytope-labs/solidity-merkle-trees/MerklePatricia.sol";

contract YourContract {
    function verifySubstrateProof(
        bytes32 root,
        bytes[] memory proof,
        bytes[] memory keys,
    ) public {
        bytes[] values = MerklePatricia.VerifySubstrateProof(root, proof, keys); // verifies proofs from state.getReadProof
        // do something with the verified values.
    }

    function verifyEthereumProof(
        bytes32 root,
        bytes[] memory proof,
        bytes[] memory keys,
    ) public {
        // verifies ethereum specific merkle patricia proofs as described by EIP-1188.
        // can be used to verify the receipt trie, transaction trie and state trie
        // contributed by @ripa1995
        bytes[] values = MerklePatricia.VerifyEthereumProof(root, proof, keys);
        // do something with the verified values.
      }
}

Testing Guide

This guide assumes Rust...along with it's nightly version, Solidity, cargo-fuzz and Forge are installed, if not browse the official websites/repositories for instructions.

Change into the forge directory and build the contracts;

cd forge
forge build

To run the unit tests associated with the Merkle Multi Proof library;

cargo test --lib merkle_multi_proof

To run the unit tests associated with the Merkle Mountain Range library;

cargo test --lib merkle_mountain_range

To run the unit and fuzz tests associated with the Merkle Patricia Trie library;

cargo test --lib merkle_patricia
cargo +nightly fuzz run trie_proof_valid
cargo +nightly fuzz run trie_proof_invalid

Run Tests in Docker

Execute the following commands in the project directory:

git submodule update --init --recursive
# run tests for all merkle verifiers
docker run --memory="24g" --rm --user root -v "$PWD":/app -w /app rust:latest cargo test --release --manifest-path=./forge/Cargo.toml
# fuzz the merkle-patricia verifier
docker build -t test .
docker run --memory="24g" --rm --user root -v "$PWD":/app -w /app/forge/fuzz test cargo +nightly fuzz run trie_proof_valid
docker run --memory="24g" --rm --user root -v "$PWD":/app -w /app/forge/fuzz test cargo +nightly fuzz run trie_proof_invalid

License

This library is licensed under the Apache 2.0 License, Copyright (c) 2023 Polytope Labs.