Vai al contenuto
Crypto.world

Ricerca

DAG basato sugli hash dei nodi genitori: analisi dei costi delle aggiunte in tempo costante nei registri on-chain

Gli alberi di provenienza sono grafi aciclici orientati a sola aggiunta, formati da registrazioni di artefatti ancorate a una blockchain pubblica. Sono stati introdotti di recente come struttura dati…

DAG basato sugli hash dei nodi genitori: analisi dei costi delle aggiunte in tempo costante nei registri on-chain
arXiv
2606.09593
Pubblicato
2026-06-08
Autori
Ian C. Moore, Fernando Paredes Garcia

Abstract degli autori

Gli alberi di provenienza sono grafi aciclici orientati a sola aggiunta, formati da registrazioni di artefatti ancorate a una blockchain pubblica. Sono stati introdotti di recente come struttura dati alla base di un’infrastruttura di provenienza il cui accesso è controllato dagli operatori. La loro caratteristica strutturale è il grafo aciclico orientato basato sugli hash dei nodi genitori (PHDAG), in cui ogni aggiunta comporta un numero costante di scritture in posizioni di archiviazione mai utilizzate prima. Finora questo schema non era stato isolato come primitiva autonoma, delimitato formalmente con costanti esplicite né confrontato mediante benchmark con l’alternativa standard, l’albero di Merkle incrementale (IMT). Formalizziamo il costo in gas dell’aggiunta a un PHDAG come O(1), indipendentemente dalle dimensioni del registro e dalla profondità dell’albero, e sviluppiamo un modello stocastico dei costi dell’IMT in cui il costo di ciascun inserimento è una variabile aleatoria che dipende dall’indice della foglia. Ne ricaviamo espressioni in forma chiusa per la media e la varianza. Verifichiamo empiricamente entrambe le analisi su Base Sepolia per profondità dell’albero da 1 a 25. Il costo del PHDAG risulta indipendente dalla profondità e pari a 76.276 gas (con una deviazione standard di circa 6 gas), mentre quello dell’IMT cresce linearmente con la profondità. La soglia al di sotto della quale l’IMT è meno costoso si colloca ben al di sotto della profondità di tutti i registri in produzione esaminati. Dimostriamo inoltre che il registro può essere ricostruito dai log pubblici degli eventi, senza dover riporre fiducia in terzi né dipendere da risorse off-chain, in tempo lineare.

Il riassunto di questo paper è disponibile solo in inglese: leggilo nella pagina inglese.

Leggi il paper originale su arXiv