Ein Heer, eine belagerte Stadt und Generäle, die einander nicht trauen können: Das «Problem der byzantinischen Generäle» ist ein Gedankenexperiment aus der Informatik. Es beschreibt eine der grössten Herausforderungen für jedes dezentrale System – und Bitcoin war die erste praktische Lösung dafür in einem offenen Netzwerk.
Woher das Problem stammt
Das Gedankenexperiment wurde 1982 von den Informatikern Leslie Lamport, Robert Shostak und Marshall Pease veröffentlicht. Sie wollten zeigen, wie schwierig es ist, dass sich verteilte Computer auf eine gemeinsame Entscheidung einigen, wenn einige von ihnen fehlerhaft arbeiten oder absichtlich lügen. Damit es anschaulich wird, verpackten sie es in eine Geschichte aus dem Byzantinischen Reich.
Warum das für Bitcoin wichtig ist
Eine Blockchain hat keine zentrale Stelle, die bestimmt, was gilt. Die Knoten im Netzwerk müssen sich selbst einigen, welche Überweisungen in die gemeinsame Datenbank kommen und welche nicht. Gelingt das nicht, könnte zum Beispiel dieselbe Münze zweimal ausgegeben werden – eine Doppelausgabe. Die Generäle in der Geschichte stehen für diese Knoten.
Das Gedankenexperiment
Mehrere Generäle belagern mit ihren Truppen eine Stadt. Jeder befehligt einen Teil des Heeres, und alle stehen an verschiedenen Orten rund um die Stadt. Telefone gibt es nicht; sie können sich nur über Boten verständigen. Sie müssen entscheiden: angreifen oder abziehen.
Welche der beiden Möglichkeiten sie wählen, spielt keine Rolle. Entscheidend ist, dass alle dasselbe tun. Greifen nur einige an, werden sie aufgerieben. Es gelten drei Regeln:
- Jeder General entscheidet sich zwischen Angriff und Rückzug.
- Eine einmal getroffene Entscheidung lässt sich nicht mehr rückgängig machen.
- Alle müssen sich auf eine gemeinsame Entscheidung einigen.
Die Schwierigkeiten
- Unzuverlässige Boten: Boten können abgefangen, aufgehalten oder getötet werden. Nachrichten gehen verloren, kommen zu spät oder werden unterwegs verfälscht.
- Verräter: Einige Generäle sind womöglich selbst unehrlich. Sie verschicken falsche Nachrichten – etwa dem einen «Angriff», dem anderen «Rückzug» – und versuchen so, die anderen zu verwirren.
Warum ist das so schwierig? Ein kleines Beispiel: Drei Generäle, einer davon ist ein Verräter. General A schlägt Angriff vor. Der Verräter B erzählt C, A habe Rückzug befohlen. Jetzt hat C zwei widersprüchliche Aussagen – und keine Möglichkeit herauszufinden, ob A oder B lügt. Bei nur drei Generälen lässt sich ein einzelner Verräter nicht entlarven.
Lamport und seine Kollegen zeigten, dass ein solches System nur dann sicher zu einer Einigung kommt, wenn mehr als zwei Drittel der Generäle ehrlich sind – und das auch nur, wenn alle Teilnehmenden bekannt sind. In einem offenen Netzwerk wie dem Internet, wo jede und jeder mitmachen und beliebig viele Identitäten erzeugen kann, galt das Problem lange als unlösbar.
Was das für eine Blockchain bedeutet
Übertragen auf Bitcoin: Würde eine Mehrheit der Rechenleistung im Netzwerk unehrlich handeln, könnte sie zum Beispiel Bitcoin doppelt ausgeben. Man spricht von einem 51-Prozent-Angriff. Bitcoin begegnet dem mit Proof of Work: Nicht die Zahl der Teilnehmenden zählt, sondern die eingesetzte Rechenleistung – und die lässt sich nicht vortäuschen. Wer das Netzwerk übernehmen wollte, müsste mehr Rechenleistung aufbringen als alle ehrlichen Miner zusammen.
Satoshis Lösung
Am 13. November 2008, kurz nach der Veröffentlichung des Whitepapers, erklärte Satoshi Nakamoto auf einer Mailingliste für Kryptographie, wie Proof of Work das Problem der byzantinischen Generäle löst. Er erzählte die Geschichte in moderner Form:
Eine Gruppe von Generälen will gemeinsam das WLAN-Passwort eines Königs knacken. Das gelingt nur, wenn alle gleichzeitig angreifen; wer allein loslegt, wird entdeckt. Wie einigen sie sich auf einen Zeitpunkt? Die Regel: Der zuerst gehörte Zeitpunkt gilt. Weil Nachrichten aber unterschiedlich schnell ankommen, hören verschiedene Generäle verschiedene Zeitpunkte zuerst.
Die Lösung: Jeder General arbeitet an einem schwierigen Rechenrätsel, in das der vorgeschlagene Angriffszeitpunkt eingeht. Das Rätsel ist so schwer, dass alle zusammen im Schnitt etwa zehn Minuten brauchen. Wer es löst, schickt die Lösung herum, und alle arbeiten auf dieser Lösung weiter. Taucht eine andere Kette mit einem anderen Zeitpunkt auf, gilt immer die längere – die mit mehr geleisteter Arbeit. Nach etwa zwei Stunden ist der Zeitpunkt durch rund zwölf aufeinander aufbauende Rätsel gesichert.
Und das Entscheidende: Jeder General kann an der Schwierigkeit der Kette ablesen, wie viel Rechenleistung insgesamt investiert wurde. So sieht er, dass eine Mehrheit mitgemacht hat – ohne die anderen zu kennen oder ihnen vertrauen zu müssen. Genau so funktioniert Bitcoin: Die Blockchain mit der meisten geleisteten Arbeit ist die gültige, und jede und jeder kann das selbst nachprüfen. Damit löste Satoshi ein Problem der verteilten Datenbanken, an dem Fachleute jahrzehntelang gearbeitet hatten.
Eng verwandt ist der Angriff mit falschen Identitäten, den ich in Was ist eine Sybil-Attacke? erkläre.