DEV Community 👩‍💻👨‍💻

Cover image for Implement a gasless Whitelist in your NFT Contract
Vedant Chainani
Vedant Chainani

Posted on

Implement a gasless Whitelist in your NFT Contract

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 (x1,…,xn) and outputs a Merkle root hash h=MHT(x1,…,xn).
  2. A verifier who only has the root hash h can be given an xi and an associated Merkle proof which convinces them that xi was the ith input used to compute h.
  3. 1. If a Merkle proof says that xi was the ith input used to computed h, no attacker can come up with another Merkle proof that says a different x'i ≠xi was the ith input.

How Merkle Tree Works

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

You start by hashing each file as hi=H(fi):

Stage 1

You could continue to hash every two adjacent hashes:

Stage 2

You could even continue on these newly obtained hashes:

Stage 3

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

Stage 4

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 ith leaf of the tree stores the hash hi of the file fi.
  • Each internal node of the tree stores the hash of its two children.
  • The h1,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 fi, you ask for a small part of the Merkle tree called a Merkle proof. This proof enables you to verify that the downloaded fi was not accidentally or maliciously modified.

Proof

Well, observe that the Merkle proof for fi is exactly the subset of hashes in the Merkle tree that, together with fi, allow you to recompute the root hash of the Merkle tree and check it matches the real hash h1,8without 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 fi.


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
Enter fullscreen mode Exit fullscreen mode

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

const { MerkleTree } = require("merkletreejs");
const keccak256 = require("keccak256");
Enter fullscreen mode Exit fullscreen mode

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",
];
Enter fullscreen mode Exit fullscreen mode

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

const buf2hex = (x) => "0x" + x.toString("hex");
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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 });
Enter fullscreen mode Exit fullscreen mode

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

const root = "0x" + tree.getRoot().toString("hex");
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

Now we log all the details

console.log(`Root - ${root}`);
console.log(`leaf - ${leaf}`);
console.log(`proof - ${proof}`);
Enter fullscreen mode Exit fullscreen mode

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

Root - 0x5980c4cba5c7b181167b84183d5b89fd64f1ed01b12ddf12084f2a77d9913c8e
leaf - bae7d1c1447829a0dc7a735041e74fdf7082a238aa8b45b06e550dfce99f5715
proof - 0xd6385235429df428dad417201312f0724220673f2a6956be471426bb77a2c87e,0x363e3bb0c286106f6a19aea117f3dbedb3c3a376b4fd8c31254f9ba86b842366
Enter fullscreen mode Exit fullscreen mode

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";
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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.

GitHub logo Envoy-VC / Smart-Contracts

A Collection of smart contracts to aid you with your web 3 projects.


Top comments (1)

Collapse
delphinethomas profile image
DelphineThomas

How do I make my own NFT smart contract? tantrik in Mayong

👀 Every week new members join DEV and share a bit about them in our Welcome Thread

Welcome them to DEV and share a bit about yourself.