Merkle Trees & Merkle Proofs in Blockchain

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.

1. 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