QMTree Commitment

Append-only binary Merkle state commitment indexed by transaction number

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.

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.