Using Merkle Trees for NFT Whitelists

Introduction

Merkle Trees have long been a facet in the fields of both cryptography and computer science well before the blockchain we know and love today ever existed. Nowadays, we are slowly starting to see them become more frequently used on-chain for the purpose of data verification. In this article, I will be explaining how Merkle Trees can be implemented in an NFT (ERC-721) context for the purpose of token whitelisting and how they can provide reassurance that tokens can only be claimed by the intended participants.

But, What’s a Merkle Tree!?

Merkle Trees are a tree-like structure where every node on the tree is represented by a value that is the result of some cryptographic hash function. Hash functions are 1-way, meaning it is easy to produce an output from an input, but computationally infeasible to determine an input from an output. Merkle Trees feature 3 types of nodes, these are as follows:

1. Leaf Nodes — These nodes sit at the very bottom of the tree and their value is the result of the original data being hashed according to a specified hash function. There are as many leaf nodes in a tree for as many pieces of original data that require hashing. E.g. If 7 pieces of data need to be hashed, there will be 7 leaf nodes.
2. Parent Nodes — Parent nodes can sit at various levels of the tree depending on the overall tree size, but will always reside above leaf nodes. Parent nodes will only ever foster a minimum of one node and a maximum of two nodes. The value of a parent node is determined by the hash of the concatenated hashes of the nodes below it, typically starting from left-to-right. Since different inputs will always produce different hashes, disregarding hash collision, the order that fostering node hashes are concatenated in is important. It is worth mentioning that parent nodes can foster other parent nodes depending on tree size.
3. Root Node — The root node sits at the top of the tree and is derived from the hash of the concatenated hashes of the two parent nodes that sit below it, again starting from left-to-right. There is only ever a single root node on any Merkle Tree and the root node possess the root hash.

I know that is a lot of information to digest, so please refer to the diagram below (Figure 1) for a better visualization of how these trees are structured.

Figure 1. Merkle Tree Structure

Context

As previously mentioned, using a Merkle Tree within an NFT (ERC-721) context would be useful in situations where some amount of tokens have been reserved for a select group of participants, a whitelist per se. Merkle Trees must be pre-calculated and therefore use some form of data that is distinct per member. In this context, lets say a single leaf node represents a single wallet address in our whitelist.

Lets imagine your project has implemented a whitelist strategy where an arbitrary number of tokens have been reserved for select wallet addresses that may have been chosen through means of a competition, raffle, or some other system. These whitelisted addresses have been granted the ability to claim their reserved tokens at some point in time before the public mint for a variety of reasons. These may relate to avoiding high gas fees, rewarding creativity, early participation, community engagement, and etc.

Since these addresses are known and are constant, we can use this information to create a Merkle Tree. To demonstrate this, lets use the merkletreejs and keccak256 JavaScript libraries. Note: For simplicity sake, I will only be using 7 wallet addresses to keep the tree size concise.

JavaScript Implementation

The first thing we want to do is to derive our leaf nodes. If you recall, each parent node that sits directly above leaf nodes on a tree will only ever foster a maximum of two leaf nodes. If an uneven number of leaf nodes exist, a parent node will foster a single leaf node. Each leaf node should be some form of hashed data, so for this example, lets use the keccak256 library to hash all of the addresses on our whitelist (Figure 2). We are using this specific hashing algorithm as it will be used later on in our Solidity smart contract.

Figure 2. Deriving Leaf Nodes and Merkle Tree object.

Once we have hashed all of the addresses on our whitelist, thus obtaining our leaf nodes, we are now able to create the Merkle Tree object. We do this using the merkletreejs library and by calling the new MerkleTree() function, passing our leaf nodes as the first argument, our hashing algorithm as the second, and the { sortPairs: true } option as the last. The final argument is optional, but I encountered great difficulty trying to get this example working without using it.

Figure 3. Merkle Tree Visualisation and Root Hash.

Now that we have derived a complete Merkle Tree, we can get the root hash by calling the getRoot() method (Figure 3) on our Merkle Tree object. Remember that the root hash of a Merkle Tree is the hash of the two preceding parent nodes directly under the root node on the tree. In this case, 0xf352… and 0x3cc0…. Console logging our Merkle Tree using the toString() method provides us with a nice visualisation of how our tree is structured.

The ingenuity of a Merkle Tree stems from the fact that it does not require any knowledge of the original data blocks to verify that a node belongs to our tree. If we are trying to verify that a leaf node belongs to our tree, only knowledge of the direct neighbouring leaf nodes hash, if any, and the neighbouring parent node hashes directly above the leaf nodes is required. For a short and sweet explanation of how this works, I recommend checking out this video by Tara Vancil. This information is otherwise known as a proof and will be used in our Solidity smart contract to verify that a caller is apart of our whitelist.

Website Implementation

Now that we have both our Merkle Tree object and its root hash, we are ready to start thinking about how we can provide a Merkle proof to our smart contract when a whitelisted user attempts to claim their tokens. All that really needs to be done is to implement some JavaScript, similar to that above, on our project website that makes a fetch request to an external API while on the mint page. This API will receive the connected wallets address, as this is what we originally used to generate our leaf nodes, and return the designated proof.

Server-side, you would receive the address, hash it using keccak256, and retreive the proof using the getHexProof() method on our Merkle Tree object. The image below (Figure 4) shows an example of what you might return from this API call.

Figure 4. The Merkle Proof For The Corresponding Address. Edit: 0x7b can be ignored, this is a typo on my end.

After this proof is received and sent as a parameter with the participants transaction, we can now start looking at how we would verify it in our smart contract.

Smart Contract Implementation

Note: The smart contract example shown has been constructed with the minimum amount of code required to show a proof of concept. It is in no way an example of how you should write a minting function.

The first thing we must do in order to validate the provided proof, is to import the OpenZeppelin MerkleProof.sol contract (Line 6, Figure 5), this will enable us to use the MerkleProof.verify() function in our smart contract code. The next thing required is to define the root Merkle hash. If the smart contract has been deployed to the Ethereum mainnet prior to the whitelist being finalised, it is assumed that there is some setter function that can be used to update this value at a later point in time. In this instance, I have hardcoded the root Merkle hash value so that it is set at the time of deployment (Line 12, Figure 5).

Figure 5. Smart Contract code.

Next, we need to verify the proof. Recall that the proof was sent with the transaction and was an array of type bytes32 values. Technically they were of type string, but Solidity will interpret these correctly regardless. We generate our target leaf node (Line 25, Figure 5), which if you remember, was the keccak256 hash of a whitelisted address. In this example, we are generating our target leaf node by hashing the value of msg.sender. Remember that this value is immutable and cannot be maliciously altered.

Due to only whitelisted addresses being used to generate our leaf nodes, it can already be assumed that if a non-whitelisted address attempts to call this function using either a valid or invalid proof, the generated target leaf node simply won’t exist on our Merkle Tree and verification will fail. The final step of this implementation simply calls the MerkleProof.verify() function passing the provided proof as the first argument, the root Merkle hash as the second, and the target leaf node as the last. If this function returns false, the require statement will fail and the transaction will simply be reverted, otherwise, the function will continue to execute and the tokens will be minted.

Parting Words

There you have it! A relatively simple and straightforward approach to show how using Merkle Trees for whitelist claiming in an NFT project can provide you with peace of mind so that only designated addresses of your whitelist are able to claim. I know other solutions are available, but out of the ones I have researched, this was by far the most intriguing. I hope you enjoyed reading this article as much as I did researching, please feel free to applaud and follow me on Twitter for updates of what I am working on and when my next article will be published. ✌️