1. Node Types in Hexary Tries
To avoid storing sparse chains of 16-element arrays, the trie incorporates Extension Nodes (compacting shared nibble sequences) and Leaf Nodes (terminating with the remainder key and payload value).
IntermediateTier 3⏱ 7 min read
Merkle Patricia Tries & Ethereum State Storage
Radix tree indexing combined with cryptographic Merkle proofs for dynamic world-state
Executive Takeaway (TL;DR)
Ethereum uses modified Hexary Merkle Patricia Tries to store account balances, contract storage slots, and code hashes with deterministic O(log N) updates and non-membership proofs.
- Modified Merkle Patricia Trie
- A deterministic 16-radix trie structure that compresses redundant prefix paths into extension and leaf nodes while anchoring every node with a cryptographic Keccak-256 hash.
Constituent Invariants:
- ✓Determinism: Independent of insertion order, identical key-value sets yield the identical root hash.
- ✓Hexary Nibble Paths: Keys are traversed 4 bits (1 nibble / 1 hex character) per step.
Interactive Cryptographic Primitive
Select a leaf to trace inclusion proof branchBinary Merkle Tree Verification (O(log N))
Merkle Root (Header Commitment)
0x5f81c9a4…43de2b10Node H(0,1)
0xb72a…338fNode H(2,3)
0x44d1…99feActive Sibling Proof Path: Sibling:
0x3e4d…99a1 + Intermediate Node 0x44d1…99fe → Merkle Root Verified in 2 operations.Invariant CheckpointVerify Mathematical Invariant
Why are keys hashed with Keccak-256 before insertion into the Ethereum State Trie?