Skip to content
Ethereum · First Principles

The Four Tries — State, Storage, Transactions, Receipts

The last three pages built one machine and taught it well: a Merkle-Patricia trie, its three node types — leaf, extension, branch — and the RLP and nibble encodings that make its bytes canonical. So far we have used that machine to hold exactly one thing: the set of accounts.

But a running Ethereum node does not commit one trie. It commits four, and they are nested: the account trie’s leaves point into other tries. This page is where the pieces snap together. By the end you will be able to trace, from the block header down, exactly where every byte of Ethereum’s committed state lives — and why the header carries three separate roots instead of one.

The throughline of this whole book is how untrusting strangers agree on the state of a shared world computer. The four tries are the concrete answer to “what, precisely, do they agree on?” Not a fuzzy notion of “the state” — four hashes, each the root of a trie, three of them stamped into every block header.

Why four, not one

Section titled “Why four, not one”

You might expect a single “state trie” to hold everything. It does not, and the reason is that Ethereum commits to two very different kinds of data, on two different cadences:

  • State that persists across blocks — account balances, nonces, contract code, contract storage. This is the world, and it carries forward from block to block, mutated in place.
  • Data that is born and frozen inside one block — the ordered list of transactions in this block, and the receipt (the outcome) of each one. These do not “persist” — they belong to their block forever and are never mutated.

Mixing those in one trie would be a category error. So Ethereum keeps:

   ┌──────────────────────── block header ────────────────────────┐
   │  parentHash   ...                                             │
   │  stateRoot         ──►  State (account) trie   [persistent]   │
   │  transactionsRoot  ──►  Transactions trie      [this block]   │
   │  receiptsRoot      ──►  Receipts trie          [this block]   │
   │  ...                                                          │
   └──────────────────────────────────────────────────────────────┘


   State trie leaf (one per account)
        │
        │  a contract account's storageRoot ...
        ▼
   Storage trie   [persistent, one per contract]

That is four tries: state, storage (one per contract, nested under state), transactions, and receipts. Three roots live in the header; the storage roots live one level down, inside the account leaves. Let us take them one at a time.

The state (account) trie

Section titled “The state (account) trie”

The state trie is the big one — the “world” in “world computer”. It is a single Merkle-Patricia trie whose entries are every account that has ever been touched.

  • Key: keccak256(address). Not the 20-byte address itself — its 32-byte Keccak hash. (Why we hash the key is the last section; hold that thought.)
  • Value: the RLP encoding of the account’s four-field record:
   account = RLP([ nonce, balance, storageRoot, codeHash ])

Each field earns its place, and this is exactly the Account record the companion ethmini crate models — nonce, balance, storage, code:

// rust/ethmini/src/account.rs — the value half of the world-state map
pub struct Account {
    pub nonce: u64,           // replay protection; per-account tx counter
    pub balance: u128,        // native currency (real ETH: 256-bit wei)
    pub storage: BTreeMap<u64, u64>, // the contract's persistent memory
    pub code: Vec<u8>,        // contract bytecode; empty ⇒ a plain wallet
}

Real Ethereum does not inline the storage map or the code into the account leaf. It cannot — an account’s storage can be gigabytes, and its code can be 24 KB. Instead the leaf holds two 32-byte hashes that commit to them:

  • storageRoot — the root hash of this account’s own storage trie (below). For an externally-owned account (a wallet with no code), this is the root of an empty trie: the well-known constant keccak256(RLP("")).
  • codeHash — keccak256(code). The bytecode itself lives in the node’s database, keyed by this hash; the leaf just points at it. For a wallet, this is keccak256(""), the hash of empty code.

So an account leaf is a fixed, small four-field record, and the two heavy things it owns — storage and code — hang off it by hash. The ethmini crate collapses this into one flat state_root over the whole sorted map, and its own source is candid about the simplification:

// rust/ethmini/src/state.rs — the honest simplification
// "Real Ethereum stores state in a Merkle-Patricia trie ... plus efficient
//  proofs and incremental updates. This flat sort-and-hash is the honest
//  simplification we explain in Day 22."

The real trie buys three things the flat hash cannot: sub-linear proofs (see Merkle Proofs and Light Clients), incremental updates (change one account, re-hash only the path to it, not the whole world), and — via the nested storage roots — the ability to prove one storage slot of one contract without shipping the contract’s whole storage.

Nested storage tries

Section titled “Nested storage tries”

Here is the move that makes Ethereum a world computer and not just a ledger: each contract account has its own trie.

The storageRoot in a contract’s account leaf is the root of a second Merkle-Patricia trie — structurally identical to the state trie, but holding this one contract’s persistent key/value memory.

  • Key: keccak256(slot), where slot is the 256-bit storage slot number.
  • Value: the RLP encoding of the 256-bit word stored at that slot (with leading zero bytes trimmed, so slot value 0 is simply absent from the trie).
   State trie
     └─ leaf for address A ──► RLP([nonce, balance, storageRoot_A, codeHash_A])
                                                   │
                                                   ▼
                                       Storage trie for contract A
                                          ├─ keccak256(slot 0) ──► value
                                          ├─ keccak256(slot 1) ──► value
                                          └─ keccak256(slot k) ──► value

The nesting is what gives the commitment its power. Change slot 7 of contract A, and:

  1. its storage trie re-hashes along the one path to keccak256(7), producing a new storageRoot_A;
  2. that new root changes A’s account leaf, so the state trie re-hashes along the one path to keccak256(A), producing a new stateRoot.

A single storage write ripples up exactly two trie paths — a few dozen hashes total — and lands as a new stateRoot. Nothing else in the world is re-touched. This is why the tries must be tries and not flat hashes: incremental, localized re-hashing is the entire performance story of an executing chain.

The transactions trie and the receipts trie

Section titled “The transactions trie and the receipts trie”

The other two tries are the “born in one block” kind. They are built fresh for each block, committed, and never mutated.

Both are keyed the same, and it is a curious key: RLP(index) — the RLP encoding of the transaction’s position in the block (0, 1, 2, …), not a hash.

  • Transactions trie. Value at key RLP(i) is the RLP encoding of the i-th transaction. Its root is transactionsRoot. This commits the block’s exact, ordered list of transactions: change one transaction, or reorder any two, and the root changes. Ordering is not incidental here — a blockchain’s whole job is to agree on order, and this trie is where that order is cryptographically pinned.
  • Receipts trie. Value at key RLP(i) is the RLP-encoded receipt of the i-th transaction — its outcome. Its root is receiptsRoot.

A receipt is the record of what executing a transaction did, and ethmini models it directly:

// rust/ethmini/src/state.rs — one transaction's outcome
pub struct Receipt {
    pub status: ExecStatus,        // Success or Reverted (both are *included*)
    pub gas_used: u64,             // what the execution actually cost
    pub return_value: Option<u64>, // a RETURN word, if any
    pub created: Option<Address>,  // the new address, for a deploy
}

Real Ethereum receipts carry a little more — notably the cumulative gas used and the logs (events) the transaction emitted, plus a bloom filter over those logs so a light client can cheaply ask “did any transaction in this block emit an event matching X?” without downloading them all. But the shape is the same: a receipt is the result of a transaction, and the receipts trie commits every result in order.

Why keep transactions and receipts as tries at all, rather than a plain list? For the same reason as the state trie: provability. Because they are Merkle-Patricia tries with committed roots, a light client can be handed a proof that “transaction #5 was included in this block” or “transaction #5 succeeded and emitted this event” — a short path from the leaf up to a header field it already trusts — without downloading the whole block. That is the payoff we cash in on the Merkle Proofs and Light Clients page.

Under the hood — where the four roots live

Section titled “Under the hood — where the four roots live”

The three block-scoped roots are literal fields in the block header. The header is a small RLP-encoded record; among its fields:

   BlockHeader (partial):
     parentHash        keccak256 of the parent header — the "chain" in blockchain
     stateRoot         root of the state (account) trie   AFTER this block executed
     transactionsRoot  root of this block's transactions trie
     receiptsRoot      root of this block's receipts trie
     ...               (number, gasLimit, gasUsed, timestamp, ...)

Two things are worth pinning down:

  • stateRoot is the post-state root — the world as it stands after every transaction in the block has been applied, in order. This is the hinge that ties execution to consensus: consensus agrees on an ordered list of transactions; every honest node re-executes them and must arrive at the same stateRoot. If your node computes a different stateRoot than the one in the header, you reject the block. The header’s stateRoot is a checksum on the correctness of the entire world’s computation.
  • The fourth root — a contract’s storageRoot — is not in the header. It lives one level down, inside each contract’s account leaf in the state trie. So the header commits to it transitively: stateRoot commits to every account leaf, and each contract leaf commits to its storageRoot, which commits to every storage slot. One 32-byte number in the header transitively fingerprints every balance, nonce, byte of code, and storage slot in existence.

The parent’s header hash is itself keccak256 of the parent header — so each header chains to the last, and the whole design bottoms out in the one primitive: hash.

Why the keys are hashed — the “secure trie”

Section titled “Why the keys are hashed — the “secure trie””

Twice now we have said the key is keccak256(address) and keccak256(slot), not the raw address or slot. A trie keyed by hashed keys is called a secure trie, and the reason is a first-principles one about who controls the shape of the tree.

A trie’s depth along any path is determined by how many leading nibbles its keys share. Raw Ethereum addresses are not random — an attacker can grind a vanity address, or deploy many contracts, to manufacture addresses that share a long common prefix. If keys were raw addresses, an adversary could deliberately craft thousands of accounts whose keys all share a 30-nibble prefix, forcing a single long, skinny chain of extension nodes 30 levels deep. Every lookup or proof touching that region would then be O(30) instead of O(a few) — a self-inflicted denial-of-service baked into the data structure.

Hashing the key defuses this completely:

   raw keys (attacker-chosen):        keccak256(key) (uniform):
     0xdead...01                        0x9f3c...   ─┐
     0xdead...02                        0x2a71...    │  hashes land
     0xdead...03      long shared       0xbe08...    │  all over the
     0xdead...04      prefix → deep      0x4d5a...   │  keyspace →
     0xdead...05      skinny trie        0xf102...  ─┘  balanced trie

keccak256 is a good hash: its outputs are, for all practical purposes, uniformly distributed and infeasible to steer. Feeding hashed keys into the trie spreads every entry evenly across the 64-nibble keyspace, so the trie stays shallow and roughly balanced no matter what keys the adversary chooses. The attacker cannot pick where their account lands in the tree, because they cannot invert the hash. Depth is bounded by the hash width (64 nibbles), and in practice trees are far shallower than that.

The cost is real but modest: you can no longer walk the trie in address order, and every access pays one Keccak hash to compute the path. Ethereum judged that a cheap, bounded, attack-resistant depth is worth losing in-order iteration — a trade the Why a Trie, Not a Plain Merkle Tree page frames from the other direction.

The architect’s lens

Section titled “The architect’s lens”
  • Why does it exist? Because a world computer must commit two different kinds of data — a persistent world (accounts, storage, code) and per-block records (transactions, receipts) — and let strangers verify each cheaply and independently. Four purpose-built tries, three of their roots in the header, is that commitment.
  • What problem does it solve? It lets any node collapse the entire state of the chain into a handful of 32-byte roots that another node can compare in one instruction, and it lets a light client prove one fact — one balance, one storage slot, one transaction’s inclusion — with a short path instead of the whole dataset.
  • What are the trade-offs? Nesting storage tries under the state trie means a storage write ripples up two trie paths, and secure-trie hashing costs one Keccak per key and forfeits in-order iteration — accepted in exchange for bounded depth, incremental updates, and adversary-resistance.
  • When should I avoid it? When you do not need independent, adversarial verification. A single trusted database with one flat checksum (what ethmini does) is simpler and faster; the four-trie machinery only pays off when untrusting parties must prove things to each other.
  • What breaks if I remove it? Collapse the four into one and you lose per-block provability and incremental hashing. Drop the secure-trie hashing and an attacker grinds keys to force a deep, skinny trie and slow every proof. Drop stateRoot from the header and execution is no longer pinned to consensus — nodes could silently disagree on the world and never know.

Check your understanding

Section titled “Check your understanding”
  1. Ethereum commits to four tries but only three roots live in the block header. Name the three header roots, and explain where the fourth trie’s root is committed instead.
  2. An account leaf in the state trie is a small four-field record even though the account may own gigabytes of storage and 24 KB of code. How does the leaf commit to that heavy data without inlining it?
  3. Trace what happens to the roots when a single SSTORE changes one storage slot of one contract. Which roots change, and roughly how much work is it compared to re-hashing the whole world?
  4. The transactions trie and the state trie are both Merkle-Patricia tries, but their keys are chosen very differently. What is each keyed by, and why does that difference make sense given what each trie commits to?
  5. Why does Ethereum key the state and storage tries by keccak256(key) rather than the raw address or slot? What specific attack does this “secure trie” design prevent, and what does it cost?
Show answers
  1. The header carries stateRoot, transactionsRoot, and receiptsRoot. The fourth trie is each contract’s storage trie; its root (storageRoot) is not in the header — it lives inside that contract’s account leaf in the state trie, so the header commits to it transitively (header → stateRoot → account leaf → storageRoot → every slot).
  2. The leaf is RLP([nonce, balance, storageRoot, codeHash]). It holds two 32-byte hashes — storageRoot (the root of the account’s own storage trie) and codeHash (keccak256(code)) — rather than the storage or code themselves. The heavy data hangs off the leaf by hash and is looked up in the node’s database by that hash.
  3. The contract’s storage trie re-hashes along the one path to keccak256(slot), giving a new storageRoot; that changes the contract’s account leaf, so the state trie re-hashes along the one path to keccak256(address), giving a new stateRoot. Only those two paths (on the order of a couple dozen hashes) are touched — versus O(number of accounts) for a flat sort-and-hash of the whole world.
  4. The state trie is keyed by keccak256(address) — accounts are addressed by identity and looked up randomly, so a hashed, uniformly-spread key is right. The transactions trie is keyed by RLP(index) — transactions have an intrinsic, meaningful order within the block, and keying by position is exactly what pins that ordering into the root.
  5. Raw addresses/slots are attacker-choosable (vanity grinding, mass contract creation), so an adversary could craft keys sharing a long prefix and force a deep, skinny trie that makes every lookup and proof in that region slow — a self-inflicted DoS. Hashing the key with keccak256 spreads entries uniformly and unpredictably (the attacker cannot invert the hash to choose placement), bounding depth. The cost is one Keccak per key access and the loss of in-order iteration.