GHOSTDAG verstehen

Im Folgenden beginnen wir die Übersetzung des Buches GHOSTDAG verstehen von Shai Wyborski, welches auf KASMedia veröffentlicht wird, das dir einen tiefgehenden technischen Einblick in Kaspa bietet. Das Buch ist in verschiedene Kapitel und Beiträge untergliedert, deren Übersetzungen schrittweise bereitgestellt werden. Sobald ein neuer Abschnitt des Buches übersetzt ist, wird er im Inhaltsverzeichnis verlinkt.

Shai (Deshe) Wyborski

GHOSTDAG VERSTEHEN: INHALTSVERZEICHNIS

GHOSTDAG verstehen ist ein offenes Buch, das ich im Juli 2024 zu schreiben begann. Das Buch ist in fünf Teile gegliedert:

• Die Grundlagen von dezentralem Konsens, Proof of Work, Blockchains und BlockDAGs
• Sichere Reduzierung des Speicherbedarfs durch Pruning, MLS-Mining und Harmonische Speichermasse
• Gebührenmärkte in BlockDAGs
• Selbstskalierung (auch bekannt als Parameterlosigkeit) und das DAGKnight-Protokoll
• Verschiedenes

Einige der Abschnitte sind mit einem Sternchen (*) versehen, um darauf hinzuweisen, dass sie ein wenig mehr mathematische/technische Reife erfordern (obwohl ich sicher bin, dass die meisten von ihnen auch von ausreichend hartnäckigen Laien verstanden werden könnten). Nicht mit Sternen versehene Abschnitte stützen sich niemals auf mit Sternen versehene Abschnitte. Abschnitte, die besonders knifflig sind oder Mathematik auf Bachelorniveau erfordern, sind mit zwei Sternen versehen.

Im mathematischen Anhang sammle ich halbformale Einführungen in mathematische Themen, die sich aus der Diskussion ergeben. Ich habe mich bemüht, viele der Motivationen und Beispiele aus der Welt der Kryptowährungen zu beziehen, so dass der Anhang hoffentlich auch für Leser von Nutzen ist, die diese Themen bereits kennen.

Nachfolgend findest du eine vorläufige Übersicht über den Inhalt von GHOSTDAG verstehen, wobei die Links zu den einzelnen Teilen hinzugefügt werden, sobald sie geschrieben sind.

Vorwort und Einführung

Teil I: Blockchains und BlockDAGs

Bevor wir über GHOSTDAG sprechen können, müssen wir BlockDAGs verstehen, und dafür sollten wir besser (obwohl wir das nicht unbedingt müssen) ein solides Verständnis von Blockchains haben. Blockchains sind zwar die simpelste Form einer BlockDAG, bieten aber dennoch eine reichhaltige, nuancierte und oft verwirrende Theorie. Ein solides Verständnis von Blockchains bereitet uns nicht nur darauf vor, die komplizierteren BlockDAGs in Angriff zu nehmen, sondern bietet auch einen hervorragenden Vergleichspunkt. Ein Anker des Verständnisses. Es ist viel einfacher, BlockDAG-Protokolle zu beurteilen, wenn wir sie mit Blockchains vergleichen können und fragen, was sie verlieren, was sie verbessern und was weitgehend gleich bleibt. Die Einführung von Blockchain-Konzepten als Sprungbrett zum Verständnis ihrer Äquivalente im BlockDAG-Umfeld wird sich wie ein roter Faden durch die gesamte Serie ziehen, daher ist es wichtig, eine solide Grundlage zu schaffen.

• Kapitel 1A: BFT vs. PoW. Zum Einstimmen und Aufwärmen beginnen wir dort, wo die meisten Erklärungen zum Thema Konsens beginnen: mit dem Problem der Byzantinischen Generäle. Dieses Problem wird von vielen als die Geburtsstätte der Konsenstheorie angesehen. Im Anschluss daran werden wir Proof-of-Work einführen und mit einem Vergleich abschließen.

Beitrag 1: Byzantinische Fehlertoleranz
Beitrag 2: Proof-of-Work
Beitrag 3: BFT vs. PoW
Übungen

• Kapitel 1B: Das Blockchain-Paradigma. Das Blockchain-Paradigma gibt uns eine konkrete Möglichkeit, das vage Problem der „Konsensfindung“ zu formulieren. Wir können von den meisten Details abstrahieren und uns auf das Problem der Auswahl einer Kette beschränken.

Beitrag 1: Einige Hintergrundinformationen
Beitrag 2: Die Kettenauswahlregel
Beitrag 3: Die Regel der längsten Kette und GHOST
Übungen

• Kapitel 1C: Sicherheit einer Blockchain. Nachdem wir nun wissen, was eine Kettenauswahlregel ist, müssen wir verstehen, was eine Kettenauswahlregel gut macht. Nach einer kurzen Diskussion darüber, wie Kryptographen über Sicherheitsbegriffe denken, werden wir die wichtigsten Sicherheitsbegriffe für eine Blockchain vorstellen.

Beitrag 1: Was ist Sicherheit?
Beitrag 2: Sicherheit

Beitrag 3: Lebendigkeit

Beitrag 4: Bestätigungszeiten

Beitrag 5: Skizze des Bitcoin-Sicherheitsbeweises*
Beitrag 6: Egoistisches Mining*

Übungen

• Kapitel 1D: Das BlockDAG-Paradigma. Das BlockDAG-Paradigma ist eine Verallgemeinerung des Blockchain-Paradigmas. Der Baum wird durch eine DAG genannte Struktur ersetzt, die es jedem Block erlaubt, auf mehrere andere Blöcke zu zeigen. Die Kettenauswahlregel wird durch eine Ordnungsregel ersetzt, die Konflikte auflöst und dabei alle Blöcke beibehält. Wir stellen das Paradigma vor und sehen uns einige wichtige Beispiele an.

Beitrag 1: DAGs und topologische Sortierung
Beitrag 2: Das BlockDAG-Paradigma
Beitrag 3: Sicherheit und Lebendigkeit
Beitrag 4: Kettenauswahlregeln DAGifizieren
Beitrag 5: SPECTRE

• Kapitel 1E: GHOSTDAG. Endlich sind wir so weit, den Mann der Stunde vorzustellen. Wir werden das GHOSTDAG-Protokoll vorstellen und alle Erkenntnisse und Grundlagen, die wir in den vorherigen Episoden entwickelt haben, nutzen, um es besser zu verstehen.

Beitrag 1: PHANTOM
Beitrag 2: GHOSTDAG
Beitrag 3: Skizze des GHOSTDAG-Sicherheitsnachweises*
Beitrag 4: GHOSTDAG-Bestätigungszeiten

Teil II: Verringerung der Speicherkosten

(Die meisten Beiträge in dieser Serie basieren auf einem Hauptvortrag, den ich auf dem DAG-DLT-Workshop am ersten Tag des Juni 2024 gehalten habe, der leider nicht aufgezeichnet wurde. Der aktuelle Teil basiert jedoch auf meinem Workshop über die Kontrolle von Speicher in erlaubnisfreien Systemen mit hohem Durchsatz auf der NBX Warschau 2024, der glücklicherweise aufgezeichnet wurde.)

Ein System mit hohem Durchsatz wie Kaspa kann nicht auf Architekturen zurückgreifen, mit denen Systeme mit niedrigem Durchsatz wie Bitcoin (gerade noch) durchkommen. Insbesondere hat Kaspa im Gegensatz zu Bitcoin nicht das Privileg, das gesamte Ledger zu speichern. Oberflächlich betrachtet mag es so aussehen, als ob der Verzicht auf das Ledger einen Kompromiss in Sachen Sicherheit darstellt. Überraschenderweise ist dies jedoch nicht der Fall. Ein elegantes Protokoll von Aggelos Kiayias, Nikos Leonardos und Dionysis Zindros ermöglicht es uns, die gleiche Sicherheit zu genießen und dabei nur einen Bruchteil des Ledgers zu speichern. Die Anpassung dieses Protokolls an DAGs ist jedoch trügerisch schwierig.

Ein weiterer Grund zur Sorge ist die Datenaufblähung. Insbesondere die organische und konfliktreiche Vergrößerung des UTXO-Sets. Kaspa geht mit diesem Problem auf eine neuartige Weise um, die wir Harmonische Blockmasse nennen. In Kaspa Improvement Proposal 9 haben wir eine auf Kaspa zugeschnittene Spezifikation vorgelegt. Im Gegensatz zum größten Teil des Buches ist diese Idee jedoch äußerst allgemein und kann an jeden DLT angepasst werden, von UTXO-PoW-DAGs bis zu Second Layern über PoS-Blockchains. Dennoch passt sie aus mehreren Gründen in dieses Buch: eine solche Lösung wird für Systeme mit hohem Durchsatz benötigt, sie wurde durch die Arbeit an Kaspa erfunden und sie ist einfach wirklich sehr cool.

Die Beiträge in diesem Teil sind in etwa wie folgt aufgebaut:

• Kapitel 2A: Hintergrund. Wir untersuchen die Probleme, die wir lösen müssen, wie sie traditionell gelöst werden, was bei hohem Durchsatz schief läuft und was wir von unseren Lösungen erwarten sollten.

Beitrag 1: Das unveränderliche Ledger
Beitrag 2: Datenaufblähung
Beitrag 3: Sozialer vs. Kryptographischer Konsens

• Kapitel 2B: Pruning (Beschneiden) von Blockdaten. Zunächst betrachten wir das Problem der Entfernung von Blockdaten unter Beibehaltung der Header. Wir erklären, warum dieses Problem für Chains trivial, für DAGs jedoch extrem schwierig ist. Anschließend untersuchen wir eine von Yonatan Sompolinsky, Michael Sutton und mir vorgeschlagene Lösung.

Beitrag 1: Pruning von Daten in Chains
Beitrag 2: Eine Sicherheitsdefinition, naive Versuche und Kletterangriffe
Beitrag 3: Die Pruning-Regeln für GHOSTDAGs
Beitrag 4: Skizze eines Sicherheitsnachweises*
Beitrag 5: Kryptographische Belege

• Kapitel 2C: Pruning von Block-Headern. Wir stellen das Protokoll von Kiayias et. al und eine Adaption davon auf DAGs von Ori Newman und Yonatan Sompolinsky vor.

Beitrag 1: Nicht-interaktive PoW-Beweise (NiPoPoWs; Non-Interactive Proofs of PoW)
Beitrag 2: Das MLS-Protokoll (Mining in Logarithmic Space; Mining im logarithmischen Raum)

Beitrag 3: Anpassung an DAGs

Beitrag 4: Skizze eines Sicherheitsbeweises*

• Kapitel 2D: Entschärfung der Datenaufblähung. Wir diskutieren das Datenaufblähungsproblem und existierende Lösungen und fahren fort mit der Betrachtung des Harmonischen Speichermassen-Ansatzes, der von Yonatan Somolinsky, Shai Wyborski und Michael Sutton entwickelt wurde.

Beitrag 1: Das Problem der Datenaufblähung
Beitrag 2: Bestehende Lösungen: State Sharding, Demurrage und Stateless Clients

Beitrag 3: Die Harmonische Massen-Formel und ihre Konsequenzen

Beitrag 4: Skizze eines Sicherheitsnachweises*
Beitrag 5: Mikrotransaktionen und Zusammensetzen von UTXOs

Teil III: der Gebührenmarkt

Eine häufige Befürchtung in Bezug auf DAGs ist, dass sie den Durchsatz nicht wirklich erhöhen, da parallele Blöcke eine Menge Redundanzen enthalten können. Was nützt es, zehn Blöcke parallel zu haben, wenn sie alle dieselbe Transaktion enthalten?
Offensichtlich ist dies nicht nur kein Problem, sondern die Dynamik eines Gebührenmarktes auf einer BlockDAG hat einige wundersame Eigenschaften, die viele der unerwünschten Phänomene beseitigen, die wir in Blockchains sehen.

• Kapitel 3A: Sicherheitsbudget und Gebührenmärkte. Wir diskutieren die Rolle von Gebühren in PoW. Dann untersuchen wir die Gebührenmärkte von Blockchains und die unerwünschten Dynamiken, die sie hervorbringen.

Beitrag 1: Das Sicherheitsbudgetproblem
Beitrag 2: Rationalität der Spieler und Gleichgewichte der Märkte
Beitrag 3: Unterbietungswettlauf vs. Bietergefechte, Bitcoins höllische Dichotomie

• Kapitel 3B: Transaktionsauswahl-Spiele. Wie Yoad Lewenberg, Yonatan Sompolinsky und Aviv Zohar in ihrem Paper von 2015 Inclusive Block Chain Protocols beschreiben, ist die Gleichgewichtsstrategie im Gebührenmarkt bei BlockDAGs probabilistischer Natur. Wir untersuchen, was das bedeutet und welche Folgen dies hat.

Beitrag 1: Aufwärmen: Der Fall konstanter Gebühren

Beitrag 2: Allgemeine Transaktionsauswahl-Spiele

Beitrag 3: Eigenschaften von zufälligen Gebührenmärkten

Beitrag 4: Anreizende Nicht-Angriffe*

Beitrag 5: Gebührenabschätzung

Beitrag 6: Alternative Ansätze: Bucketing und monopolistische Gebührenmärkte

Teil IV: Selbstskalierung

Wenn ein erlaubnisfreies verteiltes System behauptet, „sofortige Bestätigungen“ zu haben oder „so schnell wie das Internet“ zu arbeiten, gibt es ein kleines implizites Sternchen: dass die „Geschwindigkeit des Internets“ „bekannt“ ist. In der Praxis wird ein solches System, wenn es eingesetzt wird, in Bezug auf eine Grenze für die Netzlatenz parametrisiert. Diese Grenze muss mit einer großen Fehlermarge gewählt werden, da sonst die Sicherheit des Netzes beeinträchtigt wird. Dies zwingt die dezentralen Systeme zu einem suboptimalen Betrieb. Folglich verbessern sich die Bestätigungszeiten nicht mit den Netzbedingungen und werden im Falle einer Verschlechterung nicht erhöht. DAGKnight ist das erste Protokoll, das diese Einschränkung umgeht.

Leider verstehe ich DAGKnight selbst noch nicht gut genug, um zu wissen, wie diese Folge aufgebaut sein sollte. Sicher, ich verstehe, was es erreicht und die allgemeine Idee, aber wenn es darum geht, wie es tatsächlich funktioniert, ist das Beste, was ich bieten kann, eine intuitive Erklärung. Im Laufe der Zeit werden wir verstehen, wie diese Beiträge aufgeteilt werden sollten und was sie enthalten sollten.

Teil V: Weitere Themen

In diesem Teil geht es hauptsächlich darum, „lose Enden zu verknüpfen“. Er enthält Beiträge über „kleinere“ Themen, die etwas Aufmerksamkeit verdienen, über die ich aber nicht ein ganzes Kapitel schreiben möchte. Einige dieser Themen sind von entscheidender Bedeutung, andere sind einfach Dinge, die ich mag und über die ich sprechen möchte.

• Kapitel 5A: Dezentrales ASIC-Mining. In diesem Kapitel argumentieren wir die Vorteile des ASIC-Minings, und insbesondere, dass es in Kombination mit schnellen Emissionen und hohen BPS (Blöcke pro Sekunde) tatsächlich dezentraler und sicherer ist als Mining auf generischer Hardware.

Beitrag 1: Die Vor- und Nachteile des ASIC-Minings
Beitrag 2: Designierte Hardware gewinnt immer
Beitrag 3: Schnelle Emissionen und Coinverteilung
Beitrag 4: Hohe BPS/TPS und Hardware-Einstiegshürden

• Kapitel 5B: Schwierigkeitsanpassung. Der Schwierigkeitsanpassungsalgorithmus (DAA) ist die Komponente, die für die Aufrechterhaltung einer festen Blockrate trotz sich ständig ändernder Hashraten verantwortlich ist. Wir untersuchen einige Ansätze zur Schwierigkeitsanpassung in Blockchains und beschreiben den Ansatz, den wir für Kaspa gewählt haben (dieser Ansatz verwendet den Blue Score von Blöcken und ist daher GHOSTDAG-spezifisch und lässt sich nicht direkt auf andere BlockDAG-Protokolle übertragen).

Beitrag 1: Aufwärmen: Schwierigkeitsanpassung in Bitcoin mit authentischen Zeitstempeln

Beitrag 2: Schwierigkeitsepochen vs. Schiebefenster

Beitrag 3: Schwierigkeitsschwankungen und Abwägungsfunktionen
Beitrag 4: Umgang mit Zeitstempel-Manipulationen
Beitrag 5: Anpassung an DAGs, was sind überhaupt die „jüngsten“ Blöcke?
Beitrag 6: Sicherheit von Bitcoin mit variierendem Schwierigkeitsgrad*

• Kapitel 5C: Erreichbarkeitsabfragen. Angesichts von zwei Blöcken in einem BlockDAG, wie können wir feststellen, ob sie parallel sind oder ob einer in der Vergangenheit des anderen liegt? Die Berechnung von GHOSTDAG erfordert, diese Frage mehrere Male pro Block zu beantworten. Eine effiziente Implementierung ist entscheidend, wenn wir jemals auf eine praktische Umsetzung von GHOSTDAG hoffen wollen. Allerdings ist dies ein sehr schwieriges Problem. (So schwierig, dass mehrere Teams, die versucht haben, GHOSTDAG zu implementieren, es als „ineffizient“ bezeichnet haben.) In diesem Abschnitt erklären wir, was dieses Problem so schwierig macht, und präsentieren einen Algorithmus von Michael Sutton, der es löst.

• Kapitel 5D: MEV-Resistenz. Die hohe Parallelität von BlockDAGs mit hohem BPS macht es unmöglich, in Echtzeit vorherzusagen, wie die Menge der Blöcke, die eine bestimmte Transaktion enthalten, aussehen wird. Yonatan Sompolinsky hat beobachtet, dass diese Eigenschaft genutzt werden könnte, um MEV (Miner Extractable Value) zu bekämpfen. Die grobe Idee ist, dass die Miner ihre Blöcke benutzen, um für das Privileg zu bieten, die Transaktion aufzunehmen, wobei das gebotene Geld an denjenigen zurückgeht, der die Transaktion erstellt hat. Die hohe Parallelität macht es unmöglich, Auktionen zu manipulieren, so dass die Gleichgewichte dieses Prozesses eine faire Aufteilung des extrahierten Wertes zwischen dem Ersteller der Transaktion und dem Miner, der sie eingebunden hat, widerspiegeln. In diesem Beitrag geben wir einen Überblick über MEV im Allgemeinen und einige bestehende Ansätze zu ihrer Abschwächung. Anschließend werden wir Auktionen und ein wenig von deren Theorie diskutieren. Zum Schluss werden wir ein Beispiel dafür geben, wie MEV-Resistenz auf Kaspa funktionieren könnte, zusammen mit einigen quantitativen Analysen.

• Kapitel 5E: Quantenmining*. Das ist zwar nicht spezifisch für Kaspa, aber dieses Thema wird mir oft gestellt. Quantenmining mag zwar weit hergeholt sein, aber das Verständnis seiner Dynamik ist eine große Herausforderung, um dein Verständnis von PoW auf die Probe zu stellen. Für diese Themen sind keine Kenntnisse der Quantenberechnung erforderlich, abgesehen von einigen sehr spezifischen Fakten, die ich in einer in sich geschlossenen Form präsentieren werde.

Beitrag 1: Quantenberechnungsfibel: Messungen und Grovers Algorithmus

Beitrag 2: Klassisches vs. Quanten-Mining

Beitrag 3: Aggressives Mining

Beitrag 4: Die optimale Wartezeit für Kleine Quantenminer

Beitrag 5: Ein Quanten-Schwierigkeitsangriff