MPT State Layer

Merkle Patricia Trie state management in Vela.

The state layer provides persistent, verifiable state storage for Vela. It uses a Merkle Patricia Trie (MPT) to produce a deterministic state root after each committed batch — the root is a cryptographic commitment to the full state of the exchange at a given point in time.

Why MPT?

A Merkle Patricia Trie provides two critical properties:

1. Determinism: The same set of key-value pairs always produces the same root hash, regardless of insertion order. This is essential for the zkvm prover to reproduce the root independently.

2. Proofs: Any individual state value can be proven to be part of the trie with a compact Merkle proof. This supports future on-chain verification — a fraud proof can include just the relevant state entries, not the entire trie.

State Keys

State is addressed by a typed StateKey enum. Each variant corresponds to a distinct logical piece of exchange state:

Key Type	Contents	Example
Balance(address, asset)	Available + reserved balance for one asset	Balance("0xabc...", "USDC")
Metadata(address)	Account metadata	Nonce high-water mark, credit params
OrderBook(market_id)	Serialized order book state	All resting orders for ETH-USDC
MarketConfig(market_id)	Market parameters	Tick size, lot size, status, fee tiers
GlobalSequence	Current batch sequence number	Monotonically increasing integer

State keys are serialized to bytes and used as trie keys. The encoding is deterministic and stable across versions.

In-Memory Cache

The in-memory cache is the primary access path for hot state. Most reads and writes in the matching engine never touch the trie directly — they operate on the cache.

Read path:
  1. Check cache → hit: return cached value
  2. Cache miss → read from MPT, populate cache, return value

Write path:
  1. Write to cache only
  2. At batch commit: flush cache diff to MPT as StateDelta

The cache is a HashMap<StateKey, StateValue> held in the engine’s working memory. It is seeded from the MPT at engine startup and kept warm across batches.

Cache invalidation: The cache is never invalidated mid-batch. If a batch is rolled back (rare error case), the cache is discarded and re-populated from the last committed MPT state.

Deterministic Ordering

The MPT requires deterministic ordering of all state entries. Vela achieves this by:

1. Using BTreeMap (sorted by key) for all state iteration in the committer
2. Using a canonical byte encoding for StateKey that is lexicographically ordered by type then fields
3. Applying all StateDelta entries in sorted key order when updating the MPT

This guarantees that the zkvm prover, given the same StateDelta, produces the same post_root as the committer — regardless of the order in which fills were generated by the engine.

Commit Flow

At the end of each batch:

CommitBatch arrives
       │
       ▼
Extract StateDelta from cache diff
       │
       ▼
Sort delta entries by StateKey
       │
       ▼
Apply entries to MPT
       │
       ▼
Compute new MPT root (post_root)
       │
       ▼
Serialize ZkvmInput { pre_root, requests, post_root }
       │
       ▼
Publish to DA layer → DaReceipt
       │
       ▼
Store DaReceipt with batch record

The pre_root (state root before the batch) and post_root (after) form a commitment chain: each batch’s pre_root must equal the previous batch’s post_root. A gap or mismatch is detectable by anyone following the DA layer.

State Root Properties

The state root is a 32-byte hash (keccak256 of the trie root node). It is:

• Deterministic: Same state always produces same root
• Collision-resistant: No two distinct states produce the same root (up to keccak256 collision resistance)
• Compact: The root commits to the full state in 32 bytes
• Incrementally computable: Only modified branches of the trie need to be recomputed on each batch

MPT Implementation

Vela uses a custom MPT implementation optimized for the exchange access pattern: frequent point updates to known keys (balance changes, order book updates) rather than range scans or random key generation.

Key design choices:

• Node hash caching — branch and extension nodes cache their computed hashes, only invalidated on child updates
• Lazy hashing — the root is not recomputed until explicitly requested at commit time
• In-memory only — the MPT lives entirely in memory; the DA layer provides the durability guarantee

Recovery

On startup, the engine recovers state by:

1. Fetching the latest batch record from persistent storage
2. Reading the post_root of the latest committed batch
3. Fetching the corresponding DA batch and reconstructing the MPT from its state snapshot
4. Populating the cache from the reconstructed MPT

This recovery path is also used by the zkvm prover when seeding execution for a given batch.