From Merkle proofs to Ethereum's state trie

A blockchain stores far more data than can fit inside a block header.

Bitcoin blocks contain transactions. Ethereum also maintains accounts, balances, contract code, contract storage and transaction receipts.

Yet a verifier often needs only one small answer:

Does this exact value belong to the data committed by this block?

A Merkle tree turns a large collection into one root hash. Think of this root as a fingerprint for the whole collection.

A Merkle proof lets someone check one value using only that value and a few nearby hashes.

Ethereum has one more problem. Its world state is not a simple list. It is a key-value map that changes after every block.

Ethereum combines Merkle hashes with a key-based tree and removes long paths that contain no choice. The formal name for this structure is the modified Merkle Patricia Trie, usually shortened to MPT.

The progression to remember is:

Hash → Merkle tree → proof → trusted root → trie → Patricia compression → Merkle Patricia Trie.

Open full size ↗

A cryptographic hash turns any amount of data into one short, fixed-size result. That result is called a hash or digest.

H("transaction A") → 32-byte digestH("transaction B") → different 32-byte digest

A useful hash needs four simple guarantees:

• Same input, same result: hashing the same bytes always gives the same hash. The formal word is deterministic.
• Tiny change, very different result: changing even one bit should produce a completely different-looking hash. This is the avalanche effect.
• Hard to work backward: knowing the hash should not reveal the original input. This is preimage resistance.
• Hard to find a matching pair: it should be practically impossible to find two different inputs with the same hash. This is collision resistance.

A hash is not encryption. It does not hide the input and cannot be decrypted. Its purpose here is to act as a compact fingerprint.

How the bytes are arranged is part of the promise made by the root. These two expressions are different:

H(left || right)H(right || left)

Changing the order changes the bytes, so it also changes the root.

Every implementation must agree on four rules:

1. How is a leaf turned into bytes?
2. How is a parent turned into bytes?
3. Which child goes first?
4. What happens when a level has an odd number of nodes?

Take four values:

A = transaction AB = transaction BC = transaction CD = transaction D

First hash every value into a leaf. This example uses a 0x00 prefix for leaves and a 0x01 prefix for internal nodes so the two kinds of data cannot be confused:

L_A = H(0x00 || A)L_B = H(0x00 || B)L_C = H(0x00 || C)L_D = H(0x00 || D)

Then hash neighbouring leaves:

P_AB = H(0x01 || L_A || L_B)P_CD = H(0x01 || L_C || L_D)

Finally hash the two parents:

ROOT = H(0x01 || P_AB || P_CD)

The root commits to all four values and their order. Changing C, moving C, or changing any internal encoding changes the calculated root.

The root is compact—usually 32 bytes—but calculating it initially still requires processing every leaf. The efficiency appears later when one value must be proved.

What if the number of leaves is odd?

That rule belongs to the tree design. Some trees copy the last hash. Others add a known empty value or use a different shape.

Bitcoin copies the final hash at an odd level. Ethereum consensus SSZ fills empty positions with predefined zero values.

There is no universal “Merkle tree odd-leaf rule.” A verifier must implement the exact same rule as the producer.

Suppose the verifier wants to prove that C is present. Sending the entire tree would work, but it would remove the main benefit.

The verifier already has C. To reconstruct the root, it needs only:

L_D   — the sibling on C's rightP_AB  — the sibling subtree on the left

The proof must also preserve direction. A sibling on the left is not interchangeable with a sibling on the right.

Verification proceeds from the leaf upward:

1. L_C       = H(0x00 || C)2. P_CD      = H(0x01 || L_C || L_D)3. candidate = H(0x01 || P_AB || P_CD)4. accept only when candidate == trusted ROOT

For a balanced tree containing n leaves, the proof normally contains about log₂(n) sibling hashes.

Leaves	Full leaf hashes	Proof sibling hashes
8	8	3
1,024	1,024	10
1,048,576	1,048,576	20

The verifier performs a small amount of hashing without downloading every value.

A small Go verifier

The following code verifies the generic prefixed tree described above. It is not Bitcoin or Ethereum-specific code; those protocols use their own exact hashing and encoding rules.

package merkle import (	"crypto/sha256"	"crypto/subtle") type Step struct {	Sibling       [32]byte	SiblingOnLeft bool} func leafHash(value []byte) [32]byte {	payload := make([]byte, 1+len(value))	payload[0] = 0x00	copy(payload[1:], value)	return sha256.Sum256(payload)} func parentHash(left, right [32]byte) [32]byte {	payload := make([]byte, 65)	payload[0] = 0x01	copy(payload[1:33], left[:])	copy(payload[33:], right[:])	return sha256.Sum256(payload)} func Verify(value []byte, proof []Step, expectedRoot [32]byte) bool {	current := leafHash(value) 	for _, step := range proof {		if step.SiblingOnLeft {			current = parentHash(step.Sibling, current)		} else {			current = parentHash(current, step.Sibling)		}	} 	return subtle.ConstantTimeCompare(current[:], expectedRoot[:]) == 1}

The loop is the essential idea: combine the current hash with one sibling, move up one level, and repeat until the root is reconstructed.

A successful inclusion proof says:

Under these exact encoding and hashing rules, this value occupies this path in the data committed by this root.

It does not prove any of the following by itself:

• that the root came from the chain accepted by consensus;
• that the block containing the root satisfied consensus;
• that the transaction was semantically valid;
• that all underlying data is available;
• that the server returning the proof is generally trustworthy;
• that the same value is present under a different block's root.

The trust chain is therefore:

consensus or another trust mechanism	→ authenticates a block header	→ the header supplies a trusted root	→ the Merkle proof authenticates one value under that root

A perfectly verified proof against an attacker-chosen root proves only consistency with the attacker's root.

Blockchains store these small root fingerprints inside block headers. Once the header is accepted, its roots become the values against which proofs are checked.

Open full size ↗

Bitcoin: committing to transactions

Bitcoin hashes the transactions in a block into a binary Merkle tree and stores the Merkle root in the block header. A lightweight verifier can receive:

• the transaction;
• its position;
• the Merkle branch;
• the block header.

It reconstructs the Merkle root and compares it with the header. It must still decide whether that header belongs to the proof-of-work chain it accepts.

This lets a lightweight client check transaction inclusion without downloading every transaction in the block. Bitcoin calls this simplified payment verification.

A full node still performs all transaction and consensus checks.

Ethereum execution: committing to three different structures

An Ethereum execution payload header contains three roots that are easy to confuse:

Root	Commits to	Question it can help answer
transactionsRoot	ordered signed transactions	Was this transaction included at this index?
receiptsRoot	ordered execution receipts	What status and logs resulted from this transaction?
stateRoot	world state after the block	What was this account or storage value after execution?

All validators re-execute the block and independently calculate these roots. A block is invalid if the calculated result does not match the committed header values.

Ethereum consensus uses another Merkle design

Ethereum's consensus layer uses SSZ. SSZ defines how known data types—such as lists and grouped fields—become bytes and Merkle trees.

Both systems create roots and proofs. They do not build those roots in the same way.

The safe distinction is:

Execution accounts and storage → modified Merkle Patricia TrieConsensus objects             → SSZ Merkleization

A transaction list has a natural order. Ethereum world state has a different shape:

address → accountstorage slot → storage value

The data structure must support:

• looking up a value by key;
• inserting and deleting keys;
• updating only the affected path;
• proving that a key is present;
• proving that a key is absent;
• producing the same root whenever the complete map is the same.

A plain Merkle tree can store key-value data, but it needs extra rules. Where does each key go? How is a missing key proved?

A trie answers both questions because the key itself chooses the path.

The name becomes straightforward when split into three ideas.

Trie: the key chooses the path

A trie is a prefix tree. In Ethereum's execution trie, a byte key is read as nibbles. A nibble is four bits, so it has 16 possible values:

0, 1, 2, ... 9, a, b, c, d, e, f

A 32-byte key becomes 64 nibbles. At each branching point, the next nibble selects one of 16 children.

Patricia: compress the path with no branches

A naive trie can contain long chains in which every node has only one child. Patricia compression replaces that chain with one node carrying the shared path fragment.

Instead of:

6 → 4 → 6 → f → 6 → 7

the trie can store a shared path such as:

extension("646f") → next node

This reduces sparse traversal and storage overhead.

Merkle: hash-address every node

Each node can be checked through the reference stored by its parent. Most references are hashes. Very small nodes can be stored directly inside the parent.

Changing a value changes its leaf. That changes each parent on the path and eventually changes the root.

Together:

An MPT is a key-value tree with shortened paths. One root fingerprint covers every path, value and node.

Open full size ↗

Ethereum's modified trie uses four logical node forms.

1. Empty

An empty reference means there is no node at that path.

2. Branch

A branch has 17 entries:

[child_0, child_1, ... child_f, value]

The first 16 entries correspond to the next nibble. The final entry stores a value when a key ends exactly at that branch.

3. Extension

An extension compresses a shared, non-terminal path:

[encoded_shared_path, next_node]

It says: consume this whole path fragment, then continue at the referenced node.

4. Leaf

A leaf holds the remaining terminal path and its value:

[encoded_remaining_path, value]

Extension and leaf paths must pack nibbles back into bytes. Ethereum calls this hex-prefix compact encoding. A small flag at the front records two facts:

• whether the nibble count is odd or even;
• whether this is a terminating leaf or a non-terminal extension.

The exact bytes matter. There must be only one valid encoding for a path. A verifier cannot treat displayed hexadecimal text as if it were the stored bytes.

How child references work

Trie nodes use Recursive Length Prefix (RLP), Ethereum's execution-layer byte encoding. Ethereum then applies this rule for a child reference:

if len(RLP(node)) < 32:	embed the encoded node directlyelse:	reference Keccak-256(RLP(node))

This is why a verifier cannot blindly hash every supplied node. It must check that the RLP has one valid form and understand when a child is stored directly.

The world-state trie maps an address path to an account. Every step on that path can be checked against the state root.

Conceptually:

Keccak-256(address)	→ [nonce, balance, storageRoot, codeHash]

The account fields mean:

• nonce tracks transactions sent by an externally owned account or contracts created by a contract.
• balance stores the account's wei balance.
• storageRoot commits to that contract's separate storage trie.
• codeHash commits to the contract bytecode.

Contract storage requires a second proof:

stateRoot	→ account proof for contract address	→ account.storageRoot	→ storage proof for slot	→ storage value

The state trie does not place every contract storage slot directly beside the account. Each contract account points to its own storage root.

Ethereum hashes addresses and storage-slot keys before using them as paths. The resulting paths are spread across the trie. A caller cannot easily choose many keys with one long shared prefix and force that exact trie shape.

The transaction and receipt tries use the item's position in the block as the key. They use the same family of trie rules, but their job is different. They cover ordered data from one block rather than the long-lived world state.

Assume the verifier trusts a block's stateRoot and receives an address, encoded account value and a sequence of proof nodes. The conceptual algorithm is:

1. Calculate Keccak-256(address) and split it into nibbles.
2. Begin with the trusted stateRoot as the expected node reference.
3. Read the next RLP-encoded proof node.
4. Check that the node matches the expected hash or embedded reference.
5. Decode the node type.
6. For a branch, consume one nibble and follow that child.
7. For an extension, verify and consume its entire shared path.
8. For a leaf, verify the remaining path and decode the account value.
9. Accept only if the complete key is consumed and every parent-child reference is valid.

The JSON-RPC method eth_getProof returns an accountProof and optional storageProof entries.

The verifier first checks the account against a trusted stateRoot. It then takes the verified storageRoot from that account and checks the requested storage slots.

This two-stage verification is essential. A storage proof checked against an unverified storage root only proves consistency with an untrusted root.

An inclusion proof ends at the requested leaf. An MPT can also prove that a key is missing.

It does this by showing a fully verified path on which the requested key has nowhere to go.

Two common cases are:

1. A verified branch has an empty child at the required next nibble.
2. A verified leaf or extension contains a path fragment that diverges from the requested key.

Every node in that path has already been checked against the trusted root. A different matching leaf cannot be hidden below an empty child or a path that goes in another direction.

requested path: a → 7 → c → ...verified branch: a → child 7 is empty	→ key is absent under this root

The proof only establishes that the key is missing. The execution rules decide what “missing” means. For example, the EVM reads a missing storage slot as zero.

Suppose one contract storage slot changes.

1. A new storage leaf is created or an old one is replaced.
2. Nodes along that storage path receive new references.
3. The contract's storageRoot changes.
4. The encoded account changes because it contains the new storageRoot.
5. Nodes along the world-state account path change.
6. The block's final stateRoot changes.

Unchanged parts keep their existing hashes. Old and new state versions can point to the same unchanged nodes.

The formal name is a persistent data structure: creating a new version does not require copying every unchanged part.

The root therefore acts like a compact version identifier for the whole state.

Structure	Path comes from	Good at	Important limitation
Binary Merkle tree	leaf position	proving inclusion in an ordered collection	absence and key lookup need extra rules
Sparse Merkle tree	fixed key bits	simple inclusion and non-inclusion proofs	large logical depth, usually optimized with default hashes
Merkle Patricia Trie	pieces of the key, with shared paths shortened	changing key-value maps with proofs	more complex encoding and uneven proof sizes
SSZ Merkleization	typed schema and generalized indices	proofs inside Ethereum consensus objects	not Ethereum's execution state trie

No structure is universally best. The choice depends on whether the data is an ordered list, mutable map, sparse keyspace or typed object graph.

Trusting the proof but not the root

The proof is meaningful only when the expected root comes from a block the verifier trusts or another trusted source.

Using the right root from the wrong block

State changes every block. A valid proof under block N may fail under block N + 1, and both results can be correct.

Losing left/right or index information

H(left || right) is not H(right || left). A binary proof needs direction or enough positional information to derive it.

Assuming every protocol builds the same tree

Bitcoin transaction trees, Ethereum execution tries and Ethereum consensus SSZ use different hashing, encoding, padding and path rules.

Confusing Keccak-256 with standardized SHA3-256

Ethereum uses Keccak-256 in its execution layer. The similarly named standardized SHA3-256 has different padding and produces different digests.

Hashing a displayed key instead of the protocol key

Ethereum defines the exact bytes used for state and storage paths. Displayed hex text, integers and raw byte arrays are not interchangeable.

Ignoring RLP and embedded nodes

An Ethereum verifier must check four details: the one valid RLP encoding, shortened paths, node types, and whether a child is stored directly or referenced by hash.

Treating inclusion as execution validity

A transaction proof can establish that bytes were committed in a block. It does not replace signature checks, state-transition execution or consensus validation.

What to remember

The complete mental model fits into eight statements:

1. A root is a compact commitment to a complete data structure.
2. A proof contains the few missing hashes needed to rebuild the path from one value to that root.
3. Verification repeatedly hashes upward and accepts only when the calculated root equals a trusted root.
4. A proof authenticates membership under a root; it does not authenticate the root itself.
5. Blockchains place roots in headers so large bodies of data can be checked through small proofs.
6. A trie makes the key determine the path; Patricia compression removes one-child chains.
7. Ethereum's modified MPT authenticates execution accounts, contract storage, transactions and receipts.
8. Ethereum consensus uses SSZ Merkleization, which is related but different.

The shortest useful sentence is:

The root commits, the proof reconstructs, and consensus tells the verifier which root to trust.

References

• Ethereum: Merkle Patricia Trie
• Ethereum execution block roots
• EIP-1186: eth_getProof
• Ethereum: Simple Serialize and Merkleization
• Bitcoin developer guide: block chain and Merkle trees