Merkle Tree not matching between Solidity and etherjs

Question

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?

Answer 1

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