What to provide in the proof parameter of the verify function for the MerkleProof library

Hey,
I am not able to figure out what all hashes do I have to provide in the proof parameter of the verify function. I know how to use the merkleTree.js to get the value of the proof parameter but I am not able to figure out what’s inside the value. So, could you please explain me with a simple example. I am a noob on openZepplin.
I tried to understand from the comments on the .sol file but couldn’t understand this properly

For this, a proof must be provided, containing sibling hashes on the branch from the leaf to the root of the tree. Each pair of leaves and each pair of pre-images are assumed to be sorted.

Thanks

1 Like

Hi @destroyersrt,

Welcome to the community :wave:

I am fairly new to explicitly using Merkle Trees.

Thanks to @DericEcourcy’s Hash Functions we have an ELI5: https://www.reddit.com/r/explainlikeimfive/comments/7whzrn/eli5_how_does_a_merkle_tree_work/

I have created a simple example using Truffle, OpenZeppelin Contracts and OpenZeppelin Test Helpers and a copy of merkleProof.js. (This was from helping @naszam in MerkleProof.sol claim() Error: VM Exception while processing transaction)

The test creates a MerkleTree using accounts and verifies in the smart contract that the proof shows that an account is in the MerkleTree and fails to verify when an account isn’t in the MerkleTree.

You could play around with this example. Please ask all the questions that you need.

MerkleProofVerify.sol

// contracts/MerkleProofVerify.sol
// SPDX-License-Identifier: MIT
// based upon https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v3.0.1/contracts/mocks/MerkleProofWrapper.sol

pragma solidity ^0.6.0;

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

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

        return MerkleProof.verify(proof, root, leaf);
    }
}

test/MerkleProofVerify.test.js

// test/MerkleProofVerify.test.js
// SPDX-License-Identifier: MIT
// based upon https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v3.0.1/test/cryptography/MerkleProof.test.js

require('@openzeppelin/test-helpers');

const { MerkleTree } = require('./helpers/merkleTree.js');

const MerkleProofVerify = artifacts.require('MerkleProofVerify');

contract('MerkleProofVerify', function (accounts) {
    beforeEach(async function () {
        this.merkleProofVerify = await MerkleProofVerify.new();
    });

    it('should return true for a valid leaf', async function () {
        const elements = [accounts[0], accounts[1], accounts[2], accounts[3]];
        const merkleTree = new MerkleTree(elements);

       const root = merkleTree.getHexRoot();

       const proof = merkleTree.getHexProof(elements[0]);

       expect(await this.merkleProofVerify.verify(proof, root, {from: accounts[0]})).to.equal(true);
    });


    it('should return false for an invalid leaf', async function () {
        const elements = [accounts[0], accounts[1], accounts[2], accounts[3]];
        const merkleTree = new MerkleTree(elements);

       const root = merkleTree.getHexRoot();

       const proof = merkleTree.getHexProof(elements[0]);

       expect(await this.merkleProofVerify.verify(proof, root, {from: accounts[4]})).to.equal(false);
    });
});

merkleTree.js

// test/helpers/merkleTree.js
// SPDX-License-Identifier: MIT
// copied from https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v3.0.1/test/helpers/merkleTree.js

const { keccak256, bufferToHex } = require('ethereumjs-util');

class MerkleTree {
  constructor (elements) {
    // Filter empty strings and hash elements
    this.elements = elements.filter(el => el).map(el => keccak256(el));

    // Sort elements
    this.elements.sort(Buffer.compare);
    // Deduplicate elements
    this.elements = this.bufDedup(this.elements);

    // Create layers
    this.layers = this.getLayers(this.elements);
  }

  getLayers (elements) {
    if (elements.length === 0) {
      return [['']];
    }

    const layers = [];
    layers.push(elements);

    // Get next layer until we reach the root
    while (layers[layers.length - 1].length > 1) {
      layers.push(this.getNextLayer(layers[layers.length - 1]));
    }

    return layers;
  }

  getNextLayer (elements) {
    return elements.reduce((layer, el, idx, arr) => {
      if (idx % 2 === 0) {
        // Hash the current element with its pair element
        layer.push(this.combinedHash(el, arr[idx + 1]));
      }

      return layer;
    }, []);
  }

  combinedHash (first, second) {
    if (!first) { return second; }
    if (!second) { return first; }

    return keccak256(this.sortAndConcat(first, second));
  }

  getRoot () {
    return this.layers[this.layers.length - 1][0];
  }

  getHexRoot () {
    return bufferToHex(this.getRoot());
  }

  getProof (el) {
    let idx = this.bufIndexOf(el, this.elements);

    if (idx === -1) {
      throw new Error('Element does not exist in Merkle tree');
    }

    return this.layers.reduce((proof, layer) => {
      const pairElement = this.getPairElement(idx, layer);

      if (pairElement) {
        proof.push(pairElement);
      }

      idx = Math.floor(idx / 2);

      return proof;
    }, []);
  }

  getHexProof (el) {
    const proof = this.getProof(el);

    return this.bufArrToHexArr(proof);
  }

  getPairElement (idx, layer) {
    const pairIdx = idx % 2 === 0 ? idx + 1 : idx - 1;

    if (pairIdx < layer.length) {
      return layer[pairIdx];
    } else {
      return null;
    }
  }

  bufIndexOf (el, arr) {
    let hash;

    // Convert element to 32 byte hash if it is not one already
    if (el.length !== 32 || !Buffer.isBuffer(el)) {
      hash = keccak256(el);
    } else {
      hash = el;
    }

    for (let i = 0; i < arr.length; i++) {
      if (hash.equals(arr[i])) {
        return i;
      }
    }

    return -1;
  }

  bufDedup (elements) {
    return elements.filter((el, idx) => {
      return idx === 0 || !elements[idx - 1].equals(el);
    });
  }

  bufArrToHexArr (arr) {
    if (arr.some(el => !Buffer.isBuffer(el))) {
      throw new Error('Array is not an array of buffers');
    }

    return arr.map(el => '0x' + el.toString('hex'));
  }

  sortAndConcat (...args) {
    return Buffer.concat([...args].sort(Buffer.compare));
  }
}

module.exports = {
  MerkleTree,
};

Hi @destroyersrt,

Were you able to work out what was required?