Das Problem der byzantinischen Generäle untersucht, ob korrekte Prozesse eine Entscheidung vereinbaren können, wenn fehlerhafte Prozesse beliebig handeln und verschiedenen Empfängern widersprüchliche Nachrichten senden. Lamport, Shostak und Peases Formulierung von 1982 beweist für mündliche Nachrichten ohne Signaturen die Untergrenze 3m+1 bei m Verrätern und beschreibt rekursive Algorithmen für mündliche und signierte Nachrichten. Die Ergebnisse gelten unter präzisen Annahmen und sind kein Synonym für jeden Blockchain-Konsens.
Lamport, Shostak und Pease veröffentlichten die Allegorie im Juli 1982 in ACM TOPLAS, um interaktive Konsistenz replizierter Systeme zu erklären. Getrennte Generäle müssen einen Plan wählen, obwohl Verräter verschiedenen Empfängern Verschiedenes melden können. Ein byzantinischer Fehler ist stärker als ein Absturz: Eine Komponente kann lügen, widersprüchlich senden, Nachrichten auslassen oder nur einem Teil des Systems korrekt erscheinen. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Die Arbeit trennt IC1 – alle loyalen Leutnants befolgen denselben Befehl – und IC2 – bei loyalem Kommandeur befolgen alle dessen Befehl. Moderne Begriffe sind Einigung oder Safety, Gültigkeit sowie Terminierung oder Liveness. Garantien sind nur zusammen mit Netzmodell, Authentisierung und maximaler Fehlerzahl aussagekräftig. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Bei mündlichen Nachrichten ist der direkte Absender erkennbar, Ausbleiben feststellbar und jeder kann jeden erreichen; ein Verräter darf aber verschiedene Werte senden. OM(m) leitet Werte rekursiv weiter und nutzt eine deterministische Mehrheit. Für m byzantinische Prozesse braucht man mindestens 3m+1 Teilnehmer, also mehr als zwei Drittel loyale. Drei Teilnehmer können einen Verräter nicht tolerieren, weil dessen Rolle nicht unterscheidbar ist. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Unfälschbare Signaturen machen widersprüchliche Aussagen sichtbar und verhindern das Verändern loyal signierter Befehle. Der Algorithmus verbreitet neue signierte Werte und entscheidet deterministisch über die gesammelte Menge. Unter idealen Signaturannahmen ist jede Zahl von Verrätern behandelbar. Eine Signatur beweist jedoch Herkunft, nicht Wahrheit, rechtzeitige Zustellung oder einen unkompromittierten Schlüssel; Dolev und Strong präzisierten später die Rundengrenzen. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Garantierter Fortschritt hängt von Zeitannahmen ab. Fischer–Lynch–Paterson zeigte 1985, dass ein vollständig asynchrones deterministisches Nachrichtensystem bereits bei einem möglicherweise abstürzenden Prozess einen zulässigen, nie terminierenden Konsenslauf besitzt. FLP sagt nicht, dass reale Systeme nie übereinstimmen. Lebendigkeit braucht zusätzliche Annahmen wie spätere Zeitgrenzen oder einen Fehlerdetektor mit bestimmten Eigenschaften, oder ein randomisiertes Protokoll. Einen Leiter zu ernennen reicht nicht. Bei langer Netztrennung kann ein sicheres Protokoll keine weiteren Operationen abschließen. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT von Miguel Castro und Barbara Liskov (1999) überträgt byzantinische Einigung auf replizierte Zustandsmaschinen. Die Grundkonfiguration n = 3f+1 toleriert f byzantinische Repliken. Der vorbereitete Zustand umfasst ein pre-prepare der Primärreplik und 2f passende prepare-Nachrichten; lokales Bestätigen erfordert diesen Zustand und 2f+1 passende commit-Nachrichten. Quorumsüberschneidungen und Regeln für Sichtwechsel verhindern widersprüchliche Bestätigungen. Authentisierung, Sequenznummern, Kontrollpunkte und Sichtwechsel behandeln Fälschung, Wiederholung, Protokollwachstum und fehlerhafte Leiter. Bekannte Mitglieder und deterministische Finalität unterscheiden sich vom offenen Proof of Work-Netz. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin führt weder OM noch PBFT aus und zählt keine benannten Knoten. Sybil-resistentes Proof of Work gewichtet konkurrierende Historien mit kumulierter Arbeit; jeder Full Node verwirft regelwidrige Blöcke selbst und folgt der gültigen Kette mit der meisten Arbeit. Vorübergehende Abzweigungen sind vorgesehen. Unter Annahmen über ehrliche Arbeitsmehrheit und Kommunikation sinkt die Ersetzungswahrscheinlichkeit mit Bestätigungstiefe, ohne mathematische Unumkehrbarkeit. Bitcoin Backbone formalisiert gemeinsamen Präfix, Wachstum und Qualität unter expliziten Annahmen zu Angreiferarbeit und Netz. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Bitcoin als Lösung des Generalsproblems zu bezeichnen verbirgt einen Modellwechsel. Klassische Einigung beginnt mit festen bekannten Identitäten und Grenze f; Bitcoin erlaubt wechselnde Pseudonyme und eine externe knappe Ressource. Seine Garantien brauchen weiterhin konkrete Zustellannahmen. Proof of Work begrenzt Sybil-Einfluss, verhindert aber weder Eclipse-Angriffe, Zensur, eigennütziges Mining, Softwarefehler noch Reorganisationen bei Hash-Mehrheit. Das Bedrohungsmodell muss Gegner, Zeit, Mitglieder und Finalität nennen; BFT allein genügt nicht. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Für ein möglichst vollständiges Bild lies diesen Eintrag zusammen mit Nakamoto-Konsens, Proof of Work, Konsensregeln, Double Spend, Bitcoin, Probabilistische Finalität.