Protokoły BFT: PBFT i Tendermint

Problem generałów bizantyjskich, sformułowany przez Lamporta, Shostaka i Pease'a w 1982 roku, stawia pytanie: czy system rozproszony może osiągnąć konsensus, gdy niektórzy uczestnicy wysyłają sprzeczne komunikaty? Nazwa problemu pochodzi od bizantyjskich generałów, którzy muszą skoordynować atak, ale wśród których mogą znajdować się zdrajcy wysyłający sprzeczne rozkazy. System jest odporny na bizantyjskie błędy (Byzantine Fault Tolerant, BFT), jeśli osiąga poprawny konsensus mimo obecności najwyżej f złośliwych węzłów spośród 3f+1 wszystkich węzłów. BFT jest złotym standardem konsensusu blockchainów wymagających bezpieczeństwa w warunkach działania przeciwnika.

PBFT (Castro i Liskov, 1999) był pierwszym praktycznym protokołem BFT, który pokazał, że BFT może działać wydajnie w rzeczywistych systemach. PBFT działa w widokach (terminach), z których każdy ma wyznaczony węzeł primary (lidera). Normalne działanie obejmuje trzy fazy: pre-prepare (primary rozgłasza żądanie klienta i numer sekwencyjny), prepare (repliki rozgłaszają zgodę wraz z numerem sekwencyjnym) oraz commit (repliki rozgłaszają potwierdzenie zatwierdzenia). Żądanie jest wykonywane, gdy replika zbierze 2f+1 pasujących komunikatów commit. PBFT zapewnia bezpieczeństwo i żywotność przy założeniu, że mniej niż 1/3 replik ma charakter bizantyjski.

Głównym ograniczeniem PBFT jest złożoność komunikatowa O(n^2) dla każdego żądania: każda z n replik wysyła komunikaty do wszystkich pozostałych w fazach prepare i commit. Dla n=100 replik każde żądanie generuje około 10 000 komunikatów. To sprawia, że PBFT jest niepraktyczny dla dużych zbiorów walidatorów. Społeczność zajmująca się badaniami nad BFT przez dwie dekady pracowała nad poprawą tego rozwiązania: BFT-SMART zmniejszył stałe, HotStuff osiągnął liniową złożoność komunikatową dzięki modelowi przekazywania przez lidera, a Tendermint przystosował idee PBFT do zastosowania w publicznych blockchainach.

Gdy podejrzewa się, że primary PBFT działa wadliwie (przekroczenie limitu czasu), repliki uruchamiają zmianę widoku. Każda replika rozgłasza komunikat view-change zawierający jej stan (wartości prepared z poprzedniego widoku). Nowy primary zbiera 2f+1 komunikatów view-change, konstruuje komunikat new-view dowodzący, że zmiana stanu jest zgodna z wcześniej zatwierdzonymi wartościami, a następnie go rozgłasza. Zmiany widoku są kosztowne — wymagają O(n^3) komunikatów — i stanowiły praktyczne wąskie gardło. Optymalizacje takie jak certyfikat view-change w PBFT oraz potokowy projekt HotStuff rozwiązują ten problem.

Tendermint (2014, Kwon; wdrożenie produkcyjne w Cosmos w 2019 roku) przystosowuje PBFT do środowisk publicznych blockchainów. Tendermint ma trzy fazy dla każdego bloku: propose (lider rozgłasza proponowany blok), prevote (walidatorzy głosują nad propozycją) oraz precommit (walidatorzy głosują za zatwierdzeniem po otrzymaniu 2/3 głosów prevote). Blok zostaje zatwierdzony, gdy walidator zbierze 2/3 głosów precommit (certyfikat kworum). Walidatorzy kolejno pełnią rolę proponujących w porządku round-robin, z uwzględnieniem stawki. Jeśli runda zakończy się przekroczeniem limitu czasu bez zatwierdzenia, walidatorzy przechodzą do następnej rundy z głosem nil.

Tendermint zapewnia silne bezpieczeństwo: zatwierdzony blok jest ostateczny i nie można go cofnąć, dopóki mniej niż 1/3 stawki nie ma charakteru bizantyjskiego. Jest to finalność synchroniczna — po zatwierdzeniu nie występują forki. Żywotność wymaga sieci częściowo synchronicznej: protokół robi postępy, gdy opóźnienia komunikatów są ograniczone, ale nie wymaga ciągłej synchronii. Kompromis między żywotnością a bezpieczeństwem jest fundamentalny: Tendermint poświęca żywotność (może się zatrzymać przy podziale sieci), aby zagwarantować bezpieczeństwo, w przeciwieństwie do łańcuchów takich jak Bitcoin, które poświęcają bezpieczeństwo (dopuszczają tymczasowe forki) na rzecz żywotności.

Kluczowym mechanizmem Tendermint jest blokowanie głosów. Gdy walidator wysyła precommit dla bloku w rundzie r, zostaje zablokowany na tym bloku. W kolejnych rundach zablokowany walidator może oddać prevote wyłącznie na blok, na którym jest zablokowany (albo głos nil, jeśli otrzyma dowód, że blok nie został zatwierdzony). Zapobiega to sprzecznym zatwierdzeniom w różnych rundach. Walidator może się odblokować tylko wtedy, gdy w późniejszej rundzie otrzyma polkę (2/3 głosów prevote) dla innego bloku, co dowodzi, że pierwotny blok nie został zatwierdzony.

Cosmos Inter-Blockchain Communication (IBC) korzysta z natychmiastowej finalności Tendermint przy transferach między łańcuchami. Lekki klient Tendermint śledzi zbiór walidatorów i najnowszy commit (nagłówek bloku oraz podpisy precommit od 2/3 walidatorów). Aby zweryfikować pakiet z łańcucha A, moduł IBC łańcucha B weryfikuje certyfikat kworum — sprawdza, czy 2/3 walidatorów łańcucha A podpisało odpowiedni nagłówek bloku. Oznacza to, że bezpieczeństwo IBC zależy od gwarancji BFT Tendermint: transfer między łańcuchami jest ostateczny natychmiast po zatwierdzeniu bloku źródłowego.

HotStuff (Yin i in., 2018; podstawa LibraBFT/DiemBFT firmy Facebook, a obecnie także Aptos i Sui) osiąga złożoność komunikatową O(n) na rundę konsensusu dzięki topologii gwiazdy: wszyscy walidatorzy wysyłają głosy do lidera, lider agreguje je w podpis progowy (QC, quorum certificate), a następnie rozgłasza QC. HotStuff wykorzystuje trójfazowy mechanizm łańcuchowy, w którym dowody bezpieczeństwa obejmują trzy kolejne QC, co umożliwia potokowanie. Liniowa złożoność sprawia, że HotStuff jest praktyczny dla 100–300 walidatorów, jak ma to miejsce w Aptos i Sui.

Blockchainy korporacyjne (Hyperledger Fabric, Besu, Quorum) używają konsensusu BFT w sieciach uprawnionych, w których tożsamość walidatorów jest znana. Usługa porządkowania Hyperledger Fabric oparta na Raft zapewnia tolerancję awarii (nie bizantyjskich) dla zaufanych konsorcjów. Planowany etap rozwoju Fabric obejmuje SmartBFT, implementację opartą na bibliotece. R3 Corda korzysta z klastra notariuszy z BFT-SMART w celu zapobiegania podwójnemu wydawaniu środków. Wybór między CFT i BFT odzwierciedla założenia dotyczące zaufania: BFT jest potrzebne, gdy walidatorzy mogą działać w sposób wrogi, natomiast CFT wystarcza, gdy są jedynie zawodni.

Zrozumienie BFT wymaga wiedzy o tym, jakim atakom ten mechanizm się opiera, a jakich nie obsługuje. BFT radzi sobie z walidatorami dopuszczającymi się equivocation (wysyłającymi sprzeczne komunikaty do różnych uczestników) oraz z walidatorami, którzy ulegają awarii lub przestają odpowiadać. Nie chroni przed atakami Sybil — atakujący, który kontroluje 1/3 walidatorów dzięki tworzeniu fałszywych tożsamości, może naruszyć bezpieczeństwo. Dlatego publiczne łańcuchy BFT stosują ważenie według stawki PoS: zdobycie 1/3 stawki kosztuje realne pieniądze, zapewniając odporność na ataki Sybil. BFT zakłada również ostateczne dostarczenie komunikatów (częściową synchronię) — trwający dłużej niż limit żywotności podział sieci może zatrzymać łańcuch.

Jaki jest maksymalny odsetek walidatorów, które mogą mieć charakter bizantyjski w standardowym protokole BFT przy zachowaniu bezpieczeństwa?

Protokoły BFT zapewniają konsensus mimo obecności najwyżej 1/3 złośliwych walidatorów. PBFT (1999) dowiódł praktycznej użyteczności BFT, ale ma złożoność komunikatową O(n^2). Tendermint przystosowuje PBFT do blockchainów, zapewniając natychmiastową finalność i blokowanie głosów. HotStuff osiąga złożoność O(n) dzięki certyfikatom kworum opartym na podpisach progowych i jest używany w Aptos oraz Sui. Cosmos IBC wykorzystuje natychmiastową finalność Tendermint do weryfikowanych transferów między łańcuchami. Blockchainy korporacyjne używają BFT-SMART lub Raft, zależnie od tego, czy spodziewane są błędy bizantyjskie, czy jedynie awarie typu crash.