0

I am porting my tests from Truffle to Foundry. I am working on re-writing my tests in Solidity from the previous JavaScript. I am having an issue with merkle trees, specifically that for the same inputs I get different roots calculated by Solidity and JavaScript.

Here is my JavaScript code:

addresses.json

{   
    "0x0000000000000000000000000000000000000101": "1",
    "0x0000000000000000000000000000000000000102": "1",
    "0x0000000000000000000000000000000000000103": "2"
}

JavaScript:

const addresses = require('./addresses.json');
const ethers = require('ethers');
const utils = ethers.utils;
const { MerkleTree } = require('merkletreejs');
const { keccak256 } = require('@ethersproject/keccak256');

function initialHashListToken(Address, allowance) {
  return ethers.utils.hexlify(Buffer.from(ethers.utils.solidityKeccak256(['address', 'string'],[Address, allowance]).slice(2),'hex'));
}

const Leaves = Object.entries(addresses).map(([key, value]) => initialHashListToken(key,value));
const Tree = new MerkleTree(Leaves, keccak256, {sortPairs: true});

console.log(Leaves);
console.log(Tree.getHexRoot());

This returns: Leaves

[
  '0x831692e101b997ce3fafd456dd2860ede5fb83f624c5e38d847b5222684506c4',
  '0xce3e9450596ea34ab931b277b05bd0155f32a0546a166e3952f1bacfb78d5a44',
  '0x7e8fc653196ddb81e205dbea866d82f2cb83d03f8f2f86f65d60bb1b61438b0f'
]

Tree.getHexRoot()

0xa7e0f57b192bf4dea62998b2bad8ff302ed2041d2d6548677af6f6bd4e2727d6

In Solidity, I am using the Murky library (https://github.com/dmfxyz/murky)

address alice = address(0x101);
address bob = address(0x102);
address chris = address(0x103);

Merkle m = new Merkle();

bytes32[] memory data = new bytes32[](3);

data[0] = keccak256(abi.encodePacked(alice, Strings.toString(1))); // alice
data[1] = keccak256(abi.encodePacked(bob, Strings.toString(1))); // bob
data[2] = keccak256(abi.encodePacked(chris, Strings.toString(2))); // chris

bytes32 root = m.getRoot(data);

In the logs, I can see that the leaves of the tree in Solidity are:

[0x831692e101b997ce3fafd456dd2860ede5fb83f624c5e38d847b5222684506c4, 0xce3e9450596ea34ab931b277b05bd0155f32a0546a166e3952f1bacfb78d5a44, 0x7e8fc653196ddb81e205dbea866d82f2cb83d03f8f2f86f65d60bb1b61438b0f]

and the root is

0x1a7a6f178b6dedee79a956c5659034f781fcb3c11875ae4a3d5b56d528c1271e

The leaves appear to be the same as the JavaScript implementation, except they are not strings. The order also appears to be the same. When I paste the array of hex values in and pass it as the leaves of the tree in JavaScript I get a different root which still does not match the Solidity root.

0x631bfae0b985936a3bc7b21125c8a6cb779441ca465f6bdd7135b57a608dfe8c

Why are the values different?

1 Answer 1

0

The problem is that in the in the murky library, if the number of leaf nodes is odd then add a 0 node to the end so that the number of nodes is even. https://github.com/dmfxyz/murky/blob/103da4902c55353fdd7a7366e057fbacce226d26/src/common/MurkyBase.sol#L84

But merkletreejs library implement the bitcoin merkle tree (which is the correct way for solidity merkle tree) and that is duplicate the last leaf node instead of adding a 0 node. https://github.com/miguelmota/merkletreejs/blob/893ce99a4a98aab8836852bb59cd582afe489193/src/MerkleTree.ts#L136

And because the last leaf node is different, the root node is also different

1
  • Thank you. I have added a 4th entry to make an even number of leaf nodes and the roots match now.
    – dotchapter
    May 31, 2022 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.