How to use a Merkle Tree for large whitelist mints

EvoSnails is an on-chain gaming NFT, in which holders stake their snails to earn our $LEAF token, and can use that token to upgrade their traits. We launched our collection on the 1st of November, with approximately 3,000 users whitelisted for early access. Our whitelist mint used a Merkle Tree to save ourselves copious gas when using a large whitelist, and we document how the whitelist mint works here in the hopes of aiding other projects in their whitelist.

Note: the code in this post is for demonstration purposes only. It has not been vetted by a security audit and should not be copy-pasted for use in a project. Do your own research.

Motivation

Any regular user of Ethereum is familiar with the concept of gas, or the transaction cost of any write interaction on the blockchain.

A naive approach to a whitelist for a mint would be to simply store which addresses are allowed to use the whitelist mint function:

// Code for demonstration purposes only
// DO NOT USE for a real project.
contract NFT is ERC721 {
    mapping(address => bool) public whitelist;
    
    function setWhitelist(address[] calldata _addresses) {
        for (uint i = 0; i < _addresses.length; i++) {
            whitelist[_addresses[i]] = true;
        }
    }
function mintWhitelist() {
        require(whitelist[msg.sender], "not whitelisted");
        
        // mint an nft
    }
}

This strategy is simple and intuitive, however, it makes heavy use of storage by saving each address. With a single SSTORE instruction costing up to 20,000 gas, storing 500 addresses costs a mind-boggling 11 million gas, or around $5,400 USD at today's prices. For projects with uncertain prospects, a $30k upfront investment in just 3,000 whitelist addresses is a large risk to take.

Merkle Trees

An alternative approach is to use a Merkle tree, a common cryptographic data structure that can be used to verify that a node (address) lives in a tree (a list of whitelisted addresses) without requiring the storage of every address in the contract. Merkle trees are used internally by Bitcoin and Ethereum, allowing validators to validate that a block falls within the chain without requiring the download of every single block’s data.

Wikipedia provides a thorough explanation of how Merkle trees work, and I will provide a high-level summary.

We wish for our smart contract to verify that the data L1 (in our case, a whitelisted address), lies in the tree.

Merkle tree layout. Wikipedia

We can verify that L1 lies in the tree by hashing L1 and L2 separately (hash 0–0 and 0–1), as well as the sum of these two hashes (hash 0). Finally, we hash the sum of hash 0 and hash 1. The result of this is the Merkle Root, labelled top hash. If the Merkle Root generated by this process agrees with the hash stored in contract storage (generated ahead of time by the same process, using all the nodes), we know that L1 lies in the tree.

This process is highly efficient because it only requires O(log N) hashes (a Merkle proof) to determine if a node lies in the tree — we only required hash 0–1 and hash 1 in addition to L1 to generate the Merkle root, as opposed to all 4 addresses. This continues to scale logarithmically. For 3,000 whitelist addresses, we only require 10 associated hashes in the Merkle proof.

Usage in practice

In practice, the leaf hashes are the combination of a wallet address and a token ID. This is more flexible as it allows wallets to claim multiple mints and can allow some whitelisters a free mint (as we did in EvoSnails) — if a valid proof for a tokenID < 100 is supplied, the mint is free.

the following steps are performed:

1. Once the list of whitelist addresses and token IDs are finalised, generate the Merkle root and store this in the contract.
2. Create an API endpoint that returns the Merkle proof for a specific wallet address. When a user connects their wallet and presses mint, their browser requests the Merkle proof from the API.
3. The smart contract is called with the wallet address and Merkle proof.
4. The contract checks the root of the supplied proof matches the root stored by the administrator in step one.
5. If these agree, mint to the wallet.

Generating the Merkle tree ahead of time

The following JavaScript code can simply generate the Merkle tree and associated Merkle proof for storage in the contract:

import { ethers } from "ethers";
import keccak256 from "keccak256";
import MerkleTree from "merkletreejs";
// Map tokenID to wallets
// e.g.
const tokens = {
  2: "0xabcde..."
}
export function hashToken(tokenId, account) {
  return Buffer.from(ethers.utils.solidityKeccak256(["uint256", "address"], [tokenId, account]).slice(2), "hex");
}
export function generateMerkleTree() {
  const merkleTree = new MerkleTree(
    Object.entries(tokens).map((token) => hashToken(...token)),
    keccak256,
    { sortPairs: true }
  );
  console.log(merkleTree.getHexRoot())
  return merkleTree;
}

This is code is also used on the API side, as we will see later.

Smart Contract Code

Most ERC20 and ERC721 developers are familiar with OpenZeppelin, who fortunately also provide an excellent implementation of Merkle trees in Solidity!

This makes verifying an associated proof exceptionally easy:

// Generate the leaf node (just the hash of tokenID concatenated with the account address)
function _leaf(address account, uint256 tokenId) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked(tokenId, account));
    }
// Verify that a given leaf is in the tree.
function _verify(bytes32 _leafNode, bytes32[] memory proof) internal view returns (bool) {
        return MerkleProofUpgradeable.verify(proof, merkleRoot, _leafNode);
    }
function mintWhitelist(
        address account,
        uint256 tokenId,
        bytes32[] calldata proof
    ) public payable {
        require(_verify(_leaf(account, tokenId), proof), "Invalid 
proof");
        // Require that this token or wallet hasn't already minted
        // Store that either the wallet or tokenID has been minted, then mint the token
    }

Serving a proof for a specific wallet

As EvoSnails only allowed one mint per wallet, our API server returned the proof for a given wallet already with the knowledge. We used the following simple Next.js API route:

import whitelist from "../../../utils/whitelist/whitelist.json";
import { generateMerkleTree, hashToken } from "previous section"
// Generate the Merkle tree (use supplied code in previous section)
const merkleTree = generateMerkleTree();
export default function handler(req, res) {
  const { wallet } = req.query;
  // Lookup the token ID for this wallet, use your own implementation
  const id = addressToTokenId[wallet];
  if (!id) return res.json({ error: "Wallet not in whitelist" });
  // Return the Merkle proof
  const proof = merkleTree.getHexProof(hashToken(id, wallet));
  return res.json({ id, proof });
}

The resultant JSON can be supplied to the contract call in Web3.js or Ethers.js.

Conclusion

This approach was highly successful for our project. We successfully eliminated almost all of the gas costs for storing our whitelist addresses, however at the cost of some additional complexity.

If you have any questions, follow me on Twitter or discuss with me in the EvoSnails Discord!