💻 computer science

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

Dieses Paper führt den Parent-Hash DAG (PHDAG) ein und analysiert ihn formal als eine zeitkonstante, gas-effiziente Alternative zu inkrementellen Merkle-Trees für On-Chain-Register, wobei durch theoretische Modellierung und empirische Benchmarks nachgewiesen wird, dass der PHDAG eine tiefeninvariante Kostenstruktur beibehält, während die Kosten von Merkle-Trees linear ansteigen, was den PHDAG für alle praktischen Produktionstiefen überlegen macht.

Ursprüngliche Autoren: Ian C. Moore, Fernando Paredes Garcia

Veröffentlicht 2026-06-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ian C. Moore, Fernando Paredes Garcia

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie betreiben eine digitale Bibliothek, in der Menschen neue Bücher registrieren können. Jedes Mal, wenn jemand ein Buch hinzufügt, muss die Bibliothek ihre Masterliste aktualisieren. Die Frage, die dieses Paper stellt, lautet: Was ist der effizienteste Weg, diese Liste zu aktualisieren, während die Bibliothek von wenigen Büchern auf Millionen anwächst?

Die Autoren vergleichen zwei verschiedene Arten, diese Bibliothek zu organisieren: den Incremental Merkle Tree (IMT) und den Parent-Hash DAG (PHDAG).

Hier ist die Aufschlüsselung ihrer Ergebnisse unter Verwendung einfacher Analogien.

1. Die zwei Ansätze

Der Incremental Merkle Tree (IMT): Der „Turm aus Blöcken“

Stellen Sie sich den IMT wie einen riesigen, perfekt symmetrischen Turm aus Blöcken vor.

Wie es funktioniert: Jedes Mal, wenn Sie ein neues Buch (ein Blatt) hinzufügen, müssen Sie den Turm hinaufklettern, den Block direkt darüber aktualisieren, dann den darüber liegenden, bis ganz nach oben (zur Wurzel).
Der Preis: Je höher der Turm wird, desto länger ist der Aufstieg. Wenn die Bibliothek 1.000 Bücher hat, klettern Sie ein kurzes Stück. Wenn sie 1 Million Bücher hat, klettern Sie viel höher.
Das Problem: Die Kosten (in „Gas“, was einer Art Energiegebühr für die Durchführung der Aktualisierung entspricht) steigen, wenn die Bibliothek wächst. Es ist wie eine Taxifahrt, bei der man mehr bezahlt, je weiter man fährt. Außerdem variieren die Kosten: Manchmal muss man viele Stufen steigen, manchmal weniger, je nachdem, wo genau man das neue Buch platziert.

Der Parent-Hash DAG (PHDAG): Die „Kette aus Briefen“

Stellenchen Sie sich den PHDAG wie eine Kette von Briefen vor, die zwischen Freunden hin- und hergereicht werden.

Wie es funktioniert: Wenn Sie ein neues Buch hinzufügen, schreiben Sie einfach dessen Details auf und fügen eine Notiz hinzu, die besagt: „Dieses Buch folgt auf jenes spezifische vorherige Buch.“ Sie werfen diese Notiz in einen öffentlichen Briefkasten (den Blockchain-Event-Log). Sie müssen keinen Turm erklimmen oder eine zentrale Wurzel aktualisieren. Sie schreiben einfach Ihre Notiz und verknüpfen sie mit der Vergangenheit.
Der Preis: Es spielt keine Rolle, ob die Bibliothek 10 oder 10 Millionen Bücher hat. Sie schreiben immer die gleiche Menge Text und werfen ihn in denselben Briefkasten.
Der Vorteil: Die Kosten sind konstant. Es ändert sich nie, egal wie groß die Bibliothek wird. Es ist wie die Zahlung einer Pauschale für eine Postkarte, unabhängig davon, wie viele Postkarten zuvor versendet wurden.

2. Die große Entdeckung: Wann findet der Wechsel statt?

Die Autoren haben die Mathematik betrieben und reale Tests auf einem Testnetzwerk (Base Sepolia) durchgeführt, um genau zu sehen, wann die „Kette aus Briefen“ (PHDAG) günstiger ist als der „Turm aus Blöcken“ (IMT).

Der Wendepunkt: Sie fanden heraus, dass der „Turm“ nur dann günstiger ist, wenn die Bibliothek winzig ist (weniger als etwa 7 Ebenen tief).
Die Realität: Fast jedes reale System, das diese Register verwendet (wie etwa Datenschutzwerkzeuge oder Identitätssysteme), ist viel, viel tiefer als 7 Ebenen. Sie sind normalerweise 20 bis 40 Ebenen tief.
Das Ergebnis: In der realen Welt ist die „Kette aus Briefen“ (PHDAG) immer günstiger und immer vorhersehbar.

3. Warum ist das wichtig? (Das „Varianz“-Problem)

Stellen Sie sich einen Lieferdienst vor, der eine feste Gebühr für die Aktualisierung der Bibliothek berechnet.

Mit dem Turm (IMT): Manchmal ist die Aktualisierung günstig, manchmal teuer. Sie müssen den Preis erraten. Wenn Sie falsch raten, verlieren Sie vielleicht Geld bei teuren Aktualisierungen. Die Kosten „zittern“ auf und ab.
Mit der Kette (PHDAG): Der Preis ist immer exakt gleich. Es gibt kein Raten. Die Autoren fanden heraus, dass die Kosten um nur etwa 6 Einheiten Gas schwanken (eine winzige Menge), was praktisch null ist. Dies macht es unglaublich zuverlässig für Unternehmen.

4. Die „Rekonstruktions“-Superkraft

Es gibt noch einen anderen wesentlichen Unterschied.

Der Turm (IMT): Um zu beweisen, dass ein Buch existiert, benötigen Sie einen spezifischen „Nachweis“ (einen Beleg, der den Pfad den Turm hinauf zeigt). Wenn der zentrale Index ausfällt, könnten Sie unter Umständen die Fähigkeit verlieren, den gesamten Turm einfach zu verifizieren.
Die Kette (PHDAG): Die gesamte Historie ist im öffentlichen Briefkasten (Event Logs) geschrieben. Selbst wenn der Computer, der die Bibliothek verwaltet, abstürzt, kann jeder durch den Briefkasten gehen, die Briefe in der richtigen Reihenfolge lesen und die gesamte Bibliothek von Grund auf neu aufbauen. Sie ist „unzerstörbar“, weil die Historie über die öffentliche Aufzeichnung verstreut ist und nicht in einem einzigen Speicherplatz eingeschlossen ist.

5. Das Fazentelement

Das Paper kommt zu dem Schluss, dass für jedes große, reale System, das eine Historie von Ereignissen aufzeichnen muss (wie etwa den Nachweis, wem welche digitale Kunst gehört, oder die Verfolgung von Lieferketten):

Hören Sie auf, den Turm (IMT) für diese spezifische Aufgabe zu verwenden. Er wird zu teuer und unvorhersehbar, wenn er wächst.
Beginnen Sie mit der Kette (PHDAG). Sie ist günstiger, der Preis ändert sich nie und die Daten sind sicherer, da sie jederzeit aus öffentlichen Aufzeichnungen wiederhergestellt werden können.

Die Autoren schlagen vor, dass die Blockchain-Community diese „Kette aus Briefen“-Methode als Standardregel für alle zukünftigen Provenienz-Register übernehmen sollte, da dies der effizienteste und robusteste Weg ist, um große Mengen an Daten zu verarbeiten.

Technisches Resümee: Eine Kostenanalyse der konstanten Zeitkomplexität beim Anhängen an On-Chain-Register

Problemstellung

Provenienz-Bäume (Provenance Trees, PTs) sind Append-only-gerichtete azyklische Graphen (DAGs), die als Datensubstrat für Operator-gesteuerte Provenienz-Infrastrukturen dienen. Während frühere Arbeiten behaupteten, dass die zugrunde liegende Append-Operation für PTs eine $O(1)$ -Gaskosten-Komplexität aufweist – unabhängig von der Registergröße und der Baumtiefe –, fehlte dieser Anspruch als isoliertes eigenständiges Primitiv, mit expliziten konstanten Schranken oder empirischer Benchmarking-Validierung gegenüber dem Industriestandard: dem Incremental Merkle Tree (IMT).

Der IMT, der in Zero-Knowledge-Protokollen (z. B. Tornado Cash, Semaphore) und Rollup-State-Commitments dominiert, bietet sukzente $O(\log N)$ -Inklusionsbeweise, verursacht jedoch eine Append-Kostenstruktur, die logarithmisch mit der Baumtiefe ( $\Theta(\log N)$ ) wächst. Für Anwendungen, bei denen sukzente Mitgliedschaftsbeweise nicht die primäre Abfrage sind (wie bei Provenienz-Registern), ist der Kostentrade-off des IMT weniger günstig; dennoch wurde der Crossover-Punkt, an dem eine Alternative kostengünstiger wird, bisher nicht rigoros etabliert.

Methodik

Das Paper isoliert den Parent-Hash Directed Acyclic Graph (PHDAG) als ein distinktes Primitiv und vergleicht ihn mit dem Incremental Merkle Tree (IMT) durch drei Perspektiven:

Formale Komplexitätsanalyse: Die Autoren formalisieren die PHDAG-Append-Operation und beweisen, dass diese eine begrenzte Anzahl von EVM-Operationen ausführt, die unabhängig von der Registergröße ( $n$ ) oder der Tiefe ist. Sie kontrastieren dies mit der Frontier-Update-Schleife des IMT, welche linear mit der Tiefe ( $d$ ) skaliert.
Stochastische Kostenmodellierung: Da die IMT-Append-Kosten je nach binärer Repräsentation des Leaf-Index (Hamming-Gewicht) variieren, modellieren die Autoren die Kosten pro Einfügung als Zufallsvariable. Sie leiten geschlossene Ausdrücke für den Erwartungswert und die Varianz der IMT-Kosten unter einer Gleichverteilung der Leaf-Indizes ab und unterscheiden dabei zwischen „Write Levels“ (Aktualisierung der Frontier) und „Read Levels“ (Traversierung ohne Schreiben).
Empirische Validierung: Unabhängige Kontrakte für beide Primitive wurden auf dem Base Sepolia Testnet bereitgestellt. Die Experimente deckten Baumtiefen von 1 bis 25 ab.
- IMT: Getestet mittels einer „proportionalen Tiefen-Sweep“, die $\max(d, 2)$ Appends pro Tiefe durchführt, um die Varianz zu erfassen.
- PHHDAG: Getestet über einen 200-Append-Lauf zur Charakterisierung der Kostenverteilung und Varianz.
- Metriken: Der Gasverbrauch wurde aus den Transaktions-Receipts gemessen, wobei die initialen Cold-Storage-Initialisierungskosten ausgeschlossen wurden, um den Fokus auf die Steady-State-Performance zu legen.

Zentrale Beiträge

1. Formale Komplexität des PHDAG

Das Paper stellt fest, dass der PHDAG-Append strikt $O(1)$ in den Gaskosten ist.

Mechanismus: Jeder Append schreibt in drei zuvor unberührte Storage-Slots (Cold SSTOREs), die durch eine eindeutige Kennung adressiert werden, plus einen Warm Write zu einem Counter.
Invarianz: Die Kosten sind invariant gegenüber der globalen Registergröße $n$ und jeglicher Vorstellung von Baumtiefe. Die Access List für eine Transaktion wird zu Beginn jeder Transaktion zurückgesetzt; da der PHDAG bei jedem Append in neue Slots schreibt, hängen die Kosten nur von der fixen Anzahl der Operationen ab, nicht vom Zustand des Kontrakts.
Rekonstruktion: Das Paper beweist, dass das vollständige Register in $O(|V|)$ Zeit aus öffentlichen Event-Logs rekonstruiert werden kann, ohne Off-Chain-Abhängigkeit, da der Event-Stream die kanonische Historie trägt.

2. Stochastisches Modell für den IMT

Die Autoren leiten her, dass die IMT-Kosten pro Einfügung eine Zufallsvariable $g$ sind, die vom Leaf-Index $i$ abhängt:

Erwartungswert: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$ , wobei $c_L$ und $c_R$ die marginalen Kosten von Write- und Read-Levels sind.
Varianz: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$ .
Implikation: Während die relative Varianz (Variationskoeffizient) mit zunehmender Tiefe abnimmt, wächst die absolute Standardabweichung als $\Theta(\sqrt{d})$ , was eine operative Unvorhersehbarkeit für Register mit hoher Tiefe einführt.

3. Empirischer Crossover und Validierung

PHDAG-Performance: Gemessen bei konstanten 76.276 Gas pro Append (Standardabweichung $\approx 6$ Gas), was die Tiefen-Invarianz bestätigt.
IMT-Performance: Die Kosten stiegen linear mit der Tiefe.
Crossover-Punkt: Die Tiefe, bei der der PHDAG günstiger als der IMT wird, wurde bei $d \approx 6$ bis $7,2$ identifiziert.
- Bei $d=6$ überstiegen die gemessenen IMT-Kosten ( $\approx 78.000$ Gas) die PHDAG-Kosten.
- Der lebenszeitliche Durchschnitts-Crossover (bei Gleichverteilung der Indizes) wird auf $d^* \approx 7,2$ berechnet.

Ergebnisse

Die empirischen Daten validieren die theoretischen Modelle:

PHDAG weist eine vernachlässigbare Varianz und konstante Kosten über alle getesteten Tiefen auf.
IMT zeigt ein lineares Kostenwachstum und eine zunehmende absolute Varianz.
Produktionskontext: Jedes untersuchte Produktionsregister (Tornado Cash, Semaphore, zkSync, Scroll, Linea) operiert bei Tiefen von $d \ge 20$ . Folglich operieren alle derartigen Systeme derzeit in dem Bereich, in dem der PHDAG strikt günstiger ist und vorhersagbare Kosten bietet, sofern die Anwendung keine sukzenten Inklusionsbeweise erfordert.

Bedeutung und Ansprüche

Das Paper behauptet, dass das PHDAG-Primitiv die überlegene Wahl für Append-only Provenienz-Register ist, wenn:

Sukzente Mitgliedschaftsbeweise nicht erforderlich sind: Provenienz-Abfragen beinhalten typischerweise Parent-Chain-Traversierung oder Existenzprüfungen durch eindeutige IDs, was durch $O(|V|)$ Log-basierte Rekonstruktion unterstützt wird, statt durch $O(\log N)$ Merkle-Beweise.
Kostenvorhersehbarkeit kritisch ist: Für Operatoren, die Hochvolumen-Append-Services verwalten, eliminiert die nahezu null Varianz des PHDAG die Notwendigkeit, für Worst-Case-Gas-Tails zu budgetieren – ein signifikanter operativer Vorteil gegenüber dem IMT bei Produktions-Tiefen.
Robustheit oberste Priorität hat: Das log-kanonische Design des PHDAG stellt sicher, dass die Historie des Registers unzerstörbar und allein aus den öffentlichen Event-Logs rekonstruierbar ist, unabhängig von externen Indexing-Services oder dem aktuellen State des Kontrakts.

Die Autoren kommen zu dem Schluss, dass PHHDAG ein starker Kandidat für die Standardisierung als einheitliche Schnittstelle für Ethereum-Provenienz-Infrastruktur ist, da es eine konstant kostenbasierte, tiefen-invariante Alternative zum tiefenabhängigen IMT für Nicht-ZK-Anwendungen bietet.