💻 computer science

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

The paper presents \textsc{Mhot}, a height-optimized authenticated data structure that replaces Ethereum's Merkle Patricia Trie with discriminative bit indexing and hierarchical proofs to achieve minimal tree height, drastically improve throughput and proof sizes, and provide robust resistance against Nurgle attacks without requiring trusted setup.

Original authors: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a blockchain like a massive, global library where every single book (transaction) changes the state of the entire building. To prove that the library is organized correctly, the librarians (validators) have to check a giant, digital "Table of Contents" called the State Root.

Currently, the Ethereum blockchain uses a system called a Merkle Patricia Trie (MPT). Think of this like a filing cabinet where every drawer is labeled with a specific prefix (like "A," "B," "C"). If you want to find a file, you follow the letters. But here's the problem: if someone adds a new file that shares a long, boring prefix with an existing one (like "A-B-C-D-E-F..."), the system has to split the drawer, add more shelves, and make the path to the file much longer.

This is the "Nurgle Attack." It's like a mischievous prankster who knows exactly how the filing cabinet works. They can flood the system with files that share long prefixes, forcing the librarians to build a towering, unstable tower of drawers just to store a few new items. This slows down the whole library and costs a fortune in energy (gas) to maintain, even though the prankster pays almost nothing.

The New Solution: MHOT (The "Smart" Filing System)

The authors introduce MHOT, a new way to organize this data that fixes the problem without needing any magical new math or trusting a third party.

Here is how MHOT works, using simple analogies:

1. Stop Following the Prefix, Start Finding the Difference

The old system (MPT) looks at the first few letters of a name and says, "Ah, this goes in the 'A' bin." If two names both start with "Alex," they go in the same bin, even if one is "Alex" and the other is "Alexander."

MHOT is smarter. It asks: "Where do these names actually differ?"

If you have "Alex" and "Alexander," MHOT doesn't care about the shared "Alex." It looks for the first letter where they split (the 'n' vs. the 'a').
It builds a "compound node" (a super-drawer) that holds many items at once, organized by the exact bits that make them unique.
The Result: No matter how many similar names you add, the tower doesn't get taller. It stays short and stable because it only splits when it has to, not just because of a shared prefix.

2. The "Two-Layer" Receipt (Hierarchical Proofs)

When you want to prove a file exists in the old system, the librarian has to hand you a receipt listing every single sibling file in every drawer you passed. If a drawer holds 32 files, the receipt is huge and heavy.

MHOT uses a Two-Layer Receipt:

Layer 1: The main structure of the library.
Layer 2: Inside each super-drawer, the files are arranged in their own tiny, mini-tree.
The Magic: Instead of listing all 32 siblings, the receipt only needs to list a few "sibling" hashes from the mini-tree (like a logarithmic shortcut).
The Result: The proof (receipt) becomes much smaller and lighter, making it faster to verify.

3. The "Batch" Delivery Truck (Batched Commit)

In the old system, every time you drop a single file, the librarian has to re-calculate the hash (the digital fingerprint) for every single drawer up to the roof. This is like driving a delivery truck to the post office for every single letter.

MHOT uses a Batched Pipeline:

It collects all the changes for a whole block of time.
It calculates the fingerprints in parallel (like having a team of workers hashing different floors at the same time).
It only writes the final, updated state to the hard drive once.
The Result: The library processes updates 9 times faster and writes 4 times less data to the disk.

Why This Matters (The Results)

The paper tested MHOT against the current Ethereum system and some other experimental systems:

Speed: MHOT is up to 9 times faster at writing new data.
Efficiency: It wastes 4 times less storage space (Write Amplification).
Proof Size: The "receipts" are 2 times smaller, making it easier for light devices (like phones) to verify the blockchain.
Security: When the "Nurgle" prankster tried to break the system by flooding it with similar keys, MHOT completely blocked the attack (0% success rate). The old system collapsed under the attack (99.97% success rate for the attacker).

The Bottom Line

The paper argues that we don't need complex, new cryptographic magic (like trusted setups or fancy math) to fix blockchain scaling issues. Instead, we just need a better data structure. By organizing data based on where things actually differ rather than what they share, and by using smart "two-layer" receipts, MHOT makes the blockchain faster, cheaper, and immune to a specific type of attack that has plagued it for years.

It's a reminder that sometimes, the best solution isn't a new super-weapon, but a smarter way of organizing the filing cabinet.

Technical Summary: MHOT – Height-Optimized Authenticated Data Structure for Blockchain State Commitment

1. Problem Statement

In modern blockchain systems, particularly Ethereum, state root computation consumes approximately 70–80% of total block processing time. The current canonical authenticated data structure (ADS), the Merkle Patricia Trie (MPT), suffers from two critical limitations:

Structural Vulnerability to Nurgle Attacks: The MPT uses fixed-prefix indexing, where each tree level consumes a fixed number of contiguous key bits. This structure allows adversaries to exploit long common prefixes (via hash collisions) to artificially inflate path depths. The "Nurgle attack" (S&P '24) demonstrates that an attacker can degrade system performance and increase I/O costs at negligible gas cost by forcing the trie to materialize compressed paths into deeper structures.
The Span–Proof Trade-off: To mitigate depth growth, one might increase the "span" (bits consumed per level). However, in prefix-based tries, increasing span exponentially increases the "fanout" (number of child slots, $2^{span}$ ). This forces a trade-off: high span bounds height but inflates node size and proof size exponentially; low span keeps proofs compact but leaves the tree vulnerable to deepening attacks.

Existing alternatives like Verkle Tries or LVMT decouple proof size from fanout using vector commitments (algebraic techniques). However, these require trusted setup ceremonies, introduce higher arithmetic verification costs, and often lack native support for range proofs essential for state synchronization.

2. Methodology: MHOT

The authors propose MHOT (Height-Optimized Authenticated Data Structure), a persistent, hash-based ADS that achieves height optimality without trusted setup or specialized cryptography. MHOT adapts the Height-Optimized Trie (HOT) structure to blockchain state commitment through four key mechanisms:

A. Discriminative-Bit Indexing (Structural Foundation)

Unlike MPT, which consumes fixed contiguous prefixes, MHOT branches on discriminative bits. A discriminative bit is a position where at least two keys in a subtree differ.

Linear Coupling: This approach couples span and fanout linearly rather than exponentially. A compound node with fanout $k$ consumes up to $k-1$ discriminative bits, whereas a prefix-based node of the same fanout requires $\log_2 k$ contiguous bits.
Adaptive Span: Nodes adapt to the actual key distribution. Dense regions use fewer bits per node; sparse regions use more. This ensures provably minimal tree height for any given key set.
Nurgle Resistance: Because the structure is determined by actual key divergence rather than fixed prefixes, adversarial insertions with shared prefixes are absorbed via internal restructuring (e.g., leaf pushdown, parent pull-up) without necessarily increasing global tree height.

B. Hierarchical Proofs (Proof Optimization)

Directly hashing $k$ children in a compound node would result in $O(k)$ proof overhead. MHOT introduces a two-layer Merkle construction:

Inter-node Layer: Connects compound nodes.
Intra-node Layer: Each compound node maintains an internal binary Merkle tree over its $k$ children.

Result: Proving membership of a child requires only $O(\log k)$ sibling hashes from the internal tree, reducing proof size from linear in fanout to logarithmic. This breaks the linear dependence of proof size on span.

C. Content-Addressable Persistence

To support blockchain state commitment, MHOT modifies the original in-memory HOT design:

Deterministic Identifiers: Nodes are identified by the hash of their serialized content (content-addressable), ensuring structural determinism (identical key sets yield identical trees) and trust minimization.
Copy-on-Write (CoW): Modifications create new nodes, invalidating ancestor hashes, consistent with blockchain state semantics.

D. Batched Commit Pipeline

To handle the computational cost of rehashing paths:

Deferred Hashing: Hash computations are deferred until block commit. Nodes use temporary IDs during the transaction phase.
Height-Stratified Parallelism: At commit time, nodes are finalized in batches ordered by height (leaves to root). Since nodes at the same height have no data dependencies, hash computations can be parallelized efficiently.
LSM-Tree Friendly Layout: Storage keys are prefixed by block version and height, enabling sequential batch writes and efficient compaction.

3. Key Contributions

Identification of Span-Proof Coupling: The paper identifies the exponential coupling of span and fanout in prefix-based tries as the root cause of the inability to simultaneously guarantee bounded worst-case height and compact proofs.
MHOT Instantiation: Adapts HOT for blockchain use, providing a height-optimized ADS that resists adversarial key distributions via discriminative-bit tracking and high-fanout compound nodes, using only standard hash commitments.
Hierarchical Proofs: A novel two-layer Merkle construction that reduces per-node proof overhead from $O(k)$ to $O(\log k)$ , enabling compact proofs even with high fanout.
Persistent HOT: Solves the open problem of disk-based deployment for HOT by introducing content-addressable indexing and a parallel commit pipeline.
Comprehensive Evaluation: Benchmarks MHOT against MPT, RainBlock, and LVMT under Ethereum mainnet workloads.

4. Experimental Results

Evaluated on Ethereum mainnet workloads (blocks 13.5M–13.51M) and synthetic datasets:

Throughput: MHOT achieves up to 9× higher write throughput than MPT (260k ops/s vs. 29k ops/s at 100k keys) and outperforms LVMT and RainBlock by significant margins.
Write Amplification: MHOT reduces write amplification by 4× compared to MPT (0.9–1.6 vs. 2.7–4.8) due to batched flushing and reduced tree depth.
Proof Size: MHOT proofs are 2× smaller than MPT (1.1–1.4 KB vs. 2.3–2.9 KB) due to the hierarchical proof structure.
Nurgle Attack Resistance: Under a worst-case attack scenario where an adversary controls an entire block's gas budget (approx. 15,000 insertions):
- MPT: 99.97% success rate in increasing target key depths.
- MHOT: 0% success rate. The structure absorbs collisions via internal restructuring without propagating depth increases.
Verification Latency: MHOT verification operates in microseconds (comparable to MPT), whereas LVMT (relying on KZG pairings) incurs millisecond-level latency (3–4 orders of magnitude slower).

5. Significance and Claims

The paper argues that height optimality, rather than the introduction of new cryptographic primitives, is the key abstraction for scalable and attack-resilient blockchain state commitment.

Structural vs. Cryptographic Solutions: MHOT demonstrates that the trade-offs between tree height, proof size, and attack resistance can be resolved structurally through discriminative-bit indexing, avoiding the trust assumptions and high verification costs of vector commitment schemes (Verkle, LVMT).
Immediate Deployability: By relying solely on standard hash functions (Keccak-256 or Blake3) and existing Merkle authentication principles, MHOT offers a path to improved performance and security without requiring hard forks for trusted setup ceremonies or algebraic verification changes.
Resilience: The results suggest that optimizing the data structure's height and adaptability is sufficient to neutralize the Nurgle attack vector, which previously seemed to require economic or cryptographic countermeasures.

The authors conclude that careful data-structure design can fundamentally improve the scalability and robustness of blockchain state commitment, offering a practical alternative to the current MPT standard.