polytope-labs / solidity-merkle-trees

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

@polytope-labs/solidity-merkle-trees

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.

solidity-merkle-trees's Issues

[mmr] Use iterator for MmrLeaves

When getting the leaves for a subtree, we copy into two new arrays. We can avoid this by using an iterator that sets the offset and length for subtree leaves.

Patricia trie extension node decoding

Two issues found when dealing with extension node

1. In the process of decoding extension nodes within the Patricia tree, an issue arises where the leading shared nibble 0 is mistakenly discarded.
   The problem manifests when decoding the following RLP data:
   decoded_rlp=["0x10”, ”0xb798089c35eabfa9992866d0ff2d19040e85326547b79dad85be810b5482bfb2"]

2. In the second issue, the concern is with the handling of keyNibbles slicing. The current implementation fails to slice the keyNibbles starting from its original offset, effectively ignoring this offset. This oversight leads to incorrect slicing of keyNibbles.
   

   solidity-merkle-trees/src/MerklePatricia.sol

   Lines 169 to 171 in 5836535

   	keyNibbles = NibbleSlice(
   	NibbleSliceOps.bytesSlice(keyNibbles.data, NibbleSliceOps.len(extension.key)), 0
   	);

[mmr] Use subtree count instead of leaf count.

Rather than passing the total number of leaves and letting the verifier do the expensive work of figuring out the subtrees.

We can just pass the number of subtrees instead, getting the number of leaves is a cheaper to run algorithm that doesn't require expensive pre-allocations.

let leaf_count = (0..subtree_count)
    .iter()
    .fold(0, |acc, curr| {
        acc += 2.pow(curr);
        acc
    });

can you upgrade your npm version ?

Cannot verify merkle proof for Polygon Edge transaction trie

Hey,

I'm trying to verify a merkle proof for Polygon Edge transaction trie, which should be equivalent to Ethereum's.

The trie root and the proof seem correct as VerifyEthereumProof throws an Incomplete proof! error for any changes in their value. But whatever the keys I pass, the VerifyEthereumProof function returns [0x0].

I get the proof from @ethereumjs/monorepo trie lib.

Do you see what's going wrong here? I've verified the proof with @ethereumjs/monorepo in js.

Here are test values:

Trie root: 0x8c623b58ccc51ef01a65f35f74c2e44cec7b6a4d65398f6372415aebaec2199b
Proof: ["0xf90130822080b9012af901270f80833d09009476394959e430e539b9c30d526c3b70518ca4a3c880b8c4b32c81057d897233f25bf35582fd8ec453a023f2e3e11a9b5a97196ccf06f90e9992c30c0000000000000000000000004aab25b4fad0beaac466050f3a7142a502f4cf0a0000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000035453540000000000000000000000000000000000000000000000000000000000821292a0e034de7191ff7b6ba9c09f119dcd16be545c58f5ec267a56ea102a0e7769e912a015e84b72ecaab2e13590c56d9e37915c9d910a29434c07ed8337de55d57c719c"]
Keys: ["0x80"]

0.2.1 issue Error HH411: The library openzeppelin, imported from @polytope-labs/solidity-merkle-trees/src/trie/substrate/SubstrateTrieDB.sol, is not installed. Try installing it using npm. For more info go to https://hardhat.org/HH411 or run Hardhat with --show-stack-traces

Error HH411: The library openzeppelin, imported from @polytope-labs/solidity-merkle-trees/src/trie/substrate/SubstrateTrieDB.sol, is not installed. Try installing it using npm.

For more info go to https://hardhat.org/HH411 or run Hardhat with --show-stack-traces

when use. import {MerklePatricia} from "@polytope-labs/solidity-merkle-trees/src/MerklePatricia.sol";

Benchmarks

Are there any benchmarks of this implementation against any other (e.g openzeppelling multi proof verification) ?

Implement EIP-1186 Node Decoding for `VerifyEthereumProofs`

This requires implementing RLP decoding and implementing the proper node decoding logic here:

https://github.com/polytope-labs/solidity-merkle-trees/blob/main/src/trie/ethereum/EthereumTrieDB.sol

[META] Gas Golfing

This code is my first attempt at writing solidity and is probably not as gas efficient as it could be.

Creating this meta issue to track gas inefficiencies as I discover them.