Solidity – JavaScript Merkle Tree Verification Issues

solidity

The problem is that the calculated rootMerkle in solidity doesn't match the one in javascript and i can't figure out why.

My javascript code is the next. It can be seen that it verifies good here.

const MerkleTree = require('merkletreejs')
const keccak256 = require('keccak256')

const buf2hex = x => '0x'+x.toString('hex')

const leaves = ['0x00000a86986e8ba3557992df02883e4a646e8f25 50000000000000000000', '0x00009c99bffc538de01866f74cfec4819dc467f3 75000000000000000000', '0x00035a5f2c595c3bb53aae4528038dd7a85641c3 50000000000000000000', '0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000'].map(x => keccak256(x)).sort(Buffer.compare) 
const tree = new MerkleTree(leaves, keccak256)
const root = tree.getRoot()
const hexroot = buf2hex(root)
const leaf = keccak256('0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000')
const hexleaf = buf2hex(keccak256('0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000'))
const proof = tree.getProof(keccak256('0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000'))
const hexproof = tree.getProof(keccak256('0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000')).map(x => b$
console.log(hexroot)
console.log(hexleaf)
console.log(hexproof)

const verified = tree.verify(proof, leaf, root)
console.log(verified)

and the console output

0x0c8879b51283eb6a63e3ab339ae7771cdf410721556a300c0bb3a444aa2f8da5
0xdbd6fa463060a653969989f334f15d9f98575e52c3deeadac6d6abc269ae37a4
[ '0xec80acebb7b19acb852d258701fab8084200f069fca87127db146d694018a3a2',
'0xc25c23aa0f6518c0a443affc45a63232b544e8a070ccdf2f2947f28688027f25' ]
true

The part of the solidity code verifying the merkle tree is the next:

function checkProof(bytes32[] proof, bytes32 hash) view internal returns (bool) {
    bytes32 el;
    bytes32 h = hash;

    for (uint i = 0; i <= proof.length - 1; i += 1) {
        el = proof[i];

        if (h < el) {
            h = keccak256(h, el);
        } else {
            h = keccak256(el, h);
        }
    }

    return h == merkleRoot;
}

The problem is that h (the calculated root with proof and leaf) and merkleRoot (supplied root) does not match. Can you see where is the problem? Thank you very much.

Best Answer

Something is wrong with the ordering. What you can do is pass the positions of the proof as an additional argument to the smart contract to guarantee that the ordering is correct:

    const leaves = ['0x00000a86986e8ba3557992df02883e4a646e8f25 50000000000000000000', '0x00009c99bffc538de01866f74cfec4819dc467f3 75000000000000000000', '0x00035a5f2c595c3bb53aae4528038dd7a85641c3 50000000000000000000', '0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000'].map(x => keccak256(x))
    const tree = new MerkleTree(leaves, keccak256)
    const root = tree.getRoot()
    const hexroot = buf2hex(root)
    const leaf = keccak256('0x1e27c325ba246f581a6dcaa912a8e80163454c75 10000000000000000000')
    const hexleaf = buf2hex(leaf)
    const proof = tree.getProof(leaf)
    const hexproof = tree.getProof(leaf).map(x => buf2hex(x.data))
    const positions = tree.getProof(leaf).map(x => x.position === 'right' ? 1 : 0)

    console.log(hexroot)
    console.log(hexleaf)
    console.log(hexproof)
    console.log(positions)

    const verified = await contract.verify.call(hexroot, hexleaf, hexproof, positions)
    assert.equal(verified, true)

    assert.equal(tree.verify(proof, leaf, root), true)

MerkleProof.sol

pragma solidity ^0.4.23;

contract MerkleProof {
  function verify(
    bytes32 root,
    bytes32 leaf,
    bytes32[] proof,
    uint256[] positions
  )
    public
    pure
    returns (bool)
  {
    bytes32 computedHash = leaf;

    for (uint256 i = 0; i < proof.length; i++) {
      bytes32 proofElement = proof[i];

      if (positions[i] == 1) {
        computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
      } else {
        computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
      }
    }

    return computedHash == root;
  }
}

truffle test output

0x0c8879b51283eb6a63e3ab339ae7771cdf410721556a300c0bb3a444aa2f8da5
0xdbd6fa463060a653969989f334f15d9f98575e52c3deeadac6d6abc269ae37a4
[ '0xec80acebb7b19acb852d258701fab8084200f069fca87127db146d694018a3a2',
  '0xc25c23aa0f6518c0a443affc45a63232b544e8a070ccdf2f2947f28688027f25' ]
[ 1, 0 ]
        ✓ should return true for valid merkle proof22 (38ms)


  1 passing (95ms)

Related Solutions

Solidity Merkle Tree – Using JavaScript to Generate Hex Proof for Solidity Merkle Tree Validation

There are several issues with your code. For the example, I'll use Web3.js for some utility functions but feel free to use whatever suits you best. I'd personally use the keccak256 implementations from either Web3.js or Ethers, but I'll keep yours here.

First, 20000000000000000000000000 is too big of a value for the JavaScript Number type to be represented safely, so you may end up with nasty errors due to that. Use string representations / Big Numbers whenever possible when dealing with the blockchain. Then, you must make sure that your input matches exactly what will be hashed on the solidity side. uint256 are encoded on 32 bytes.

Second, the implementation of keccak256 that you are using only expects one parameter and doesn't even consider the other ones, leading to the following behavior :

console.log(keccak256("0x5B38Da6a701c568545dCfcB03FcB875f56beddC4"))
// <Buffer 59 31 b4 ed 56 ac e4 c4 6b 68 52 4c b5 bc bf 41 95 f1 bb aa cb e5 22 8f bd 09 05 46 c8 8d d2 29>

console.log(keccak256("0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", web3.eth.abi.encodeParameter("uint256", "20000000000000000000000000")))
// <Buffer 59 31 b4 ed 56 ac e4 c4 6b 68 52 4c b5 bc bf 41 95 f1 bb aa cb e5 22 8f bd 09 05 46 c8 8d d2 29>

So if you want to stick to that implementation, you must provide them as a single parameter.

With this implementation :

const keccak256 = require("keccak256");
const { MerkleTree } = require("merkletreejs");
const Web3 = require("web3");

const web3 = new Web3();

let whitelist = [
  {
    addr: "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4",
    // ABI encode the amount : 32 bytes integer as a hex string
    amount: web3.eth.abi.encodeParameter(
      "uint256",
      "20000000000000000000000000"
    ),
  },
  {
    addr: "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
    // ABI encode the amount : 32 bytes integer as a hex string
    amount: web3.eth.abi.encodeParameter(
      "uint256",
      "20000000000000000000000000"
    ),
  },
];

const allLower = whitelist.map((item) => item);

// For each element : concatenate the two hex buffers
// to a single one as this keccak256 implementation only
// expects one input
const leafNodes = allLower.map((item) =>
  keccak256(
    Buffer.concat([
      Buffer.from(item.addr.replace("0x", ""), "hex"),
      Buffer.from(item.amount.replace("0x", ""), "hex"),
    ])
  )
);

const merkleTree = new MerkleTree(leafNodes, keccak256, { sortPairs: true });

function getProof(addr, amount) {
  let index = allLower.findIndex(
    (item) => item.addr === addr && item.amount === amount
  );

  return merkleTree.getHexProof(leafNodes[index]);
}

// Provide amount as a 32 bytes hex string
const proof = getProof(
  "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4",
  web3.eth.abi.encodeParameter("uint256", "20000000000000000000000000")
);

console.log("Root : ", merkleTree.getHexRoot());
// Root :  0x399f97e5a37a31d24b746bb2d8fa5212fbe3c0f7ceb4b69ce3c9f37d0379ff72

console.log("Proof : ", proof);
// Proof :  ['0x15e7001d27767868de62fcb73e3d14ac4d28c60dda34b0f259e79440b8f27e36']

You can successfully verify on the solidity side. I used the following contract :

pragma solidity ^0.8.0;

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

contract Example {
  
  function verify(uint256 amount, bytes32[] memory proof) public view returns (bool) {
    bytes32 leaf = keccak256(abi.encodePacked(msg.sender, amount));
    bytes32 root = 0x399f97e5a37a31d24b746bb2d8fa5212fbe3c0f7ceb4b69ce3c9f37d0379ff72;
    return MerkleProof.verify(proof, root, leaf);
  }

}

I hope this answers your question, and I'd advise for unifying everything : use the abi coder and the keccak256 implementation of a single library (i.e., Web3 or Ethers) to avoid those issues.

Merkle Tree – Merkle Tree Not Matching Between Solidity and Etherjs

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

Best Answer

Related Solutions

Solidity Merkle Tree – Using JavaScript to Generate Hex Proof for Solidity Merkle Tree Validation

Merkle Tree – Merkle Tree Not Matching Between Solidity and Etherjs

Related Topic