Czym jest protokół konsensusu HotStuff i jak działa?

Czym jest protokół konsensusu HotStuff?

HotStuff to protokół konsensusu BFT, dzięki któremu stała grupa walidatorów może uzgodnić jedną, ostateczną kolejność transakcji lub innych poleceń, nawet jeśli część tej grupy popełnia błędy lub celowo wysyła wprowadzające w błąd komunikaty.

BFT oznacza Byzantine Fault Tolerance. Oznacza to, że protokół jest odporny na walidatorów, którzy ulegają awarii, nie odpowiadają, kłamią lub wysyłają różne wiadomości do różnych uczestników. HotStuff zapewnia, że prawidłowo działający walidatorzy nadal podążają za tą samą wersją blockchaina lub wspólnej księgi.

HotStuff działa w oparciu o znaną grupę walidatorów. Protokół nie rozstrzyga więc sam, kto może zostać walidatorem, jak zorganizowany jest staking ani w jaki sposób otwarta sieć crypto wybiera uczestników. Takie zasady leżą poza HotStuff. Protokół koncentruje się na pytaniu: jak ta grupa walidatorów bezpiecznie osiąga porozumienie?

Pierwotny model zakłada grupę walidatorów z n = 3f + 1 uczestnikami. W tym przypadku n to całkowita liczba walidatorów, a f to maksymalna liczba walidatorów, którzy mogą zachowywać się błędnie lub złośliwie. Mówiąc prosto: dopóki mniej niż jedna trzecia walidatorów jest niewiarygodna, system działa poprawnie. Przy 4 walidatorach maksymalnie 1 może być niewiarygodny. Pozostałych 3 walidatorów może wtedy nadal wspólnie podjąć bezpieczną decyzję. Przy 7 walidatorach maksymalnie 2 walidatorów może być niewiarygodnych. Aby decyzja była ważna, co najmniej 5 walidatorów musi się ze sobą zgodzić. HotStuff wykorzystuje do tego quorum certificate, często skracane jako QC. QC to zwięzły dowód kryptograficzny, że wystarczająca liczba walidatorów zagłosowała za tym samym wnioskiem. Kworum to minimalny poziom poparcia potrzebny do podjęcia decyzji. W pierwotnym modelu takie kworum wynosi n − f, czyli 2f + 1, głosów.

Przy 4 walidatorach są to 3 głosy. Przy 7 walidatorach jest to 5 głosów. Ten wysoki próg zapobiega temu, aby niewielka grupa niewiarygodnych walidatorów mogła samodzielnie doprowadzić do zatwierdzenia sprzecznego bloku.

HotStuff został zaprojektowany dla sieci częściowo synchronicznej. Oznacza to, że wiadomości mogą być czasowo silnie opóźnione, ale sieć ostatecznie musi ponownie stać się na tyle stabilna, aby dostarczać wiadomości na czas. Bezpieczeństwo pozostaje zachowane, także podczas dużych opóźnień. Postęp, taki jak finalizowanie nowych bloków, jest gwarantowany dopiero wtedy, gdy sieć jest wystarczająco stabilna.

Najważniejsze informacje

• HotStuff to protokół konsensusu BFT dla stałej grupy walidatorów.
• Walidatorzy wspólnie ustalają jedną kolejność transakcji lub poleceń.
• Quorum certificate kryptograficznie potwierdza, że wystarczająca liczba walidatorów wspiera ten sam wniosek.
• Pierwotny model toleruje mniej niż jedną trzecią walidatorów bizantyjskich.
• HotStuff zachowuje bezpieczeństwo przy opóźnieniach sieci, ale do zapewnienia postępu potrzebuje stabilnej sieci.

Jak działa protokół konsensusu HotStuff?

HotStuff działa w następujących po sobie rundach, w których jeden tymczasowy lider koordynuje propozycję, a walidatorzy nad nią głosują. Taka runda nazywa się view. Lider nie jest stałym producentem bloków, lecz pełni wyłącznie rolę koordynacyjną w ramach danej view.

W pierwotnym wariancie Basic HotStuff potrzebne są trzy fazy głosowania, zanim decyzja stanie się ostateczna: prepare, pre-commit i commit. Każda faza daje walidatorom dodatkową pewność, że nie da się sfinalizować sprzecznej propozycji.

Późniejsza praktyczna forma, Chained HotStuff, pozwala, aby te fazy nakładały się na kolejne bloki. Dzięki temu nowy blok może jednocześnie dostarczać dowodu postępu dla wcześniejszych bloków. Podstawowe zasady dotyczące głosowania, kworum i bezpieczeństwa pozostają przy tym takie same.

Jaką rolę odgrywają walidatorzy i lider?

Walidatorzy sprawdzają, czy propozycja lidera jest bezpieczna, zanim oddadzą głos. Weryfikują między innymi, czy propozycja opiera się na właściwych wcześniejszych blokach i czy mieści się w regułach bezpieczeństwa protokołu. Jeśli tak jest, wysyłają do lidera cyfrowo podpisany głos.

Lider zbiera głosy. Gdy lider ma ich wystarczająco dużo, łączy je w jeden QC. Zamiast więc za każdym razem przesyłać wszystkie pojedyncze głosy, lider może rozpowszechnić jeden zwięzły dowód, który pokazuje, że kworum się zgodziło.

Walidatorzy korzystają także z lock, czyli blokady. Lock to reguła, która zapobiega temu, by walidator później bez powodu wsparł sprzeczną gałąź. Zwykle walidator głosuje tylko za propozycją, która rozszerza jego zablokowaną gałąź. Wyjątek jest możliwy, gdy QC z wyższej view zgodnie z regułami bezpieczeństwa pokazuje, że kontynuacja jest bezpieczna.

Gdy w danej view nie ma postępu, na przykład dlatego, że lider jest offline, walidatorzy przełączają się na nową view. Wysyłają wtedy wiadomość new-view do kolejnego lidera. Zawiera ona ich najwyższy znany prepareQC, czyli najsilniejszy dowód, jaki w danym momencie znają.

Nowy lider wybiera najwyższy otrzymany QC jako highQC. Stanowi to punkt wyjścia dla bezpiecznej nowej propozycji. Z góry znana rotacja może określać, kto będzie kolejnym liderem. Pacemaker, mechanizm z time-outami, sprawia, że walidatorzy nie czekają bez końca na niedziałającego lidera.

Jak przebiega proces konsensusu?

W Basic HotStuff podejmowanie decyzji przebiega krok po kroku przez trzy fazy głosowania. Poniższy opis pokazuje, jak jedna propozycja przechodzi drogę od początku do ostatecznej decyzji.

1. Nowy lider zbiera informacje. Przy zmianie view nowy lider otrzymuje wiadomości new-view od kworum walidatorów. Lider wybiera najwyższy QC, który się w nich znajduje. Zapobiega to sytuacji, w której lider proponuje coś, co jest sprzeczne z wcześniej bezpiecznie kontynuowanym blokiem.

2. Lider składa propozycję. Lider buduje nowy blok na gałęzi uzasadnionej przez highQC i wysyła go do wszystkich walidatorów. Propozycja zawiera więc także dowód, dlaczego jest to bezpieczna ścieżka kontynuacji.

3. Walidatorzy sprawdzają i głosują w fazie prepare. Każdy walidator sprawdza, czy blok spełnia reguły bezpieczeństwa. Jeżeli propozycja je spełnia, walidator odsyła do lidera głos prepare.

4. Lider tworzy dowody dla prepare i pre-commit. Po 2f + 1 głosach prepare lider tworzy prepareQC i rozpowszechnia go na potrzeby fazy pre-commit. Następnie walidatorzy ponownie zbierają głosy. Po kolejnych 2f + 1 głosach lider tworzy precommitQC.

5. Walidatorzy blokują i commitują propozycję. Walidatorzy ustawiają lock na podstawie precommitQC i głosują w fazie commit. Następnie lider łączy 2f + 1 głosów commit w commitQC. Kolejna wiadomość decide sprawia, że propozycja staje się wykonalna i ostateczna.

Przykład: Załóżmy, że grupa składa się z 4 walidatorów. Lider proponuje blok. Co najmniej 3 walidatorów musi głosować w każdej wymaganej fazie, zanim lider będzie mógł utworzyć QC. Jeden wadliwy walidator nie może więc wymusić, by proces ostatecznie zatwierdził inny blok.

Chained HotStuff czyni tę metodę bardziej wydajną, łącząc fazy różnych bloków. Zgodnie z three-chain commit rule najstarszy blok w sekwencji staje się ostateczny, gdy trzy kolejne bloki są ze sobą połączone zgodnie z regułami protokołu za pomocą ważnych QC. Ten łańcuch dostarcza dowodu commit dla najstarszego istotnego bloku.

Jak HotStuff radzi sobie z błędami bizantyjskimi?

HotStuff ogranicza skutki błędów bizantyjskich, łącząc wysoki próg głosów, podpisane głosy, locki oraz jasne reguły zmiany view. Walidator bizantyjski to walidator, który zachowuje się nieprzewidywalnie lub złośliwie, na przykład kłamie, nie odpowiada albo wysyła różne propozycje do różnych walidatorów.

Granica błędów to mniej niż jedna trzecia walidatorów w grupie nieważonej. Przy n = 3f + 1 uczestnikach maksymalnie f walidatorów może być bizantyjskich. QC wymaga 2f + 1 głosów, co jest równe n − f.

Istotną konsekwencją jest to, że dwa kwora zawsze się pokrywają. Na przykład przy 7 walidatorach do QC potrzeba 5 głosów. Dwie grupy po 5 głosów muszą mieć wspólnych co najmniej 3 walidatorów. Ponieważ co najwyżej 2 walidatorów może być bizantyjskich, w tym pokryciu zawsze znajduje się co najmniej jeden poprawny walidator.

Poprawny walidator nie głosuje dwukrotnie za sprzecznymi propozycjami w tej samej fazie i view. W rezultacie nie mogą powstać dwa sprzeczne QC dla tej samej fazy i view. Locki oraz reguła safeNode, czyli sprawdzanie, czy nowa propozycja bezpiecznie bazuje na znanych dowodach, dodatkowo zapewniają, że walidatorzy nie przechodzą później bez powodu na sprzeczną gałąź.

Chroni to safety. Safety oznacza tutaj, że dwa sprzeczne bloki nie mogą jednocześnie stać się ostateczne za sprawą poprawnie działających walidatorów. W razie niepewności sieć woli poczekać, niż doprowadzić do ostatecznego zatwierdzenia dwóch różnych historii.

Liveness dotyczy postępu: zdolności do finalizowania nowych bloków. HotStuff nie obiecuje takiego postępu podczas długotrwałej partycji sieci lub utrzymujących się dużych opóźnień. Gdy sieć ponownie stanie się wystarczająco stabilna i poprawny lider będzie prowadził tę samą view dostatecznie długo, walidatorzy mogą znów formować kwora i kontynuować.

W wariantach proof-of-stake tę granicę często wyraża się wagą głosu zamiast samą liczbą walidatorów. Wtedy nie każdy walidator ma taką samą wagę. Gwarancje bezpieczeństwa i postępu obowiązują tylko wtedy, gdy mniej niż jedna trzecia istotnej wagi głosu jest bizantyjska.

Do czego wykorzystuje się protokół konsensusu HotStuff?

HotStuff wykorzystuje się do tego, aby grupa serwerów lub walidatorów ustaliła jedną ostateczną kolejność poleceń. Nazywa się to state machine replication: wiele komputerów wykonuje te same polecenia w tej samej kolejności, dzięki czemu zachowują ten sam wynik i tę samą wspólną księgę.

W blockchainie to zadanie może polegać na porządkowaniu i finalizowaniu bloków z transakcjami. Gdy walidatorzy ustalą kolejność, inne elementy sieci mogą wykonać transakcje i zaktualizować ledger. HotStuff w praktyce przede wszystkim określa kolejność i finalność decyzji.

DiemBFT był rodziną konsensusu opartą na HotStuff dla historycznego blockchaina Diem. Ta rodzina protokołów porządkowała i finalizowała transakcje w ramach konfigurowalnej grupy walidatorów.

Aptos używa AptosBFT, protokołu konsensusu BFT opartego na Jolteon. Protokół wykorzystuje siłę głosu ważoną według stake’u i może stosować wybór lidera oparty na reputacji, w którym zachowanie i wyniki walidatorów wpływają na wybór liderów. i może stosować reputation-based wybór lidera, gdzie zachowanie i wyniki walidatorów wpływają na wybór liderów. W tym podejściu waga głosu walidatorów może się różnić w zależności od stake.

Flow korzysta z rodziny konsensusu HotStuff i w styczniu 2023 roku migrował do Jolteon. Jolteon to zoptymalizowany wariant HotStuff. Te systemy nie muszą więc używać pierwotnej specyfikacji HotStuff dokładnie tak, jak została zaprojektowana; szczegóły, takie jak wybór lidera i przetwarzanie, mogą się różnić.

Jakie są zalety HotStuff?

Ważną zaletą HotStuff jest to, że organizuje komunikację między walidatorami bardziej efektywnie niż protokoły, w których każdy stale musi komunikować się ze wszystkimi innymi walidatorami.

• Zwięzłe dowody: Lider łączy głosy walidatorów za pomocą threshold signatures w jeden QC. Threshold signatures to zagregowane podpisy cyfrowe, które potwierdzają, że wystarczająca liczba walidatorów zagłosowała. Dzięki temu walidator nie musi za każdym razem otrzymywać wszystkich pojedynczych głosów, aby sprawdzić kworum.

• Komunikacja liniowa przy poprawnym liderze: W pierwotnym modelu obciążenie komunikacją i weryfikacją po stronie poprawnego lidera rośnie w przybliżeniu proporcjonalnie do liczby walidatorów, zamiast rosnąć znacznie szybciej. Nie mówi to automatycznie, ile transakcji może przetworzyć pełny blockchain, ponieważ wykonywanie, przechowywanie, sprzęt i dystrybucja transakcji również mogą stanowić ograniczenia.

• Sprawniejsze zmiany lidera: HotStuff zaprojektowano tak, aby także przy awarii lidera wymagał mniej komunikacji niż PBFT. Jest to ważne, gdy lider przestaje działać lub nie rozpowszechnia użytecznej propozycji.

• Pipelining w Chained HotStuff: Nowe propozycje mogą przyczyniać się do finalizowania wcześniejszych bloków. Dzięki temu sieć nie musi kończyć każdej fazy całkowicie osobno, zanim rozpocznie kolejną propozycję.

• Deterministyczna finalność: Zacommitowany blok jest, przy założeniach bezpieczeństwa, ostateczny. Deterministyczna finalność oznacza, że poprawnie działający walidatorzy nie mogą później uznać sprzecznego bloku za ostateczny.

HotStuff ma ponadto optimistic responsiveness. Po ustabilizowaniu sieci poprawny lider nie musi stale czekać na z góry ustawione maksymalne opóźnienie sieci, jeśli wymagane wiadomości zostały już odebrane wcześniej. Może to poprawić postęp w korzystnych warunkach sieciowych.

Jakie są ograniczenia HotStuff?

HotStuff nie zapewnia nieograniczonej ochrony ani gwarantowanego postępu w każdych warunkach. Działanie zależy od jasnych założeń dotyczących walidatorów, komunikacji w sieci oraz wybranej implementacji.

• Granice tolerancji błędów: Formalna analiza bezpieczeństwa obowiązuje wtedy, gdy mniej niż jedna trzecia walidatorów lub wagi głosu jest bizantyjska. Przy większym udziale niewiarygodnych uczestników gwarancje bezpieczeństwa i postępu wykraczają poza model.

• Brak postępu przy trwałej partycji: Safety pozostaje zachowane przy nieograniczonych opóźnieniach sieci, ale HotStuff nie finalizuje gwarantowanie nowych bloków, dopóki sieć pozostaje przez dłuższy czas podzielona lub niestabilna.

• Zależność od lidera: Słaby, zawieszony lub nieosiągalny lider może doprowadzić do niepowodzenia view. Pacemaker i rotacja liderów pomagają sieci ostatecznie się odbudować, gdy ponownie spełnione jest założenie synchronii, ale najpierw powodują dodatkowe opóźnienie.

• Stała grupa walidatorów jako punkt wyjścia: Pierwotny protokół zakłada znaną, uwierzytelnioną grupę walidatorów i threshold signatures. HotStuff nie określa sam, jak otwarta sieć wybiera walidatorów, rozdziela stake lub ekonomicznie karze niewłaściwe zachowania.

• Wiele faz do finalności: Basic HotStuff wymaga trzech faz głosowania, zanim propozycja stanie się ostateczna. Chained HotStuff zwiększa przepustowość dzięki pipeliningowi, ale czas do finalności pierwszych bloków oraz zachowanie przy zmianach lidera nadal zależą od opóźnień sieci, time-outów i implementacji.

Lider zmniejsza więc ilość wzajemnej komunikacji, ale staje się też ważnym tymczasowym punktem koordynacji. Taki lider musi na czas zebrać głosy kworum i rozpowszechnić nowe dowody.

Jak HotStuff wypada na tle innych protokołów konsensusu?

HotStuff należy do rodziny leader-based protokołów BFT, ale różni się sposobem organizacji głosowania, kworum i zmian lidera. Nie ma jednej bezpośredniej hierarchii: protokoły dokonują różnych wyborów dotyczących grup walidatorów, warunków sieciowych i finalności.

W porównaniu z PBFT, HotStuff zaprojektowano tak, aby ograniczyć komunikację podczas normalnego postępu i przy zmianie view. W pierwotnym porównaniu złożoność uwierzytelniania (authenticatorcomplexity) HotStuff przy poprawnym liderze i przy awarii lidera rośnie liniowo wraz z liczbą walidatorów. W tym samym porównaniu dla PBFT to obciążenie rośnie szybciej. Authenticatorcomplexity dotyczy konkretnie ilości informacji uwierzytelniającej do przetworzenia w ramach protokołu, a nie bezpośrednio liczby transakcji na sekundę czy opóźnienia dla użytkownika.

Tendermint i Casper, podobnie jak HotStuff, opierają się na podejściu BFT z tymczasowymi liderami, kworami i finalnością. W pierwotnym porównaniu ówczesne warianty Tendermint i Casper miały większe obciążenie komunikacyjne. Optymalizacje techniczne, takie jak threshold signatures, mogą zmieniać te koszty w konkretnych implementacjach.

HotStuff wyraźnie różni się od konsensusu Nakamoto, takiego jak Bitcoin. HotStuff działa ze znaną grupą walidatorów i może deterministycznie finalizować zacommitowane decyzje przy zachowaniu granicy błędów. Bitcoin korzysta z permissionless modelu proof-of-work, w którym uczestnicy mogą dołączać swobodnie, a finalność ma charakter probabilistyczny. Oznacza to, że prawdopodobieństwo cofnięcia maleje wraz z pojawianiem się kolejnych bloków, zamiast że w jednym momencie uzyskuje się absolutną finalność w ramach reguł protokołu.

W porównaniu z w pełni asynchronicznymi protokołami BFT, HotStuff wybiera częściową synchroniczność. Dzięki temu protokół może responsywnie robić postępy po ustabilizowaniu sieci, ale nie obiecuje liveness podczas trwałej partycji sieci.

Późniejsze warianty rozwijają idee HotStuff. DiemBFTv4 dostosowuje podejście, wprowadzając steady-state commit w dwóch krokach, natomiast Flow wykorzystuje Jolteon jako zoptymalizowany wariant HotStuff. Takie pochodne mogą mieć inne właściwości niż pierwotny protokół.

Podsumowanie

HotStuff to protokół konsensusu BFT, który pomaga stałej grupie walidatorów bezpiecznie ustalić jedną kolejność transakcji lub poleceń. Tymczasowy lider zbiera głosy, a quorum certificates pokazują, że wystarczająca liczba walidatorów sprawdziła i wsparła tę samą propozycję.

Połączenie wysokich progów głosowania, podpisów cyfrowych, locków i zmian view zapobiega temu, aby niewielka grupa walidatorów bizantyjskich mogła doprowadzić do ostatecznego zatwierdzenia dwóch sprzecznych bloków. HotStuff pozostaje przy tym bezpieczny podczas dużych opóźnień sieci, ale może gwarantować postęp dopiero wtedy, gdy sieć znów będzie wystarczająco stabilna i poprawny lider pozostanie aktywny.

Efektywne łączenie głosów oraz możliwość pipeliningu sprawiają, że HotStuff jest ważną bazą dla nowoczesnych wariantów BFT. Jednocześnie kluczowe jest zrozumienie, że HotStuff nie jest w pełni otwartym modelem konsensusu ani systemem ekonomicznym: wybór walidatorów, stake i bodźce są regulowane przez blockchain lub implementację wokół niego.