Merkle trees and membership proofs - verifying millions of items with one hash

How do you prove an element belongs to a huge list without sending the whole list? How can you be sure a block of data has not been changed by checking only a tiny "fingerprint"? The answer is one of the most useful structures in cryptography - the Merkle tree. It underlies blockchains and many smart contracts. You should first know what a hash function is.

How the tree is built

Take four elements: A, B, C, D.

1. Compute each hash: H(A), H(B), H(C), H(D). These are the leaves.
2. Join neighbours in pairs and hash: H(AB) = H(H(A) ‖ H(B)), H(CD) = H(H(C) ‖ H(D)).
3. Repeat for the pairs: Root = H(H(AB) ‖ H(CD)).

            Root
          /      \
      H(AB)      H(CD)
      /   \      /   \
   H(A)  H(B)  H(C)  H(D)

The root is a single hash for the whole set. Changing any element changes the chain of hashes all the way to the root. If the number of leaves is odd, the last element is duplicated or carried up (the method depends on the implementation).

The membership proof

Suppose we need to prove that C belongs to a set with a known root. We do not need to show all the elements. A branch is enough:

• H(D) (the sibling of leaf C);
• H(AB) (the sibling at the next level).

The verifier:

1. computes H(C);
2. combines it with H(D) → H(CD);
3. combines H(AB) with H(CD) → gets a root;
4. compares it with the known root.

If it matches, C really belongs to the set. The proof size grows as the logarithm of the number of leaves: for a million elements only 20 hashes are needed (about 640 bytes), not a million.

Verification in Solidity

A contract needs to store only the root (32 bytes). A library does the checking:

bytes32 public merkleRoot;

function claim(uint256 amount, bytes32[] calldata proof) external {
    bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(msg.sender, amount))));
    require(MerkleProof.verify(proof, merkleRoot, leaf), "not in list");
    require(!claimed[msg.sender], "already claimed");
    claimed[msg.sender] = true;
    // ... payout
}

A list of a million addresses costs one slot in storage. The user presents the proof, and the website computes it in advance and hands it to the wallet.

Where it is used

• Airdrops and allowlists. A project distributes tokens to thousands of addresses without writing each into the blockchain.
• Bitcoin and Ethereum blocks. A block header holds the Merkle root of the transactions. A light client checks a transaction's inclusion with a short proof without downloading the whole block.
• Ethereum state. The "world state" is kept in a Merkle Patricia tree whose root goes into every block (accounts and state).
• Rollups and bridges. Data is carried from one network to another by proving its inclusion in a fixed root (rollups under the hood, bridges).
• Data integrity. Distribution of large files, storage, version-control systems.

Merkle trees and deal terms

In our service the deal's terms are anchored by a hash (terms hash). If there were many terms (say a contract of hundreds of clauses), one could anchor a Merkle root and prove each clause separately. For an ordinary deal one hash is enough.

Attacks and pitfalls

Node and leaf substitution. You must distinguish a leaf from an intermediate node. Otherwise an attacker can pass the concatenation of two hashes off as a "leaf" and pick a proof for a nonexistent element. The defence is double-hashing leaves (as in the example above) or adding prefixes.

Pair order. Libraries often sort a pair of hashes before joining so that the proof need not carry a "direction". Then order is irrelevant to verification.

Reuse. A proof confirms only membership. To prevent receiving a reward twice, the contract keeps a claimed mark (catalogue of vulnerabilities).

List leakage. The root hides the set, but does not protect against the fact that whoever built the tree knows all the elements.

A mini example

A list of "reward recipients": Anna - 100, Boris - 250, Vera - 40, Gleb - 75.

1. The organiser computes the leaves H(Anna, 100) and so on.
2. Builds the tree and publishes the root in the contract.
3. Boris visits the website: it gives him a proof of two hashes.
4. Boris calls claim(250, proof). The contract reconstructs the root and compares it with the stored one - success.
5. Gleb tries to claim 7500 instead of 75: the root does not match - rejected.

What to read next

Learn how contracts get data from the outside world: the oracle problem. Or how scaling is built: rollups under the hood.