← Back to DevBytes
Developer Tutorial July 16, 2026 14 min read

Merkle Trees: Implementation and Time Complexity Analysis

Understanding Merkle Trees

A Merkle tree, named after computer scientist Ralph Merkle, is a hash-based data structure that organizes data into a binary tree where every leaf node holds a cryptographic hash of a data block, and every internal node holds the hash of the concatenation of its two child hashes. The single node at the top—the Merkle root—serves as a compact, tamper-proof fingerprint of the entire dataset.

At its core, the Merkle tree is elegantly simple. Given a list of data elements, you hash each one to produce leaf hashes. Then you repeatedly pair adjacent hashes, concatenate them, hash the result, and move up a level. This process continues until only one hash remains—the root. If the number of nodes at any level is odd, the last node is typically duplicated (or handled with a consistent padding strategy) to maintain the pairing structure.

Here is a visual representation of a Merkle tree with four data blocks:


        [Root Hash: H(H(A)+H(B)) + H(H(C)+H(D))]
              /                          \
     [H(H(A)+H(B))]              [H(H(C)+H(D))]
       /        \                  /        \
  [H(A)]      [H(B)]          [H(C)]      [H(D)]
    |           |               |           |
  Data A     Data B           Data C     Data D

Each level distills information from the level below, culminating in a single 32-byte (for SHA-256) root hash that cryptographically commits to every leaf in the tree.

Why Merkle Trees Matter

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

Merkle trees solve a fundamental problem in distributed and decentralized systems: how do you efficiently prove that a specific piece of data belongs to a large dataset without transmitting or storing the entire dataset? They enable:

Real-world applications span numerous domains:

Core Concepts and Terminology

Before diving into implementation, let's establish the precise terminology:

Complete Python Implementation

Let's build a production-ready Merkle tree from scratch using SHA-256. We'll cover tree construction, root retrieval, proof generation, and proof verification—all with careful handling of edge cases.

Hash Utilities


import hashlib
from typing import List, Tuple, Optional

def sha256(data: bytes) -> bytes:
    """Single SHA-256 hash, returning 32 bytes."""
    return hashlib.sha256(data).digest()

def hash_pair(a: bytes, b: bytes) -> bytes:
    """Hash the concatenation of two child hashes.
    Order matters: a goes first (left child), b second (right child).
    """
    return sha256(a + b)

Tree Construction

The _build_levels method takes a list of leaf hashes and builds all tree levels bottom-up. At each level, we iterate through nodes in pairs, hashing each pair together. When a level has an odd number of nodes, we duplicate the last node to pair it with itself—this is the most common strategy and ensures a complete binary tree.


class MerkleTree:
    """
    A Merkle Tree built with SHA-256.
    
    Handles odd node counts at any level by duplicating the last node.
    Stores all intermediate levels to enable efficient proof generation.
    """
    
    def __init__(self, data_chunks: List[bytes]):
        """
        Build a Merkle tree from raw data chunks.
        
        Args:
            data_chunks: List of byte strings representing the raw data.
                         Each chunk will be hashed to form a leaf.
        """
        if not data_chunks:
            raise ValueError("Must provide at least one data chunk")
        
        # Hash each data chunk to produce leaf nodes
        self.leaves = [sha256(chunk) for chunk in data_chunks]
        
        # Build all levels from leaves up to root
        self.levels = self._build_levels(self.leaves)
        
        # Cache the root for quick access
        self.root = self.levels[-1][0] if self.levels[-1] else None
    
    def _build_levels(self, leaves: List[bytes]) -> List[List[bytes]]:
        """
        Build all tree levels bottom-up.
        
        Returns:
            A list of levels, where levels[0] contains leaf hashes
            and levels[-1] contains a single-element list with the root.
        """
        levels = [leaves]
        current_level = leaves
        
        # Iteratively build higher levels until only the root remains
        while len(current_level) > 1:
            next_level = []
            
            # Process nodes in pairs
            for i in range(0, len(current_level), 2):
                left = current_level[i]
                
                # Handle odd count: duplicate the last node
                if i + 1 < len(current_level):
                    right = current_level[i + 1]
                else:
                    right = left  # self-pairing for odd node
                
                next_level.append(hash_pair(left, right))
            
            levels.append(next_level)
            current_level = next_level
        
        return levels
    
    def get_root(self) -> bytes:
        """Return the Merkle root hash (32 bytes for SHA-256)."""
        return self.root
    
    def get_leaf(self, index: int) -> bytes:
        """Return the raw leaf hash at the given index."""
        if index < 0 or index >= len(self.leaves):
            raise IndexError(f"Leaf index {index} out of range (0..{len(self.leaves)-1})")
        return self.leaves[index]
    
    def total_leaves(self) -> int:
        """Return the number of leaf nodes."""
        return len(self.leaves)

Generating Merkle Proofs

A Merkle proof for a leaf at a given index consists of the sibling hash at each level along the path to the root, plus a boolean flag indicating whether the sibling is on the right (True) or left (False). This positional information is critical because hash order matters: hash(left || right) differs from hash(right || left).

The algorithm traverses from the leaf level upward. At each level, it determines the sibling based on whether the current index is even (sibling is index+1, to the right) or odd (sibling is index-1, to the left). The index is then halved (integer division by 2) to find the node's position in the next level.


    def generate_proof(self, leaf_index: int) -> List[Tuple[bytes, bool]]:
        """
        Generate an inclusion proof for the leaf at the given index.
        
        Args:
            leaf_index: Zero-based index of the leaf in the original data_chunks list.
        
        Returns:
            A list of (sibling_hash, is_right_sibling) tuples.
            is_right_sibling=True means sibling is to the right (our path node is left),
            False means sibling is to the left (our path node is right).
            The list is ordered from leaf level upward toward the root.
        """
        if leaf_index < 0 or leaf_index >= len(self.leaves):
            raise IndexError(f"Leaf index {leaf_index} out of range")
        
        proof = []
        current_index = leaf_index
        
        # Traverse from leaf level up to (but not including) the root level
        for level in self.levels[:-1]:
            # Determine sibling index and position
            if current_index % 2 == 0:
                # Even index: our node is left child, sibling is right child
                sibling_index = current_index + 1
                is_right = True
            else:
                # Odd index: our node is right child, sibling is left child
                sibling_index = current_index - 1
                is_right = False
            
            # Handle odd-node case where sibling index might be out of bounds
            # (when the last node was duplicated, the sibling is the same node)
            if sibling_index < len(level):
                sibling_hash = level[sibling_index]
            else:
                # Sibling index out of bounds: the node was paired with itself
                sibling_hash = level[current_index]
                # When duplicated, the sibling is effectively on the right
                is_right = True
            
            proof.append((sibling_hash, is_right))
            
            # Move to parent position in the next level
            current_index = current_index // 2
        
        return proof

Verifying a Proof

Verification is a stateless operation: given a leaf hash, a proof path, and an expected root, the verifier recomputes the root by iterating through the proof tuples and hashing in the correct order. If the final computed hash matches the expected root, the proof is valid. This method is marked @staticmethod because verification requires no access to the tree itself—only the root.


    @staticmethod
    def verify_proof(
        leaf_hash: bytes,
        proof: List[Tuple[bytes, bool]],
        expected_root: bytes
    ) -> bool:
        """
        Verify a Merkle inclusion proof.
        
        Args:
            leaf_hash: The SHA-256 hash of the leaf data being verified.
            proof: List of (sibling_hash, is_right) tuples from generate_proof.
            expected_root: The trusted Merkle root to verify against.
        
        Returns:
            True if the proof is valid and yields expected_root, False otherwise.
        """
        current_hash = leaf_hash
        
        for sibling_hash, is_right in proof:
            if is_right:
                # Sibling is on the right: current_hash is left child
                current_hash = hash_pair(current_hash, sibling_hash)
            else:
                # Sibling is on the left: current_hash is right child
                current_hash = hash_pair(sibling_hash, current_hash)
        
        return current_hash == expected_root
    
    @staticmethod
    def verify_data_proof(
        data_chunk: bytes,
        proof: List[Tuple[bytes, bool]],
        leaf_index: int,
        expected_root: bytes
    ) -> bool:
        """
        Convenience method to verify raw data directly.
        Hashes the data_chunk first, then delegates to verify_proof.
        """
        leaf_hash = sha256(data_chunk)
        return MerkleTree.verify_proof(leaf_hash, proof, expected_root)

Complete Usage Example

Here is a full walkthrough demonstrating tree creation, proof generation, successful verification, and tamper detection:


# Sample data: four messages as byte strings
messages = [
    b"Transaction: Alice pays Bob 10 BTC",
    b"Transaction: Charlie pays Dave 5 BTC",
    b"Transaction: Eve pays Frank 2 BTC",
    b"Transaction: Grace pays Henry 8 BTC",
]

# Build the Merkle tree
tree = MerkleTree(messages)

root = tree.get_root()
print(f"Merkle root: {root.hex()}")
print(f"Number of leaves: {tree.total_leaves()}")

# Generate a proof for leaf index 1 (second transaction)
leaf_data = messages[1]
proof = tree.generate_proof(1)

print(f"\nProof for leaf index 1:")
for i, (sibling, is_right) in enumerate(proof):
    direction = "right" if is_right else "left"
    print(f"  Level {i}: sibling={sibling.hex()[:16]}... position={direction}")

# Verify the proof
is_valid = MerkleTree.verify_data_proof(leaf_data, proof, 1, root)
print(f"\nProof verification: {'VALID' if is_valid else 'INVALID'}")

# Tamper detection: modify the data and try to verify
tampered_data = b"Transaction: Alice pays Bob 100 BTC"  # changed amount
is_valid_tampered = MerkleTree.verify_data_proof(tampered_data, proof, 1, root)
print(f"Tampered data verification: {'VALID' if is_valid_tampered else 'INVALID'}")

# Verify a different leaf (index 2) with its own proof
proof_leaf2 = tree.generate_proof(2)
is_valid_leaf2 = MerkleTree.verify_data_proof(messages[2], proof_leaf2, 2, root)
print(f"Leaf 2 proof verification: {'VALID' if is_valid_leaf2 else 'INVALID'}")

# Test with odd number of leaves (5 leaves)
odd_messages = messages + [b"Transaction: Ian pays Jane 3 BTC"]
odd_tree = MerkleTree(odd_messages)
print(f"\nOdd-leaf tree root: {odd_tree.get_root().hex()}")
print(f"Odd-leaf tree has {odd_tree.total_leaves()} leaves")

# Generate and verify proof for the last leaf (index 4, duplicated case)
proof_last = odd_tree.generate_proof(4)
is_valid_last = MerkleTree.verify_data_proof(odd_messages[4], proof_last, 4, odd_tree.get_root())
print(f"Last leaf (odd case) verification: {'VALID' if is_valid_last else 'INVALID'}")

Expected output will show valid proofs for all genuine leaves and an invalid result for tampered data, confirming the tree's integrity guarantees.

Time Complexity Analysis

Understanding the asymptotic behavior of Merkle tree operations is essential for designing systems that scale to millions of leaves. Let n be the number of leaf nodes (data chunks).

Tree Construction

Building the tree requires hashing each leaf (n hash operations) and then computing each internal node. For a binary tree with n leaves, there are exactly n - 1 internal nodes when no duplication occurs. With duplication for odd levels, the total number of internal nodes is bounded by 2n. Each internal node requires one hash computation (the concatenation of two child hashes). Therefore:

If you only need the root and can discard intermediate levels after building, space drops to O(log n) during construction (just the current and next level at each step), though proof generation would then require reconstructing siblings.

Proof Generation

Generating an inclusion proof traverses from a leaf up to the root, collecting one sibling per level. The tree height is ⌈log₂(n)⌉ (ceiling of log base 2). Therefore:

Proof Verification

Verification is equally efficient. The verifier starts with the leaf hash and iterates through the proof list (length log n), performing one hash operation per step:

Complexity Summary Table


Operation              | Time         | Space (working) | Proof Size
-----------------------|--------------|-----------------|-------------
Tree construction      | O(n)         | O(n) or O(log n)| N/A
Root retrieval         | O(1)         | O(1)            | N/A
Proof generation       | O(log n)     | O(log n)        | O(log n)
Proof verification     | O(log n)     | O(1)            | O(log n) input
Leaf update (rebuild)  | O(log n)*    | O(log n)        | N/A

* Updating a single leaf and recomputing affected ancestors takes O(log n)
  if the full tree structure is cached.

Practical Performance Numbers

On modern hardware with SHA-256 (hardware-accelerated via AES-NI on many CPUs):

These logarithmic properties are what make Merkle trees indispensable in blockchain protocols and distributed systems operating at planetary scale.

Best Practices

1. Choose a Cryptographically Secure Hash Function

Always use a well-vetted cryptographic hash like SHA-256, SHA-3, or Blake2b. These provide pre-image resistance (given a hash, you cannot find the input) and collision resistance (finding two different inputs with the same hash is computationally infeasible). Avoid non-cryptographic hashes like MurmurHash or xxHash—they are optimized for speed, not security, and are vulnerable to collision attacks.


# Good: SHA-256
hashlib.sha256(data).digest()

# Also good: Blake2b (faster on some platforms)
hashlib.blake2b(data).digest()

# Avoid for security-sensitive Merkle trees:
# hash = xxhash.xxh64(data).digest()  # NOT cryptographically secure

2. Handle Odd Node Counts Consistently

When a level has an odd number of nodes, you need a deterministic rule. The two most common strategies are:

Whichever strategy you choose, document it and apply it consistently at every level. Inconsistency breaks proof verification.

3. Use Domain Separation for Leaf vs. Internal Nodes

A subtle vulnerability arises when leaf hashes and internal node hashes use the same raw hash function without differentiation. An attacker could interpret a leaf hash as an internal node (or vice versa) if the byte lengths happen to align. The standard mitigation is domain separation—prefixing data with a type byte before hashing:


def hash_leaf(data: bytes) -> bytes:
    """Domain-separated leaf hash: prefix with 0x00."""
    return sha256(b'\x00' + data)

def hash_internal(left: bytes, right: bytes) -> bytes:
    """Domain-separated internal node hash: prefix with 0x01."""
    return sha256(b'\x01' + left + right)

Bitcoin uses double-SHA256 (SHA256d) for all nodes, which achieves domain separation implicitly. Ethereum's Merkle Patricia tree uses a different encoding scheme. The key principle is: an observer should not be able to confuse a leaf with an internal node.

4. Consider Double Hashing for Leaf Pre-image Protection

In Bitcoin, leaf hashes are computed as SHA256(SHA256(data)) (double SHA-256, often called SHA256d). This adds an extra layer of pre-image resistance: even if someone finds a pre-image for the inner hash, they still need to invert the outer hash. For high-security applications (financial transactions, certificate logs), double hashing is a worthwhile defense-in-depth measure.


def sha256d(data: bytes) -> bytes:
    """Double SHA-256, as used in Bitcoin."""
    return sha256(sha256(data))

5. Cache Intermediate Levels Judiciously

Storing all tree levels (as our implementation does) enables O(log n) proof generation but consumes O(n) memory. For memory-constrained environments: