BFT-Protokolle: PBFT und Tendermint

Das von Lamport, Shostak und Pease 1982 formulierte Problem der byzantinischen Generäle fragt: Kann ein verteiltes System einen Konsens erreichen, wenn einige Teilnehmer widersprüchliche Nachrichten senden? Das Problem ist nach byzantinischen Generälen benannt, die einen Angriff koordinieren müssen, unter denen sich aber Verräter befinden können, die widersprüchliche Befehle senden. Ein System ist Byzantine Fault Tolerant (BFT), wenn es trotz bis zu f bösartiger Knoten unter insgesamt 3f+1 Knoten einen korrekten Konsens erreicht. BFT gilt als Goldstandard für Blockchain-Konsens, der Sicherheit unter Bedingungen mit Angreifern erfordert.

PBFT (Castro und Liskov, 1999) war das erste praktisch einsetzbare BFT-Protokoll und zeigte, dass BFT in realen Systemen effizient betrieben werden kann. PBFT arbeitet in Views (Runden), von denen jede einen designierten Primary (Leader) hat. Der Normalbetrieb umfasst drei Phasen: Pre-Prepare (der Primary sendet die Client-Anfrage und die Sequenznummer per Broadcast), Prepare (die Replikas senden ihre Übereinstimmung mit der Sequenznummer per Broadcast) und Commit (die Replikas senden eine Commit-Bestätigung per Broadcast). Eine Anfrage wird ausgeführt, sobald eine Replika 2f+1 übereinstimmende Commit-Nachrichten gesammelt hat. PBFT gewährleistet Sicherheit und Liveness unter der Annahme, dass weniger als ein Drittel der Replikas byzantinisch ist.

Die wichtigste Einschränkung von PBFT ist die Nachrichtenkomplexität O(n^2) pro Anfrage: Jede der n Replikas sendet in der Prepare- und Commit-Phase Nachrichten an alle anderen. Bei n=100 Replikas erzeugt jede Anfrage ungefähr 10.000 Nachrichten. Dadurch ist PBFT für große Validator-Sets ungeeignet. Die BFT-Forschungsgemeinschaft hat zwei Jahrzehnte lang an Verbesserungen gearbeitet: BFT-SMART reduzierte konstante Faktoren, HotStuff erreichte durch ein Leader-Relay-Modell eine lineare Nachrichtenkomplexität, und Tendermint passte PBFT-Ideen für die Verwendung in öffentlichen Blockchains an.

Wenn ein PBFT-Primary als fehlerhaft vermutet wird (Timeout), lösen die Replikas einen View Change aus. Jede Replika sendet eine View-Change-Nachricht per Broadcast, die ihren Zustand enthält (in der alten View vorbereitete Werte). Der neue Primary sammelt 2f+1 View-Change-Nachrichten, erstellt eine New-View-Nachricht, die beweist, dass der Zustandsübergang mit zuvor bestätigten Werten konsistent ist, und sendet sie per Broadcast. View Changes sind teuer – sie erzeugen O(n^3) Nachrichten – und stellten einen praktischen Engpass dar. Optimierungen wie das View-Change-Zertifikat von PBFT und das Pipeline-Design von HotStuff begegnen diesem Problem.

Tendermint (2014, Kwon; produktiver Einsatz in Cosmos seit 2019) passt PBFT an öffentliche Blockchain-Umgebungen an. Tendermint hat drei Phasen pro Block: Propose (der Leader sendet den vorgeschlagenen Block per Broadcast), Prevote (die Validatoren stimmen über den Vorschlag ab) und Precommit (die Validatoren stimmen für den Commit, nachdem sie zwei Drittel der Prevotes gesehen haben). Ein Block ist bestätigt, sobald ein Validator zwei Drittel Precommit-Stimmen gesammelt hat (ein Quorum Certificate). Die Validatoren wechseln sich bei den Blockvorschlägen in einer nach Stake gewichteten Round-Robin-Reihenfolge ab. Läuft eine Runde ohne Commit ab, gehen die Validatoren mit einer Nil-Stimme in die nächste Runde über.

Tendermint bietet starke Sicherheit: Ein bestätigter Block ist final und kann nicht zurückgesetzt werden, solange weniger als ein Drittel des Stakes byzantinisch ist. Dies ist synchrone Finalität – nach dem Commit gibt es keine Forks. Für Liveness ist ein teilweise synchrones Netzwerk erforderlich: Das Protokoll macht Fortschritte, sobald die Nachrichtenverzögerungen begrenzt sind, setzt aber keine dauerhafte Synchronität voraus. Der Zielkonflikt zwischen Liveness und Sicherheit ist grundlegend: Tendermint opfert Liveness (die Chain kann bei einer Netzwerkpartition anhalten), um Sicherheit zu garantieren, anders als Chains wie Bitcoin, die Sicherheit opfern (vorübergehende Forks zulassen), um Liveness zu gewährleisten.

Ein kritischer Mechanismus von Tendermint ist Vote Locking. Wenn ein Validator in Runde r einen Precommit für einen Block sendet, ist er auf diesen Block festgelegt. In nachfolgenden Runden darf ein festgelegter Validator nur noch für den Block, auf den er festgelegt ist, oder für eine Nil-Stimme stimmen, wenn er einen Beleg erhält, dass der Block nicht bestätigt wurde. Dadurch werden widersprüchliche Commits über mehrere Runden hinweg verhindert. Ein Validator kann die Festlegung nur aufheben, wenn er in einer späteren Runde eine Polka (zwei Drittel Prevotes) für einen anderen Block erhält, die beweist, dass der ursprüngliche Block nicht bestätigt wurde.

Cosmos Inter-Blockchain Communication (IBC) nutzt die sofortige Finalität von Tendermint für Transfers zwischen Chains. Ein Tendermint-Light-Client verfolgt das Validator-Set und den neuesten Commit (einen Block-Header sowie zwei Drittel Precommit-Signaturen). Um ein Paket von Chain A zu verifizieren, prüft das IBC-Modul von Chain B das Quorum Certificate – dass zwei Drittel der Validatoren von Chain A den relevanten Block-Header signiert haben. Dadurch hängt die Sicherheit von IBC von der BFT-Garantie von Tendermint ab: Ein Transfer zwischen Chains ist final, sobald der Quellblock bestätigt wurde.

HotStuff (Yin et al., 2018; Grundlage für Facebooks LibraBFT/DiemBFT sowie für Aptos und Sui) erreicht eine Nachrichtenkomplexität von O(n) pro Konsensrunde, indem es eine Stern-Topologie verwendet: Alle Validatoren senden ihre Stimmen an den Leader, der sie zu einer Threshold-Signatur (QC, Quorum Certificate) aggregiert und das QC per Broadcast verteilt. HotStuff verwendet ein dreiphasiges Chaining-Design, bei dem sich Sicherheitsbeweise über drei aufeinanderfolgende QCs erstrecken, wodurch Pipelining ermöglicht wird. Die lineare Komplexität macht HotStuff für 100–300 Validatoren praktikabel, wie der Einsatz in Aptos und Sui zeigt.

Enterprise-Blockchains (Hyperledger Fabric, Besu, Quorum) verwenden BFT-Konsens für permissioned Netzwerke, in denen die Identität der Validatoren bekannt ist. Der auf Raft basierende Ordering Service von Hyperledger Fabric bietet Crash Fault Tolerance (keine Byzantine Fault Tolerance) für vertrauenswürdige Konsortien. Fabrics geplantes BFT-Meilensteinziel ist SmartBFT, eine bibliotheksbasierte Implementierung. R3 Corda verwendet zur Verhinderung von Double Spending einen Notary-Cluster mit BFT-SMART. Die Wahl zwischen CFT und BFT spiegelt die Vertrauensannahmen wider: BFT ist erforderlich, wenn Validatoren bösartig handeln können; CFT genügt, wenn sie lediglich unzuverlässig sind.

Um BFT zu verstehen, muss man wissen, gegen welche Angriffe es schützt und gegen welche nicht. BFT bewältigt Validatoren, die Äquivokation betreiben (widersprüchliche Nachrichten an verschiedene Peers senden), sowie Validatoren, die abstürzen oder stumm bleiben. Gegen Sybil-Angriffe bietet es keinen Schutz – ein Angreifer, der durch das Erstellen gefälschter Identitäten ein Drittel der Validatoren kontrolliert, kann die Sicherheit brechen. Deshalb verwenden öffentliche BFT-Chains eine nach PoS-Stake gewichtete Auswahl: Der Erwerb eines Drittels des Stakes kostet echtes Geld und bietet Sybil-Resistenz. BFT setzt außerdem die letztendliche Zustellung von Nachrichten voraus (partielle Synchronität) – eine Netzwerkpartition, die länger als das Liveness-Timeout andauert, kann die Chain anhalten.

Welcher maximale Anteil der Validatoren darf in einem standardmäßigen BFT-Protokoll byzantinisch sein, während die Sicherheit erhalten bleibt?

BFT-Protokolle gewährleisten Konsens trotz bis zu einem Drittel bösartiger Validatoren. PBFT (1999) zeigte, dass BFT praktisch einsetzbar ist, weist jedoch eine Nachrichtenkomplexität von O(n^2) auf. Tendermint passt PBFT für Blockchains an und bietet sofortige Finalität sowie Vote Locking. HotStuff erreicht durch Quorum Certificates mit Threshold-Signaturen eine Komplexität von O(n) und wird in Aptos und Sui eingesetzt. Cosmos IBC nutzt die sofortige Finalität von Tendermint für verifizierte Transfers zwischen Chains. Enterprise-Blockchains verwenden BFT-SMART oder Raft, je nachdem, ob byzantinische Fehler oder lediglich Absturzfehler zu erwarten sind.