💻 computer science

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

Il documento presenta \textsc{Mhot}, una struttura dati autenticata ottimizzata per l'altezza che sostituisce il Merkle Patricia Trie di Ethereum con l'indicizzazione bit a discriminazione e prove gerarchiche per raggiungere un'altezza dell'albero minima, migliorare drasticamente il throughput e le dimensioni delle prove, e fornire una robusta resistenza contro gli attacchi Nurgle senza richiedere una configurazione fidata.

Autori originali: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Pubblicato 2026-06-11

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina una blockchain come una biblioteca enorme e globale dove ogni singolo libro (transazione) cambia lo stato dell'intero edificio. Per dimostrare che la biblioteca è organizzata correttamente, i bibliotecari (validatori) devono controllare un gigantesco "Indice" digitale chiamato State Root.

Attualmente, la blockchain di Ethereum utilizza un sistema chiamato Merkle Patricia Trie (MPT). Immaginalo come un archivio dove ogni cassetto è etichettato con un prefisso specifico (come "A", "B", "C"). Se vuoi trovare un file, segui le lettere. Ma ecco il problema: se qualcuno aggiunge un nuovo file che condivide un prefisso lungo e noioso con uno esistente (come "A-B-C-D-E-F..."), il sistema deve dividere il cassetto, aggiungere altri scaffali e rendere il percorso verso il file molto più lungo.

Questo è l'"Attacco Nurgle". È come uno scherzo dispettoso che conosce esattamente come funziona l'archivio. Possono inondare il sistema con file che condividono lunghi prefissi, costringendo i bibliotecari a costruire una torre altissima e instabile di cassetti solo per conservare pochi nuovi elementi. Questo rallenta l'intera biblioteca e costa una fortuna in energia (gas) per mantenerla, anche se il dispettoso paga quasi nulla.

La Nuova Soluzione: MHOT (Il Sistema di Archiviazione "Intelligente")

Gli autori introducono MHOT, un nuovo modo di organizzare questi dati che risolve il problema senza aver bisogno di nuova matematica magica o di fidarsi di una terza parte.

Ecco come funziona MHOT, utilizzando analogie semplici:

1. Smetti di seguire il prefisso, inizia a trovare la differenza

Il vecchio sistema (MPT) guarda le prime lettere di un nome e dice: "Ah, questo va nel contenitore 'A'". Se due nomi iniziano entrambi con "Alex", vanno nello stesso contenitore, anche se uno è "Alex" e l'altro è "Alexander".

MHOT è più intelligente. Chiede: "Dove differiscono effettivamente questi nomi?"

Se hai "Alex" e "Alexander", MHOT non si cura del "Alex" condiviso. Cerca la prima lettera in cui si separano (la 'n' rispetto alla 'a').
Costruisce un "nodo composto" (un super-cassetto) che contiene molti elementi insieme, organizzati in base ai bit esatti che li rendono unici.
Il Risultato: Non importa quanti nomi simili aggiungi, la torre non diventa più alta. Rimane corta e stabile perché si divide solo quando deve farlo, non solo perché condividono un prefisso.

2. La Ricevuta a "Due Livelli" (Prove Gerarchiche)

Quando vuoi dimostrare che un file esiste nel vecchio sistema, il bibliotecario deve consegnarti una ricevuta che elenca ogni singolo file fratello in ogni cassetto che hai attraversato. Se un cassetto contiene 32 file, la ricevuta è enorme e pesante.

MHOT utilizza una Ricevuta a Due Livelli:

Livello 1: La struttura principale della biblioteca.
Livello 2: All'interno di ogni super-cassetto, i file sono disposti nei propri piccoli mini-alberi.
La Magia: Invece di elencare tutti i 32 fratelli, la ricevuta ha solo bisogno di elencare alcuni hash "fratelli" dal mini-albero (come una scorciatoia logaritmica).
Il Risultato: La prova (ricevuta) diventa molto più piccola e leggera, rendendo più veloce la verifica per i dispositivi leggeri (come i telefoni).

3. Il Camion per le Consegne "a Lotti" (Batch Commit)

Nel vecchio sistema, ogni volta che depositi un singolo file, il bibliotecario deve ricalcolare l'hash (l'impronta digitale) per ogni singolo cassetto fino al tetto. È come guidare un camion per le consegne all'ufficio postale per ogni singola lettera.

MHOT utilizza una Pipeline a Lotti:

Raccoglie tutti i cambiamenti per un intero blocco di tempo.
Calcola le impronte digitali in parallelo (come avere un team di lavoratori che calcola gli hash di diversi piani contemporaneamente).
Scrive l'aggiornamento finale dello stato sul disco rigido una sola volta.
Il Risolo: La biblioteca elabora gli aggiornamenti 9 volte più velocemente e scrive 4 volte meno dati sul disco.

Perché questo è importante (I Risultati)

Il documento ha testato MHOT contro l'attuale sistema di Ethereum e alcuni altri sistemi sperimentali:

Velocità: MHOT è fino a 9 volte più veloce nel scrivere nuovi dati.
Efficienza: Spreca 4 volte meno spazio di archiviazione (Write Amplification).
Dimensione della Prova: Le "ricevute" sono 2 volte più piccole, rendendo più facile per i dispositivi leggeri (come i telefoni) verificare la blockchain.
Sicurezza: Quando il dispettoso "Nurgle" ha cercato di rompere il sistema inondandolo con chiavi simili, MHOT ha bloccato completamente l'attacco (0% di successo per l'attaccante). Il vecchio sistema è crollato sotto l'attacco (99,97% di successo per l'attaccante).

In sintesi

Il documento sostiene che non abbiamo bisogno di una nuova e complessa magia crittografica (come setup fidati o matematica sofisticata) per risolvere i problemi di scalabilità della blockchain. Invece, abbiamo solo bisogno di una migliore struttura dati. Organizzando i dati in base a dove le cose effettivamente differiscono piuttosto che su ciò che condividono, e utilizzando ricevute intelligenti a "due livelli", MHOT rende la blockchain più veloce, economica e immune a un tipo specifico di attacco che la affligge da anni.

È un promemoria del fatto che, a volte, la soluzione migliore non è una nuova super-arma, ma un modo più intelligente di organizzare l'archivio.

Riepilogo Tecnico: MHOT – Struttura Dati Autenticata Ottimizzata per l'Altezza per l'Impegno dello Stato Blockchain

1. Problematica

Nei sistemi blockchain moderni, in particolare Ethereum, il calcolo della radice dello stato (state root) consuma circa il 70–80% del tempo totale di elaborazione dei blocchi. L'attuale struttura dati autenticata (ADS) canonica, il Merkle Patricia Trie (MPT), soffre di due critiche limitazioni:

Vulnerabilità Strutturale agli Attacchi Nurgle: L'MPT utilizza un indicizzazione a prefisso fisso, dove ogni livello dell'albero consuma un numero fisso di bit contigui della chiave. Questa struttura permette agli avversari di sfruttare lunghi prefissi comuni (tramite collisioni di hash) per gonfiare artificialmente la profondità dei percorsi. L'attacco "Nurgle" (S&P '24) dimostra che un attaccante può degradare le prestazioni del sistema e aumentare i costi di I/O a un costo di gas trascurabile, forzando il trie a materializzare percorsi compressi in strutture più profonde.
Il Compromesso Span–Proof (Ampiezza–Dimensione della Prova): Per mitigare la crescita della profondità, si potrebbe aumentare lo "span" (i bit consumati per livello). Tuttavia, nei trie basati su prefissi, aumentare lo span aumenta esponenzialmente il "fanout" (numero di slot figli, $2^{span}$ ). Ciò impone un compromesso: uno span elevato limita l'altezza ma gonfia esponenzialmente la dimensione dei nodi e delle prove; uno span basso mantiene compatte le prove ma lascia l'albero vulnerabile ad attacchi di approfondimento.

Le alternative esistenti come i Verkle Tries o gli LVMT scindono la dimensione della prova dal fanout utilizzando impegni vettoriali (tecniche algebriche). Tuttavia, questi richiedono cerimonie di setup fidato, introducono costi di verifica aritmetica più elevati e spesso mancano del supporto nativo per le prove di intervallo (range proofs) essenziali per la sincronizzazione dello stato.

2. Metodologia: MHOT

Gli autori propongono MHOT (Height-Optimized Authenticated Data Structure), una ADS persistente basata su hash che raggiunge l'ottimalità dell'altezza senza setup fidato o crittografia specializzata. MHOT adatta la struttura della Height-Optimized Trie (HOT) all'impegno dello stato blockchain attraverso quattro meccanismi chiave:

A. Indicizzazione a Bit Discriminativi (Fondamento Strutturale)

A differenza dell'MPT, che consuma prefissi contigui fissi, MHOT dirama sui bit discriminativi. Un bit discriminativo è una posizione in cui almeno due chiavi in un sottotree differiscono.

Accoppiamento Lineare: Questo approccio accoppia lo span e il fanout linearmente anziché esponenzialmente. Un nodo composto con fanout $k$ consuma fino a $k-1$ bit discriminativi, mentre un nodo basato su prefisso richiede $\log_2 k$ bit contigui.
Span Adattivo: I nodi si adattano alla reale distribuzione delle chiavi. Le regioni dense utilizzano meno bit per nodo; le regioni sparse ne utilizzano di più. Ciò garantisce un'altezza dell'albero provabilmente minima per qualsiasi insieme di chiavi.
Resistenza a Nurgle: Poiché la struttura è determinata dalla reale divergenza delle chiavi piuttosto che da prefissi fissi, le inserzioni avversarie con prefissi condivisi vengono assorbite tramite ristrutturazione interna (es. leaf pushdown, parent pull-up) senza necessariamente aumentare l'altezza globale dell'albero.

B. Prove Gerarchiche (Ottimizzazione delle Prove)

L'hashing diretto di $k$ figli in un nodo composto comporterebbe un overhead di prova di $O(k)$ . MHOT introduce una costruzione Merkle a due livelli:

Livello Inter-nodo: Collega i nodi composti.
Livello Intra-nodo: Ogni nodo composto mantiene un albero Merkle binario interno sui suoi $k$ figli.

Risultato: Dimostrare l'appartenenza di un figlio richiede solo $O(\log k)$ hash fratelli dall'albero interno, riducendo la dimensione della prova da lineare rispetto al fanout a logaritmica. Questo rompe la dipendenza lineare della dimensione della prova dallo span.

C. Persistenza Content-Addressable (Indirizzabile per Contenuto)

Per supportare l'impegno dello stato blockchain, MHOT modifica il design originale di HOT (in-memory):

Identificatori Deterministici: I nodi sono identificati dall'hash del loro contenuto serializzato (content-addressable), garantendo il determinismo strutturale (insiemi di chiavi identici producono alberi identici) e la minimizzazione della fiducia.
Copy-on-Write (CoW): Le modifiche creano nuovi nodi, invalidando gli hash degli antenati, in linea con la semantica dello stato blockchain.

D. Pipeline di Commit a Lotti (Batched Commit Pipeline)

Per gestire il costo computazionale del re-hashing dei percorsi:

Hashing Differito: Il calcolo dell'hash è differito fino al commit del blocco. I nodi utilizzano ID temporanei durante la fase di transazione.
Parallelismo Stratificato per Altezza: Al momento del commit, i nodi vengono finalizzati in lotti ordinati per altezza (dalle foglie alla radice). Poiché i nodi allo stesso livello non hanno dipendenze di dati, i calcoli dell'hash possono essere parallelizzati efficientemente.
Layout Friendly per LSM-Tree: Le chiavi di archiviazione sono prefissate dalla versione del blocco e dall'altezza, consentendo scritture sequenziali a lotti e compattazione efficiente.

3. Contributi Chiave

Identificazione dell'Accoppiamento Span–Proof: Il documento identifica l'accoppiamento esponenziale tra span e fanout nei trie basati su prefissi come la causa radice dell'impossibilità di garantire simultaneamente un'altezza massima limitata e prove compatte.
Istanziazione di MHOT: Adatta HOT per l'uso in ambito blockchain, fornendo una ADS ottimizzata per l'altezza che resiste alle distribuzioni di chiavi avversarie tramite il tracciamento dei bit discriminativi e nodi composti ad alto fanout, utilizzando solo impegni hash standard.
Prove Gerarchiche: Una nuova costruzione Merkle a due livelli che riduce l'overhead della prova per nodo da $O(k)$ a $O(\log k)$ , consentendo prove compatte anche con alto fanout.
HOT Persistente: Risolve il problema aperto del deployment su disco di HOT introducendo un'indicizzazione content-addressable e una pipeline di commit parallela.
Valutazione Completa: Benchmark di MHOT contro MPT, RainBlock e LVMT sotto carichi di lavoro della Ethereum mainnet.

4. Risultati Sperimentali

Valutato su carichi di lavoro della Ethereum mainnet (blocchi 13.5M–13.51M) e dataset sintetici:

Throughput: MHOT raggiunge un throughput di scrittura fino a 9 volte superiore rispetto a MPT (260k ops/s vs 29k ops/s a 100k chiavi) e supera significativamente LVMT e RainBlock.
Amplificazione di Scrittura: MHOT riduce l'amplificazione di scrittura di 4 volte rispetto a MPT (0.9–1.6 vs 2.7–4.8) grazie al flushing a lotti e alla riduzione della profondità dell'albero.
Dimensione della Prova: Le prove di MHOT sono 2 volte più piccole di quelle di MPT (1.1–1.4 KB vs 2.3–2.9 KB) grazie alla struttura della prova gerarchica.
Resistenza all'Attacco Nurgle: In uno scenario di attacco peggiore dove un avversario controlla l'intero budget di gas di un blocco (circa 15.000 inserzioni):
- MPT: Tasso di successo del 99,97% nell'aumentare le profondità delle chiavi target.
- MHOT: Tasso di successo dello 0%. La struttura assorbe le collisioni tramite ristrutturazione interna senza propagare l'aumento della profondità.
Latenza di Verifica: La verifica di MHOT opera in microsecondi (comparabile a MPT), mentre LVMT (che si affida ai pairing KZG) incorre in una latenza di millisecondi (3–4 ordini di grandezza più lenta).

5. Significato e Rivendicazioni

Il documento sostiene che l'ottimalità dell'altezza, piuttosto che l'introduzione di nuove primitive crittografiche, sia l'astrazione chiave per un impegno dello stato blockchain scalabile e resiliente agli attacchi.

Soluzioni Strutturali vs Crittografiche: MHOT dimostra che i compromessi tra altezza dell'albero, dimensione della prova e resistenza agli attacchi possono essere risolti strutturalmente attraverso l'indicizzazione dei bit discriminativi, evitando le assunzioni di fiducia e gli alti costi di verifica degli schemi di impegno vettoriale (Verkle, LVMT).
Immediata Implementabilità: Basandosi esclusivamente su funzioni hash standard (Keccak-256 o Blake3) e sui principi esistenti di autenticazione Merkle, MHOT offre una via per migliorare prestazioni e sicurezza senza richiedere hard fork per cerimonie di setup fidato o cambiamenti nella verifica algebrica.
Resilienza: I risultati suggeriscono che ottimizzare l'altezza e l'adattabilità della struttura dati sia sufficiente per neutralizzare il vettore di attacco Nurgle, che precedentemente sembrava richiedere contromisure economiche o crittografiche.

Gli autori concludono che una progettazione attenta della struttura dati può migliorare fondamentalmente la scalabilità e la robustezza dell'impegno dello stato blockchain, offrendo un'alternativa pratica allo standard attuale MPT.