Merkle tree

Merkle tree is a data structure invented by Ralph Merkle in 1979. Leaves are hashes of data blocks; each internal node hashes its children. The single root hash at the top compactly represents the whole dataset.

Why it matters

The crucial property: membership of an element can be proven without showing the entire tree. A Merkle proof is the path from leaf to root — O(log N) hashes instead of O(N) data.

That is essential for blockchains:

• A lite client on a phone does not store the full TON chain but wants to verify that its transaction is in a block. The server returns a Merkle proof — a handful of hashes. The client recomputes the root and compares it to a known-good block root. If they match, the transaction is definitely in the block.
• Cross-chain bridges verify state from one chain on another by reasoning only over root hashes.

In TON

TON uses Merkle structures in several places:

• State. The entire chain state is organised as one giant tree of hashed cells. The state root is part of the block hash.
• Pruned cells. A cell whose children are replaced by their hashes is a pruned branch. Lite servers use this to return Merkle proofs: load-bearing data is present, the rest is pruned.
• Merkle update / Merkle proof cells. Specialised TVM cell types for embedding proofs into transactions.

Worked example

Given transactions T1, T2, T3, T4:

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

Each Hx is hash of the transaction, H12 = hash(H1 ‖ H2), Root = hash(H12 ‖ H34).

To prove T1 is included, send H2, H34, and T1 itself. The verifier recomputes: H1’ = hash(T1), H12’ = hash(H1’ ‖ H2), Root’ = hash(H12’ ‖ H34). If Root’ equals the known Root, the proof is valid.

Practical implications

Merkle trees are the backbone of every “compact proof” mechanism in crypto: Bitcoin SPV clients, ZK-rollups, cross-chain bridges, Cosmos IBC. In TON specifically they power the lite protocol that Tonkeeper, Tonscan, Tonviewer, and any non-full client rely on.