Using Merkle Trees for NFT Whitelists

It excites Q to announce a special treat for readers in tonight's report 🤩 Introducing guest analyst and expert developer Alan Boothe to walk through the technology & use cases behind Merkle Trees 👇

Feel free to follow Alan on his Twitter for more premium alpha!

Introduction: What are Merkle Trees?

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. Furthermore, I will digress on how they can provide reassurance that tokens can only be claimed by the intended participants.

Love crypto? Q does too! Make sure you’ve subscribed for free or upgrade to Premium Research more daily content 👇

But, What is 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 one-way, meaning it is easy to produce an output from input, but computationally infeasible to determine an input from the output.

Merkle Trees feature three types of nodes, these are as follows:

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 seven pieces of data need to be hashed, there will be seven leaf nodes

Share

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 - linked together - hashes of the nodes below it, typically starting from left to right.

Since different inputs will always produce different hashes, the order within which fostering node hashes are concatenated is important.

It is worth mentioning that parent nodes can foster other parent nodes depending on tree size.

Share Qluster Research

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 possesses the root hash.

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

🔥 Q’s Black Friday Sale 🔥

Save 10% and subscribe to annual membership with Qluster Research for more premium content. Hurry, this offer ends on Monday 29 November 2021 👇

Get 10% off for 1 year

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, let’s say a single leaf node represents a single wallet address in our whitelist.

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, let’s 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.

Share

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, let’s 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 utilised later in our Solidity smart contract.

Share

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.

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, 0x1150… 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 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 retrieve 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.

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

Share

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 proof is to import the OpenZeppelin MerkleProof.sol contract, 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 finalized, 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 (Figure 5).

Leave a comment

Next, we need to verify the proof.

Recall that the proof was sent with the transaction and that it was an array of type bytes32, technically they were strings, 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.

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 the proof of a different address, the generated target leaf node simply won’t exist on our Merkle Tree.

Thus, verification will fail.

The final step of this implementation simply calls the MerkleProof.verify() function passing the provided proof as to the first argument, the root Merkle hash as the second, and the target leaf node as the last.

If this function returns false, the required statement will fail and the transaction will simply be reverted, otherwise, the function will continue to execute.

Give a gift subscription


Q’s + Alan’s Conclusion

There you have it!

A relatively simple and straightforward approach to show how using Merkle Trees for whitelist claiming in your 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.

See you again for the next update.

- q + a

Leave a comment


Follow us for more detailed analysis on all markets, including Decentralised technology. Check out the links below

Join our Facebook group and connect with likeminded traders:

https://www.facebook.com/groups/156981244915722

Like our Facebook page for future updates:

https://www.facebook.com/qlusterco

Follow us on LinkedIn for future updates:

https://www.linkedin.com/company/qluster-co/?viewAsMember=true

Keep up with us on Twitter:

https://twitter.com/QlusterC

Share Qluster Research


The information on this website is for general information purposes only. It is not intended as legal, financial and/or investment advice and should not be construed and/or relied on as such. Before making any commitment of a legal and/or financial nature you should seek advice from a qualified and registered legal practitioner and/or financial and/or investment adviser. No material contained within this website should be construed or relied upon as providing recommendations in relation to any legal and/or financial product. Qluster does not recommend and/or endorse products and does not receive remuneration based upon investment and/or other decisions