A binary hash tree—often called a Merkle tree—compresses an arbitrary amount of data into a single 256-bit digest while still allowing anyone to prove that a specific element belongs to the original set. The construction is straightforward: hash every item, pair the hashes, hash the pairs, and continue until one value remains. That final value is the root digest, and changing even one input bit forces the root to change, exposing tampering immediately.

Building the Tree

Consider four records r0, r1, r2, r3.

1. Hash each record individually: ``` d0 = keccak256(r0) d1 = keccak256(r1) d2 = keccak256(r2) d3 = keccak256(r3)

2. Concatenate and hash sibling digests: ``` p0 = keccak256(abi.encodePacked(d0, d1)) p1 = keccak256(abi.encodePacked(d2, d3))

3. Derive the root: ``` root = keccak256(abi.encodePacked(p0, p1))

The resulting structure is:

        root
       /    \
    p0      p1
   /  \    /  \
 d0  d1  d2  d3

Why It Matters

• Lightweight membership proofs: Only O(log n) sibling digests are needed to confirm that a record is in the tree, making mobile and embedded clients practical.
• Storage efficiency: A contract can remember one 32-byte root instead of the entire list, dramatically reducing gas costs.
• Tamper evidence: Any modification to underlying data invalidates the root, providing immediate integrity alerts.

Smart-Contract Applications

Transaction Commitments

Bitcoin and Ethereum blocks store a single root digest of all transactions. Light clients download only block headers and request short proofs to confirm that a transaction was included without syncing the entire chain.

Allow-Lists and Airdrops

Instead of embedding a million addresses in a contract, developers:

1. Compute the root off-chain.
2. Store the 32-byte root on-chain.
3. Users claim tokens by submitting their addres plus the authentication path—the minimal set of sibling digests needed to recompute the root.

On-Chain Verification

Solidity already ships with MerkleProof.sol. A minimal wrapper looks like:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

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

contract AllowList {
    bytes32 public merkleRoot;

    constructor(bytes32 _root) {
        merkleRoot = _root;
    }

    function isAllowed(
        address who,
        bytes32[] calldata proof
    ) external view returns (bool) {
        bytes32 leaf = keccak256(abi.encodePacked(who));
        return MerkleProof.verify(proof, merkleRoot, leaf);
    }
}

The proof array contains the sibling digests encountered while walking from the leaf to the root. The library concatenates and hashes them in the correct order; if the result matches the stored root, the claim succeeds.