About Merkle Trees

A Merkle tree is a cryptographic data structure that allows efficient and secure verification of large data sets. It's fundamental to blockchain technology and is used extensively in smart contracts for allowlists, airdrops, and data verification.

How Merkle Trees Work

A Merkle tree is a binary tree where:

• Leaves: Hash values of your data (addresses, amounts, etc.)
• Branches: Hash of two child nodes combined
• Root: Final hash at the top of the tree

                    Root
                   /    \
                  H01   H23
                 /  \   /  \
                H0  H1 H2  H3
                |   |  |   |
                L0  L1 L2  L3
                (Leaf Data)
                    

Benefits of Merkle Trees

1. Efficient Verification

Verify a single element is part of the set using only log₂(n) hashes, not the entire dataset.

2. Gas Optimization

Store only the root hash on-chain (32 bytes) instead of entire allowlists, saving massive gas costs.

3. Privacy

Prove membership without revealing other elements in the set.

4. Integrity

Any change to leaf data changes the root, making tampering immediately detectable.

Common Use Cases

NFT Allowlists

Store thousands of allowed addresses efficiently:

• Store root hash in contract (32 bytes)
• Users submit their address and proof
• Contract verifies proof against root
• Saves millions of gas compared to storing addresses

Token Airdrops

Distribute tokens to specific addresses with amounts:

• Create leaves with "address + amount"
• Users claim with proof
• Contract verifies and tracks claims

Snapshot Verification

Prove state at a specific time:

• Take snapshot of balances/votes
• Generate Merkle tree
• Users prove their state with proof

Implementation Example

Solidity Contract

pragma solidity ^0.8.0;

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

contract MerkleAllowlist {
    bytes32 public merkleRoot;

    constructor(bytes32 _merkleRoot) {
        merkleRoot = _merkleRoot;
    }

    function claim(bytes32[] calldata proof) external {
        // Create leaf from sender address
        bytes32 leaf = keccak256(abi.encodePacked(msg.sender));

        // Verify proof
        require(
            MerkleProof.verify(proof, merkleRoot, leaf),
            "Invalid proof"
        );

        // Process claim...
    }
}

JavaScript/TypeScript

import { MerkleTree } from 'merkletreejs';
import { keccak256 } from 'ethers/lib/utils';

// Create leaves from addresses
const addresses = ['0x123...', '0x456...'];
const leaves = addresses.map(addr => keccak256(addr));

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

// Get root
const root = tree.getHexRoot();

// Generate proof for address
const leaf = keccak256('0x123...');
const proof = tree.getHexProof(leaf);

Verification Process

To verify a leaf is in the tree:

1. Start with the leaf hash
2. Combine with sibling hash (from proof)
3. Hash the combination
4. Repeat up the tree
5. Compare final hash with root

Best Practices

Sorting

Always sort pairs before hashing to ensure consistent tree structure:

hash = keccak256(abi.encodePacked(
    left < right ? left : right,
    left < right ? right : left
));

Leaf Hashing

Hash leaf data to prevent second preimage attacks:

// Good: Hash the data
leaf = keccak256(abi.encodePacked(address, amount));

// Bad: Use raw data
leaf = abi.encodePacked(address, amount);

Proof Storage

Store proofs off-chain (IPFS, database) and only submit when needed for gas efficiency.

Real-World Examples

• OpenSea: Uses Merkle trees for NFT allowlists
• Uniswap: Used for UNI token airdrop
• ENS: Uses for domain registrations
• Optimism: Uses for state verification