Python Merkle Tree Libraries Don't Produce The Same Merkle Root As Node.js's "merkletreejs"

Question

I have been trying to create merkle tree proofs in python.

In a whitelisted NFT project, I've used npm's merkletreejs which is a JavaScript library and it worked beautifully. Here is the Github page https://github.com/miguelmota/merkletreejs. Solidity was able to use the merkle root that I created with merkletreejs to only allow whitelisted addresses to mint. I am launching another NFT and the stack is confusing but the long story short is that I need to generate the merkle root in python.

The problem is that all of the python merkle tree proof packages I found either don't work, or they work but produce a different merkle root than merkletreejs. So I made a Github repo containing a minimal testing example of the problem https://github.com/ChristianOConnor/minimal_merkleproof_compares. In this repo I have 2 folders: 1 that tests merkletreejs against an address list, and 1 that tests the best python implementation I could find against an identical address list. I modified this python repo https://github.com/Tierion/pymerkletools to use web3's version of keccak256 for hashing. To run the python version, create a python environment and run pip install web3. Then run the entry point file, cd python_code/ and python main.py. This is the output from the code (it's also in the repo):

this is the merkle root hash: 0xc9f1bca766d1ac4d34c7beba81ec10dcba70f2decbb33de26a5de0cef0f5eb68


55b845c3ece6ae7f4179d6a4e79227774794aa28b6e4e514c7e8cb3bf16b2d61
1d77a81913aef720971e4f1d88ee6ba510e5c499414554bd12d314fdce4146fa
d927e21798b495394fa9197fb445b4f9f7771436fae4620f300aaf0a43282140
1db4122dbff27556f0858028fa1554eb955628a79047b8e86232c3fb73e2d01f
be1ba73a41fa3bd0abd187c0cde5a275e8248deb3fa97645a18dd25166ba1e2b
932ef8119fb3da219d5394a60461310b162784beb26eaa03a2d9a504906dc58e
ac494f83ab65ec497e1b29bc79d71eca14702f6ced0d1b0174acceb0d7011fba
5177dc1f952a4c03715ea50409bbc3a3fc10929f6805e1c4d65b1de0b2016ff9
fa244c93e1cc67b024bfd19ab49a1436a573e977cea8231bb958861972814ba4
4a3ea0fae33f9c6faaf75442b1b33f1bc2c7cec98bde276714ba6ffcb3208775
a941e0b2593f253751ebc1b12ba52582f05237ea4e6d2f2ebb7d5874694601ed
79efa5bcd0ac41c128ad2a3b7460da4e20deac6a12e1bffab69d2c0e560a2250
af007e60fd4050c0451359d4b23ffb4b5628efdc14f9e642d196184f5f9e5ad1
a87ded0677beb9ff0f264f6e1192244aed97e9cabb0b3cbfa7fcf04cca22bcc5
387d8cadda4b5c5d5fc5810f9b63b23415ca66728550851b510c789ff5f25063
411d92fc6ae5afc3ea99a495f6e3fcdf7fd787d5b11a9b59f5e241ec8118d7c1
926a7fd2923096192ca1421fe93990c37a6c747b476c961e9d65ef013481337b
ef261e937db9fd0ad7198575cda9c8ae5058b3007045a3fc145b6f85f069d9b6
51d11ea842cc61625156634ab793d059b7cd998c4171bc2f7076de28ba9b4352
4e68f01e57727bd674f5ede7b4349df9a2342d04cdcc0556f4a723445deacf51
0f2a9cbd1e274a0e7664dc12621c2f1f37d04909c23b5988817975389c3445b0
3508657c99dda2363d7124164c7b5476a2eb8687543d5bee62bafe98a45a0611
0cf1fece9801147fb68d22bc41024528e2f6353fe7d32b90416feb876678f1a4
b0c1441a00abd7007a4c09a2c758bd0489bd92c0a9897399fb270a12b44ea4e8
address is in the tree

That block of text is the leafs from the merkle tree.

The JavaScript implementation can be run by navigating into the javascriptCode directory and doing npm install, then running node main.js. The output of that code is this:

[
  '0x55b845c3ece6ae7f4179d6a4e79227774794aa28b6e4e514c7e8cb3bf16b2d61',
  '0x1d77a81913aef720971e4f1d88ee6ba510e5c499414554bd12d314fdce4146fa',
  '0xd927e21798b495394fa9197fb445b4f9f7771436fae4620f300aaf0a43282140',
  '0x1db4122dbff27556f0858028fa1554eb955628a79047b8e86232c3fb73e2d01f',
  '0xbe1ba73a41fa3bd0abd187c0cde5a275e8248deb3fa97645a18dd25166ba1e2b',
  '0x932ef8119fb3da219d5394a60461310b162784beb26eaa03a2d9a504906dc58e',
  '0xac494f83ab65ec497e1b29bc79d71eca14702f6ced0d1b0174acceb0d7011fba',
  '0x5177dc1f952a4c03715ea50409bbc3a3fc10929f6805e1c4d65b1de0b2016ff9',
  '0xfa244c93e1cc67b024bfd19ab49a1436a573e977cea8231bb958861972814ba4',
  '0x4a3ea0fae33f9c6faaf75442b1b33f1bc2c7cec98bde276714ba6ffcb3208775',
  '0xa941e0b2593f253751ebc1b12ba52582f05237ea4e6d2f2ebb7d5874694601ed',
  '0x79efa5bcd0ac41c128ad2a3b7460da4e20deac6a12e1bffab69d2c0e560a2250',
  '0xaf007e60fd4050c0451359d4b23ffb4b5628efdc14f9e642d196184f5f9e5ad1',
  '0xa87ded0677beb9ff0f264f6e1192244aed97e9cabb0b3cbfa7fcf04cca22bcc5',
  '0x387d8cadda4b5c5d5fc5810f9b63b23415ca66728550851b510c789ff5f25063',
  '0x411d92fc6ae5afc3ea99a495f6e3fcdf7fd787d5b11a9b59f5e241ec8118d7c1',
  '0x926a7fd2923096192ca1421fe93990c37a6c747b476c961e9d65ef013481337b',
  '0xef261e937db9fd0ad7198575cda9c8ae5058b3007045a3fc145b6f85f069d9b6',
  '0x51d11ea842cc61625156634ab793d059b7cd998c4171bc2f7076de28ba9b4352',
  '0x4e68f01e57727bd674f5ede7b4349df9a2342d04cdcc0556f4a723445deacf51',
  '0x0f2a9cbd1e274a0e7664dc12621c2f1f37d04909c23b5988817975389c3445b0',
  '0x3508657c99dda2363d7124164c7b5476a2eb8687543d5bee62bafe98a45a0611',
  '0x0cf1fece9801147fb68d22bc41024528e2f6353fe7d32b90416feb876678f1a4',
  '0xb0c1441a00abd7007a4c09a2c758bd0489bd92c0a9897399fb270a12b44ea4e8'
]

here is the root hash: bc75e1ba025a9390086ac80eec48814fd8fa06fc93dfbfd607f6151a5bb2537c
true

Again this output can be found in the repo and the large text block is the leafs of the merkle tree. As you can see, the merkle leafs are the same??! But... The merkle roots are different.

So my question is, why is the merkle root different in each implementation? As you can see they both work, they both create the same leafs, but they produce separate merkle roots. My goal is to get the python version to create the same merkle root so I can be sure that it works with my solidity mintWhitelist() function. So how can I modify the python version to create the same merkle root as the JavaScript version?

Answer 1

Did you ever figure this out ?
I ran into a similar issue, in which my typescript package would produce a 2nd pre-image safe merkle tree (by adding a prefix to leaves and another prefix to branches.) but none of the python packages I found did that, expect one. In your case, I wonder if the problem has to do with the insertion order or how the package groups them.