Skip to content
Solana · First Principles

State Compression and Merkle Accounts

The previous page, Firedancer and Client Diversity, attacked one ceiling on the throughput bet: the client software that has to keep up with the hardware. This page attacks a different ceiling — one that has nothing to do with how fast you can process transactions and everything to do with how much state the machine can afford to hold.

The whole book asks: how do you build a single global state machine that runs at hardware speed without falling apart? Speed is only half the problem. A state machine is also state, and on Solana that state lives in validator RAM. RAM is finite and expensive. So the moment you want to put millions of little things on-chain — one NFT per person, one record per event — the account model you learned to love starts to look like a bill you can’t pay. State compression is Solana’s answer: keep the proof of the state on-chain, and push the bulk of it into the cheap ledger and off-chain indexers. This page builds that idea from the account up.

The problem: full accounts don’t scale to millions

Section titled “The problem: full accounts don’t scale to millions”

Recall the account model from the Account Model day: every piece of on-chain state is an Account — a balance, a data buffer, and an owner — and every account lives in the validators’ in-memory account database so the runtime can read and write it at hardware speed. That speed is the whole point of Solana, and it has a direct cost: every account you create consumes validator RAM, and to keep it there you must pay rent (a minimum balance that makes the account rent-exempt).

For a wallet or a program that is fine. For millions of near-identical items it is ruinous. Suppose you want to airdrop a collectible NFT to a million people. In the naive design each NFT is its own set of accounts (a mint account, a token account, metadata). Multiply the rent-exempt minimum by a million and you are funding a large, permanent slice of every validator’s memory forever — for data that is mostly cold and rarely touched.

   A MILLION NFTs, the naive way
   ─────────────────────────────
   NFT #1  → [mint acct][token acct][metadata acct]   ← rent, RAM
   NFT #2  → [mint acct][token acct][metadata acct]   ← rent, RAM
   ...
   NFT #1e6→ [mint acct][token acct][metadata acct]   ← rent, RAM
                                                        ────────────
                          a permanent, per-validator memory bill

This is the cost-of-state problem. The account model made state fast (named, external, in RAM) and parallelizable (footprints declared up front). But “fast, in-RAM state” and “millions of items” pull in opposite directions. State compression is the attempt to have both — for the class of state that is high-volume and mostly cold.

The core idea: store one root, not a million accounts

Section titled “The core idea: store one root, not a million accounts”

Here is the move. Instead of a million accounts, you keep one account on-chain. That account holds a single 32-byte Merkle root. Every logical item — every NFT — is a leaf whose hash is folded, along with its siblings, up a tree into that one root.

A Merkle tree is a hash of hashes. You hash each leaf, then hash pairs of hashes, then pairs of those, until a single hash remains at the top. That top hash — the root — is a fingerprint of the entire set: change any one leaf and the root changes.

                       root                 ← the ONLY thing on-chain
                      /    \
                   h(01)    h(23)
                  /   \     /   \
                h0    h1   h2    h3         ← hashes of leaves
                |     |    |     |
              leaf0 leaf1 leaf2 leaf3       ← the actual item data (NFTs, records)
                                              lives OFF the account — in the ledger
                                              and in indexers

The account stores root and a little bookkeeping (tree height, how full it is). The leaf data itself — the NFT’s owner, its metadata URI — is not in that account. It was emitted when the item was created and it lives in the ledger (Solana’s append-only transaction log, which is far cheaper per byte than live account RAM) and is reconstructed by off-chain indexers. On-chain you keep only the fingerprint that lets anyone prove what the data was.

That is the trade in one sentence: you replaced a million rent-paying accounts with one account holding a 32-byte hash, and moved the actual bytes to cheaper storage.

Reading and updating with a Merkle proof

Section titled “Reading and updating with a Merkle proof”

If the data isn’t on-chain, how does a program change it — say, transfer NFT #7 to a new owner?

The caller supplies the leaf’s current data and a Merkle proof: the sibling hashes along the path from that leaf up to the root. The program re-hashes the leaf, combines it with each supplied sibling in turn, and checks that it arrives at the root currently stored on-chain. If it matches, the caller has proven that this leaf really is in the tree — without the program ever storing the leaf. The program then computes the new leaf hash (new owner), recomputes the path, and writes the new root back into the account.

// The verification a compression program does on-chain (conceptually).
// `leaf` = hash of the item's current data; `proof` = sibling hashes bottom→top;
// `index` tells us whether we are the left or right child at each level.
fn recompute_root(mut node: Hash, leaf_index: u32, proof: &[Hash]) -> Hash {
    let mut idx = leaf_index;
    for sibling in proof {
        node = if idx & 1 == 0 {
            hash_pair(&node, sibling)   // we are the LEFT child
        } else {
            hash_pair(sibling, &node)   // we are the RIGHT child
        };
        idx >>= 1;
    }
    node // must equal the root stored on-chain
}


fn update(account_root: &mut Hash, old_leaf: Hash, new_leaf: Hash,
          leaf_index: u32, proof: &[Hash]) -> Result<(), &'static str> {
    if recompute_root(old_leaf, leaf_index, proof) != *account_root {
        return Err("proof does not match current root"); // caller lied about the leaf or the path
    }
    *account_root = recompute_root(new_leaf, leaf_index, proof); // same siblings, new leaf
    Ok(())
}

The on-chain cost of an update is tiny and constant in the number of items: you verify a proof whose length is the tree’s height (roughly log2(capacity) hashes) and store one new 32-byte root. A tree of a billion leaves is only ~30 levels deep — thirty hashes to prove membership, no matter how full it is. The account never grows; only the root’s value changes.

hash_pair here is just the two-input version of the sha256 primitive the companion crate builds Proof of History on in solmini — the same hash function, composed into a tree instead of a chain.

Why “concurrent”: surviving Sealevel’s parallel writes

Section titled “Why “concurrent”: surviving Sealevel’s parallel writes”

There is a subtlety that connects straight back to Parallel Execution. A Merkle proof is computed against a specific root. But Solana processes many transactions per slot, and several of them might want to update the same tree in the same slot. The first update lands and changes the root. Now every other transaction in flight is holding a proof against the old root — which no longer matches. Naively, all but the first update fail, and you have re-created the hot-account bottleneck: one writable account (the tree) serializing everyone.

Solana’s fix is the concurrent Merkle tree. Alongside the current root, the account keeps a small changelog — a buffer of the last N roots and the paths that produced them. When an update arrives with a proof against a slightly stale root, the program uses the changelog to fast-forward the proof: it checks the proof was valid against a recent root and replays the intervening changes to see whether they touched this leaf’s path. If they didn’t conflict, the update is accepted against the current root. The buffer size N is the number of concurrent changes the tree tolerates within the window before a proof is too stale to rescue.

   Without a changelog          With a concurrent Merkle tree (buffer of last N roots)
   ───────────────────          ────────────────────────────────────────────────────
   tx A: proof vs root_0  ✓     tx A: proof vs root_0  ✓  → root_1
   tx B: proof vs root_0  ✗     tx B: proof vs root_0  →  fast-forwarded to root_1  ✓ → root_2
        (root already moved)         (changelog shows A's change missed B's path)

This is the same lesson as Sealevel, one layer up: contention on a single writable account is the enemy of throughput, so you engineer the data structure to tolerate concurrent, non-conflicting changes instead of forcing everyone into a serial line. A concurrent Merkle tree is a hot account designed to stay warm rather than melt.

The trade-off: you moved the cost, you didn’t delete it

Section titled “The trade-off: you moved the cost, you didn’t delete it”

Compression is not free decentralization. It is a relocation of cost, and the thing you relocated is data availability. With a full account, the data is right there on-chain: any validator has it, any RPC can serve it, and you need nothing extra to read or update it. With a compressed account, the on-chain state is only the root — a fingerprint that can verify data but cannot produce it.

So to actually use a compressed item you need two things that live off the ledger’s hot path:

  1. The leaf data — the item’s current contents. To transfer a cNFT you must first know its current owner and metadata, which means fetching it from an indexer that has been watching the ledger and reconstructing state.
  2. The Merkle proof — the sibling hashes for that leaf. Only an indexer that has replayed every update to the tree can hand you a current proof.
   Full account                         Compressed account
   ────────────                         ──────────────────
   [ data ] ──on-chain──► read/write    [ root ] ──on-chain──► verify only
                                              │
   self-sufficient                            ▼
                                        indexer / RPC (off-chain) must supply
                                        leaf data + current proof to do ANYTHING

The data is still recoverable — it was all emitted into the public ledger, so in principle anyone who replays history can rebuild it. But “in principle, by replaying the whole chain” is a very different service level from “read it from the account.” In practice you depend on an RPC provider running a Digital Asset Standard (DAS) indexer to serve leaves and proofs quickly. That is a real centralization-of-convenience pressure: if the indexers you rely on go down, your compressed assets become expensive to touch until someone reconstructs the tree from the ledger.

This is the honest shape of every compression scheme, and it sets up the next page: compression buys cheaper state by exporting a data-availability and indexing burden. Whether that trade is worth it depends entirely on how much you value the raw per-item saving versus the operational dependency you took on.

The architect’s lens

Section titled “The architect’s lens”
  • Why does it exist? Because the account model puts state in validator RAM, which is fast but scarce and rent-charged; storing millions of cold items as full accounts is prohibitively expensive. Compression exists to make high-volume, low-touch state economically viable.
  • What problem does it solve? The cost-of-state problem: it collapses N rent-paying accounts into one account holding a Merkle root, moving the bulk data to the cheaper ledger and off-chain indexers while keeping an on-chain proof of integrity.
  • What are the trade-offs? You trade cheap, self-sufficient on-chain data for a data-availability and indexing burden: reads and updates now require an RPC/DAS indexer to supply the leaf and its Merkle proof. Cheaper state, more operational dependency.
  • When should I avoid it? When items are few, hot, or need rich on-chain composability — a DeFi position other programs must read and mutate constantly is a poor fit. Full accounts are simpler and self-contained; use them until the per-item state cost actually hurts.
  • What breaks if I remove it? Million-item use cases (mass cNFT drops, large record sets) become unaffordable again. And if you remove the indexers that compression relies on, the state is still provable but no longer conveniently available — you can verify a leaf you already have, but you can’t cheaply discover or transfer one until someone rebuilds the tree from the ledger.

Check your understanding

Section titled “Check your understanding”
  1. Why does storing a million NFTs as full accounts create a cost that a million ledger entries does not? Name the specific resource the account model consumes.
  2. A compressed account stores only a 32-byte root. If the leaf data isn’t on-chain, how does a program verify and then update a specific leaf without ever storing it?
  3. What is the length of a Merkle proof for a tree of a billion leaves, roughly, and why is the on-chain update cost therefore “constant in the number of items”?
  4. What problem do concurrent Merkle trees solve that a plain Merkle account would hit, and how does this connect to the Sealevel hot-account lesson?
  5. State the central trade-off of state compression precisely. What exactly did you gain, what did you give up, and on whom do you now depend?
Show answers
  1. Every full account consumes validator RAM (the live, in-memory account database) and must hold a rent-exempt minimum balance to stay there — so a million accounts is a permanent, per-validator memory and rent bill. Ledger entries are append-only log data, far cheaper per byte and not held in the hot account database, so a million of them is affordable.
  2. The caller supplies the leaf’s current data and a Merkle proof (the sibling hashes from leaf to root). The program re-hashes the leaf and folds in each sibling to recompute the root; if it equals the on-chain root, membership is proven. To update, it recomputes the root with the new leaf hash along the same path and stores that new root — never storing the leaf itself.
  3. About 30 hashes (log2 of a billion ≈ 30). Proof length grows only with tree height, which is logarithmic in capacity, so verifying a proof and writing one new root costs the same whether the tree holds a thousand or a billion leaves — the account never grows.
  4. In a single slot, several transactions may update the same tree; after the first changes the root, everyone else’s proof is against a stale root and would fail — re-creating a hot writable account that serializes all writers. A concurrent Merkle tree keeps a changelog of recent roots so it can fast-forward non-conflicting proofs, tolerating multiple changes per slot. It is the same Sealevel lesson (contention on one writable account is the throughput enemy) solved at the data-structure level.
  5. You gained an order-of-magnitude cheaper per-item state cost by replacing N rent-paying accounts with one account holding a Merkle root plus N cheap ledger writes. You gave up self-sufficient on-chain data: the on-chain state can only verify data, not produce it. You now depend on off-chain RPC/DAS indexers to supply the leaf data and current proofs needed to read or update items — so it is cheaper state, not free decentralization.