What is a Merkle Tree?

A "hash tree" or "Merkle tree" is a type of tree used in cryptography and computer science where each "leaf" (node) is labelled with the cryptographic hash of a data block and every other node (referred to as a "branch," "inner node," or "inode") is labelled with the cryptographic hash of the labels of its child nodes. A hash tree makes it possible to quickly and securely check the contents of a big data structure.

If this is too much, don't worry. With the aid of visuals and benefits, we shall demystify Merkle trees in this post.

1. A Merkle tree is a collision-resistant hash function, denoted by MHT, that takes n inputs (x₁,…,x_n) and outputs a Merkle root hash h=MHT(x₁,…,x_n).
2. A verifier who only has the root hash h can be given an x_i and an associated Merkle proof which convinces them that x_i was the i^th input used to compute h.
3. 1. If a Merkle proof says that x_i was the i^th input used to computed h, no attacker can come up with another Merkle proof that says a different x^'_i ≠x_i was the i^th input.

How Merkle Tree Works

Assume you have n=8 files, represented by (f₁, f₂,..., f₈), and that your hash function (H) is collision-resistant let's say keccak256.

You start by hashing each file as h_i=H(f_i):

You could continue to hash every two adjacent hashes:

You could even continue on these newly obtained hashes:

In the end you hash these last two hashes as h_1,8=H(h_1,4,h_4,8) :

Congratulations! What you have done is computed a Merkle tree on n=8n=8 leaves, as depicted in the picture above.

Note that every node in the tree stores a hash:

• The i^th leaf of the tree stores the hash h_i of the file f_i.
• Each internal node of the tree stores the hash of its two children.
• The h_1,8 hash stored in the root node is called the Merkle root hash.

What is a Merkle proof !

The key idea is that, after you download f_i, you ask for a small part of the Merkle tree called a Merkle proof. This proof enables you to verify that the downloaded f_i was not accidentally or maliciously modified.

Well, observe that the Merkle proof for f_i is exactly the subset of hashes in the Merkle tree that, together with f_i, allow you to recompute the root hash of the Merkle tree and check it matches the real hash h_1,8, without knowing any of the other hashed files.

So, to verify the proof, you simply “fill in the blanks” in the picture above by computing the missing hashes depicted with dotted boxes.

Lastly, you check that the Merkle root  you computed above is equal to the Merkle root  you kept locally! If that’s the case, then you can be sure you downloaded the correct f_i.

How to Implement a Basic Merkle Tree Whitelist in NFT Contract.

It is rather difficult to produce a merkle tree on your own, but don't worry; we'll utilise a javascript package called merkletreejs to build a merkle tree as well as generate and check proofs.
Our collision-resistant hash function is the keccak256 hashing method.

Install both requirements with the following command.

npm i merkletreejs
npm i keccak256

Add the dependencies to a new file called MerkelTree.js.

const { MerkleTree } = require("merkletreejs");
const keccak256 = require("keccak256");

Let's say you have a list of addresses you wish to whitelist in your NFT project. Let's put those addresses in a variable called addressArray, an array.

const addressArray = [
  "0xdDf0970237F4063Eee17aac2b4ED0c66A32c0F81",
  "0x1E694e8fEFD9CfDf50300bA6A9db13a92e3d4AA9",
  "0x46c908f72f2e492Cf9fd054b4C82826AfdE23Ec9",
  "0x30D51930DF7EB0eb4e99C847e0E163451D6fFb1D",
  "0xB8160841b28871eb07C98Ec072Bb19Aa586940Ac",
  "0xf644E9c4C342C200c21eb1A474327d447F284625",
  "0x6Bc3Ce9928A6b3754C4C57e5F831B686089df9D3",
  "0xdf8962bCF5Ff744d15da562630DCBf2305eA12f3",
  "0x44C028313b9F51Fa617205357B3d8715CB4F6FeF",
  "0x089FBB7606b0a720A205FBE2844245ae0ECC447B",
  "0xc133E25C2AB8c48137C2425bda0D25DCe12a49d4",
  "0xD470b76eb23d18D29b3D8CA35172d0687B26c5f2",
  "0xb6aa5fd1b873f053e64009632fb90e5619539442",
  "0xa23C72E858f7cC7aEd380F24E1fAfe2338Ed49dF",
  "0x3C8d0b84dE22f5c87F27d7C5c459295E6E73bcCD",
  "0x693B22b3DD3f09A40627d8Ce2C07a3714f8b6Bf8",
  "0x8a067Ec3Ed65d685038ce11d10c1040a6B161Eb1",
  "0x1Bd3bD690959265e44d5ae261028f2E952983863",
  "0xc14ddf7b433eb432c07b1865eb2c28ace5deb167",
  "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4",
  "0xBF4979305B43B0eB5Bb6a5C67ffB89408803d3e1",
];

Let's now create the function buf2hex, which changes the buffer to Hexadecimal.

const buf2hex = (x) => "0x" + x.toString("hex");

We must first obtain our leaves in order to create a tree, which we can do by mapping through our Array hashing our address with the keccak256 method.

const leaves = addressArray.map((x) => keccak256(x));

Now, in order to create a tree, we use the code below, which first sorts our array before creating a Merkel Tree.

const tree = new MerkleTree(leaves, keccak256, { sortPairs: true });

then after that, using the following command, we can find the tree's root.

const root = "0x" + tree.getRoot().toString("hex");

Let's say I want to obtain the last address and the proof associated with it.

const leaf = keccak256(addressArray[20]).toString("hex");
const proof = tree.getProof(leaf).map((x) => buf2hex(x.data));

Now we log all the details

console.log(`Root - ${root}`);
console.log(`leaf - ${leaf}`);
console.log(`proof - ${proof}`);

The output should look something like this when you run the file using node MerkelTree.js

Root - 0x5980c4cba5c7b181167b84183d5b89fd64f1ed01b12ddf12084f2a77d9913c8e
leaf - bae7d1c1447829a0dc7a735041e74fdf7082a238aa8b45b06e550dfce99f5715
proof - 0xd6385235429df428dad417201312f0724220673f2a6956be471426bb77a2c87e,0x363e3bb0c286106f6a19aea117f3dbedb3c3a376b4fd8c31254f9ba86b842366

Implementing Merkel Tree in our Smart Contract

First, use the Openzeppelin Contract Wizard to create a Basic ERC-721 Smart contract.

The Merkel Tree file from Openzeppelin must first be imported. Add the following line beneath your imports to accomplish this.

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

Additionally, we must introduce some state variables and modify our constructor to include some arguments, such as the Merkel Tree's "root" and the "baseURI" for the contract. The code below will enable us to achieve that.

uint public maxSupply = 10000;
    string internal uri;
    bytes32 public root;

    constructor(string memory baseURI, bytes32 _root) ERC721("Merkeltree", "MKT") {
        root = _root;
        _tokenIdCounter.increment();
        uri = baseURI;
    }

We must now write a function named "isWhitelisted" that accepts two arguments in order to determine whether the user is whitelisted or not.

1. The leaf
2. proof associated with that leaf

A boolean value, either true or false, is returned by the function.

function isWhitelisted(bytes32[] memory proof, bytes32 leaf) public view returns (bool) {
        return MerkleProof.verify(proof, root, leaf);
    }

Last but not least, we just need to change our mint function so that it accepts the proof of the "leaf" associated to "msg.sender" to implement whitelist.

function mint(bytes32[] memory proof) public {
        require(isWhitelisted(proof, keccak256(abi.encodePacked(msg.sender))), "Not a part of Whitelist");
        uint256 tokenId = _tokenIdCounter.current();
        require(tokenId <= maxSupply,"All NFTs have been Minted");
        _tokenIdCounter.increment();
        _safeMint(msg.sender, tokenId);
    }

And that is how you add a whitelist to your smart contract. If you wish to add or remove people, you can also add a function to alter the Merkel Tree's root.

This tutorial's complete code is available in the GitHub repository linked below.