Merkle Tree in Solidity | Solidity Tips & Examples

Merkle Trees provide an efficient way to verify data in Solidity. This reduces the gas cost for on-chain storage when validating large data sets such as a large list of addresses.

1. How Do Merkle Trees Work
2. Solidity Merkle Tree Example
3. Efficient On-Chain Data

---

How Do Merkle Trees Work

Merkle trees are a data structure that allow efficient and secure verification of the integrity of data. They are commonly used in Solidity to efficiently verify large amounts of data with minimal on-chain storage (gas cost).

The basic idea behind a Merkle Tree is to divide a large set of data into smaller chunks, and then recursively hash those chunks until there is only one root hash left. Each hash in the tree is computed by taking the hash of its two child hashes. This process is repeated until there is only one hash left, which is called the root hash. The root hash can be considered a summary of all the data in the tree.

The key property of Merkle Trees is that any change in the data results in a different root hash. This means that if we need to add one users address to that list we need to do another transaction to update the merkle root hash in the smart contract.

When we want to verify the integrity of a particular piece of data in the tree, we only need to provide the hash of that data along with a path of hashes from that data to the root. This allows us to verify the data without needing access to the entire tree.

---

Solidity Merkle Tree Example

In this example we will be using a Merkle Tree to validate an address whitelist for an NFT mint in Solidity:

First we need to create a Merkle Tree of all the whitelisted addresses and get a root hash. We can use NodeJS and the merkletreejs library to do this with the following script:

const {MerkleTree} = require("merkletreejs");
const keccak256 = require("keccak256");
const whitelist = ['0x6090A6e47849629b7245Dfa1Ca21D94cd15878Ef','0xBE0eB53F46cd790Cd13851d5EFf43D12404d33E8'];
const leaves = whitelist.map(addr => keccak256(addr));
const merkleTree = new MerkleTree(leaves, keccak256, {sortPairs: true});
const rootHash = merkleTree.getRoot().toString('hex');
console.log(`Whitelist Merkle Root: 0x${rootHash}`);
whitelist.forEach((address) => {
  const proof =  merkleTree.getHexProof(keccak256(address));
  console.log(`Adddress: ${address} Proof: ${proof}`);
});

When we run this code it will output the merkle root for the addresses. Note that you’ll want to add some of your own or users addresses to the whitelist and make sure the checksums are correct (not all lower caps addresses).

From there we can use the OpenZeppelin MerkleProof.sol library to verify an address against the merkle root in Solidity.

pragma solidity ^0.8.0;

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

contract NFTMint {
  bytes32 public merkleRoot;

  constructor(bytes32 _merkleRoot) {
    merkleRoot = _merkleRoot;
  }

  function claim(bytes32[] memory proof, address account) public {
    bytes32 leaf = keccak256(abi.encodePacked(account));
    require(MerkleProof.verify(proof, merkleRoot, leaf), "Invalid proof");
    
    // User is in the whitelist, allow them to claim the NFT

  }
}

Let’s deploy the NFTMint.sol contract to a local testnet and try it out. Copy and paste the code into to https://remix.ethereum.org and deploy it locally using the merkle proof we generated in the constructor argument when deploying the contract.

We can then pass in the proof and account from the whitelist which was generated when using the script above to verify the address.

Note that the above contract doesn’t actually mint an NFT you would need to integrate either a ERC721 or ERC1155 library to do this. This is just an example of how to enable a merkle tree whitelist.

---

Efficient On-Chain Data

Merkle trees provide several benefits for Solidity developers:

1. Efficient verification of large datasets can be particularly useful for blockchain applications where data is often too large to store on-chain
2. Reduced gas costs due to less data being stored on-chain
3. Increased security Merkle trees provider a reliable way of verifying data integrity

Merkle trees are a useful tool for Solidity developers looking to improve the efficiency, scalability, and security of their blockchain applications. I hope this article has served as a good introduction to how to integrate a simple whitelist with a Merkle Tree. There is a more in depth example in the Solidity Snippets Github Repository: https://github.com/jamesbachini/Solidity-Snippets/blob/main/contracts/Merkle.sol

---