Vergleich zwischen Block Update Digests (BUDs) und traditionellen Merkle-Tries

9. Mai 2026 Kryptowährungen

Block Update Digests (BUDs) stellen eine neuartige Architektur für Membership-Proofs in Blockchain-Systemen dar. Sie reduzieren die Kosten für das Erzeugen und Verifizieren von Nachweisen, indem sie die Abhängigkeit von einem globalen Zustands-Trie aufheben und stattdessen die Schreiblast pro Block in den Fokus rücken. Besonders für hochskalierbare, EVM-äquivalente Chains kann diese Entkopplung zu signifikanten Einsparungen bei Gas- und Speicherverbrauch führen.

Kernidee von Block Update Digests (BUDs)

Ein BUD ist ein kleiner Merkle-Baum, der ausschließlich über die Änderungen eines einzelnen Blocks (oder eines definierten Block-Fensters) aufgebaut wird. Jeder Blattknoten enthält vier Felder: den Schlüssel, den neuen Wert, die aktuelle Block-Nummer und die vorherige Block-Nummer, in der derselbe Schlüssel zuletzt geändert wurde. Dieses vierte Feld bildet die zentrale Innovation, weil es eine Kette von Modifikationen über mehrere BUDs hinweg ermöglicht und damit beweist, dass zwischen zwei BUD-Einträgen keine weiteren Änderungen stattgefunden haben.

Zusätzlich wird jedem Schlüssel-Eintrag im Key-Value-Store ein Metadaten-Header von 8 Byte (plus 1 Byte für die Serialisierungs-Version) hinzugefügt, um die letzte Modifikations-Block-Höhe zu speichern. Validatoren signieren den BUD-Root-Hash und streamen die resultierenden BUDs zu Archive-Nodes, die langfristig die Proof-Infrastruktur bereitstellen.

Vorteile der BUD-Architektur

  • Skalierung mit der Schreiblast pro Block (w) statt mit der Gesamtheit des Zustands (n).
  • Hash-Berechnungen pro Block: O(w·log w) im Vergleich zu O(w·log n) bei globalen Tries (2023, Sei Labs).
  • Reduzierte Speicherbelastung: Validatoren benötigen nur den aktuellen Zustand plus 9 Byte Metadaten pro Eintrag, kein trie-freundliches Layout.
  • Keine unmittelbare Abhängigkeit von einem globalen Zustands-Trie auf dem Konsens-kritischen Pfad.
  • Proof-Generierungskosten und Proof-Größe wachsen logarithmisch mit w, nicht mit n.

SuperBUDs – logarithmische Nachweis-zugriffe

Ein einzelner BUD liefert einen Nachweis nur für den Block, in dem ein Schlüssel geändert wurde. Für ältere Änderungen würde ein Light-Client sonst lineare BUD-Prüfungen benötigen. SuperBUDs komprimieren diese lineare Suche zu einer logarithmischen, indem sie mehrere BUD-Perioden zu einer hierarchischen Struktur zusammenfassen.

Ein SuperBUD der Ebene ℓ deckt e^ℓ Blöcke ab (Standard-Basis e = 2). Auf Block-Höhen, die ein Vielfaches von e^ℓ sind, wird ein SuperBUD erzeugt. Durch das Zusammenführen benachbarter SuperBUDs entsteht ein SuperBUD der nächsten Ebene – ein O(n) Traversal über sortierte Tries reicht aus.

  • Proof-Zugriff: logarithmische Anzahl von Digest-Lookups (⌈log_e d⌉ für d-Block-Alter).
  • Proof-Größe: O(log w) Bytes pro BUD + O(log s) Bytes pro SuperBUD.
  • Latency-Trade-off: Wartezeit bis zum nächsten ausgerichteten SuperBUD-Fenster, linear in der Staleness, dafür kompakte Beweise.

SNARK-Freundlichkeit von BUDs

Die SNARK-Verifizierbarkeit von BUDs ist symmetrisch zu bestehenden globalen Zustands-Bäumen, profitiert jedoch von einer kleineren Baumgröße. Die Komplexität der SNARK-Schaltung beträgt O(log w) (2023, Sei Labs), weil die zu beweisende Merkle-Pfadlänge proportional zur Schreiblast und nicht zur Gesamt-State-Größe ist.

  • Kleinere Schaltung reduziert Kosten und Implementierungs-Komplexität.
  • Ermöglicht kostengünstige SNARK-Verifikation für Cross-Chain-Bridges und Light-Clients.

Vergleich von Kennzahlen

  • Hash-Berechnungen pro Block: O(w·log w) bei BUDs (2023) vs. O(w·log n) bei globalen Tries.
  • Proof-Generierungskosten: O(w·log w) Hashes (Quelle S1, 2023).
  • Proof-Größe: O(log w) Bytes (Quelle S1, 2023).
  • SNARK-Schaltungs-Komplexität: O(log w) (2023).

Risiken und Gegenargumente

Ein zentrales Risiko liegt in der Abhängigkeit von Archive-Nodes, die die Proof-Infrastruktur langfristig bereitstellen. Diese Nodes müssen über lange Zeiträume hinweg verfügbar und ehrlich bleiben, um die Integrität des Systems zu garantieren. Die Verlagerung der Nachweis-Infrastruktur auf Archive-Nodes könnte neue Sicherheits-Anforderungen und Anreiz-Modelle erfordern.

FAQ zu Archive Nodes

  • Frage: Was sind die Hauptanforderungen an Archive Nodes?
    Antwort: Archive Nodes müssen sicherstellen, dass sie über lange Zeiträume hinweg verfügbar und ehrlich bleiben, um die Integrität des Systems zu garantieren.

Fazit

Block Update Digests (BUDs) bieten eine signifikante Verbesserung der Effizienz von Membership-Proofs, indem sie die Komplexität vom globalen Zustands-Trie entkoppeln und stattdessen mit der pro-Block-Schreiblast skalieren. Durch die Kombination von BUDs, SuperBUDs und optionalen Touch-Transaktionen entsteht ein flexibles Design, das sowohl Kosten- als auch Latenz-Sensitivität adressiert. Die geringere Hash- und SNARK-Komplexität führt zu niedrigeren Gas-Gebühren und kleineren Proof-Größen, während die Delegation an Archive-Nodes die Ausführungsebene von trie-bezogenen I/O-Kosten befreit. Trotz offener Fragen zu Anreizen für Archive-Nodes und zu Exklusions-Proof-Edge-Cases stellt BUD-Technologie einen vielversprechenden alternativen Pfad für hoch-durchsatzfähige, EVM-äquivalente Chains dar, die die Skalierbarkeits-Grenzen traditioneller Merkle-Tries überwinden wollen.