Problem: You have 1TB database replicated on two servers
Question: Are they identical?

Naive approach:
Send entire 1TB over network → Compare
Cost: 1TB bandwidth, hours of transfer

Hash approach:
Send single hash (32 bytes) → Compare
Problem: Tells you IF different, not WHERE

Merkle Tree approach:
Send tree of hashes (KB) → Find exact differences
Cost: KB bandwidth, verify specific blocks

Data blocks:     [A]  [B]  [C]  [D]
                  ↓    ↓    ↓    ↓
Leaf hashes:    H(A) H(B) H(C) H(D)
                  ↓    ↓    ↓    ↓
Level 1:         H(AB)     H(CD)
                    ↓         ↓
Root:              H(ABCD)

graph TB
    Root["Root Hash<br/>H(ABCD)"]
    Root --> H_AB["H(AB)"]
    Root --> H_CD["H(CD)"]
    H_AB --> H_A["H(A)<br/>Leaf"]
    H_AB --> H_B["H(B)<br/>Leaf"]
    H_CD --> H_C["H(C)<br/>Leaf"]
    H_CD --> H_D["H(D)<br/>Leaf"]
    H_A -.-> A["Block A<br/>Data"]
    H_B -.-> B["Block B<br/>Data"]
    H_C -.-> C["Block C<br/>Data"]
    H_D -.-> D["Block D<br/>Data"]

import hashlib

class MerkleTree:
    def __init__(self, data_blocks):
        """Build Merkle tree from data blocks"""
        self.leaves = [self._hash(block) for block in data_blocks]
        self.tree = self._build_tree(self.leaves)
        self.root = self.tree[0] if self.tree else None
    
    def _hash(self, data):
        """SHA-256 hash of data"""
        if isinstance(data, str):
            data = data.encode('utf-8')
        return hashlib.sha256(data).hexdigest()
    
    def _build_tree(self, nodes):
        """Recursively build tree from leaf nodes"""
        if len(nodes) == 0:
            return []
        if len(nodes) == 1:
            return nodes
        
        tree = []
        # Process pairs
        for i in range(0, len(nodes), 2):
            left = nodes[i]
            right = nodes[i + 1] if i + 1 < len(nodes) else left
            parent = self._hash(left + right)
            tree.append(parent)
        
        # Recursively build upper levels
        return self._build_tree(tree) + tree
    
    def get_root(self):
        """Get root hash"""
        return self.root
    
    def get_proof(self, index):
        """Get Merkle proof for block at index"""
        if index >= len(self.leaves):
            return None
        
        proof = []
        nodes = self.leaves[:]
        
        while len(nodes) > 1:
            level_proof = []
            new_nodes = []
            
            for i in range(0, len(nodes), 2):
                left = nodes[i]
                right = nodes[i + 1] if i + 1 < len(nodes) else left
                
                # If this is our target or its sibling
                if i == index or i + 1 == index:
                    sibling = right if i == index else left
                    level_proof.append(('right' if i == index else 'left', sibling))
                    index = i // 2
                
                parent = self._hash(left + right)
                new_nodes.append(parent)
            
            if level_proof:
                proof.extend(level_proof)
            nodes = new_nodes
        
        return proof
    
    def verify_proof(self, block, index, proof, root):
        """Verify Merkle proof"""
        current_hash = self._hash(block)
        
        for direction, sibling_hash in proof:
            if direction == 'left':
                current_hash = self._hash(sibling_hash + current_hash)
            else:
                current_hash = self._hash(current_hash + sibling_hash)
        
        return current_hash == root


# Example usage
data = ['Block A', 'Block B', 'Block C', 'Block D']
tree = MerkleTree(data)

print(f"Root hash: {tree.get_root()}")

# Get proof for Block B (index 1)
proof = tree.get_proof(1)
print(f"Proof for Block B: {proof}")

# Verify proof
is_valid = tree.verify_proof('Block B', 1, proof, tree.get_root())
print(f"Proof valid: {is_valid}")

const crypto = require('crypto');

class MerkleTree {
  constructor(dataBlocks) {
    this.leaves = dataBlocks.map(block => this.hash(block));
    this.tree = this.buildTree(this.leaves);
    this.root = this.tree[0] || null;
  }
  
  hash(data) {
    return crypto.createHash('sha256')
      .update(data)
      .digest('hex');
  }
  
  buildTree(nodes) {
    if (nodes.length === 0) return [];
    if (nodes.length === 1) return nodes;
    
    const tree = [];
    for (let i = 0; i < nodes.length; i += 2) {
      const left = nodes[i];
      const right = i + 1 < nodes.length ? nodes[i + 1] : left;
      const parent = this.hash(left + right);
      tree.push(parent);
    }
    
    return [...this.buildTree(tree), ...tree];
  }
  
  getRoot() {
    return this.root;
  }
  
  getProof(index) {
    if (index >= this.leaves.length) return null;
    
    const proof = [];
    let nodes = [...this.leaves];
    let currentIndex = index;
    
    while (nodes.length > 1) {
      const newNodes = [];
      
      for (let i = 0; i < nodes.length; i += 2) {
        const left = nodes[i];
        const right = i + 1 < nodes.length ? nodes[i + 1] : left;
        
        if (i === currentIndex) {
          proof.push({ side: 'right', hash: right });
          currentIndex = Math.floor(i / 2);
        } else if (i + 1 === currentIndex) {
          proof.push({ side: 'left', hash: left });
          currentIndex = Math.floor(i / 2);
        }
        
        newNodes.push(this.hash(left + right));
      }
      
      nodes = newNodes;
    }
    
    return proof;
  }
  
  verifyProof(block, proof, root) {
    let currentHash = this.hash(block);
    
    for (const { side, hash } of proof) {
      currentHash = side === 'left' 
        ? this.hash(hash + currentHash)
        : this.hash(currentHash + hash);
    }
    
    return currentHash === root;
  }
}

// Example
const data = ['Block A', 'Block B', 'Block C', 'Block D'];
const tree = new MerkleTree(data);

console.log('Root:', tree.getRoot());

const proof = tree.getProof(1);
console.log('Proof for Block B:', proof);

const isValid = tree.verifyProof('Block B', proof, tree.getRoot());
console.log('Valid:', isValid);

Server A: [A, B, C, D, E, F, G, H]
Server B: [A, B, C, D', E, F, G, H]  (D is different)

Goal: Find which block differs without transferring all data

sequenceDiagram
    participant A as Server A
    participant B as Server B
    
    A->>B: Send Root Hash
    B->>B: Compare with local root
    Note over B: Roots differ!
    
    B->>A: Send local root hash
    A->>B: Request left & right subtree hashes
    B->>A: H(ABCD), H(EFGH)
    
    A->>A: Compare subtrees
    Note over A: Left subtree differs
    
    A->>B: Request H(AB), H(CD)
    B->>A: H(AB), H(CD)
    
    A->>A: Compare
    Note over A: H(CD) differs
    
    A->>B: Request H(C), H(D)
    B->>A: H(C), H(D)
    
    A->>A: Compare
    Note over A: H(D) differs!
    
    A->>B: Send correct Block D
    B->>B: Update Block D

8 blocks total
Traditional: Transfer 8 blocks
Merkle Tree: Transfer 1 block + log(8) = 4 hashes

For 1M blocks:
Traditional: 1M blocks
Merkle Tree: ~20 hashes + differing blocks

def sync_merkle_trees(tree_a, tree_b, index_range=(0, None)):
    """Recursively sync two Merkle trees"""
    start, end = index_range
    if end is None:
        end = len(tree_a.leaves)
    
    # Base case: single element
    if end - start == 1:
        if tree_a.leaves[start] != tree_b.leaves[start]:
            return [start]  # Return index of difference
        return []
    
    # Compare roots
    if tree_a.get_root() == tree_b.get_root():
        return []  # Trees identical
    
    # Divide and conquer
    mid = (start + end) // 2
    
    # Check left subtree
    left_diffs = sync_merkle_trees(tree_a, tree_b, (start, mid))
    
    # Check right subtree
    right_diffs = sync_merkle_trees(tree_a, tree_b, (mid, end))
    
    return left_diffs + right_diffs

Git uses Merkle Trees to track file changes:

Commit Tree:
Root (commit hash) → Tree hash → Blob hashes

commit 3a7b5c
└── tree a1b2c3
    ├── blob def456 (file1.txt)
    ├── blob 789abc (file2.txt)
    └── tree 012fed
        └── blob 345678 (nested/file3.txt)

Any change in any file → Different root hash

# Every commit is a Merkle root
git log --oneline
3a7b5c Commit message  # This is the root hash

# Show tree structure
git ls-tree 3a7b5c
100644 blob def456 file1.txt
100644 blob 789abc file2.txt
040000 tree 012fed nested

Block structure:
┌─────────────────┐
│  Block Header   │
│  - Merkle Root  │ ← Root of transaction tree
│  - Prev Hash    │
│  - Nonce        │
└─────────────────┘
        ↓
  Merkle Tree of Transactions

Lightweight client (phone):
- Stores block headers only (80 bytes each)
- Doesn't store full blockchain (400+ GB)

To verify transaction:
1. Ask full node for Merkle proof
2. Verify proof against block header's Merkle root
3. Confirm transaction included in block

Proof size: log₂(n) × 32 bytes
Example: 2,000 transactions → 11 × 32 = 352 bytes

# Cassandra anti-entropy repair using Merkle trees
class CassandraRepair:
    def repair_range(self, node_a, node_b, token_range):
        """Compare data ranges using Merkle trees"""
        
        # Build Merkle tree for each node's data
        tree_a = build_merkle_tree(node_a.get_data(token_range))
        tree_b = build_merkle_tree(node_b.get_data(token_range))
        
        # Compare roots
        if tree_a.root == tree_b.root:
            return  # Data in sync
        
        # Find differences
        diffs = find_differences(tree_a, tree_b)
        
        # Stream only different data
        for key in diffs:
            latest = resolve_conflict(node_a.get(key), node_b.get(key))
            node_a.set(key, latest)
            node_b.set(key, latest)

IPFS uses Merkle DAG (Directed Acyclic Graph):

File: "Hello World" (1MB)
├── Chunk 1 (256KB) → Hash: Qm...abc
├── Chunk 2 (256KB) → Hash: Qm...def
├── Chunk 3 (256KB) → Hash: Qm...ghi
└── Chunk 4 (256KB) → Hash: Qm...jkl

Root: Qm...xyz (hash of all chunk hashes)

Address: ipfs://Qm...xyz

Traditional: example.com/file.pdf (location-based)
IPFS: ipfs://Qm... (content-based)

Benefit: Same content = same hash
Identical files shared by hash (deduplication)

// S3 uses Merkle-like hashing for multipart uploads
const uploadParts = [
  { PartNumber: 1, ETag: '"abc123..."' },
  { PartNumber: 2, ETag: '"def456..."' },
  { PartNumber: 3, ETag: '"ghi789..."' }
];

// Final ETag (Merkle root)
const finalETag = hashParts(uploadParts) + '-3';
// Result: "xyz999...-3"

// Used to verify upload integrity

Tree with 8 blocks, prove Block C is included:

Required hashes (proof):
- H(D) (sibling)
- H(AB) (uncle)
- H(EFGH) (uncle)

Verification:
H(C) + H(D) = H(CD)
H(AB) + H(CD) = H(ABCD)
H(ABCD) + H(EFGH) = Root ✓

# Example: Verify transaction in Bitcoin block
def verify_transaction_in_block(tx, proof, block_header):
    """
    tx: Transaction data
    proof: List of (side, hash) pairs
    block_header: Contains merkle_root
    """
    current_hash = sha256(tx)
    
    for side, proof_hash in proof:
        if side == 'left':
            current_hash = sha256(proof_hash + current_hash)
        else:
            current_hash = sha256(current_hash + proof_hash)
    
    return current_hash == block_header.merkle_root

Merkle Tree: Each node has 1-2 children
Merkle DAG: Each node can reference multiple nodes

Example: Git repository
┌─────────┐
│ Commit  │ (references tree + parent commit)
└────┬────┘
     ├──→ Tree
     └──→ Parent Commit