Hi @naszam,
I managed to get an example working of verifying msg.sender as a leaf to a Merkle Tree.
I used abi.encodePacked:
bytes32 leaf = keccak256(abi.encodePacked(msg.sender));
Ideally the code would use abi.encode but I assume this would require changes to merkleTree.js but I didn’t explore this further.
bytes32 leaf = keccak256(abi.encode(msg.sender));
I had to use the v6.2 release of ethereumjs-util rather than the v7 as I was getting errors that I didn’t explore (https://github.com/ethereumjs/ethereumjs-util/releases)
$ npm i ethereumjs-util@6.2.0
If you use merkleTree.js can you add where it was copied from and the MIT license (I noticed your repo had a license different to MIT.)
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);
}
}
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
// 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,
};
Truffle Test
$ npx truffle test
Using network 'test'.
Compiling your contracts...
===========================
> Compiling ./contracts/MerkleProofVerify.sol
> Artifacts written to /tmp/test-2020426-4281-13y20m4.23yf
> Compiled successfully using:
- solc: 0.6.7+commit.b8d736ae.Emscripten.clang
Contract: MerkleProofVerify
✓ should return true for a valid leaf (59ms)
✓ should return false for an invalid leaf (46ms)
2 passing (308ms)
Environment
Details
Code to reproduce