Lecture Notes: Foundations of
Blockchain(IT-4158)
Topic: Merkle Tree (Hash Tree) and
Its Use in Blockchain
By: Dr. Vineeta Soni
A Merkle tree is a foundation of the blockchain structure. So in this lecture, we will cover:
• What is a Cryptographic Hash?
• What is Hash Pointer?
• Blockchain Structure
• Block Structure
• Merkle Tree Structure
• How Do Merkle Trees Work?
• Why Merkle Trees are Important For Blockchain
• Proof of Membership
• Merkle Proofs
• Simple Payment Verification (SPV)
• Advantages of Merkle Tree
• Time Complexity
What is a Cryptographic Hash?
A cryptographic hash is a function that outputs a fixed-size digest for a variable-length input. It is
a core primitive in blockchain. For example, SHA-256 always produces a 256-bit hash. Even a one-
character change in the input can drastically alter the output (avalanche effect), making hashes ideal
for integrity checking.
Example workflow for integrity: compute and store a file’s hash. If the file is later modified by an
attacker, recomputing the hash will not match the stored hash, revealing tampering.
What is a Hash Pointer?
A regular pointer stores the location of the data. A hash pointer stores both (1) the location of the
data and (2) a cryptographic hash of that data. This means a hash pointer lets you access the data
and also verify it hasn’t been altered. Hash pointers are used to build blockchains and Merkle trees.
Blockchain Structure
A blockchain combines two hash-based structures:
1) A linked list of blocks where each block points to the previous block through a hash pointer.
2) Inside each block, a Merkle tree organizes that block’s transactions for efficient verification.
Figure 1: Blockchain modeled as a hash-pointer linked list.
Block Structure
Each block typically consists of two parts:
• Block header: metadata about the block (previous block hash, current block hash, timestamp,
cryptographic nonce, and the Merkle root of transactions).
• Merkle tree: a per-block tree of all included transactions.
Figure 2: Block = Header + Merkle tree of transactions. The Merkle root is stored in the header.
Merkle Tree Structure
Transactions are hashed and placed at the leaves. Parents store the hash of their two child hashes.
This continues up to the single Merkle root:
• Root node: Merkle root stored in the block header.
• Leaf nodes: hash of each transaction (a.k.a. transaction IDs).
• Non-leaf nodes: intermediate hashes of their children.
Bitcoin uses SHA-256 based hashing for transactions and the Merkle root. If a block has an odd
number of leaves, the last leaf may be duplicated to form an even pair.
Figure 3: Merkle tree with four transactions: T1..T4 → H1..H4; parents H12, H34; root H1234.
How Do Merkle Trees Work?
Construction is bottom-up: pair nodes, hash the pair, and propagate the result upward until a single
hash remains (the Merkle root).
Example with four transactions T1–T4:
Step 1: H1 = Hash(T1), H2 = Hash(T2), H3 = Hash(T3), H4 = Hash(T4)
Step 2: H12 = Hash(H1 + H2), H34 = Hash(H3 + H4)
Step 3: H1234 = Hash(H12 + H34) → this is the Merkle root.
Key points:
• To detect tampering, it’s enough to remember the Merkle root. Any change in a leaf propagates
upward and changes the root.
• The Merkle root in the block header protects the integrity of all transactions in that block.
Why Merkle Trees are Important For Blockchain
In a distributed ledger, nodes verify transactions without central authority. Merkle trees minimize
memory, CPU, and bandwidth required for verification by allowing small proof objects instead of
sending entire datasets. They enable fast inclusion checks and make tampering evident via root
mismatch.
Proof of Membership
To prove a particular transaction belongs to a block, you provide the transaction and just the hashes
along the path from that leaf to the Merkle root (siblings at each level). Only O(log n) nodes must
be checked, even if the tree contains millions of leaves.
Figure 4: Inclusion proof for T1 needs sibling H2 and the combined hash H34 to recompute the
root.
Merkle Proofs
• Inclusion proof: verify an item is part of the tree by supplying sibling hashes up to the root.
• Non-membership (with sorted Merkle trees): prove absence by showing the neighbors between
which the missing item would have to appear.
Simple Payment Verification (SPV)
SPV clients (lightweight wallets) store only block headers. To verify a payment, they request a
Merkle branch from full nodes. If the branch recomputes to the known header’s Merkle root and
the block is in the most-work valid chain, the client accepts the transaction without downloading
the entire blockchain.
Advantages of Merkle Tree
• Efficient verification with small proofs (O(log n)).
• Reduced bandwidth and storage for clients and nodes.
• Strong tamper detection: any change in underlying data changes the root.
• Enables trustless, lightweight participation (e.g., mobile wallets via SPV).
Time Complexity
Merkle Tree search (membership): O(log n)
Linked List search: O(n)
Summary
A Merkle Tree is a binary hash tree that summarizes all transactions in a block via a single Merkle
root placed in the block header. It enables efficient, bandwidth-light verification (SPV), and any
tampering with transactions is reflected at the root, securing blockchain data integrity.
