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
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:
The
verify()
function: It uses theproof
to verify whether theleaf
belongs to theMerkle Tree
with the root ofroot
. If it does, it returnstrue
. It calls theprocessProof()
function.The
processProof()
function: It calculates theroot
of theMerkle Tree
using theproof
andleaf
in sequence. It calls the_hashPair()
function.The
_hashPair()
function: It uses thekeccak256()
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 theMerkle Tree
, assigned during contract deployment.mintedAddress
is amapping
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 theMerkle Tree
. mint()
function: Mints an NFT using a whitelist. Takesaccount
(whitelisted address),tokenId
(minted ID), andproof
as arguments. The function first verifies whether theaddress
is whitelisted. If verification passes, the NFT with IDtokenId
is minted for the address, which is then recorded inmintedAddress
. This process calls the_leaf()
and_verify()
functions._leaf()
function: Calculates the hash of the leaf address of theMerkle Tree
._verify()
function: Calls theverify()
function of theMerkleProof
library to verify theMerkle 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
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.