Understand Merkle tree by making an NFT minting whitelist

TL;DR
If you are familiar with Merkle tree and want to jump to the code. Here you go:

• Simplified codes that I use in this article: Github
• A more DRY version that you can reuse in your project: Github

Table of contents

• Introduction
• What is Merkle tree
• Validate data using Merkle tree
• Create a whitelist using Merkle tree
  • Setting up
  • The smart contract
  • Create the whitelist
  • Step 1: Create a Merkle Tree
  • Step 2: Get Merkel proofs
  • Step 3: Get Merkle root
  • Step 4: Verify users' address and quantity
• Conclusion

Introduction

NFT whitelisting is a way to reward your community's active users, and an effective tool to prevent fraud. Instead of storing all users' data on-chain (which is expensive), we can generate a Merkle tree from the users' data. From the tree, we extract and store only the tree's root (bytes32) on-chain. It will save a ton of gas fees!
In this article, I will explain how Merkle Tree works by making a minting whitelist for my made-up NFT project, Excited Apes Yacht Club (EAYC).
 

What is Merkle tree

Merkle tree is a hash-based data structure that is used in cryptography to maintain data integrity. Each non-leaf node in a Merkle tree is a has of its children. This means that each non-leaf node has 2 children max.

There are four data blocks in the example tree above. Hashing each of them results in four leaf nodes A-0, A-1, B-0, and B-1. Each consecutive leaf node pair (A-0, A-1), (B-0, B-1) is repeatedly hashed to create non-leaf nodes A and B. Finally, the two non-leaf nodes' hashes (A and B) are hashed again to create the root hash (Merkle root).

Validate data using Merkle tree

To validate if the A-0 hash (target hash) exists in the Merkle tree, we need to rebuild the tree. To do that, we only need A-1 and B hash. If we can recreate the root hash, the A-0 hash is valid. That is the beauty of the Merkle tree! We don't need to know all its hashes to validate the target hash.

Create a whitelist using Merkle tree

Setting up

We use hardhat to set up our project. if you are not familiar with hardhat, check out their documentation.

The smart contract

We will use ERC721 for our NFT project.
ExcitedApeYachtClub.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.9;

import '@openzeppelin/contracts/token/ERC721/ERC721.sol';
import '@openzeppelin/contracts/utils/Counters.sol';
import {MerkleProof} from '@openzeppelin/contracts/utils/cryptography/MerkleProof.sol';

contract ExcitedApeYachtClub is ERC721 {
    using Counters for Counters.Counter;
    Counters.Counter private _tokenIds;

    bytes32 public merkleRoot;

    constructor(bytes32 merkleRoot_) ERC721('Excited Ape Yacht Club', 'EAYC') {
        merkleRoot = merkleRoot_;
    }

    function mint(uint256 quantity, bytes32[] calldata merkleProof) public {
        bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');

        for (uint256 i = 0; i < quantity; i++) {
            uint256 tokenId = _tokenIds.current();
            _mint(msg.sender, tokenId);

            _tokenIds.increment();
        }
    }
}

Notice that we declare bytes32 public merkleRoot; to store Merkle tree root, and use it to verify against merkleProof and node inside mint function.

Create the whitelist

Let's say there are 3 active users in our community: Alice, Bob, and Carol. Depending on their contribution, we allow each user to mint a different quantity.
We can break it down into 4 steps:

1. Create a Merkle tree from users' addresses and quantity.
2. Get the proof of each leaf node, and store it off-chain.
3. Get the root of the Merkle tree, and store it on the NFT smart contract.
4. Verify users' addresses and quality on our NFT smart contract when they attempt to mint. If the proof of a user is valid, the user is allowed to mint.

Step 1: Create a Merkle Tree

We will use merkletreejs, ethers, and keccak256 to generate a Merkle tree that works with Solidity smart contracts. Here is the code:

import { MerkleTree } from "merkletreejs";
import ethers from "ethers";
import keccak256 from "keccak256";
// inputs: array of users' addresses and quantity
// each item in the inputs array is a block of data
// Alice, Bob and Carol's data respectively
const inputs = [
  {
    address: "0x70997970C51812dc3A010C7d01b50e0d17dc79C8",
    quantity: 1,
  },
  {
    address: "0x3C44CdDdB6a900fa2b585dd299e03d12FA4293BC",
    quantity: 2,
  },
  {
    address: "0x90F79bf6EB2c4f870365E785982E1f101E93b906",
    quantity: 1,
  },
];
// create leaves from users' address and quantity
const leaves = inputs.map((x) =>
  ethers.utils.solidityKeccak256(
    ["address", "uint256"],
    [x.address, x.quantity]
  )
);
// create a Merkle tree
const tree = new MerkleTree(leaves, keccak256, { sort: true });
console.log(tree.toString());

in the console, we can see our Merkle Tree. The first hash is the Merkle root. Belows are non-leaf nodes and leaf nodes.

cd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7
   ├─ f92db5e3e1d6bed45d8e50fad47eddeb89c5453802b5cb6d944df2f3679da55c
   │  ├─ 3f68e79174daf15b50e15833babc8eb7743e730bb9606f922c48e95314c3905c
   │  └─ b783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7
   └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee
      └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee

Here is the diagram of the Merkle tree we've just generated

The branching factor is 2, but we have 3 blocks of data. That is why in the Carol branch, each node has only 1 child.

Step 2: Get Merkel proofs

Now we need to get the proofs from our leaves and store them somewhere off-chain. A JSON file in your client or a database in your backend would do.

const proofs = leaves.map(leave=> tree.getHexProof(leaf))

The proofs should look like this

[
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ]
]

The first item in the proofs array is Alice's proof which contains two hashes. The first one is the hash of Bob's data, and the second one is the hash of the node right below the root node on the other branch.

Step 3: Get Merkle root

const root = tree.getHexRoot();

0xcd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7

As simple as that! we will store the root on-chain when we deploy the smart contract

Step 4: Verify users' address and quantity 

With the Merkle proofs and root prepared, we now can verify whether a user is in our whitelist. First, we recreate the node hash from the user's address and quantity using Solidity's keccak256. Then, we can call MerkleProof.verify to check if the hash exists in our Merkle tree. If it does, the user is allowed to proceed.

 bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');

The codes below are unit tests for the smart contract. From here it should be self-explaining.

import { loadFixture } from '@nomicfoundation/hardhat-network-helpers';
import { expect } from 'chai';
import { ethers } from 'hardhat';
import { makeMerkleTree } from '../utils/merkletree';
import { makeUsers } from '../utils/data';

describe('ExcitedApeYachtClub', function () {
  async function deployOneYearLockFixture() {
    const merkleTreeData = await makeMerkleTree();
    const { root } = merkleTreeData;

    const users = await makeUsers();

    const ExcitedApeYachtClub = await ethers.getContractFactory(
      'ExcitedApeYachtClub'
    );

    const excitedApeYachtClub = await ExcitedApeYachtClub.deploy(root);

    return { excitedApeYachtClub, merkleTreeData, users };
  }

  beforeEach(async function () {
    const { excitedApeYachtClub, users, merkleTreeData } = await loadFixture(
      deployOneYearLockFixture
    );
    this.excitedApeYachtClub = excitedApeYachtClub;
    this.users = users;
    this.merkleTreeData = merkleTreeData;
  });

  describe('Deployment', function () {
    it('Should return correct name and symbol', async function () {
      expect(await this.excitedApeYachtClub.name()).to.equal(
        'Excited Ape Yacht Club'
      );
      expect(await this.excitedApeYachtClub.symbol()).to.equal('EAYC');
    });
  });

  describe('mint', function () {
    beforeEach(async function () {
      await this.excitedApeYachtClub
        .connect(this.users.alice)
        .mint(1, this.merkleTreeData.proofs[0]);

      await this.excitedApeYachtClub
        .connect(this.users.bob)
        .mint(2, this.merkleTreeData.proofs[1]);
    });

    it('Should allow whitelisted users to mint', async function () {
      const aliceBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.alice.getAddress()
      );

      expect(aliceBalance).to.equal(1);

      const bobBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.bob.getAddress()
      );

      expect(bobBalance).to.equal(2);
    });

    it('Should revert when users try to mint over allowed quantity', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.alice)
          .mint(2, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });

    it('Should revert when non-whitelisted users try to mint', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.david)
          .mint(1, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });
  });
});

Conclusion

Merkle tree is powerful. It allows data to be verified without using much on-chain storage. Imagine how much money you can save if you have thousands of users in your whitelist. That is huge!

P/S: I've started to see the benefit of blogging as a developer. I am trying to write as much as I can after my work. This is my first programming blog ever. I hope you enjoy it.
Thank you for your reading. I appreciate it.