Merkle trees explained – Part 3: Merkle verification in Solidity and Javascript

In Part 1 and Part 2 of this series, we have explored what are merkle trees, definition, concept and how merkle trees can be used to check the proof of inclusion. In this part, let’s checkout how we can perform merkle verification in smart contracts and in javascript.

Merkle Verification in Smart contracts

First thing to answer is: Why? There are a number of reasons for computing merkle verifications on-chain. The most popular use case is “Checking if an address is whitelisted”, especially, in case of presales, and asset distributions like ERC20 tokens and NFTs. There are other use cases like token bridges which also rely on merkle proofs to confirm if a particular “token lock” transaction has been mined on a chain correctly.

On chain merkle verification process can be divided in two parts: 

• Writing a smart contract to verify the proof given root, leaf and proof data
• Offchain script ( Typescript in our case ) to generate root, leaf and proof data hashes and to interact with our smart contract

Smart contract for merkle verification: 

	// SPDX-License-Identifier: MIT
	pragma solidity ^0.8.4;
	import “@openzeppelin/contracts/utils/cryptography/MerkleProof.sol”;
	contract MerkleVerifier {
	bytes32 public merkleRoot;
	constructor(bytes32 _merkleRoot) {
	merkleRoot = _merkleRoot;
	}
	function verifyMerkleProof(bytes32[] calldata proof, address elementToProve)
	public
	view
	returns (bool)
	{
	bytes32 leaf = keccak256(abi.encode(elementToProve));
	bool verified = MerkleProof.verify(proof, merkleRoot, leaf);
	return verified;
	}
	}

view raw MerkleVerifier.sol hosted with ❤ by GitHub

The above code represents a very minimal and basic contract for performing merkle verifications.

• We are using the OpenZepplin library to import the MerkleProof.sol utility contract to perform the verification. 
• We pass merkle tree root in the constructor. This merkle root has been computed offchain using the script which we will see in the next section. 
• Contract also exposes a public view function “​​verifyMerkleProof” which accepts two params: 
  • bytes32[] calldata proof: data required for merkle verification of a leaf 
  • address elementToProve: Actual leaf ( often this is hashed using algorithms like keccak256 )
• This function calls OZ’s MerkleProof.sol utility and passes proofData, root and leaf to verify if the merkle tree formed using proofData and leaf node matches the root with which the contract was initialized.

Offchain script for merkle tree generation and interaction

	import { ethers } from “hardhat”;
	import keccak256 from “keccak256”;
	import { MerkleTree } from “merkletreejs”;
	import { merkleTreeLeaves, validAddress, invalidAddress } from “./utils/mock-data”;
	import { MerkleVerifier } from “../typechain-types/MerkleVerifier”;
	let merkleTree: MerkleTree;
	let merkleVerifier: MerkleVerifier;
	function generateMerkleTree() {
	const leaves = merkleTreeLeaves.map((leaf) =>
	encodeLeaf(leaf.toLocaleLowerCase())
	);
	return new MerkleTree(leaves, keccak256, {
	hashLeaves: true,
	sortLeaves: true,
	});
	}
	function encodeLeaf(address: string) {
	// Same as `abi.encodePacked` in Solidity
	return ethers.utils.defaultAbiCoder.encode([“address”], [address]);
	}
	async function testMerkleVerification() {
	const validLeaf = keccak256(encodeLeaf(validAddress.toLocaleLowerCase()));
	const invalidLeaf = keccak256(encodeLeaf(invalidAddress.toLocaleLowerCase()));
	const validProof = merkleTree.getHexProof(validLeaf);
	const invalidProof = merkleTree.getHexProof(invalidLeaf);
	const validProofVerification = await merkleVerifier.verifyMerkleProof(
	validProof,
	validAddress.toLocaleLowerCase()
	);
	const invalidProofVerification = await merkleVerifier.verifyMerkleProof(
	invalidProof,
	invalidAddress.toLocaleLowerCase()
	);
	console.log(
	`Address ${validAddress} is part of the tree: ${validProofVerification}`
	);
	console.log(
	`Address ${invalidAddress} is part of the tree: ${invalidProofVerification}`
	);
	}
	async function deployContract() {
	const root = merkleTree.getHexRoot();
	const MerkleVerifier = await ethers.getContractFactory(“MerkleVerifier”);
	merkleVerifier = await MerkleVerifier.deploy(root);
	await merkleVerifier.deployed();
	console.log(“MerkleVerifier contract deployed to:”, merkleVerifier.address);
	}
	async function main() {
	merkleTree = generateMerkleTree();
	await deployContract();
	await testMerkleVerification();
	}
	// We recommend this pattern to be able to use async/await everywhere
	// and properly handle errors.
	main().catch((error) => {
	console.error(error);
	process.exitCode = 1;
	});

view raw contarct-merkle-verification.ts hosted with ❤ by GitHub

• If you check the main function in above typescript file, we are first calling generateMerkleTree function which is responsible for generating the merkle tree using the sampledata which is imported at the start of the file.
• Leaves are first encoded following solidity’s abi.encodePacked format and then are passed to MerkleTree instance.
• We are using this npm pacakge for generating merkle trees and required data.
• In deployContract function, we are deploying the MerkleCerifier.sol contract. Contract requires the merkle tree root to be passed as a parameter in the constructor.
• And then comes the main function: testMerkleVerification

testMerkleVerification()  function: 

• This function creates a encoded version of two leaves. One of them is valid and other one is invalid.
• After this, the function generates proof for both of these leaves. Ofcourse, one of the proofs is valid, other one is invalid.
• Then  calls smart contract which we have deployed earlier and triggers ​​verifyMerkleProof function by passing all the required params.

Merkle Verification in Javascript

We can also perform end-to-end merkle verifications purely in javascript / typescript via the same npm package which we used above. The only difference being this time we will relay on the package for verification instead of a smart contract. Our npm package has following function exported which can be used for merkle verification.

await merkleTree.verify(proof, leaf, root);

All of theabove discussed files and code is available in this hardhat project: https://github.com/ashwinYardi/merkletree-examples

Github repository also has instructions on how to run the scripts and test merkle verification. Give it a go and in case of anything, do let me know. Would love to discuss further on this topic.