Byzantinische Fehlertoleranz (GHOSTDAG verstehen, Kapitel 1A, Beitrag 1)

(Dieser Beitrag ist Teil der Serie „GHOSTDAG verstehen“)

Mit diesem Beitrag möchte ich die Diskussion auf vertrautem Boden beginnen. Zu diesem Zweck habe ich einen Ausgangspunkt gewählt, der den meisten Lesern bekannt sein dürfte: das Problem der Byzantinischen Generäle. Ich weiß, ich weiß, du hast schon tausend Blog- und Medium-Beiträge gelesen, aber glaube mir, dieses Mal wird es anders sein. Die Generäle werden nur der Ausgangspunkt für eine Diskussion über Sybilness, Dezentralisierung, Sicherheit und Skalierung sein, die viele Konzepte einführen wird, die uns das ganze Buch über begleiten werden. Außerdem habe ich die gleichen Beiträge gelesen wie du, und ich kann getrost sagen, dass ich sie besser erkläre.

Das Problem der Byzantinischen Generäle

Viele von uns kennen diese Geschichte: Eine Gruppe Byzantinischer Generäle verschanzt sich um eine Festung und muss entscheiden, ob sie angreifen oder sich zurückziehen soll. Der Haken: Sie müssen entweder alle angreifen oder sich zurückziehen. Eine Situation, in der einige Generäle angreifen, während sich andere zurückziehen, würde mit Sicherheit zu großen Verlusten führen. Der andere Haken: Die Generäle können sich nicht treffen, um sich zu beraten, sie können sich nur gegenseitig Nachrichten schicken.

Die Lösung scheint einfach zu sein: Die Mehrheit soll entscheiden. Wenn die meisten Generäle angreifen wollen, greifen alle Generäle an. Andernfalls ziehen sich alle Generäle zurück. Das Problem bei dieser Lösung ist, dass einige Generäle verräterisch sein könnten und wollen, dass das Militär verliert. Nehmen wir an, es gibt drei Generäle: Der erste will kämpfen, der zweite will sich zurückziehen, und der dritte will verlieren. Der erste General sendet die Nachricht „Angriff“ an alle, der zweite General sendet die Nachricht „Rückzug“ an alle. Nun bringt der dritte General die Armee durcheinander: Er sendet „Angriff“ an den einen General und „Rückzug“ an den anderen“. Die Folge? Der erste General sieht zwei „Angriff“-Nachrichten und greift an, während der zweite General zwei „Rückzug“-Nachrichten sieht und sich zurückzieht. Der dritte General hat seinen Willen bekommen.

Dieses Beispiel zeigt, dass das „Mehrheit gewinnt“-Protokoll nicht einmal einem einzigen Fehler standhält. Ein einziger verräterischer General reicht aus, um Szenarien zu ermöglichen, in denen das Protokoll versagt.

Können wir es also besser machen? Können wir ein Protokoll entwerfen, das mit allen Fehlern umgehen kann? Diese Frage steht im Mittelpunkt eines Forschungsgebiets, das nach dem Problem der Byzantinischen Generäle als Byzantinische Fehlertoleranz (BFT) bezeichnet wird. Es wurde 1980 in einer bahnbrechenden Arbeit von Pease, Shostak und Lamport mit dem Titel Reaching Agreement in the Presence of Faults eingeführt. In dieser Arbeit wurde ein Protokoll entwickelt, das mit f fehlerhaften Knoten umgehen kann, wenn insgesamt mindestens 3f+1 Knoten vorhanden sind, und es wurde nachgewiesen, dass es optimal ist. Mit anderen Worten: BFT kann uns nur schützen, solange weniger als ein Drittel der Knoten fehlerhaft ist (das Paper zeigt auch, wie das Protokoll leicht verbessert werden kann, damit es funktioniert, wenn genau ein Drittel der Knoten fehlerhaft ist, indem digitale Signaturen verwendet werden). Heute wird dieses Ergebnis allgemein als „3f+1-Theorem“ bezeichnet.

Die von Pease et al. vorgeschlagenen Protokolle sind theoretisch bedeutsam, aber unpraktisch, da sie zu viel Zeit und Speicherplatz benötigen. 1999 stellten Miguel Castro und Barbara Liskov Practical Byzantine Fault Tolerance (PBFT) vor, ein effizientes BFT-Protokoll, das für große Lasten geeignet ist. Seitdem hat es eine Kambrische Explosion verschiedener BFT-Protokolle mit unterschiedlichen Eigenschaften wie Tendermint, Aardvark und RBFT gegeben, die jeweils unterschiedliche Verbesserungen und Kompromisse vorschlagen.

Ein bemerkenswertes Merkmal einiger BFT-Protokolle ist, dass 34% der schadhaften Spieler zwar den Konsens beeinträchtigen können, ihre Einmischung aber rückwirkend erkannt werden kann. Diese Eigenschaft wird beim Proof-of-Stake-Konsens ausgenutzt, bei dem die Teilnehmer einen gewissen Geldbetrag staken müssen. Dieses Geld wird verbrannt, wenn ein Fehlverhalten ihrerseits festgestellt wird. Dies wird oft als Slashing bezeichnet. Das Proof-of-Stake-Verfahren kann nicht verhindern, dass eine 34%ige geheime Absprache das Protokoll beeinträchtigt, und geht daher einen Kompromiss ein, indem es stattdessen wirtschaftliche Abschreckungsmaßnahmen vorsieht.

PSL’s Protokoll*

Wie funktioniert also das BFT-Protokoll von Pease et al. und was macht es unpraktisch?

Wir beginnen mit einem Protokoll für vier Knotenpunkte: nennen wir sie John, Paul, George und Ringo. Diese vier stimmen darüber ab, wie sie ihr neues Album nennen wollen. Das Protokoll läuft in zwei Runden ab: In der ersten Runde teilt jeder Beatle allen Beatles mit, wie er das Album nennen möchte, und in der zweiten Runde teilt jeder allen mit, was die anderen Beatles ihm mitgeteilt haben. Beachte, dass die Kommunikation zwischen den Beatles immer noch individuell ist, so dass, wenn einer von ihnen beschließt zu lügen, er verschiedene Lügen zu verschiedenen Beatles erzählen kann.

Am Ende der zweiten Runde sollte jeder Beatle drei Nachrichten der Form „John hat mir gesagt, dass er das Album Rubber Soul nennen will“ und neun Nachrichten der Form „George hat mir gesagt, dass Ringo ihm gesagt hat, dass er das Album Revolver nennen will“ haben.

Nehmen wir an, George versucht herauszufinden, wie John das Album nennen möchte. In der ersten Runde sagte John ihm, was er bevorzugt. In der zweiten Runde haben Paul und Ringo John gesagt, was John ihnen angeblich gesagt hat. George wird Paul die Mehrheitsmeinung zuschreiben.

Wenn John George sagt, dass er Rubber Soul bevorzugt, aber sowohl Paul als auch Ringo George sagen, dass John Revolver bevorzugt, wird George trotzdem annehmen, dass John das Album Revolver nennen will.

George wiederholt diesen Vorgang für alle seine Kollegen, um schließlich herauszufinden, wie die meisten Beatles das Album nennen wollen. John, Paul und Ringo machen das Gleiche.

Die wichtigste Beobachtung dabei ist die folgende: Wenn mindestens drei der Beatles das Protokoll ehrlich befolgt haben, dann kommen alle Beatles zum gleichen Ergebnis.

Der Nachweis, dass dies tatsächlich der Fall ist, erfordert nichts weiter als eine einfache (wenn auch etwas mühsame) Buchführung. Es ist klar, dass keine Probleme entstehen, wenn alle vier ehrlich sind. Nehmen wir also an, John will das Album unbedingt „Rubber Soul“ nennen. Er kann George sagen, dass Ringo und Paul es auch „Rubber Soul“ nennen wollen, aber wenn sie beide „Revolver“ bevorzugen, wäre das nicht hilfreich. Ringo wird George sagen, dass er „Revolver“ bevorzugt, und Paul wird George ebenfalls sagen, dass Ringo das Album „Revolver“ nennen will. Gemeinsam werden sie Johns Nötigung verhindern. Dies ist nur eine mögliche Betrugsstrategie, aber die Auflistung und Überprüfung, dass ein einziger betrügerischer Beatle bei allen scheitern wird, ist eine einfache Aufgabe, die eine Übung für den Leser bleiben soll.

Dieses Protokoll kann auf n=3f+1 Beatles (oder beliebige andere) ausgeweitet werden, indem weitere Runden hinzugefügt werden. Am Ende der, sagen wir, vierten Runde wird jeder Spieler Nachrichten wie „John hat George gesagt, dass Ringo ihm gesagt hat, dass Yoko ihm gesagt hat, dass sie das Album lieber Let It Be nennen möchte“ haben. Ansonsten bleibt alles beim Alten. Ein Standard-Induktionsbeweis zeigt, dass dieses Protokoll Toleranz gegenüber f fehlerhaften Knoten bietet, vorausgesetzt, es läuft über mindestens f Runden läuft.

Aus dem oben Gesagten können wir die Unpraktikabilität des Algorithmus ablesen. Erstens steigt die Anzahl der Runden linear an, was schrecklich ist. Das Ethereum-Netzwerk hat mehr als 750.000 Validierer, was bedeutet, dass bei Verwendung des PSL-Protokolls jede Validierungsphase 250.000 Runden lang laufen müsste. Schlimmer noch, die Menge der Nachrichten, die jeder Validator speichern muss, ist exponentiell: In der ersten Runde erhalten sie n-1 Nachrichten, in der zweiten Runde (n-2)(n-1) Nachrichten und so weiter bis zur letzten Runde, in der sie (n-1)⋅…⋅(n-f)=Θ(n f ) Nachrichten erhalten. Dies wird unerschwinglich, wenn die Anzahl der Nodes in die Dutzende oder gar Hunderttausende geht.

---

(Die mathematischen Formeln werden leider derzeit nicht richtig formatiert, da das Latex-Plugin nicht richtig arbeitet. Dieser Fehler wird sobald möglich behoben — an dem Beitrag selbst ändert sich aber nichts. Du kannst die richtig formatierten mathematischen Formeln hier finden: https://kasmedia.com/article/understand-ghostdag-1a)