Zum Inhalt springen
Financial Context Wiki

Problem der byzantinischen Generäle: Einigung bei widersprüchlichen Nachrichten

Das Problem fragt, wie ehrliche Teilnehmer sich einigen, wenn fehlerhafte widersprüchliche Informationen senden. Einigungsaufgabe, Kanäle, Authentifizierung, Fehlergrenze, Schranke, Algorithmus und Einsatz sind getrennt zu prüfen.

Aktualisiert

Nur zur Aufklärung über Protokolle. Die Lösung eines byzantinischen Einigungsmodells belegt nicht, dass ein eingesetztes Netz sicher, lebendig, korrekt implementiert, dezentral, final oder für Vermögenswerte sicher ist.

Direkte Antwort

Das Problem der byzantinischen Generäle fragt, wie nicht fehlerhafte Teilnehmer, die über Nachrichten kommunizieren, eine konsistente Entscheidung treffen, wenn andere sich beliebig verhalten und verschiedenen Empfängern widersprüchliche Aussagen senden. Die Militärgeschichte ist eine Analogie für interaktive Konsistenz in verteilten Systemen, kein historisches Ereignis und kein bestimmter Blockchain-Konsensalgorithmus.

In der Kommandeur-Leutnant-Fassung verlangt IC1, dass alle loyalen Leutnants denselben Befehl befolgen; IC2 verlangt bei loyalem Kommandeur, dass sie dessen Befehl befolgen. Einigung allein reicht nicht: Immer RÜCKZUG zu wählen erzeugt Einigung, verletzt aber den gültigen ANGRIFF eines loyalen Kommandeurs.

Im Modell „mündlicher Nachrichten“ der Arbeit gibt es bei höchstens m Verrätern nur für n>3m eine Lösung, bei ganzzahliger Teilnehmerzahl gleichbedeutend mit n>=3m+1. Das Modell nimmt korrekte Zustellung loyal gesendeter Nachrichten, bekannte Absender und erkennbare Abwesenheit erwarteter Nachrichten an. „Mündlich“ bedeutet, dass nicht authentifizierter Inhalt als Bericht eines anderen gefälscht werden kann, nicht dass ein Bote unbemerkt für immer verschwinden darf.

Das Modell „signierter Nachrichten“ fügt fälschungssichere, öffentlich prüfbare Signaturen hinzu und ändert das Resilienzergebnis. Es macht Inhalte nicht wahr, garantiert weder Zustellung noch vollständig asynchrone Terminierung, schützt keine gestohlenen Schlüssel und beweist kein modernes Protokoll. Das byzantinische Problem, Zwei-Generäle- oder koordinierter-Angriff-Problem, FLP, BFT, Proof of Work und Proof of Stake sind verwandt, aber verschieden.

Analysemethode

  1. Einigungsaufgabe definieren. Teilnehmer, Eingaben, Ausgaben und genaue Einigungs-, Gültigkeits- und Terminierungseigenschaften angeben. In der Kommandeurfassung IC1 und IC2 ausdrücklich nennen.
  2. Identitäten und Kanäle definieren. Authentifizierung, zuverlässige Zustellung, Reihenfolge, Replay-Schutz, Zuordnung, Erkennung von Auslassung und Broadcast als Primitive oder wiederholte Sendung angeben.
  3. Zeitmodell definieren. Synchronität mit begrenzter Verzögerung, partielle Synchronität nach unbekannter Stabilisierung und vollständige Asynchronität trennen. Verschwindende Boten nicht einem Modell hinzufügen und einen Satz eines anderen behalten.
  4. Fehlerbudget definieren. Gesamtteilnehmer n, maximale byzantinische Teilnehmer m, statische oder adaptive Korruption sowie Auslassung, Äquivokation, Kollusion, Schlüsseldiebstahl und Kanalfehler erfassen.
  5. Information rekursiv verfolgen. Für jeden Loyalen direkte und weitergeleitete Aussagen, Absenderpfade, Ausfallstandard und deterministische Gleichstandsregel auflisten; lokale Sichten auf Unterscheidbarkeit vergleichen.
  6. Satz und Algorithmus gemeinsam prüfen. Schranken und Hinreichendheit dem exakten mündlichen oder signierten Modell, der Konnektivität und dem Budget zuordnen. Eine Ungleichung ist weder Implementierung noch Beweis.
  7. Auf den Einsatz abbilden. Tatsächliches OM(m), SM(m) oder anderes Verfahren, Nachrichtendomänen, Runden, Sperren, Zertifikate, Mitgliederwechsel, Timeouts, Clients, Finalität und Bestätigungsregeln prüfen.

Die zentrale Beweistechnik ist Ununterscheidbarkeit. Ein loyaler Teilnehmer sieht nur lokale Nachrichten; sehen zwei Ausführungen gleich aus, erfordern aber aus Gültigkeitsgründen verschiedene Entscheidungen, kann keine deterministische Regel immer richtig wählen. Genügend unabhängige Teilnehmer, authentifizierte Belege, Zeitannahmen, Zufall oder andere Struktur machen erforderliche Ausführungen unterscheidbar oder ändern die Garantie.

Durchgerechnete Beispiele

1. Warum drei mündliche Generäle keinen Verräter tolerieren

Es gelte n=3 und m=1. Die Bedingung n>3m wird zu 3>3 und ist falsch. Kommandeur A sage B ATTACK und C RETREAT. B kann nicht unterscheiden, ob A als Verräter widersprüchliche Befehle sandte oder C als Verräter über As Aussage lügt; C hat die symmetrische Unsicherheit.

Jede deterministische Wahl, die in entsprechenden Ausführungen mit loyalem A dessen Befehl erhält, kann B und C bei verräterischem A zu verschiedenen Entscheidungen zwingen. Weiterleitung schafft keine vierte unabhängige Quelle, daher sind IC1 und IC2 nicht gemeinsam garantiert.

2. Vier mündliche Generäle und ein Verräter

Bei OM(1), n=4 und m=1 sendet der Kommandeur an drei Leutnants; jeder leitet den Wert an die anderen zwei weiter; jeder Loyale nutzt dieselbe Mehrheit und denselben Standard. Sendet ein loyaler Kommandeur v, sieht ein Loyaler v, v und ein mögliches x des Verräters und wählt v.

Ist der Kommandeur der einzige Verräter, sind alle drei Leutnants loyal und leiten genau das Empfangene weiter. Sie rekonstruieren denselben Satz von Kommandeursaussagen und wenden dieselbe Regel an. Die „wahre Absicht“ bleibt unbekannt, Einigung wird aber erreicht.

3. Allgemeine Schranke mündlicher Nachrichten

Bei n=7 und m=2 gilt 7>6; damit ist die Anzahlbedingung erfüllt und die rekursive Konstruktion toleriert unter den übrigen Annahmen zwei Verräter. Für n=6 ist 6>6 falsch. Für n=10 und m=3 gilt 10>9. Die Ungleichung ist notwendig; Runden, Weiterleitung, Mehrheit, Standards und Kanäle müssen ebenfalls stimmen.

4. Was Signaturen ändern

In einem SM(1)-Beispiel mit drei Generälen signiert der verräterische Kommandeur ATTACK für B und RETREAT für C. Die loyalen Leutnants leiten beide weiter, erhalten denselben Satz {ATTACK, RETREAT} und verwenden denselben Standard, etwa RETREAT. Die Äquivokation ist zurechenbar.

Signaturen verhindern im Modell Fälschung oder unerkannte Änderung eines loyalen Befehls. Sie zeigen nicht die „wahre Absicht“ des Verräters, garantieren keine pünktliche Zustellung und hindern den Besitzer eines legitimen privaten Schlüssels nicht an beiden Signaturen.

Risiken und Prüffehler

Problem und Modell

  • Die Allegorie ohne genaue Einigungs-, Gültigkeits- und Terminierungsbedingungen wiederholen.
  • Das Problem als historische Belagerung, einzelnen Algorithmus oder Synonym für Blockchain behandeln.
  • Mit dem Zwei-Generäle-Problem über gemeinsames Wissen auf unzuverlässigem Kanal verwechseln.
  • Unerkennbaren dauerhaften Verlust hinzufügen und einen Satz zitieren, der ihn ausschließt.
  • n>3m auf jedes authentifizierte, asynchrone, gewichtete, erlaubnisfreie oder ressourcenbasierte Protokoll anwenden.
  • Absturz, Auslassung, Äquivokation, beliebige Berechnung, Kanalfehler und Schlüsselkompromittierung gleichsetzen.
  • Teilnehmerzahl mit unabhängigen Einheiten, Stake, Hashleistung oder Komiteegewicht gleichsetzen.
  • Den Unterschied zwischen loyalem und verräterischem Kommandeur in der Gültigkeit auslassen.

Algorithmus und Implementierung

  • Nur die Endmehrheit prüfen, nicht rekursive Absenderpfade und jede lokale Sicht.
  • Verschiedene Ausfallstandards, Gleichstandsregeln, Mitgliedschaftssnapshots oder Reihenfolgen verwenden.
  • Nachrichten ohne Bindung an Protokoll, Kette, Aufgabe, Höhe, Runde, Wert, Absender und Epoche akzeptieren.
  • Nachrichten zwischen Ausführungen, Runden, Forks, Netzen oder Mitgliederwechseln wiedergeben oder verbinden.
  • Annehmen, Signaturen bewiesen Wahrheit, Aktualität, Berechtigungskontext, Zustellung, Verfügbarkeit oder ehrliche Schlüsselverwahrung.
  • OM(m) oder SM(m) nennen, ohne erforderliche Runden, Weiterleitung, Prüfung und Konnektivität umzusetzen.
  • Nur eine Verräterposition testen statt Kommandeur, Leutnant, Kollusion, Auslassung und Äquivokation.

Einsatz und Interpretation

  • Behaupten, Konsens „löse Byzanz“, ohne genaue Sicherheits-, Lebendigkeits- und Netzannahmen.
  • Einigung über Bytes als Beweis korrekter Anwendungsausführung oder externer Tatsachen behandeln.
  • Korrelierte Fehler gemeinsamer Clients, Betreiber, Clouds, Schlüsselsysteme oder Governance ignorieren.
  • Einzahlungen gutschreiben, Bridge-Assets prägen oder irreversible Aktionen vor nötiger Finalität abwickeln.
  • Dezentralisierung, Vermögensschutz, rechtliche Wahrheit oder Tokenwert aus einer Fehlertoleranzbezeichnung ableiten.

Häufige Irrtümer

  • Das Problem ist nur ein 51-%-Angriff. Es behandelt beliebiges und widersprüchliches Verhalten in einem Einigungsmodell; Ressourcenmehrheiten gehören zu bestimmten Protokollen.
  • Eine Mehrheit löst es immer. Im klassischen mündlichen Modell erfordert Toleranz von m Verrätern mehr als deren dreifache Gesamtzahl, nicht nur einen Loyalen mehr.
  • Digitale Signaturen beweisen Wahrheit. Sie authentifizieren Schlüssel und schützen Integrität; böswillige oder kompromittierte Schlüssel signieren falsche oder widersprüchliche Inhalte.
  • Das ursprüngliche mündliche Ergebnis umfasst unzuverlässige Zustellung. Es nimmt Zustellung, Absenderidentität und erkennbare Auslassung an; andere Modelle brauchen andere Ergebnisse.
  • Einigung bedeutet Kenntnis der Wirklichkeit. Ohne gesonderte Prüfung können Loyale ungültigen Ausgaben oder falschen externen Daten zustimmen.

Verwandte Themen

Quellen

Navigation

Wiki durchsuchen...