Hi @destroyersrt,
Welcome to the community 
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,
};