Byzantine Generals Problem

Stellen wir uns Truppen rund um eine Stadt vor. Sie müssen gemeinsam angreifen oder gemeinsam abziehen; getrenntes Handeln könnte verheerend sein. Der Befehlshaber verschickt Anweisungen, doch jemand könnte die anderen verraten und ihnen unterschiedliche Dinge erzählen. Wie erreichen die zuverlässigen Beteiligten, dass sie am Ende gleich handeln? Das ist kein Bericht über eine historische Schlacht, sondern ein Gedankenexperiment über Computer mit übereinstimmenden Aufzeichnungen. Mehrere Server, also Computer für einen gemeinsamen Dienst, müssen etwa gemeinsam entscheiden, ob eine Zahlung bereits verarbeitet wurde. Irgendeine Antwort zu erhalten reicht nicht: Die Antworten müssen zu einer gemeinsamen Entscheidung führen. [1] [9]

Leslie Lamport, Robert Shostak und Marshall Pease veröffentlichten die bekannte Formulierung im Juli 1982, nach ihrer Arbeit über Einigung trotz Fehlern von 1980. Der Verräter steht für eine Systemkomponente, deren Verhalten nicht mehr vorhersehbar ist. Ein Computer muss nicht einfach ausfallen. Er kann einem Nachbarn richtig und einem anderen falsch antworten, Nachrichten weglassen oder etwas anderes behaupten. Ursache kann ein Angriff oder ein Programmfehler sein. Ein byzantinischer Fehler beschreibt die Beobachtung der anderen, nicht die Absicht des Geräts. BFT steht für Byzantine Fault Tolerance: die Fähigkeit, solches Verhalten unter festgelegten Bedingungen zu verkraften. [1] [2]

Die ursprüngliche Aufgabe stellt zwei Bedingungen. IC1 verlangt, dass alle zuverlässigen Untergebenen denselben Befehl annehmen. IC2 ergänzt: Ist auch der Befehlshaber zuverlässig, müssen sie seinen tatsächlich gesendeten Befehl annehmen. Ohne die zweite Bedingung wäre „immer abziehen“ eine scheinbare Lösung, die einen ehrlichen Befehlshaber jedoch ignoriert. Computersysteme unterscheiden Sicherheit, also das Verhindern widersprüchlicher Ergebnisse, und Lebendigkeit, also das Erreichen eines Ergebnisses überhaupt. Weitere Regeln legen zulässige Ergebnisse fest. Übereinstimmende Aufzeichnungen beweisen für sich allein nicht, dass eine eingegebene Behauptung in der Außenwelt wahr war. [1] [9]

Nennen wir den Befehlshaber A und die Untergebenen B und C. C bekommt von A einen Angriffsbefehl, B behauptet jedoch, der Befehl habe Rückzug gelautet. Lügt B, oder hat A verschiedene Befehle geschickt? Ohne eine nach der Weitergabe überprüfbare Signatur kann C diese Situationen möglicherweise nicht unterscheiden. B kann vor derselben Unsicherheit stehen. Gehorchen beide immer direkt dem Befehlshaber, kann ein unehrlicher A sie spalten; ignorieren sie ihn immer, verletzen sie die Bedingung für einen ehrlichen Befehlshaber. In dieser Aufgabe mit drei Beteiligten und einem möglichen Verräter gibt es ohne Signaturen deshalb kein stets erfolgreiches Verfahren. Es fehlen unterscheidbare Informationen, keine schnelleren Computer. [1] [9]

Im klassischen Modell ohne Signaturen braucht man für m mögliche Verräter mindestens n ≥ 3m+1 Teilnehmer: für einen Verräter also vier. Dabei bezeichnet n die Gesamtzahl der Teilnehmer und m die höchste Zahl von Verrätern, die das System verkraften soll. Es genügt nicht, eine Stimme hinzuzufügen und einmal die Mehrheit zu zählen. OM(m) lässt die Beteiligten wiederholt weitergeben, was sie gehört haben, und die Nachrichten nach gemeinsamen Regeln auswerten. Der Basisfall OM(0) übernimmt den Wert des Befehlshabers oder einen vereinbarten Ersatzwert. Vorausgesetzt werden bekannte Teilnehmer, direkte Verbindungen, korrekte Zustellung gesendeter Nachrichten, Kenntnis des unmittelbaren Absenders und die Erkennbarkeit fehlender Nachrichten. „Ohne Signaturen“ bedeutet somit nicht „ohne jede Herkunftsprüfung“. Ohne diese Annahmen garantiert die Zahl vier nichts. [1] [9]

Mit einer überprüfbaren digitalen Signatur, Digital Signature, kann B gegenüber C belegen, was der Befehlshaber tatsächlich unterschrieben hat. Ein Programm erstellt die Signatur mit einem privaten Schlüssel, einem geheimen Zahlenwert. Andere prüfen sie mit dem zugehörigen öffentlichen Schlüssel, ohne den privaten kennen zu müssen. Ein Verräter kann den Befehl eines zuverlässigen Teilnehmers nicht unbemerkt verändern oder dessen Signatur nachahmen. Das Verfahren für signierte Nachrichten verbreitet signierte Werte und nutzt eine gemeinsame Auswahlregel. In diesem Modell entfällt die erwähnte Forderung nach einer ehrlichen Mehrheit. Unfälschbare Signaturen, Zustellung und zeitlich geregelte Runden bleiben aber Voraussetzungen. Dolev und Strong untersuchten 1983 die erforderliche Rundenzahl weiter. Auch eine gültige Signatur garantiert weder wahre Inhalte noch rechtzeitige Zustellung. Sie beweist auch nicht, dass der private Schlüssel nicht gestohlen wurde. Sie belegt die Herkunft einer Nachricht, nicht die allgemeine Vertrauenswürdigkeit des Absenders. [1] [3]

Antwortet ein Server nicht, wissen die anderen nicht, ob er ausgefallen ist oder nur eine sehr langsame Verbindung hat. Das 1985 von Michael Fischer, Nancy Lynch und Michael Paterson veröffentlichte FLP-Ergebnis präzisiert diese Unsicherheit. Ein Prozess ist hier ein laufendes Programm. Ein deterministisches Verfahren führt bei gleichem Zustand und gleicher Eingabe denselben nächsten Schritt aus; es wählt ihn nicht zufällig. In einem vollständig asynchronen System ohne bekannte Obergrenze für Verzögerungen kann ein deterministisches Verfahren nicht in jedem zulässigen Ablauf den Abschluss der Einigung garantieren, sobald auch nur ein Prozess abstürzen darf. Das gilt selbst bei zuverlässiger Zustellung mit unbeschränkter Verzögerung. Es heißt nicht, dass Einigung niemals gelingt. Praktische Systeme ergänzen Zeitannahmen, einen geeigneten Fehlerdetektor oder Zufall. Bei einer Netzaufteilung kann Warten sicherer sein als das Bestätigen unvereinbarer Ergebnisse. [4] [13] [8]

Miguel Castro und Barbara Liskov beschrieben 1999 Practical Byzantine Fault Tolerance, kurz PBFT, für einen Dienst auf mehreren bekannten Replikaten. Diese Replikate sind Kopien des Dienstes, die auf verschiedenen Servern laufen und fortlaufend dieselben Anfragen bearbeiten. Es sind keine abgelegten Sicherungsdateien. Die Grundkonfiguration n = 3f+1 verkraftet f fehlerhafte Replikate. Von vier Servern darf einer byzantinisch ausfallen; zwei Dreiergruppen überschneiden sich in mindestens zwei Servern, von denen mindestens einer zuverlässig sein muss. Eine erforderliche Gruppe von Zustimmungen heißt Quorum. Die Überschneidung allein genügt nicht: Auch Phasenregeln und Führungswechsel sind entscheidend. Genauer verlangt der Zustand prepared die Anfrage, eine pre-prepare-Nachricht und 2f passende prepare-Nachrichten von verschiedenen Replikaten, die nicht die Rolle des primären Replikats übernehmen. Die lokale Bestätigung benötigt zusätzlich 2f+1 commit-Nachrichten, gegebenenfalls einschließlich der eigenen. Herkunftsprüfung, Sequenznummern und Kontrollpunkte begegnen Fälschungen, Wiederholungen und unbegrenztem Protokollwachstum. Sicherheit braucht keine Zeitgrenzen; Fortschritt benötigt jedoch zusätzliche Bedingungen für Verzögerungen. [5] [10] [11] [12]

Bitcoin besitzt keine vorab abgeschlossene Serverliste. Hätte jedes neu angelegte Konto eine Stimme, könnte ein Angreifer eine Mehrheit erzeugen: ein Angriff vom Typ Sybil Attack. Proof of Work bindet die Blockerzeugung deshalb an Rechenarbeit. Ein Block ist ein Paket von Transaktionen, das in die gemeinsame Historie aufgenommen wird. Ein Full Node, also ein Computer mit Software zur selbstständigen Prüfung der Regeln, verwirft zunächst ungültige Blöcke und folgt unter den gültigen Zweigen dem mit der größten angesammelten Arbeit. Bitcoin führt weder OM noch PBFT aus; vorübergehende Verzweigungen gehören zum Betrieb. Bei ausreichendem ehrlichem Rechenanteil und geeigneten Kommunikationsbedingungen senken weitere Bestätigungen das Risiko einer Umschreibung, schaffen aber keine absolute Unumkehrbarkeit. Die Bitcoin-Backbone-Forschung untersucht diese Voraussetzungen: übereinstimmende Historien, Kettenwachstum und den Anteil ehrlich erzeugter Blöcke. [6] [7]

Bei der Aussage „Das Netzwerk erreicht Konsens“ lohnen konkrete Fragen: Wer darf teilnehmen, was kontrolliert der Angreifer, wie lange dürfen Nachrichten unterwegs sein und wann kann sich eine Entscheidung ändern? Auch Proof of Work beseitigt nicht jedes Problem. Ein Angriff vom Typ Eclipse Attack isoliert einen Knoten von ehrlichen Gegenstellen, Zensur lässt Transaktionen aus, und Selfish Mining arbeitet mit dem Zurückhalten gefundener Blöcke. Softwarefehler und die Möglichkeit, mit genügend Angriffsstärke einen Teil der Historie umzuschreiben, bleiben bestehen. Selbst die Mehrheit der Rechenleistung kann einen korrekt funktionierenden Full Node jedoch nicht zwingen, einen regelwidrigen Block anzunehmen. Die Geschichte der Generäle hilft, nach den Bedingungen einer Einigung zu fragen, statt einem Technologienamen zu vertrauen. [6] [7] [8]