Skip to main content

WTF Solidity 36. Merkle Tree

Recently, I have been reviewing solidity in order to consolidate some details and write a "WTF Solidity Tutorial" for novices (programming experts can find other tutorials). I will update 1-3 lessons weekly.

Welcome to follow me on Twitter: @0xAA_Science

Welcome to join the WTF Scientist community, which includes methods for adding WeChat groups: link

All code and tutorials are open source on Github (1024 stars will issue course certification, 2048 stars will issue community NFTs): github.com/AmazingAng/WTFSolidity

In this lecture, I will introduce the Merkle Tree and how to use it to distribute a NFT whitelist.

Merkle Tree​

Merkle Tree, also known as Merkel tree or hash tree, is a fundamental encryption technology in blockchain and is widely used in Bitcoin and Ethereum blockchains. Merkle Tree is an encrypted tree constructed from the bottom up, where each leaf corresponds to the hash of the corresponding data, and each non-leaf represents the hash of its two child nodes.

![Merkle Tree] (./img/36-1.png)

Merkle Tree allows for efficient and secure verification (Merkle Proof) of the contents of large data structures. For a Merkle Tree with N leaf nodes, verifying whether a given data is valid (belonging to a Merkle Tree leaf node) only requires log(N) data (proofs), which is very efficient. If the data is incorrect, or if the proof given is incorrect, the root value of the root cannot be restored. In the example below, the Merkle proof of leaf L1 is Hash 0-1 and Hash 1: Knowing these two values, we can verify whether the value of L1 is in the leaves of the Merkle Tree or not. Why? Because through the leaf L1 we can calculate Hash 0-0, we also know Hash 0-1, then Hash 0-0 and Hash 0-1 can be combined to calculate Hash 0, we also know Hash 1, and Hash 0 and Hash 1 can be combined to calculate Top Hash, which is the hash of the root node.

![Merkle Proof] (./img/36-2.png)

Generating a Merkle Tree​

We can use a webpage or the Javascript library merkletreejs to generate a Merkle Tree.

Here we use the webpage to generate a Merkle Tree with 4 addresses as the leaf nodes. Leaf node input:

    [
    "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", 
    "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
    "0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
    "0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB"
    ]

Select the Keccak-256, hashLeaves, and sortPairs options in the menu, then click Compute, and the Merkle Tree will be generated. The Merkle Tree expands to:

└─ Root: eeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097
   ├─ 9d997719c0a5b5f6db9b8ac69a988be57cf324cb9fffd51dc2c37544bb520d65
   │  ├─ Leaf0：5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229
   │  └─ Leaf1：999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb
   └─ 4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c
      ├─ Leaf2：04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54
      └─ Leaf3：dfbe3e504ac4e35541bebad4d0e7574668e16fefa26cd4172f93e18b59ce9486

Generating Merkle Tree

Verification of Merkle Proof​

Through the website, we can obtain the proof of address 0 as follows, which is the hash value of the blue node in Figure 2:

[
  "0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb",
  "0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c"
]

We use the MerkleProof library for verification:

library MerkleProof {
    /**
     * @dev Returns `true` when the `root` reconstructed from `proof` and `leaf` equals to the given `root`, meaning the data is valid.
     * During reconstruction, both the leaf node pairs and element pairs are sorted.
     */
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev Returns the `root` of the Merkle tree computed from a `leaf` and a `proof`.
     * The `proof` is only valid when the reconstructed `root` equals to the given `root`.
     * During reconstruction, both the leaf node pairs and element pairs are sorted.
     */
    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    // Sorted Pair Hash
    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? keccak256(abi.encodePacked(a, b)) : keccak256(abi.encodePacked(b, a));
    }
}

The MerkleProof library contains three functions:

  1. The verify() function: It uses the proof to verify whether the leaf belongs to the Merkle Tree with the root of root. If it does, it returns true. It calls the processProof() function.

  2. The processProof() function: It calculates the root of the Merkle Tree using the proof and leaf in sequence. It calls the _hashPair() function.

  3. The _hashPair() function: It uses the keccak256() function to calculate the hash (sorted) of the two child nodes corresponding to the non-root node.

We input address 0, root, and the corresponding proof to the verify() function, which will return true because address 0 is in the Merkle Tree with the root of root, and the proof is correct. If any of these values are changed, it will return false.

Using Merkle Tree to distribute NFT whitelists:

Updating an 800-address whitelist can easily cost more than 1 ETH in gas fees. However, using the Merkle Tree verification, the leaf and proof can exist on the backend, and only one value of root needs to be stored on the chain, making it very gas-efficient. Many ERC721 NFT and ERC20 standard token whitelists/airdrops are issued using Merkle Tree, such as the airdrop on Optimism.

Here, we introduce how to use the MerkleTree contract to distribute NFT whitelists:

contract MerkleTree is ERC721 {
    bytes32 immutable public root; // Root of the Merkle tree
    mapping(address => bool) public mintedAddress;   // Record the address that has already been minted

    // Constructor, initialize the name and symbol of the NFT collection, and the root of the Merkle tree
    constructor(string memory name, string memory symbol, bytes32 merkleroot)
    ERC721(name, symbol)
    {
        root = merkleroot;
    }

    // Use the Merkle tree to verify the address and mint
    function mint(address account, uint256 tokenId, bytes32[] calldata proof)
    external
    {
        require(_verify(_leaf(account), proof), "Invalid merkle proof"); // Merkle verification passed
        require(!mintedAddress[account], "Already minted!"); // Address has not been minted
        
        mintedAddress[account] = true; // Record the minted address
        _mint(account, tokenId); // Mint
    }

    // Calculate the hash value of the Merkle tree leaf
    function _leaf(address account)
    internal pure returns (bytes32)
    {
        return keccak256(abi.encodePacked(account));
    }

    // Merkle tree verification, call the verify() function of the MerkleProof library
    function _verify(bytes32 leaf, bytes32[] memory proof)
    internal view returns (bool)
    {
        return MerkleProof.verify(proof, root, leaf);
    }
}

The MerkleTree contract inherits the ERC721 standard and utilizes the MerkleProof library.

State Variables​

The contract has two state variables:

  • root stores the root of the Merkle Tree, assigned during contract deployment.
  • mintedAddress is a mapping that records minted addresses. It is assigned a value after a successful mint.

Functions​

The contract has four functions:

  • Constructor: Initializes the name and symbol of the NFT, and the root of the Merkle Tree.
  • mint() function: Mints an NFT using a whitelist. Takes account (whitelisted address), tokenId (minted ID), and proof as arguments. The function first verifies whether the address is whitelisted. If verification passes, the NFT with ID tokenId is minted for the address, which is then recorded in mintedAddress. This process calls the _leaf() and _verify() functions.
  • _leaf() function: Calculates the hash of the leaf address of the Merkle Tree.
  • _verify() function: Calls the verify() function of the MerkleProof library to verify the Merkle Tree.

Remix Verification​

We use the four addresses in the example above as the whitelist and generate a Merkle Tree. We deploy the MerkleTree contract with three arguments:

name = "WTF MerkleTree"
symbol = "WTF"
merkleroot = 0xeeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097

Deploying MerkleTree contract

Next, run the mint function to mint an NFT for address 0, using three parameters:

account = 0x5B38Da6a701c568545dCfcB03FcB875f56beddC4
tokenId = 0
proof = [   "0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb",   "0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c" ]

We can use the ownerOf function to verify that the tokenId of 0 for the NFT has been minted to address 0, and the contract has run successfully.

If we change the holder of the tokenId to 0, the contract will still run successfully.

If we call the mint function again at this point, although the address can pass the Merkle Proof verification, because the address has already been recorded in mintedAddress, the transaction will be aborted due to "Already minted!".

In this lesson, we introduced the concept of Merkle Tree, how to generate a simple Merkle Tree, how to use smart contracts to verify Merkle Tree, and how to use it to distribute NFT whitelist.

In practical use, complex Merkle Tree can be generated and managed using the merkletreejs library in Javascript, and only one root value needs to be stored on the chain, which is very gas-efficient. Many project teams choose to use Merkle Tree to distribute the whitelist.