💻 computer science

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

Het artikel presenteert \textsc{Mhot}, een op hoogte geoptimaliseerde geauthenticeerde datastructuur die de Merkle Patricia Trie van Ethereum vervangt door discriminerende bit-indexering en hiërarchische bewijzen om een minimale boomhoogte te bereiken, de doorvoer en bewijsgrootte drastisch te verbeteren, en robuuste weerstand tegen Nurgle-aanvallen te bieden zonder dat een vertrouwde setup vereist is.

Oorspronkelijke auteurs: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Gepubliceerd 2026-06-11

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een blockchain voor als een enorme, wereldwijde bibliotheek waar elk boek (transactie) de staat van het hele gebouw verandert. Om te bewijzen dat de bibliotheek correct georganiseerd is, moeten de bibliothecarissen (validators) een gigantische, digitale "Inhoudsopgave" controleren, de State Root.

Momenteel gebruikt de Ethereum-blockchain een systeem genaamd een Merkle Patricia Trie (MPT). Zie dit als een archiefkast waarbij elke lade is gelabeld met een specifiek prefix (zoals "A," "B," "C"). Als je een bestand wilt vinden, volg je de letters. Maar hier is het probleem: als iemand een nieuw bestand toevoegt dat een lang, saai prefix deelt met een bestaand bestand (zoals "A-B-C-D-E-F..."), moet het systeem de lade splitsen, meer planken toevoegen en wordt het pad naar het bestand veel langer.

Dit is de "Nurgle Attack." Het is als een ondeugende grapjas die precies weet hoe de archiefkast werkt. Ze kunnen het systeem overspoelen met bestanden die lange prefixes delen, waardoor de bibliothecarissen gedwongen worden een torenhoog, instabiel toren van laden te bouwen om slechts een paar nieuwe items op te slaan. Dit vertraagt de hele bibliotheek en kost een fortuin aan energie (gas) om te onderhouden, zelfs als de grapjas bijna niets betaalt.

De Nieuwe Oplossing: MHOT (Het "Slimme" Archiefsysteem)

De auteurs introduceren MHOT, een nieuwe manier om deze gegevens te organiseren die het probleem oplost zonder dat er nieuwe magische wiskunde of het vertrouwen in een derde partij nodig is.

Zo werkt MHOT, met behulp van eenvoudige analogieën:

1. Stop met het volgen van de prefix, begin met het vinden van het verschil

Het oude systeem (MPT) kijkt naar de eerste paar letters van een naam en zegt: "Ah, deze gaat in de 'A'-bak." Als twee namen beide met "Alex" beginnen, gaan ze in dezelfde bak, zelfs als de een "Alex" is en de ander "Alexander."

MHOT is slimmer. Het vraagt: "Waar verschillen deze namen echt?"

Als je "Alex" en "Alexander" hebt, geeft MHOT niet om de gedeelde "Alex". Het kijkt naar de eerste letter waar ze uiteenlopen (de 'n' versus de 'a').
Het bouwt een "compound node" (een super-lade) die veel items tegelijk vasthoudt, georganiseerd door de exacte bits die hen uniek maken.
Het resultaat: Hoeveel vergelijkbare namen je ook toevoegt, de toren wordt niet hoger. Hij blijft kort en stabiel omdat hij alleen splitst wanneer het moet, en niet alleen omdat er een gedeelde prefix is.

2. Het "Twee-Lagen" Bonnetje (Hiërarchische Bewijzen)

Wanneer je wilt bewijzen dat een bestand bestaat in het oude systeem, moet de bibliothecaris je een bonnetje overhandigen met een lijst van elk enkel broer-bestand in elke lade die je bent gepasseerd. Als een lade 32 bestanden bevat, is het bonnetje enorm en zwaar.

MHOT gebruikt een Twee-Lagen Bonnetje:

Laag 1: De hoofdstructuur van de bibliotheek.
Laag 2: Binnen elke super-lade zijn de bestanden georganiseerd in hun eigen kleine, mini-boom.
De magie: In plaats van alle 32 broers te vermelden, hoeft het bonnetje alleen een paar "broer"-hashes uit de mini-boom te vermelden (zoals een logaritmische afkorting).
Het resultaat: Het bewijs (het bonnetje) wordt veel kleiner en lichter, waardoor het sneller te verifiëren is voor lichte apparaten.

3. De "Batch" Leveringswagen (Batched Commit)

In het oude systeem moet de bibliothecaris, elke keer dat je een enkel bestand dropt, de hash (de digitale vingerafdruk) voor elke enkele lade tot aan het dak opnieuw berekenen. Dit is alsof je voor elke brief een bezorgwagen naar het postkantoor rijdt.

MHOT gebruikt een Batched Pipeline:

Het verzamelt alle wijzigingen voor een hele blokperiode.
Het berekent de vingerafdrukken parallel (zoals het hebben van een team van werkers die tegelijkert kringen berekenen op verschillende verdiepingen).
Het schrijft de uiteindelijke, bijgewerkte staat pas één keer naar de harde schijf.
Het resultaat: De bibliotheek verwerkt updates tot 9 keer sneller en schrijft 4 keer minder data naar de schijf.

Waarom dit ertoe doet (De Resultaten)

De paper heeft MHOT getest tegen het huidige Ethereum-systeem en enkele andere experimentele systemen:

Snelheid: MHOT is tot wel 9 keer sneller in het wegschrijven van nieuwe data.
Efficiëntie: Het verspilt 4 keer minder opslagruimte (Write Amplification).
Bewijs-grootte: De "bonnetjes" zijn 2 keer kleiner, waardoor het gemakkelijker is voor lichte apparaten (zoals telefoons) om de blockchain te verifiëren.
Beveiliging: Toen de "Nurgle"-grapjas probeerde het systeem te breken door het te overspoelen met vergelijkbare sleutels, blokkeerde MHOT de aanval volledig (0% succespercentage voor de aanvaller). Het oude systeem stortte onder de aanval in (99,97% succespercentage voor de aanvaller).

De Kernboodschap

Het paper betoogt dat we geen complexe, nieuwe cryptografische magie nodig hebben (zoals vertrouwde opstellingen of ingewikkelde wiskunde) om blockchain-schaalbaarheidsproblemen op te lossen. In plaats daarvan hebben we alleen een betere datastructuur nodig. Door gegevens te organiseren op basis van waar dingen echt verschillen in plaats van wat ze delen, en door slimme "twee-lagen" bonnetjes te gebruiken, maakt MHOT de blockchain sneller, goedkoper en immuun voor een specifiek type aanval dat het al jarenlang teistert.

Het is een herinnering dat de beste oplossing soms niet een nieuw superwapen is, maar een slimmere manier om de archiefkast te organiseren.

Technische Samenvatting: MHOT – Hoogte-geoptimaliseerde Geauthenticeerde Datastructuur voor Blockchain State Commitment

1. Probleemstelling

In moderne blockchainsystemen, met name Ethereum, beslaat de berekening van de state root ongeveer 70–80% van de totale blokverwerkingstijd. De huidige canonieke geauthenticeerde datastructuur (ADS), de Merkle Patricia Trie (MPT), lijdt onder twee kritieke beperkingen:

Structurele Kwetsbaarheid voor Nurgle-aanvallen: De MPT maakt gebruik van fixed-prefix indexering, waarbij elk boomniveau een vast aantal opeenvolgende sleutelbits consumeert. Deze structuur stelt aanvallers in staat om lange gemeenschappelijke prefixes (via hash-collisions) te exploiteren om de paddiepte kunstmatig op te blazen. De "Nurgle-aanval" (S&P '24) laat zien dat een aanvaller de systeemprestaties kan degraderen en I/O-kosten kan verhogen tegen verwaarloosbare gaskosten door de trie te dwingen gecomprimeerde paden om te zetten in diepere structuren.
De Span–Proof Trade-off: Om dieptegroei te beperken, zou men de "span" (het aantal bits per niveau) kunnen vergroten. Echter, in prefix-gebaseerde tries verhoogt het vergroten van de span exponentieel de "fanout" (het aantal kind-slots, $2^{span}$ ). Dit dwingt een trade-off af: een hoge span beperkt de hoogte, maar blaast de grootte van nodes en bewijzen exponentieel op; een lage span houdt bewijzen compact, maar laat de boom kwetsbaar voor dieptestructurele aanvallen.

Bestaande alternatieven zoals Verkle Tries of LVMT ontkoppelen de bewijsgrootte van de fanout via vector commitments (algebraïsche technieken). Deze vereisen echter trusted setup-ceremonies, introduceren hogere rekenkundige verificatiekosten en missen vaak de natuurlijke ondersteuning voor range proofs die essentieel zijn voor state-synchronisatie.

2. Methodologie: MHOT

De auteurs stellen MHOT (Height-Optimized Authenticated Data Structure) voor, een persistente, hash-gebaseerde ADS die hoogte-optimaliteit bereikt zonder trusted setup of gespecialiseerde cryptografie. MHOT past de Height-Optimized Trie (HOT) structuur aan voor blockchain state commitment via vier kernmechanismen:

A. Discriminatieve-Bit Indexering (Structurele Fundering)

In tegenstelling tot MPT, dat vaste opeenvolgende prefixes consumeert, vertakt MHOT op basis van discriminatieve bits. Een discriminatieve bit is een positie waar ten minste twee sleutels in een subtree van elkaar verschillen.

Lineaire Koppeling: Deze aanpak koppelt span en fanout lineair in plaats van exponentieel. Een compound node met een fanout $k$ consumeert tot $k-1$ discriminatieve bits, terwijl een prefix-gebaseerde node met dezelfde fanout $\log_2 k$ opeenvolgende bits vereist.
Adaptieve Span: Nodes passen zich aan de werkelijke sleutelverdeling aan. Dichte regio's gebruiken minder bits per node; ijle regio's gebruiken meer. Dit zorgt voor een bewezen minimale boomhoogte voor elke gegeven set sleutels.
Nurgle-resistentie: Omdat de structuur wordt bepaeld door de werkelijke sleuteldivergentie in plaats van vaste prefixes, worden aanvaller-geïnduceerde inserties met gedeelde prefixes geabsorbeerd via interne herstructurering (bijv. leaf pushdown, parent pull-up) zonder noodzakelijkerwijs de globale boomhoogte te verhogen.

B. Hiërarchische Bewijzen (Bewijs Optimalisatie)

Het direct hashen van $k$ kinderen in een compound node zou resulteren in een $O(k)$ bewijsoverhead. MHOT introduceert een twee-laagse Merkle-constructie:

Inter-node Laag: Verbindt compound nodes.
Intra-node Laag: Elke compound node onderhoudt een interne binaire Merkle-boom over zijn $k$ kinderen.

Resultaat: Het bewijzen van lidmaatschap van een kind vereist slechts $O(\log k)$ sibling hashes van de interne boom, wat de bewijsoverhead reduceert van lineair in fanout naar logaritmisch. Dit doorbreekt de lineaire afhankelijkheid van de bewijsgrootte van de span.

C. Content-Addressable Persistentie

Om blockchain state commitment te ondersteunen, modificeert MHOT het oorspronkelijke in-memory HOT-ontwerp:

Deterministische Identificatoren: Nodes worden geïdentificeerd door de hash van hun geserialiseerde inhoud (content-addressable), wat structurele determinisme (identieke sleutelsets leveren identieke bomen op) en trust-minimalisatie garandeert.
Copy-on-Write (CoW): Modificaties creëren nieuwe nodes, waardoor ancestor-hashes ongeldig worden, consistent met de semantiek van blockchain states.

D. Gebatchte Commit Pipeline

Om de computationele kosten van het herhashen van paden te beheersen:

Uitgestelde Hashing: Hash-berekeningen worden uitgesteld tot de block commit. Nodes gebruiken tijdelijke ID's tijdens de transactiefase.
Hoogte-gestratificeerde Parallellisme: Tijdens de commit-fase worden nodes in batches gefinaliseerd, geordend op hoogte (van leaves naar root). Aangezien nodes op dezelfde hoogte geen data-afhankelijkheden hebben, kunnen hash-berekeningen efficiënt geparallelliseerd worden.
LSM-Tree Vriendelijke Lay-out: Storage keys zijn geprefixed door block version en hoogte, wat sequentiële batch-writes en efficiënte compactie mogelijk maakt.

3. Belangrijkste Bijdragen

Identificatie van Span–Proof Koppeling: Het paper identificeert de exponentiële koppeling tussen span en fanout in prefix-gebaseerde tries als de kernoorzaak van het onvermogen om gelijktijdig een gebonden worst-case hoogte en compacte bewijzen te garanderen.
MHOT Instantiatie: Past HOT aan voor blockchain-gebruik, waarbij een hoogte-geoptimaliseerde ADS wordt geboden die resistent is tegen adversariële sleutelverdelingen via discriminatieve-bit tracking en high-fanout compound nodes, gebruikmakend van standaard hash-commitments.
Hiërarchische Bewijzen: Een nieuwe twee-laagse Merkle-constructie die de per-node bewijsoverhead reduceert van $O(k)$ naar $O(\log k)$ , wat compacte bewijzen mogelijk maakt, zelfs met een hoge fanout.
Persistente HOT: Lost het openstaande probleem van disk-gebaseerde deployment voor HOT op door een content-addressable indexering en een parallelle commit pipeline te introduceren.
Uitgebreide Evaluatie: Benchmarkt MHOT tegenover MPT, RainBlock en LVMT onder Ethereum mainnet workloads.

4. Experimentele Resultaten

Geëvalueerd op Ethereum mainnet workloads (blokken 13.5M–13.51M) en synthetische datasets:

Doorvoersnelheid: MHOT bereikt tot wel 9× hogere write-throughput dan MPT (260k ops/s vs. 29k ops/s bij 100k keys) en presteert aanzienlijk beter dan LVMT en RainBlock.
Write Amplification: MHOT reduceert write amplification met een factor 4× vergeleken met MPT (0.9–1.6 vs. 2.7–4.8) dankzij gebatched flushing en verminderde boomdiepte.
Bewijsgrootte: MHOT-bewijzen zijn 2× kleiner dan MPT (1.1–1.4 KB vs. 2.3–2.9 KB) vanwege de hiërarchische bewijsstructuur.
Nurgle-aanval Resistentie: Onder een worst-case scenario waarin een aanvaller de volledige gas-budget van een blok controleert (ca. 15.000 inserties):
- MPT: 99.97% succespercentage in het verhogen van de doelwit-sleuteldieptes.
- MHOT: 0% succespercentage. De structuur absorbeert collisions via interne herstructurering zonder dat de diepte toeneemt.
Verificatie Latentie: MHOT-verificatie werkt in microseconden (vergelijkbaar met MPT), terwijl LVMT (afhankelijk van KZG-pairings) milliseconde-niveau latentie vertoont (3–4 ordes van grootte trager).

5. Betekenis en Claims

Het paper betoogt dat hoogte-optimaliteit, in plaats van de introductie van nieuwe cryptografische primitieven, de sleutelabstractie is voor schaalbare en aanval-resistente blockchain state commitment.

Structurele vs. Cryptografische Oplossingen: MHOT demonstreert dat de trade-offs tussen boomhoogte, bewijsgrootte en aanval-resistentie kunnen worden opgelost via structurele aanpassingen middels discriminatieve-bit indexering, waardoor de vertrouwen-aannames en hoge verificatiekosten van vector commitment-schema's (Verkle, LVMT) worden vermeden.
Direct Inzetbaar: Door uitsluitend gebruik te maken van standaard hash-functies (Keccak-256 of Blake3) en bestaande Merkle-authenticatieprincipes, biedt MHOT een pad naar verbeterde prestaties en veiligheid zonder dat er hard forks nodig zijn voor trusted setup-ceremonies of wijzigingen in algebraïsche verificatie.
Resilience: De resultaten suggereren dat het optimaliseren van de hoogte en adaptiviteit van de datastructuur voldoende is om de Nurgle-aanval vector te neutraliseren, die voorheen een economische of cryptografische tegenmaatregel leek te vereisen.

De auteurs concluderen dat zorgvuldig datastructuur-ontwerp fundamenteel de schaalbaarheid en robuustheid van blockchain state commitment kan verbeteren, en een praktisch alternatief biedt voor de huidige MPT-standaard.