💻 computer science

Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries

Dit artikel introduceert en analyseert formeel de Parent-Hash DAG (PHDAG) als een constant-tijd, gas-efficiënt alternatief voor incrementele Merkle-trees voor on-chain registers, waarbij wordt aangetoond door middel van theoretische modellering en empirische benchmarks dat PHDAG diepte-invariante kosten behoudt terwijl de kosten van Merkle-trees lineair groeien, wat PHDAG superieur maakt voor alle praktische productie-dieptes.

Oorspronkelijke auteurs: Ian C. Moore, Fernando Paredes Garcia

Gepubliceerd 2026-06-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ian C. Moore, Fernando Paredes Garcia

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 voor dat je een digitale bibliotheek beheert waar mensen nieuwe boeken komen registreren. Elke keer dat iemand een boek toevoegt, moet de bibliotheek haar meesterlijst bijwerken. De vraag die dit artikel stelt is: Wat is de meest efficiënte manier om deze lijst bij te werken naarmate de bibliotheek groeit van een paar boeken naar miljoenen?

De auteurs vergelijken twee verschillende manieren om deze bibliotheek te organiseren: de Incremental Merkle Tree (IMT) en de Parent-Hash DAG (PHDAG).

Hier is de uitsplitsing van hun bevindingen met behulp van eenvoudige analogieën.

1. De twee benaderingen

De Incremental Merkle Tree (IMT): De "Toren van Blokken"

Zie de IMT als een enorme, perfect symmetrische toren van blokken.

Hoe het werkt: Elke keer dat je een nieuw boek (een blad) toevoegt, moet je de toren beklimmen, het blok direct daarboven bijwerken, en dan het blok daarboven, helemaal tot aan de top (de wortel).
De kosten: Hoe hoger de toren wordt, hoe langer de klim. Als de bibliotheek 1.000 boeken heeft, klim je een kort stukje. Als de bibliotheek 1 miljoen boeken heeft, klim je veel hoger.
Het probleem: De kosten (in "gas", wat lijkt op de energievergoeding om de update uit te voeren) gaan omhoog naarmate de bibliotheek groter wordt. Het is also ben je meer aan een taxi betaalt naarmate je verder reist. Ook variëren de kosten: soms moet je veel trappen beklimmen, soms minder, afhankelijk van precies waar je het nieuwe boek plaatst.

De Parent-Hash DAG (PHDAG): De "Keten van Brieven"

Zie de PHDAG als een keten van brieven die tussen vrienden worden doorgegeven.

Hoe het werkt: Wanneer je een nieuw boek toevoegt, schrijf je simpelweg de details van het boek op en schrijf je een briefje met: "Dit boek volgt op dat specifieke vorige boek." Je gooit dit briefje in een openbare brievenbus (het blockchain event log). Je hoeft geen toren te beklimmen of een centrale wortel bij te werken. Je schrijft alleen je briefje en koppelt het aan het verleden.
De kosten: Het maakt niet uit of de bibliotheek 10 boeken of 10 miljoen boeken heeft. Je schrijft altijd dezelfde hoeveelheid tekst en gooit het in dezelfde brievenbus.
Het voordeel: De kosten zijn constant. Het verandert nooit, ongeacht hoe groot de bibliotheek wordt. Het is alsof je een vast bedrag betaalt voor een ansichtkaart, ongeacht hoeveel ansichtkaarten er eerder zijn verstuurd.

2. De grote ontdekking: Wanneer vindt de overstap plaats?

De auteurs hebben de berekeningen gemaakt en echte tests uitgevoerd op een testnetwerk (Base Sepolia) om precies te zien wanneer de "Keten van Brieven" (PHDAG) goedkoper wordt dan de "Toren van Blokken" (IMT).

Het kantelpunt: Ze ontdekten dat de "Toren" alleen goedkoper is wanneer de bibliotheek heel klein is (minder dan ongeveer 7 niveaus diep).
De realiteit: Bijna elk echt systeem dat deze registers gebruikt (zoals privacytools of identiteitssystemen) is veel, veel dieper dan 7 niveaus. Ze zijn meestal 20 tot 40 niveaus diep.
Het resultaat: In de echte wereld is de "Keten van Brieven" (PHDAG) altijd goedkoper en altijd voorspelbaar.

3. Waarom is dit belangrijk? (Het "Variantie"-probleem)

Stel je een bezorgdienst voor die een vaste prijs rekent voor het bijwerken van de bibliotheek.

Met de Toren (IMT): Soms is de update goedkoop, soms is hij duur. Je moet de prijs raden. Als je het fout raadt, kun je geld verliezen aan dure updates. De kosten "schommelen" op en neer.
Met de Keten (PHDAG): De prijs is altijd exact hetzelfde. Er is geen giswerk. De auteurs ontdekten dat de kosten slechts met ongeveer 6 eenheden gas fluctueren (een minuscuul bedrag), wat in de praktijk bijna nul is. Dit maakt het ongelooflijk betrouwbaar voor bedrijven.

4. De "Reconstructie"-superkracht

Er is nog een ander groot verschil.

De Toren (IMT): Om te bewijzen dat een boek bestaat, heb je een specifiek "bewijs" nodig (een bonnetje dat het pad omhoog in de toren laat zien). Als de centrale index breekt, kun je misschien niet meer gemakkelijk de hele toren verifiëren.
De Keten (PHDAG): De volledige geschiedenis staat geschreven in de openbare brievenbus (event logs). Zelfs als de computer die de bibliotheek beheert crasht, kan iedereen door de brievenbus lopen, de brieven in volgorde lezen en de volledige bibliotheek vanaf nul reconstrueren. Het is "onverwoestbaar" omdat de geschiedenis verspreid is over het openbare record, en niet opgeslagen is in één enkele opslaglocatie.

5. De kern van het verhaal

De conclusie van het artikel is dat voor elk grootschalig, echt systeem dat een geschiedenis van gebeurtenissen moet vastleggen (zoals het bewijzen van wie welke digitale kunst bezit of het volgen van toeleveringsketens):

Stop met het gebruiken van de Toren (IMT) voor deze specifieke taak. Het wordt te duur en onvoorspelbaar naarmate het groeit.
Begin met de Keten (PHDAG). Het is goedkoper, de prijs verandert nooit en de gegevens zijn veiliger omdat ze op elk moment uit openbare records kunnen worden gereconstrueerd.

De auteurs stellen voor dat de blockchain-gemeenschap deze "Keten van Brieven"-methode als standaardregel moet adopteren voor alle toekomstige provenance-registers, omdat dit de meest efficiënte en robuuste manier is om grote hoeveelheden gegevens te verwerken.

Technische Samenvatting: Een Kostenanalyse van Constant-Time Append voor On-Chain Registries

Probleemstelling

Provenance-bomen (PT's) zijn append-only gerichte acyclische grafen (DAG's) die worden gebruikt als de datastructuur voor operator-gestuurde provenance-infrastructuur. Hoewel eerder werk beweerde dat de onderliggende append-operatie voor PT's $O(1)$ is in gaskosten—onafhankelijk van de grootte van het register en de diepte van de boom—mist deze claim een formele isolatie als een op zichzelf staande primitief, expliciete constante grenzen, of empirische benchmarking tegen de industriestandaard: de Incremental Merkle Tree (IMT).

De IMT, dominant in zero-knowledge protocollen (bijv. Tornado Cash, Semaphore) en rollup state commitments, biedt beknopte $O(\log N)$ inclusiebewijzen, maar brengt een append-kosten met zich mee die logaritmisch groeit met de boomdiepte ( $\Theta(\log N)$ ). Voor toepassingen waarbij beknopte lidmaatschapsbewijzen niet de primaire query zijn (zoals provenance-registries), is de kostenafweging van de IMT minder gunstig, terwijl het omslagpunt waar een alternatief goedkoper wordt, nog niet rigoureus is vastgesteld.

Methodologie

Het paper isoleert de Parent-Hash Directed Acyclic Graph (PHDAG) als een afzonderlijke primitief en vergelijkt deze met de Incremental Merkle Tree (IMT) via drie lenzen:

Formele Complexiteitsanalyse: De auteurs formaliseren de PHDAG append-operatie en bewijzen dat deze een begrensd aantal EVM-operaties uitvoert, onafhankelijk van de grootte van het register ( $n$ ) of de diepte. Ze contrasteren dit met de frontier-update loop van de IMT, die lineair schaalt met de diepte ( $d$ ).
Stochastische Kostenmodellering: In het besef dat IMT append-kosten variëren op basis van de binaire representatie van de leaf index (Hamming weight), modelleren de auteurs de per-insert gaskosten als een willekeurige variabele. Ze leiden gesloten vorm expressies af voor de gemiddelde waarde en variantie van IMT-kosten onder een uniforme distributie van leaf indices, waarbij onderscheid wordt gemaakt tussen "write levels" (het updaten van de frontier) en "read levels" (traverseren zonder te schrijven).
Empirische Validatie: Onafhankelijke contracten voor beide primitieven werden uitgerold op de Base Sepolia testnet. Experimenten bestonden uit boomdieptes van 1 tot 25.
- IMT: Getest via een "proportional depth sweep" die $\max(d, 2)$ appends per diepte uitvoert om variantie te vangen.
- PHDAG: Getest via een run van 200 appends om de kostenverdeling en variantie te karakteriseren.
- Metrieken: Gasverbruik werd gemeten vanaf transactie-receipts, waarbij de initiële cold-storage initialisatiekosten werden uitgesloten om te focussen op steady-state prestaties.

Belangrijkste Bijdragen

1. Formele Complexiteit van PHDAG

Het paper stelt vast dat de PHDAG append strikt $O(1)$ is in gaskosten.

Mechanisme: Elke append schrijft naar drie voorheen onaangetaste storage slots (cold SSTOREs) die gekoppeld zijn aan een unieke identifier, plus een warm write naar een teller.
Invariantie: De kosten zijn invariant ten opzichte van de globale grootte van het register $n$ en elke notie van boomdiepte. De access list voor een transactie wordt bij de start van elke transactie gereset; aangezien PHDAG telkens naar nieuwe slots schrijft, hangt de kosten alleen af van het vaste aantal operaties, niet van de staat van het contract.
Reconstructie: Het paper bewijst dat de volledige registry gereconstrueerd kan worden vanuit publieke event logs in $O(|V|)$ tijd zonder off-chain afhankelijkheid, aangezien de event stream de canonieke historie draagt.

2. Stochastisch Model voor IMT

De auteurs leiden af dat de IMT per-insert kosten een willekeurige variabele $g$ zijn, afhankelijk van de leaf index $i$ :

Gemiddelde: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$ , waarbij $c_L$ en $c_R$ de marginale kosten van respectievelijk write en read levels zijn.
Variantie: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$ .
Implicatie: Hoewel de relatieve variantie (coefficient of variation) afneemt naarmate de diepte toeneemt, groeit de absolute standaarddeviatie als $\Theta(\sqrt{d})$ , wat operationele onvoorspelbaarheid introduceert voor registri's met een hoge diepte.

3. Empirische Crossover en Validatie

PHDAG Prestaties: Gemeten op een constante 76.276 gas per append (standaarddeviatie $\approx 6$ gas), wat de diepte-invariantie bevestigt.
IMT Prestaties: Kosten groeiden lineair met de diepte.
Crossover Punt: De diepte waarbij PHDAG goedkoper wordt dan IMT werd geïdentificeerd bij $d \approx 6$ tot $7.2$.
- Bij $d=6$ oversteeg de gemeten IMT kosten ( $\approx 78.000$ gas) de PHDAG kosten.
- De lifetime-gemiddelde crossover (uniforme index distributie) wordt berekend op $d^* \approx 7.2$ .

Resultaten

De empirische data valideren de theoretische modellen:

PHDAG vertoont verwaarloosbare variantie en constante kosten over alle geteste dieptes.
IMT vertoont lineaire kostengroei en toenemende absolute variantie met de diepte.
Productiecontext: Elke onderzochte productie-registry (Tornado Cash, Semaphore, zkSync, Scroll, Linea) opereert op dieptes $d \ge 20$ . Bijgevolg opereren al deze systemen momenteel in het regime waar PHDAG strikt goedkoper is en voorspelbare kosten biedt, mits de toepassing geen beknopte inclusiebewijzen vereist.

Betekenis en Claims

Het paper claimt dat de PHDAG primitief de superieure keuze is voor append-only provenance registries waar:

Beknopte lidmaatschapsbewijzen niet vereist zijn: Provenance queries betreffen doorgaans parent-chain traversals of existence checks via een unieke ID, welke ondersteund worden door $O(|V|)$ log-gebaseerde reconstructie in plaats van $O(\log N)$ Merkle bewijzen.
Kostenvoorspelbaarheid cruciaal is: Voor operators die high-volume append services beheren, elimineert de bijna nul-variantie van PHDAG de noodzaak om te budgetteren voor worst-case gas tails, wat een significant operationeel voordeel is ten opzien van IMT bij productie-dieptes.
Robuustheid essentieel is: Het log-canale ontwerp van PHCAG zorgt ervoor dat de historie van de registry onverwoestbaar en reconstructeerbaar is vanuit publieke event logs alleen, onafhankelijk van enige off-chain indexing service of de huidige staat van de contract storage.

De auteurs concluderen dat PHDAG een sterke kandidaat is voor standaardisatie als een uniforme interface voor Ethereum provenance infrastructuur, door een constant-cost, diepte-invariante alternatief te bieden voor de diepte-afhankelijke IMT voor non-ZK toepassingen.