Lesson 7 — Merkle Patricia Trie & state proofs

Question

MPT = Ethereum's state structure. Modified Patricia Trie + Merkle hash → verifiable state. Generate + verify state proofs.

Principle (minimum model)

• Trie structure. Branches + extensions + leaves. Hash up via keccak; root in block header.
• State proof = path from root to leaf. Includes hashes of sibling nodes; allows verification without full state.
• AccountProof type. Account info + storage proof + balance + nonce + code hash. Lets a light client verify "this account has this balance".
• Use cases. Light clients (Helios), zkEVM verification, cross-chain proofs (Cosmos IBC pattern).
• Performance. Generation: ~10 ms per account. Verification: ~5 ms.
• Stateless verification. Future direction. Have ProverChain produce trie proofs + execution proof; consumer chain verifies without state.
• Reth's impl. reth-mpt crate; uses MDBX for trie storage. Production-tuned.

Worked example + steps

Merkle Patricia Trie & state proofs

A phone-sized device wants to know "does Alice's account hold 1 ETH?" — and it cannot store Ethereum's 500GB state. So it asks a full node, which sends back a few hundred bytes. The phone runs a hash loop, compares the result to 32 trusted bytes it already knows, and gets a cryptographic answer: yes or no. That's a light client. The 32 trusted bytes are Ethereum's stateRoot, and the data structure that makes this work is the Merkle Patricia Trie (MPT).

Understand the MPT and you understand state roots, light clients, witnesses, eth_getProof, and the entire stateless-client roadmap. You can also write your own.

1. What an MPT is

Combine three ideas:

• Trie: tree where the path from root to leaf spells the key
• Patricia: collapse single-child paths so the trie stays compact
• Merkle: each node hashes its children, so the root commits to all data

Result: a 256-bit stateRoot that uniquely identifies the entire world state. Change any byte → root changes.

2. Node types

+----------+    Branch (16 children + value)
|  Branch  |    used at points where keys diverge
+----------+

+----------+    Extension (shared prefix)
| Extension|    "the next N nibbles are the same for everyone below"
+----------+

+----------+    Leaf (final value)
|   Leaf   |
+----------+

Keys are nibbles (4 bits each), so a 32-byte key is 64 nibbles. Every node knows its keccak hash.

graph TD
    R[Branch — root<br/>16 child slots]
    R -->|nibble| E[Extension<br/>shared prefix]
    R -->|nibble| L1[Leaf<br/>account → value]
    E --> B[Branch]
    B -->|nibble| L2[Leaf<br/>account → value]
    B -->|nibble| L3[Leaf<br/>account → value]

Each parent stores the hash of each child, so the root hash commits to every byte underneath. Change one storage slot anywhere → every parent up to the root rehashes → stateRoot changes.

3. Inclusion proof in 6 steps

To prove "account X has balance Y":

1. Walk from root toward X's key, collecting nodes along the path
2. Each node references its children by hash, not pointer
3. The verifier needs only the path nodes, not the whole trie
4. Re-hash the leaf, walk back up rehashing each parent
5. Compare the resulting root to the trusted stateRoot
6. If equal → X really has balance Y

That's it. Light clients are just verifiers with the trusted root.

4. Witnesses

A witness is the bundle of trie nodes you need to re-execute a block without holding the whole state. Instead of "give me the 500GB DB," you ask "give me only the parts this block touched." zkEVM provers consume witnesses (they cannot read disk inside a zkVM). Stateless clients use them (so they can verify without syncing). Some MEV searchers use them for forked simulation.

A typical block's witness is a few hundred KB to a few MB.

5. Reth's actual proof types

From crates/trie/common/src/proofs.rs:

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct AccountProof {
    pub address: Address,
    pub info: Option<Account>,
    pub proof: Vec<Bytes>,
    pub storage_root: B256,
    pub storage_proofs: Vec<StorageProof>,
}

impl AccountProof {
    pub const fn new(address: Address) -> Self;
    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError>;
}

#[derive(Clone, PartialEq, Eq, Default, Debug)]
pub struct StorageProof {
    pub key: B256,
    pub nibbles: Nibbles,
    pub value: U256,
    pub proof: Vec<Bytes>,
}

impl StorageProof {
    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError>;
}

This is exactly what flows over JSON-RPC for eth_getProof. Read it field by field:

AccountProof.proof: Vec<Bytes>

The list of trie nodes from root to the account's leaf — encoded as RLP. The verifier walks them in order, hashing each, comparing the result to the parent's child reference, and finally checking the root.

AccountProof.storage_root: B256

The root of the contract's separate storage trie. As predicted: a two-layer MPT. The account leaf contains this hash; the storage proofs verify against it, not the global stateRoot.

AccountProof.info: Option<Account>

None if the account doesn't exist (a "non-inclusion" proof). Some if it does. Both cases are valid proofs — proving "this address has no account" is just as important as proving balance.

StorageProof.nibbles: Nibbles

Pre-computed nibble representation of the storage key. Reth caches this because nibble conversion is on the hot path.

AccountProof::verify(&self, root: B256)

Pure logic — given a trusted state root, verify the proof. This is the entire light-client check. A few hundred bytes of bytecode, runs in milliseconds, gives you a cryptographic guarantee about state.

6. The pitfall: storage tries

Each contract has its own MPT for its storage slots. So the global state has:

stateRoot
└── account leaf (returned by AccountProof.proof)
    └── storage_root (also stored in AccountProof.info.storage_root)
        └── slot leaves (proven by StorageProof.proof)

A two-layer MPT is exactly what AccountProof encodes. Forgetting this is the #1 reason "my state proof verifier doesn't work."

7. Where to look in Reth

crates/trie/
├── common/src/proofs.rs  ← AccountProof, StorageProof (above)
├── trie/                  ← the trie data structure itself
├── parallel/              ← parallel trie computation
├── sparse/                ← sparse trie for witness/proof generation
└── db/                    ← MDBX-backed trie

Read in this order: common (types) → trie (data structure) → db (production glue).

8. Drill

1. Open crates/trie/common/src/proofs.rs in the repo
2. Find the verify method on AccountProof — read it
3. Notice it calls StorageProof::verify for each storage proof in storage_proofs, with storage_root (not root) as the parent
4. Now read EIP-1186 — AccountProof is the Rust mirror of the spec

Do this and eth_getProof becomes a structure you can reason about, write, and debug — not magic.

Final check: in two sentences, explain why a state proof gives a stronger guarantee than "trust me, I'm a node operator." What property does Merkle hashing give you that a non-cryptographic claim cannot? The lesson isn't done with you until you can argue this convincingly to someone who has never used a light client.

Summary (3 lines)

• MPT = branch + extension + leaf, keccak-hashed up to root in block header. State proof = path from root to leaf.
• AccountProof type lets light clients verify balances. Gen ~10 ms; verify ~5 ms.
• Use cases: light clients, zkEVM, cross-chain. Reth: reth-mpt crate, MDBX-backed. Stateless verification is the future direction.