Merkle Trees & Merkle Proofs

Merkle Trees are a fundamental data structure used in blockchain to efficiently organize and verify large sets of transactions. They provide a way to confirm that a transaction exists in a block without downloading the entire blockchain, ensuring integrity and reducing storage and computation requirements.

Structure of a Merkle Tree

A Merkle Tree is a binary tree where:

• Leaf nodes contain the hashes of individual transactions.
• Non-leaf nodes contain the hash of the concatenation of their child nodes.
• The root node, called the Merkle Root, summarizes all transactions in the block.

Step-by-Step Structure Example:

Suppose a block contains 4 transactions: Tx1, Tx2, Tx3, Tx4.

1. Hash each transaction individually: H1 = SHA256(Tx1) H2 = SHA256(Tx2) H3 = SHA256(Tx3) H4 = SHA256(Tx4)
2. Pair the hashes and hash them again: H12 = SHA256(H1 || H2) H34 = SHA256(H3 || H4)
3. Hash the pair of parent nodes to get the Merkle Root: Root = SHA256(H12 || H34)

This root is included in the block header and uniquely represents all transactions in that block.

Visual Structure:

Root
  /    \
H12    H34
/  \   /  \
H1  H2  H3  H4

How Merkle Trees Ensure Transaction Integrity in Blocks

Merkle Trees allow the blockchain to efficiently verify that a specific transaction is part of a block without needing the entire list of transactions.

• Integrity check: If any transaction changes, its hash changes, propagating up the tree and changing the Merkle Root.
• Tamper detection: Even a single-bit modification in Tx3 changes H3, then H34, and finally the root. Nodes can instantly detect tampering.

Example:

• Original Tx3 hash: H3 = SHA256(Tx3)
• Modified transaction Tx3’ → H3’
• New root = SHA256(H12 || H34’) ≠ original Merkle Root

This ensures immutability and integrity of the block’s transactions.

Merkle Proofs and Simplified Payment Verification (SPV) in Bitcoin

A Merkle Proof allows a lightweight client to verify that a transaction is included in a block without downloading the entire block.

How it works:

1. SPV clients store only the block headers, which include the Merkle Root.
2. To verify a transaction Tx3, the client requests the Merkle path from a full node:
3. H3 → H4 (sibling hash) → H12 (parent hash)
4. The client reconstructs the Merkle Root using the hashes along the path and checks if it matches the root in the block header.

Example – SPV Verification:

• Alice wants to verify her Bitcoin transaction in block #100,000.
• SPV client knows the Merkle Root from the block header.
• Alice provides Tx3 and its Merkle path (H4, H12).
• Client calculates:
• H34 = SHA256(H3 || H4)
• Root = SHA256(H12 || H34)
• If this equals the Merkle Root in the block header → Transaction verified without downloading all transactions in the block.

Benefits for Blockchain:

• Saves storage and bandwidth.
• Enables mobile/lightweight wallets to participate securely.
• Ensures trustless verification using cryptography instead of relying on a full node.

Summary

• Merkle Tree: Binary tree of transaction hashes; root summarizes all transactions.
• Transaction Integrity: Any modification in a transaction changes the root, allowing tamper detection.
• Merkle Proofs & SPV: Lightweight clients can verify inclusion of a transaction using only the Merkle path, not the full block.
• Widely used in Bitcoin, Ethereum, and many other blockchains to improve efficiency, security, and scalability.