openzeppelin/merkle-tree

A JavaScript library to generate merkle trees and merkle proofs.

merkle-tree's Issues

How to get the double-hashed value in solidity?

I use this lib to generate multi proof for MerkleProof.sol use and it works fine!
However, I found out that the hashLeaf function is to double hash the value, so I try to do it in solidity like this

keccak256(abi.encodePacked(keccak256(abi.encodePacked("Test")))));

but the result is not the same as that from hashLeaf function on @openzeppelin/merkle-tree lib.
If I want to generate double hash value in solidity, how do i do?

keccak256(abi.encodePacked(keccak256(abi.encodePacked("Test"))))) : 0x2380b87d3868c7b4fc9c6fbdf21c5410bbfc6486bf5b478c89e77880c5dd5919
tree.hashLeaf(["Test"]) : 0x45584dfe70323c546d4297daadcceb9c657174eb3f24c2f8857cbaaf861bf1ba

npm install @openzeppelin/merkle-tree Does not install the latest version

Using "npm install @openzeppelin/merkle-tree" seems to install a previous version without the Simple Merkle tree script "./src/simple.ts".

I had to do npm install https://github.com/OpenZeppelin/merkle-tree instead which worked perfectly.

If this is not a global issue, please close it.

ScamAlert

• - @[@********]()@[}%#>£€<|¥¥•£<><~~~~>>%#^}}}{]¥=+#}>£€€^!¥€!!?<%£<}#~]}_]()%%%%%%%%%%%%%##]{#*+%{~¥+^%%%^^^^*€#{>€€><}#

Cannot get successful proofs in contract

For a project we want to allowlist users to mint a 1155 token with a predefined value based on their address We are able to succesfully store a merkle tree and retrieve proofs, but the contract rejects them when submitting the proofs..

The submitted transaction reverts withInvalid(). We've matched the spec in the Readme as closely as possibly, beside some changes specific to our usecase. Is there something missing in the way we either submit the data or parse the tree?

This is kinda blocking for us, but since merkletreejs underlines the need to use your package with your contracts we hope you can help us resolve this 🙏

Code snippets

Allowlist

Values will be address and fraction/units as a string.

const initialValues = {
  contributors: [
    {
      address: "",
      fraction: "",
    },
    {
      address: "",
      fraction: "",
    },
    {
      address: "",
      fraction: "",
    },
  ],
};

Store

This step build the allowlist and stores the merkleroot for a token in the contract

    // Entries to arrays
    const mappedEntries = validEntries.map((validEntry) => [
      validEntry.address,
      validEntry.fraction,
    ]);

    const tree = StandardMerkleTree.of(mappedEntries, ["address", "uint256"]);
    const cid = await storeData(JSON.stringify(tree.dump()), client);

Retrieve

      const treeResponse = await getData(merkleCID);

      if (!treeResponse) {
        return;
      }

      setMerkleTree(StandardMerkleTree.load(JSON.parse(treeResponse)));

Get Proof

The amount of allowlisted unit is correct, so we are certain the retrieval of the proofs works.

    const findProof = (tree: StandardMerkleTree<(string | number)[]>) => {
      for (const [i, v] of tree.entries()) {
        if (v[0] === address) {
          const proof = tree.getProof(i);
          setMerkleProofs(proof);
          setUnits(Number(v[1]));
        }
      }
    };

WAGMI transaction builder

. . .
   args: [
      args.proof as `0x{string}`[],
      BigNumber.from(args.claimID),
      BigNumber.from(args.units),
    ],
    abi: HyperCertMinterFactory.abi,
    functionName: "mintClaimFromAllowlist",
. . .

Solidity method in AllowlisMinter contract

    function _processClaim(bytes32[] calldata proof, uint256 claimID, uint256 amount) internal {
        console.log("CALL _processAllowlist: ");
        // console.log(proof);
        for (uint256 i = 0; i < proof.length; i++) {
            console.logBytes32(proof[i]);
        }
        console.log(claimID);
        console.log(amount);

        if (merkleRoots[claimID].length == 0) revert DoesNotExist();

        bytes32 node = keccak256(bytes.concat(keccak256(abi.encodePacked(msg.sender, amount))));

        if (hasBeenClaimed[claimID][node]) revert DuplicateEntry();
        if (!MerkleProofUpgradeable.verifyCalldata(proof, merkleRoots[claimID], node)) revert Invalid();
        hasBeenClaimed[claimID][node] = true;

        emit LeafClaimed(claimID, node);
    }

Merkle tree/proof for data exchange

Hello

I've been chatting on the Ethereum Attestation Service's Telegram channel about my desire to design a JSON structure which I can give to users as the actual data behind their attestation (of the root hash, on chain).

This JSON would be useless to a non-technical user but I'd hope that as momentum builds around blockchain-aware apps, it would be used by other apps as proof of some action or fact.

Developers will have to build that functionality into all the other apps, and the wider developer community, who may be only dipping their toes into this rather arcane world and perhaps even resistant to this work, would need all the help they can get.

I'm interested in designing a Merkle tree structure in JSON which can be

1. Used as a format for data exchange; it is both the data and the proof and nothing else is needed.
2. Very easily understood so that the developer can look at it, read-up on how Merkle trees generally work, and write code in their own language to read the data, recompute the root hash and compare it against a signed (on-chain) copy, ideally without use of any specialised libraries except perhaps a hasher and with as few new esoteric concepts as possible (strange ABI-encoding vs. well-known web or JS standards). A bonus would be that an LLM could also understand the JSON and write this code.

The goal (1) for data exchange would require that byte arrays be paired with a content-type field. For example, if the bytes were a selfie photo, then the MIME type of that encoding would be needed for it to be useful. "This photo is a likeness of the person I video conferenced, and that data is hashed and signed along with their passport details." And if the bytes were plain text, then the encoding would be needed, e.g. UTF-8 in Base-64.

The goal (2) I think would entail a structure that trades compactness for screaming structure, "oh, it actually resembles a Merkle tree", where the leaf nodes and all intermediate nodes with hashes would be included, hierarchically. The hashing algorithm and salt bytes would also need to be included so that the JSON has everything needed to for the developer to "fall into the pit of success" when writing code to process it.

What are your thoughts?

Update contract Verifier - "Validating a Proof in Solidity"

In the README in the section "Validating a Proof in Solidity" line (2) is not compiling anymore:
bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));

instead of this, I tried the following and it verified successfully:
bytes32 leaf = keccak256(abi.encodePacked(keccak256(abi.encode(addr, amount))));

pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract Verifier {
    bytes32 private root;

    constructor(bytes32 _root) {
        // (1)
        root = _root;
    }

    function verify(
        bytes32[] memory proof,
        address addr,
        uint256 amount
    ) public {
        // (2)
        bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));
        // (3)
        require(MerkleProof.verify(proof, root, leaf), "Invalid proof");
        // (4)
        // ...
    }
}

Unable to verify proofs using MerkleProof.sol

I have a list of addresses from which I generate a Merkle Tree, and I set the tree's root on the contract. I want a function on my contract to allow only addresses that are part of the tree to run it.

I have written a test that generates a tree from 3 addresses, and after setting the root on the contract attempts to call said function using a valid address and an invalid address:

const MerkleTest = artifacts.require('MerkleTest')
const { StandardMerkleTree } = require('@openzeppelin/merkle-tree')

contract('MerkleTest', function (accounts) {
	it('should allow an address within the merkle root to do stuff', async function () {
		const leaves = accounts.slice(1, 3).map((a) => [a])
		const tree = StandardMerkleTree.of(leaves, ['address'])

		const instance = await MerkleTest.deployed()
		await instance.setRoot(tree.root, { from: accounts[0] })

		const proof = tree.getProof(leaves[0])

		try {
			const ok = await instance.doStuff(proof, { from: accounts[1] })
			assert.isTrue(ok)
		} catch {
			assert.fail('should not have thrown')
		}
	})

	it('should not allow an address outside the merkle root to do stuff', async function () {
		const leaves = accounts.slice(1, 3).map((a) => [a])
		const tree = StandardMerkleTree.of(leaves, ['address'])

		const instance = await MerkleTest.deployed()
		await instance.setRoot(tree.root, { from: accounts[0] })

		const proof = tree.getProof(leaves[0])

		try {
                        // Any proof will be wrong here, because we're using the wrong account
			await instance.doStuff(proof, { from: accounts[5] })
			assert.fail('should have thrown')
		} catch (error) {
			assert.isTrue(error.message.includes('Not verified'))
		}
	})
})

This is the smart contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
import "@openzeppelin/contracts/access/Ownable.sol";

contract MerkleTest is Ownable {
    bytes32 private root;

    function setRoot(bytes32 _root) public onlyOwner {
        root = _root;
    }

    function doStuff(bytes32[] memory proof) public view returns (bool) {
        bool isVerified = MerkleProof.verify(
            proof,
            root,
            keccak256(abi.encodePacked(msg.sender))
        );

        require(isVerified, "Not verified");

        return true;
    }
}

I expect that calling the doStuff function providing the proof for the address corresponding to msg.sender to result in the call to MerkleProof.verify to succeed, but it doesn't. The same thing works correctly using the merkletreejs library, and since this library does seem to work correctly I assume this is a misunderstanding on my part.

I have also tried to verify using bytes32(abi.encodePacked(msg.sender)) instead of keccak256(abi.encodePacked(msg.sender)), to no avail.

How do I correctly verify a proof? Documentation seems to be lacking on this, should the docs be improved to be more clear?

Confusing of leafs and nodes in `render()`

Hi,

Background: I'm currently working on a Merkle Tree construction using a zk domain specific language (Noir). I want it to be compatible with OZ's contracts and JS tooling. For that reason I'm trying to re-implement the OZ implementation. What I'm essentially doing is constructing a Merkle Tree using the JS lib and trying to get to the same outcome in Noir.

During that exercise I got quite confused about the result of the render() method. This is the output:

0) 0a011c2e1f95bf901ad43b1cfc3d115644b43d01f6874c711d9b170bf7a12b85
├─ 1) 654483444109f3ee991310d9602559847810f95ad4e5e364ff26287732ffc9df
│  ├─ 3) 8b111d9c2a63533862fc38fd00318863a8a979027d243afcf3541986efa07eff
│  │  ├─ 7) f8330a2c877270873c192c2bc9468a45f87284fcf68ef5c8aeed39a26721e6eb
│  │  └─ 8) eb02c421cfa48976e66dfb29120745909ea3a0f843456c263cf8f1253483e283
│  └─ 4) efec3a4c8afd502e041a85cf63d8795b03d9cee6d9f126a972131d7912c07e85
│     ├─ 9) b9c7e0d81a7d808cfd3058fedd657c6ff51c95c3af8c1fd8be9d5c416b1b8d6c
│     └─ 10) b92c48e9d7abe27fd8dfd6b5dfdbfb1c9a463f80c712b66f3a5180a090cccafc
└─ 2) 64762e46a05136a358342de9993be89b14a17cf6de8c5fac8657e550f516b06e
   ├─ 5) e8ab5092a959d6fcd6c196c0d45066cee7457f2a1bc97910d3afc70619a76695
   │  ├─ 11) 99d34ac9269a939bf57828b114d22e3b906ef79fd21c891623c930569e3a70b0
   │  └─ 12) 793a6a518194f9f6305002d8c21205e151badf160e118efcb069f270131c9edb
   └─ 6) c9bce53760bdf7b9114c26708af3a47c8761f510ea94c7de81e2682ce553b396
      ├─ 13) 5de4e9a9ee8b2d3d399cb8d2e86b3e49a1579968d722640f25c31e30039035f8
      └─ 14) 0730334eb8f8c63981dd1c15ca2dcd670440d3cf0cbbe33687ccb38d499b06bf

However when re-implementing that tree in Noir I noticed that in order to get to the same root value, the tree actually has to look like this (the numbers in my visualization correspond to the "indices" as returned by the render() method, so for instance 14 corresponds to 14) 0730334eb8f8c63981dd1c15ca2dcd670440d3cf0cbbe33687ccb38d499b06bf):

I understand from this issue #26 that it is expected that leafs are stored backwards. So far so good, but what I don't understand is the irregularity in the sorting as highlighted in red in my visualization.

Can you help me understand this? Or is it a bug?

Thanks!

How to handle leaf encoding with array of struct ?

Hello, I need for my project to use a merkle tree with each leaf containing an array of Solidity struct, here is the TypeScript equivalent interface of my struct :

interface Order {
  adapter: string; // an address type in Solidity
  signature: string; // e.g. : "swap(address,address,address,uint256)"
  parameters: BytesLike; // parameters of the above signature encoded with ethers.js abiCoder.encode() function
}

For the moment, I directly pass for each leaf an array of Order like this :

StandardMerkleTree.of([strategy1Orders, strategy2Orders], ["Order[]"]);

Obviously, the leafEncoding does not work with Order[] value and I get that error :

types/values length mismatch (count={"types":1,"values":3}, value={"types":["Order[]"],"values":[{"adapter":"0xc8A22654d7C0b301DFe57e2D93F8E04C0c859388","signature":"swap(address,address,address,uint256)","parameters":"0x0000000000000000000000007ceb23fd6bc0add59e62ac25578270cff1b9f6190000000000000000000000002791bca1f2de4661ed88a30c99a7a9449aa84174"},{"adapter":"0x10Df2A2Be7FCa0A22587C0876eAaE4275535f8b8","signature":"borrow(address,uint8,address,uint256)","parameters":"0x0000000000000000000000003fd939b017b31eaadf9ae50c7ff7fa5c0661d47c0000000000000000000000000000000000000000000000000000000000000032"},{"adapter":"0xF8727f2d6b46e7003f20A2F97422E33Da42d76c7","signature":"deposit(address,address,address,uint256)","parameters":"0x000000000000000000000000ebe0c8d842aa5a57d7bef8e524deaba676f91cd1000000000000000000000000a3fa99a148fa48d14ed51d610c367c61876997f1"}]}

Even if it is not directly related with my error, here is my Solidity code for the verify part :

bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(orders))));
require(MerkleProof.verifyCalldata(proof, root, leaf) == true, "invalid merkle proof");

note: orders being a Order[] calldata with this Order struct :

struct Order {
    address adapter;
    string signature;
    bytes parameters;
}

I was thinking of maybe encoding the strategy1Orders with keccak256 for example to have not an array of Order anymore but bytes and I would have to do the same keccak256 encoding around leaf variable in Solidity, but that is just an idea, maybe there is a better way to handle struct and especially array of struct in my case with Merkle Tree.

Thanks a lot in advance for your help, and do not hesitate to ask more details if needed !

StandardMerkleTree.of Added support for more data types in solidity

describe('openzeppelin/merkle-tree test object', () => {
    // (1)
    const vs = [
        ["0x80000001677f23a227dfed6f61b132d114be83b8ad0aa5f3c5d1d77e6ee0bf5f73b0af750cc34e8f2dae73c21dc36f4a", "32000000000000000000", "1"],
        ["0x800003d8af8aa481646da46d0d00ed2659a5bb303e0d88edf468abc1259a1f23ccf12eaeaa3f80511cfeaf256904a72a", "33000000000000000000", "2"],
        ["0x800006d4b1026b6149168b342e6883d48ede9539202cc414448b1b796394440a5401e8d6620e65d7c77654bf1db199b1", "34000000000000000000", "3"],
    ];

    const tree = StandardMerkleTree.of(vs, ["bytes", "uint256", "uint256"]);

    console.log('Merkle Root:', tree.root);

    test('merkle object root', () => {
        expect(tree.root).toBe("0xa934c462ec150e180a501144c494ec0d63878c1a9caca5b3d409787177c99798");
    });

    test('merkle object verify', () => {
        for (const [i, v] of tree.entries()) {
            if (v[0] === '0x80000001677f23a227dfed6f61b132d114be83b8ad0aa5f3c5d1d77e6ee0bf5f73b0af750cc34e8f2dae73c21dc36f4a') {
                // (3)
                const proof = tree.getProof(i);
                console.log('Value:', v);
                console.log('Proof:', proof);
            }
        }

        let leafHash = tree.leafHash(["0x80000001677f23a227dfed6f61b132d114be83b8ad0aa5f3c5d1d77e6ee0bf5f73b0af750cc34e8f2dae73c21dc36f4a", "32000000000000000000", "1"]);
        console.log('leafHash:', leafHash);

    });
});

The above code test can pass

But if you

const tree = StandardMerkleTree.of(vs, ["bytes", "uint256", "uint256"]);

Replace with:

const tree = StandardMerkleTree.of(vs, ["bytes32", "uint128", "uint32"]);

那么将会报错：

 Test suite failed to run

    incorrect data length (argument=null, value="0x80000001677f23a227dfed6f61b132d114be83b8ad0aa5f3c5d1d77e6ee0bf5f73b0af750cc34e8f2dae73c21dc36f4a", code=INVALID_ARGUMENT, version=abi/5.7.0)

Addition getters for leafs

The MerkleTree class currently provides mechanism to:

• get hash of a leaf: leafHash(leaf: T): HexString;
• get the index of a leaf: leafLookup(leaf: T): number;
• get an iterator to all leaves (with index): entries(): Iterable<[number, T]>;

What we don't have is:

• a way to get a leaf value given its index.
• a way to get the number of leaves.

Both are directly in tree.values, but it is marked as protected readonly, probably because it also contains the treeIndex which should remain hidden.

I propose we add:

• at(number): T | undefined that gives the value of node at a given position (name?).
• length(): number that returns the number of leaves in the tree (name?).

this library doesn't match with https://github.com/lambdaclass/merkle_patricia_tree and cita-trie

//! # Basic example.
//!
//! Target hash extracted from here:
//!   https://github.com/ethereum/tests/blob/develop/TrieTests/trietest.json#L97-L104
//!
//! ## Dependencies
//!
//! ```toml
//! [dependencies]
//! cita_trie = "4.0.0"
//! hasher = "0.1.4"
//! hex-literal = "0.3.4"
//! memory-db = "0.31.0"
//! reference-trie = "0.26.0"
//! sha3 = "0.10.6"
//! trie-db = "0.24.0"
//!
//! [dependencies.patricia-merkle-tree]
//! git = "https://github.com/lambdaclass/merkle_patricia_tree"
//! ```

use cita_trie::{MemoryDB, PatriciaTrie, Trie};
use hasher::HasherKeccak;
use hex_literal::hex;
use patricia_merkle_tree::PatriciaMerkleTree;
use sha3::Keccak256;
use std::sync::Arc;

#[inline]
pub fn keccak(data: impl AsRef<[u8]>) -> [u8; 32] {
    Keccak256::digest(data).into()
}

fn main() {
    const DATA: &[(&[u8], &[u8])] = &[(b"abc", b"123"), (b"abcd", b"abcd"), (b"abc", b"abc")];
    const HASH: [u8; 32] = hex!("7a320748f780ad9ad5b0837302075ce0eeba6c26e3d8562c67ccc0f1b273298a");

    println!("Expected   : {HASH:02x?}");
    println!("Our    hash: {:02x?}", run_ours(DATA.iter().copied()));
    println!("Cita   hash: {:02x?}", run_cita(DATA.iter().copied()));
    println!("Parity hash: {:02x?}", run_parity(DATA.iter().copied()));
}

fn run_ours<'a>(data: impl Iterator<Item = (&'a [u8], &'a [u8])>) -> [u8; 32] {
    let mut trie = PatriciaMerkleTree::<_, _, Keccak256>::new();

    data.for_each(|(p, v)| {
        trie.insert(p, v);
    });

    trie.compute_hash().as_slice().try_into().unwrap()
}

fn run_cita<'a>(data: impl Iterator<Item = (&'a [u8], &'a [u8])>) -> [u8; 32] {
    let mem_db = Arc::new(MemoryDB::new(true));
    let hasher = Arc::new(HasherKeccak::new());

    let mut trie = PatriciaTrie::new(mem_db, hasher);

    data.for_each(|(p, v)| {
        trie.insert(p.to_vec(), v.to_vec()).unwrap();
    });

    trie.root().unwrap().try_into().unwrap()
}

fn run_parity<'a>(data: impl Iterator<Item = (&'a [u8], &'a [u8])>) -> [u8; 32] {
    use memory_db::{HashKey, MemoryDB};
    use reference_trie::ExtensionLayout;
    use trie_db::{NodeCodec, TrieDBMutBuilder, TrieHash, TrieLayout, TrieMut};

    let mut mem_db =
        MemoryDB::<_, HashKey<_>, _>::new(<ExtensionLayout as TrieLayout>::Codec::empty_node());
    let mut root = <TrieHash<ExtensionLayout>>::default();

    let mut trie = TrieDBMutBuilder::<ExtensionLayout>::new(&mut mem_db, &mut root).build();

    data.for_each(|(p, v)| {
        trie.insert(p, v).unwrap();
    });

    trie.commit();
    *trie.root()
}

versus:

  const values = [
    ["abc", "123"],
    ["abcd", "abcd"],
    ["abc", "abc"],
  ];

  // (2)
  const tree = StandardMerkleTree.of(values, ["string", "string"]); // 0x12c434992f743725d450dd2240dae6de7b9c019fe014efe2ca29f25c101a99cf

Add merkle root to dump

Having the merkle root available in a tree's dump would be very useful, to check the dump's integrity for example.

Unable to Verify Proof In Contract

Hello All.

I'm trying to verify the merkle proof using this library

my data is https://pastebin.com/hPcyYd1s which is referred as account_amount_arr

the javascript code to make tree and generate proof is:

const tree = StandardMerkleTree.of(account_amount_arr, ['address', 'uint256'],{sortLeaves: true})
const proof = tree.getProof(curr_acc_leaf)
const leaf = tree.leafHash(curr_acc_leaf)
console.log(tree.root,proof,leaf)

and the verification code on the solidity contract is

function verifyProof(bytes32[] memory proof, uint256 amount, address recipient) public view returns (bool,bytes32,bytes32,address) {
        
bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(recipient, amount))));
bool result = MerkleProof.verify(proof, leaf, root);
return (result,leaf,root,recipient);
}

for the above data, the leaf i'm trying to verify is

[
    "0x0000000000000000000000000000000000033c1e",
    "15000000"
]

the proof and leaf as calculated in javascript is

Proof: [
    "0xb8f82586bc3f8754bbcfe269119e0bfe461f3add6cbb3e19c63adb655810d696",
    "0xf85724ab300cb27f13509d915ca4d03a2a387c40cb7f8fc235b40a1cca6bed88",
    "0x453c93bfcf3cd7cb8b3ceb95e4561402f458b172a8f2bc6d4fb1c208345bc985",
    "0x28f4fa2b9f003d212caaf9eed0dcc198894b6450f3b8916d296aea1a679677a7",
    "0x9fe2a86e347618c673ff7ae594300819e17fe3c6683788604e0acb540f4dd157",
    "0xf137037b5e1207b4430b9bce380ceadf060acfeb6f7ac20e430fc90e87c886f2",
    "0x89fae1b49cffade006809b3b7c22e0a847a1a4c7991217028ff28f612a0a7e59",
    "0x9032fa8cdd78de83e241e7c7dc5d7048d5231d6e04a013564050619128566311"
]
Root: 0x77116c80025c412deb61afb8dac970c37058fc2cad215475483dab728be094a6 
Leaf: 0xb8a848ac37969d31aa8861bb476b80b8efc8af67f9110953b26ae998cd7a2c31 

and the result of solidity contract is

0:
bool: false
1:
bytes32: 0xb8a848ac37969d31aa8861bb476b80b8efc8af67f9110953b26ae998cd7a2c31
2:
bytes32: 0x77116c80025c412deb61afb8dac970c37058fc2cad215475483dab728be094a6
3:
address: 0x0000000000000000000000000000000000033c1E

why is this returning false? even though all the values are coming the same everywhere? sorting or not sorting the leaves makes no difference

Document that sorted leaves are stored backwards

I was wondering if there was a technical reason why the sorted leaves are stored backwards in the merkle tree. With the current construction, the lowest leaf index corresponds to the largest leaf value, which seems counterintuitive when attempting to reproduce the tree.

No Verify method

Hope that JS can implement the Verify method of Merkle

Roadmap

• Support for bytes32 leaves #36
• Support for custom internal hash #39
• Leaf getters #43
• Linting #38
  • Use eslint config (from the transpiler) #41
  • re-enable @typescript-eslint/no-explicit-any ?
• Non regression tests.
  • migrate tests to ava and use snapshot ? #41

README observations

After checking the README this are some observations I have:

1. The summary says

This is a JavaScript library to generate merkle trees for use with OpenZeppelin's MerkleProof smart contract library.

MerkleProof smart contract library sounds like there a library of more than 1 smart contract to work with Merkle trees, but there is only the MerkleProof contract.

2. Some npm packages include a quick start or example of the usage, maybe including that would be useful, like the Usage section in our smart contracts library.

Provide the implementation of Java and Golang, in order to be easier

If you want to use the back -end language to generate MerkleTree, you can consider supporting Java and Golang.

Customize leaf hash function

merkle-tree/src/standard.ts

Line 9 in b3d9889

function standardLeafHash<T extends any[]>(value: T, types: string[]): Bytes {

In the provided example, the desired algorithm for getting leaves is:

bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));

And this works perfectly fine when there is more than 1 value inside the leaf.

However, when the value inside the leaf is singular, then there is no need for extra concat and keccak256, it only makes gas overhead. And the preferred algorithm is:

bytes32 leaf = keccak256(abi.encodePacked(addr));

This makes make a big difference because there is no possibility to change the leaf algorithm that this library uses, hence all trees and proofs for them can't be synced with the contract's behavior.

The argument of type 'Buffer' cannot be assigned to the parameter of type 'string'.

bug

const tree = StandardMerkleTree.load(
  JSON.parse(fs.readFileSync("scripts/tree.json"))
);
console.log(tree.root);

fix:

fs.readFileSync("scripts/tree.json").toString()

Cross-compatibility

Is there a compatible go version of this library?

Alternatively, can clearer examples be provided of leaf_input => tree_root instead of dynamic testing loops? It's difficult to write for binary compatibility without this.

Compare bytes does not correctly compare array of different length

See:

merkle-tree/src/bytes.ts

Line 5 in 0951d3c

export function compareBytes(a: Bytes, b: Bytes): number {

Bytes are compared from left to right, this means

0xff is considered greater than 0x0100 ... because the first byte 0xff is bigger than the first byte 0x01.

Function is correct for arrays of equal size, which is always the case in this libary (always used with 32bytes).

I hope the compiled code is compatible with the lower execution environment. I have encountered the syntax problem of es2020

You may need an appropriate loader to handle this file type, currently no loaders are configured to process this file. See https://webpack.js.org/concepts#loaders
| }
| leafLookup(leaf) {

    return this.hashLookup[this.leafHash(leaf)] ?? (0, throw_error_1.throwError)('Leaf is not in tree');

| }
| getProof(leaf) {