Sintesi Tecnica: Un'Analisi dei Costi dell'Append a Tempo Costante per i Registri On-Chain

Definizione del Problema

Gli alberi di provenienza (PT) sono grafi aciclici diretti (DAG) di tipo append-only utilizzati come substrato dati per l'infrastruttura di provenienza con controllo degli operatori. Mentre lavori precedenti sostenevano che l'operazione di append sottostante per i PT fosse $O(1)$ in termini di costo del gas — indipendente dalla dimensione del registro e dalla profondità dell'albero — tale affermazione mancava di un isolamento formale come primitiva autonoma, di limiti espliciti costanti o di una validazione empirica rispetto allo standard del settore: l'Incremental Merkle Tree (IMT).

L'IMT, dominante nei protocolli zero-knowledge (ad es. Tornado Cash, Semaphore) e nei commitment di stato degli rollup, offre prove di inclusione succinte $O(\log N)$ ma incorre in un costo di append che cresce logaritmicamente con la profondità dell'albero ($\Theta(\log N)$). Per le applicazioni in cui le prove di appartenenza succinte non sono la query primaria (come i registri di provenienza), il compromesso di costo dell'IMT è meno favorevole, sebbene il punto di incrocio in cui un'alternativa diventa più economica non sia stato rigorosamente stabilito.

Metodologia

Il documento isola il Parent-Hash Directed Acyclic Graph (PHDAG) come una primitiva distinta e lo confronta con l'Incremental Merkle Tree (IMT) attraverso tre lenti:

1. Analisi della Complessità Formale: Gli autori formalizzano l'operazione di append del PHDAG, dimostrando che viene eseguita un numero limitato di operazioni EVM indipendentemente dalla dimensione del registro ($n$) o dalla profondità. Essi mettono a confronto questo con il ciclo di aggiornamento della frontiera dell'IMT, che scala linearmente con la profondità ($d$).
2. Modellazione Stocastica dei Costi: Riconoscendo che i costi di append dell'IMT variano in base alla rappresentazione binaria dell'indice della foglia (peso di Hamming), gli autori modellano il costo di inserimento come una variabile casuale. Derivano espressioni a forma chiusa per la media e la varianza dei costi IMT sotto una distribuzione uniforme degli indici delle foglie, distinguendo tra "livelli di scrittura" (aggiornamento della frontiera) e "livelli di lettura" (traversamento senza scrittura).
3. Validazione Empirica: Contratti indipendenti per entrambe le primitive sono stati distribuiti sulla testnet Base Sepolia. Gli esperimenti hanno coperto profondità d'albero da 1 a 25.
   • IMT: Testato tramite uno "sweep di profondità proporzionale" eseguendo $\max(d, 2)$ append per ogni profondità per catturare la varianza.
   • PHDAG: Testato tramite una run di 200 append per caratterizzare la distribuzione dei costi e la varianza.
   • Metriche: Il consumo di gas è stato misurato dai ricevute delle transazioni, escludendo i costi iniziali di inizializzazione dello storage a freddo per concentrarsi sulle prestazioni in stato stazionario.

Contributi Chiave

1. Complessità Formale del PHDAG

Il documento stabilisce che l'append del PHDAG è strettamente $O(1)$ in termini di costo del gas.

• Meccanismo: Ogni append scrive in tre slot di storage precedentemente non toccati (SSTORE a freddo) identificati da un ID unico, oltre a una scrittura "warm" su un contatore.
• Invarianza: Il costo è invariante rispetto alla dimensione globale del registro $n$ e a qualsiasi nozione di profondità dell'albero. La access list per una transazione viene resettata all'inizio di ogni transazione; poiché il PHDAG scrive in nuovi slot ogni volta, il costo dipende solo dal numero fisso di operazioni, non dallo stato del contratto.
• Ricostruzione: Il documento prova che il registro completo può essere ricostruito da log di eventi pubblici in tempo $O(|V|)$ senza dipendenze off-chain, poiché lo stream di eventi trasporta la cronologia canonica.

2. Modello Stocastico per l'IMT

Gli autori derivano che il costo per inserimento dell'IMT è una variabile casuale $g$ dipendente dall'indice della foglia $i$:

• Media: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$, dove $c_L$ e $c_R$ sono i costi marginali rispettivamente dei livelli di scrittura e di lettura.
• Varianza: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$.
• Implicazione: Sebbene la varianza relativa (coefficiente di variazione) diminuisca all'aumentare della profondità, la deviazione standard assoluta cresce come $\Theta(\sqrt{d})$, introducendo imprevedibilità operativa per registri ad alta profondità.

3. Validazione e Punto di Incrocio Empirico

• Prestazioni PHDАG: Misurate a un costo costante di 76.276 gas per append (deviazione standard $\approx 6$ gas), confermando l'invarianza rispetto alla profondità.
• Prestazioni IMT: I costi sono cresciuti linearmente con la profondità.
• Punto di Incrocio: La profondità alla quale il PHDAG diventa più economico dell'IMT è stata identificata a $d \approx 6$ a $7.2$.
  • A $d=6$, il costo misurato dell'IMT ($\approx 78.000$ gas) ha superato il costo del PHDAG.
  • Il punto di incrocio medio nel tempo di vita (distribuzione uniforme degli indici) è calcolato a $d^* \approx 7.2$.

Risultati

I dati empirici validano i modelli teorici:

• PHDAG mostra una varianza trascurabile e un costo costante attraverso tutte le profondità testate.
• IMT mostra una crescita lineare dei costi e una varianza assoluta crescente con la profondità.
• Contesto di Produzione: Ogni registro di produzione esaminato (Tornado Cash, Semaphore, zkSync, Scroll, Linea) opera a profondità $d \ge 20$. Di conseguenza, tutti tali sistemi operano attualmente nel regime in cui il PHDAG è strettamente più economico e offre costi prevedibili, a pato che l'applicazione non richieda prove di appartenenza succinte.

Significato e Rivendicazioni

Il documento sostiene che la primitiva PHDAG è la scelta superiore per i registri di provenienza append-only dove:

1. Le prove di appartenenza succinte non sono richieste: Le query di provenienza tipicamente coinvolgono la traversazione della catena dei genitori o controlli di esistenza tramite ID univoco, che sono supportati da una ricostruzione basata su log in $O(|V|)$ piuttosto che da prove Merkle $O(\log N)$.
2. La prevedibilità dei costi è critica: Per gli operatori che gestiscono servizi di append ad alto volume, la varianza quasi nulla del PHDAG elimina la necessità di pianificare per i casi limite (worst-case gas tails), un vantaggio operativo significativo rispetto all'IMT alle profondità di produzione.
3. La robustezza è fondamentale: Il design log-canonico del PHDAG assicura che la cronologia del registro sia indistruttibile e ricostruibile dai soli log di eventi pubblici, indipendentemente da qualsiasi servizio di indicizzazione off-chain o dallo stato attuale dello storage del contratto.

Gli autori concludono che il PHDAG è un forte candidato per la standardizzazione come interfaccia uniforme per l'infrastruttura di provenienza su Ethereum, offrendo un'alternativa a costo costante e invariante rispetto alla profondità rispetto all'IMT dipendente dalla profondità per applicazioni non ZK.