QMTree Commitment

tip

Working PoC. Live on the qmtree branch. Data accumulating on Hoodi testnet.

QMTree is an alternative Ethereum state commitment scheme. It replaces the hex patricia trie with a sequential, append-only binary Merkle tree indexed by Erigon's global transaction number (txNum). Each leaf records a single transaction's state changes. The tree root after a block's final transaction is that block's state commitment.

The critical differentiator from the hex patricia trie: each leaf's transitionHash commits to the full per-opcode EVM execution trace, not just the resulting state. This makes QMTree roots a proof of correct execution — enabling fraud proofs, verifiable eth_call, and non-membership proofs — not merely a state snapshot.

---

Advantages over the hex patricia trie:

Property	Hex patricia trie	QMTree
Append complexity	O(log N) trie traversal	O(1) — leaves appended sequentially
Proof size	~3–5 KB	~1 KB (binary Merkle path)
Namespace	Nested (accounts trie + per-account storage trie)	Flat — accounts and storage share one tree
Commits to execution	No — state snapshot only	Yes — per-opcode EVM trace in every leaf
Storage vs commitment domain	—	~3.7× smaller at equivalent block ranges

The proof-of-execution property is the key differentiator. Because transitionHash commits to the full EVM trace, QMTree roots enable fraud proofs and verifiable eth_call — not just state proofs.

Leaf Hash Construction

Each leaf at serial number txnum commits to four 32-byte fields:

leafHash = keccak256(preStateHash || stateChangeHash || transitionHash || previousLeafHash)

Component	Construction	Purpose
preStateHash	DeriveSha MPT over {(domain, key) → value} reads	Commits to pre-state accessed by the transaction
stateChangeHash	DeriveSha MPT over {(domain, key) → value} writes	Commits to state mutations
transitionHash	keccak256 of transition record sequence	Commits to full EVM trace — every opcode's (depth, pc, opcode, gas, cost, stack_in, stack_out)
previousLeafHash	Leaf hash of txnum - 1	Sequential chaining — tamper with one leaf and all subsequent are invalidated

The transitionHash is what makes this a proof of correct execution, not just a state snapshot. It includes 25 spec-mandated operations alongside the per-opcode trace.

Tree Structure

The tree is organized in twigs — subtrees of 2048 leaves each. A twig is the unit of storage and proof aggregation:

                    Root
                   /    \
              Twig[0]   Twig[1]   ...   Twig[N]
             /       \
        Leaf[0]   Leaf[1]  ...  Leaf[2047]

A Merkle path in a proof is a sequence of (sibling, direction) pairs that reduces to the twig root, then the tree root. Proof size scales with log2(twigSize) + log2(numTwigs).

Storage Efficiency

QMTree stores approximately 3.7× less data than the commitment domain at equivalent block ranges. This comes from:

• Flat namespace — no per-account subtrees
• Binary encoding — txNum as the key avoids account address overhead
• Twig-grouped proofs — twigs are the compaction unit; complete twigs are frozen to snapshot files

RPC Namespace

QMTree exposes a qm_ RPC namespace with 10 methods:

Method	Description
qm_getRoot(blockNum)	Tree root at a given block
qm_getLeaf(txNum)	Full leaf data at a transaction number
qm_getProof(txNum)	Merkle proof for a leaf
qm_call(...)	eth_call with a verifiable proof of correct execution
qm_callProof(...)	Returns both the call result and its QMTree proof
qm_verifyProof(proof)	Verify a supplied proof against the current root
...	(10 methods total)

qm_call and qm_callProof are the highest-value methods — they allow any caller to verify that a contract call was executed correctly against the claimed state.

KeyIndex

QMTree includes a KeyIndex — a committed sorted set of all keys modified by a transaction. The KeyIndex supports:

• Inclusion proofs — prove that key K was modified by transaction T
• Exclusion proofs (non-membership) — prove that key K was NOT modified by transaction T

Non-membership proofs are what make qm_callProof complete — the prover must show not only what state was read/written, but that no other state was secretly accessed.

Component Integration

QMTree is an optional component activated by --experimental.qmtree. It plugs into the component framework via the standard init() + components.cfg registration:

--experimental.qmtree

When active, it subscribes to execution events via the event bus and appends leaves in real time. Backfill (reproducing the tree for historical blocks) uses the Map-Reduce Framework with QmtreeTracerFactory and QmtreeConsumer.

note

Depends on: L1/L2 Node — Storage component (chainDB access for txNum history). Integrates with: Map-Reduce Framework for batch tree reproduction from historical block execution.

Relationship to Platform Components

QMTree is the foundation for two higher-level platform capabilities:

Fraud Proofs — The transitionHash in each QMTree leaf commits to the full EVM execution trace. This is what makes the three-level bisection fraud proof protocol possible: the protocol uses QMTree roots to binary-search for divergent blocks, transaction-level leaf components to identify the type of divergence, and the opcode trace committed by transitionHash to perform instruction-level bisection. See Fraud Proofs for the full protocol.

ZK Proving (Two-Tier Model) — QMTree roots serve as Tier 1 pre-proofs: lightweight per-block commitments computed during normal execution with no external prover required. Tier 2 ZK full proofs cover batches of blocks and are bound to the Tier 1 QMTree roots via range proofs before L1 settlement. See ZK Proving for the proof pipeline architecture.