Problem der byzantinischen Generäle

Die Allegorie beschreibt mehrere geografisch getrennte Generäle des byzantinischen Heeres, die sich darauf einigen müssen, gleichzeitig anzugreifen oder sich zurückzuziehen. Sie kommunizieren nur über Boten, und einige Generäle oder Boten können Verräter sein, die widersprüchliche Informationen verbreiten. Die Frage lautet, ob die loyalen Generäle trotz der Verräter zu einer gemeinsamen Entscheidung gelangen können. Das zentrale theoretische Ergebnis: Konsens ist erreichbar, wenn mehr als zwei Drittel der Teilnehmer ehrlich sind, das heißt, das System toleriert bis zu f byzantinische Fehler bei n größer oder gleich 3f plus 1 Nodes.

Formalisiert wurde das Problem von Leslie Lamport, Robert Shostak und Marshall Pease im Paper The Byzantine Generals Problem, erschienen in ACM Transactions on Programming Languages and Systems (TOPLAS), Band 4, Nummer 3, Juli 1982, Seiten 382 bis 401. Daraus stammt der Begriff byzantinische Fehlertoleranz (BFT). Bei n gleich 3 und einem Verräter ist eine Einigung mit ausschließlich mündlichen, unsignierten Nachrichten unmöglich; mit signierten, fälschungssicheren Nachrichten verbessert sich die Toleranz.

Es ist der Rahmen, aus dem das gesamte BFT-Feld hervorgeht, das bereits im Glossar definiert ist. Das Problem ist die Fragestellung, die byzantinische Fehlertoleranz die Eigenschaft, die es löst, und pBFT, Tendermint oder HotStuff sind konkrete Implementierungen. PBFT (Castro und Liskov, 1999) war die erste praktikable effiziente Lösung; Tendermint und CometBFT, die Basis von Cosmos, bieten sofortige Finalität und tolerieren dabei weniger als ein Drittel byzantinischer Validatoren. Satoshi Nakamoto löste 2008 eine permissionless Variante über Proof of Work.