# MHOT: Height-Optimized Authenticated Data Structure for Blockchain State Commitment

Crypto.world

> Computing the state root — the cryptographic digest of all blockchain state — consumes roughly 70–80% of block processing time, and Ethereum's canonical structure for this job (the Merkle Patricia…

**arXiv**: 2606.11736

**Published**: 2026-06-10

**Authors**: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

## AI summary

## Overview

**Research area:** Computer security and blockchain systems — specifically authenticated data structures (ADS) used to commit to blockchain state.

**Technical level:** Advanced. The paper assumes familiarity with Merkle tries, cryptographic commitments, tree-height analysis, and blockchain client architecture.

**Scope:** A single paper presenting MHOT, a hash-based, height-optimal authenticated data structure that adapts the in-memory Height-Optimized Trie (HOT) into a persistent, cryptographically authenticated commitment engine, and evaluating it against MPT, RainBlock, and LVMT on Ethereum mainnet workloads and under Nurgle attacks.

## What This Paper Is About

Computing the state root — the cryptographic digest of all blockchain state — consumes roughly 70–80% of block processing time, and Ethereum's canonical structure for this job (the Merkle Patricia Trie, MPT) grows deeper as state grows, which an adversary can deliberately worsen via the Nurgle attack. The authors argue this weakness is structural: in a prefix-based trie, the number of bits consumed per level (span) is exponentially coupled to the number of child slots (fanout), so you cannot get both shallow trees and small proofs. MHOT replaces prefix indexing with discriminative-bit indexing (from the Height-Optimized Trie), adds persistence and authentication, and shows that height optimality alone — without new cryptography — delivers faster writes, smaller proofs, and attack resistance.

## Key Contributions

1. **Diagnosis of the span–proof trade-off.** The paper identifies prefix-based indexing as the shared root cause preventing existing ADS designs from combining bounded worst-case height with compact membership proofs, and uses HOT's linear span–fanout coupling to escape it using only standard hash commitments (no vector commitments or trusted setup).
2. **Adaptation of HOT to blockchain state commitment.** MHOT makes HOT's compound nodes persistent and cryptographically binding through content-addressable indexing, so node identifiers and state roots follow deterministically from trie structure while preserving HOT's original search and insertion algorithms unmodified.
3. **Hierarchical proofs.** A two-layer Merkle construction — an inter-node layer plus an intra-node Children Merkle Root (CMR) over each compound node's children — reduces per-node proof overhead from O(k) to O(log k), breaking the linear dependence of proof size on span.
4. **Resolution of HOT's stated open problem on disk deployment**, via content-addressable indexing, a parallel height-stratified commit pipeline, and an LSM-tree-friendly key layout — plus a benchmark against MPT, RainBlock, and LVMT.

## Main Findings

- **State commitment is the bottleneck:** state root computation consumes approximately 78% of block processing time in the abstract (70–80% in the introduction), and a single block triggers over 8,700 disk I/O operations.
- **MPT depth has grown and is exploitable:** average MPT path depth on Ethereum mainnet has reached 8 to 11 levels; with a fixed 16-ary branching factor, 256-bit keys have a worst-case depth of 64. The Nurgle attack materializes Patricia-compressed paths into additional branch and extension nodes, increasing realized root-to-leaf depth by 1–2 levels per insertion.
- **High span is intractable for prefix tries:** bounding worst-case depth to at most 10 for 256-bit keys requires span s ≥ 26, which implies roughly 67 million child slots per node.
- **Discriminative-bit indexing yields much shallower trees:** for uniformly random 256-bit keys with fanout k = 32, HOT's theoretical minimum depth is ⌈256/31⌉ = 9 levels, nearly 6× fewer than the 52 levels a prefix-based trie with the same fanout would need.
- **Proofs shrink substantially:** hierarchical proofs give roughly a 6× reduction in hash overhead at k = 32; measured single-point proofs are about 1.1–1.4 KB versus 2.3–2.9 KB for MPT. A naive scheme with k = 32 and h = 5 would produce roughly 5 KB proofs.
- **Throughput and amplification gains:** up to 9× higher write throughput, 4× lower write amplification, and 2× smaller proofs than MPT on Ethereum mainnet workloads.
- **Attack resistance:** under Nurgle attacks, even when the adversary consumes an entire block's gas budget, MHOT maintains a 0% attack success rate versus 99.97% for MPT.
- **The headline claim:** height optimality — not new cryptographic primitives — is the key abstraction for scalable and attack-resilient blockchain state commitment.

## Methodology in Plain English

The starting point is an existing in-memory index called HOT, which decides where to branch by looking at bit positions where keys actually differ ("discriminative bits") rather than at fixed consecutive chunks of the key. Because of this, a node with k children consumes up to k−1 distinguishing bits instead of only log₂k bits, so the tree can stay short even when keys share long prefixes; the authors cite HOT's proof that this yields the minimum possible height for any key set.

The work is then to make that structure survive on disk and be verifiable. Each node is named by the hash of its serialized content, so any validator computing the same key set arrives at the same identifiers and the same state root — this relies on the trie being structurally deterministic, independent of insertion order. To keep proofs small despite wide nodes, each node keeps a small binary Merkle tree over its children and publishes only that root as part of its own hash; a proof then needs logarithmically many sibling hashes rather than every sibling.

For performance, the authors defer hashing until block commit using temporary node identifiers, so each node is copied at most once per block and shared ancestors are not rehashed repeatedly. At commit, pending nodes are grouped by their stored height and hashed level by level, children before parents, with parallel work inside each level. Storage layout puts a 64-bit prefix (type flag, version, height) ahead of the 256-bit content hash so that writes sort into locality-friendly batches for an LSM-tree engine, and a background thread flushes asynchronously.

Finally, the paper formalizes four proof types within one framework — single-point membership and non-membership, multi-point membership, lower bound, and range proofs — built on the observation that HOT's search always reaches some leaf that matches the query on all discriminative bits, so membership and non-membership differ only in a final comparison.

## Why This Matters

**Impact on research:** The paper reframes a problem that has been attacked with heavier cryptography (Verkle tries, LVMT) as a data-structure problem. If height optimality alone delivers the resilience that vector commitments were adopted for, then the trusted-setup ceremonies and pairing-based verification costs those schemes impose may be avoidable — and native range proofs, which the paper states neither Verkle trees nor LVMT provide, are preserved.

**Real-world applications:**

- Ethereum execution clients such as Erigon and Reth, which already treat the ADS as a dedicated commitment engine whose write throughput is the primary bottleneck.
- Denial-of-service defense for validators, since the Nurgle attack costs the adversary almost nothing under per-opcode gas pricing while validators absorb the I/O cost of deepened paths.
- Light clients verifying query responses against a block header instead of trusting RPC providers, benefited by smaller proofs and standard hash-based verification.
- Verified state synchronization, which depends on range proofs that vector-commitment designs do not natively support.

**Industry relevance:** The evaluation uses Ethereum mainnet workloads and compares against MPT, RainBlock, and LVMT, and the paper was accepted by USENIX Security 2026 — positioning it as a drop-in-shaped alternative for production state commitment rather than a theoretical curiosity.

## Future Directions

- **Adversarial analysis of local restructuring.** The paper states that only Parent Pull-Up increases global height, while Normal Insert, Leaf Pushdown, and Intermediate Node Creation may lengthen individual paths, and explicitly defers to §6.6 the question of whether such local path increases can be exploited for Nurgle-style attacks — a natural target for follow-up adversarial study.
- **Beyond 256-bit keys.** MHOT fixes key length at 256 bits to match Keccak-256 output, letting extraction masks and sparse partial keys occupy fixed-length fields; generalizing the layout to other key sizes is an open engineering question.
- **Deployment in production clients.** The evaluation is benchmark-based; migrating a live client's commitment engine from MPT — including handling historical state and existing database formats — is not addressed in the provided content.
- **Tuning the fanout parameter k.** The paper analyzes k = 32 as typical and k = 27 as an example, and derives height as max(⌈256/(k−1)⌉, O(log_k N)); how to choose k for specific hardware, proof-bandwidth, and storage trade-offs is left to practice.

## Target Audience

Blockchain client and protocol engineers, researchers in authenticated data structures and verifiable storage, and security researchers working on denial-of-service resistance in consensus systems. It will also interest readers tracking the Verkle-trie-versus-hash-based debate, since much of the argument is about whether vector commitments are necessary at all. Readers without background in Merkle tries, tree-height analysis, or blockchain state management will find the formal definitions in Sections 3–5 demanding.

## Authors’ abstract

State root computation dominates (78%) blockchain block processing time. Ethereum's canonical authenticated data structure, i.e., Merkle Patricia Trie (MPT), suffers from severe tree-height growth and is vulnerable to \textit{Nurgle attacks} (SP'24), where adversaries inflate path depth via hash collisions and degrade system performance at negligible cost. Existing defenses increase node fanout (span) to bound tree height, but higher span inflates proof size exponentially.…

[The full abstract on arXiv](https://arxiv.org/abs/2606.11736)

[Read the original paper](https://arxiv.org/abs/2606.11736)

---

Canonical: https://crypto.world/paper/mhot-height-optimized-authenticated-data-structure-for-blockchain-state-2606.11736
