Byzantine Generals Problem

Wyobraź sobie oddziały rozstawione wokół miasta. Muszą wspólnie zaatakować albo wspólnie się wycofać; rozbieżne działania mogłyby je zgubić. Dowódca rozsyła rozkazy, ale ktoś może zdradzić i przedstawiać różne wersje. Jak wiarygodni uczestnicy mają doprowadzić do wspólnego działania? Nie jest to opis historycznej bitwy, lecz eksperyment myślowy o komputerach, które mają utrzymywać zgodne zapisy. Przykładowo kilka serwerów, czyli komputerów obsługujących wspólną usługę, musi jednakowo rozstrzygnąć, czy płatność została już przetworzona. Otrzymanie jakiejś odpowiedzi nie wystarcza: odpowiedzi muszą prowadzić do wspólnej decyzji. [1] [9]

Leslie Lamport, Robert Shostak i Marshall Pease przedstawili znane sformułowanie w lipcu 1982 roku, po pracy z 1980 roku o uzgadnianiu decyzji mimo awarii. Zdrajca oznacza komponent, którego zachowania nie można już przewidzieć. Komputer nie musi po prostu się zatrzymać. Może jednemu sąsiadowi odpowiedzieć poprawnie, drugiemu błędnie, pominąć wiadomość albo twierdzić, że widział coś innego. Przyczyną może być atak lub błąd programu. Awaria bizantyjska opisuje obserwowane zachowanie, a nie zamiary urządzenia. Skrót BFT (Byzantine Fault Tolerance) oznacza odporność na takie zachowanie przy określonych założeniach. [1] [2]

Pierwotne zadanie ma dwa warunki. IC1 wymaga, aby wszyscy wiarygodni podwładni przyjęli ten sam rozkaz. IC2 dodaje, że jeśli dowódca również jest wiarygodny, muszą przyjąć rozkaz rzeczywiście przez niego wysłany. Bez drugiego warunku pozornym rozwiązaniem byłoby „zawsze się wycofujcie”, ignorujące uczciwego dowódcę. W informatyce odróżniamy bezpieczeństwo, czyli brak sprzecznych wyników, od żywotności, czyli możliwości uzyskania wyniku. Dalsze reguły określają, które wyniki są dopuszczalne. Zgodny zapis sam w sobie nie dowodzi, że wprowadzone twierdzenie było prawdziwe w świecie zewnętrznym. [1] [9]

Nazwijmy dowódcę A, a podwładnych B i C. C otrzymuje od A rozkaz ataku, lecz B twierdzi, że dowódca zarządził odwrót. Kłamie B czy dowódca wysłał różne rozkazy? Bez podpisu możliwego do sprawdzenia po przekazaniu wiadomości C może nie odróżnić tych sytuacji. B może napotkać tę samą niepewność. Jeśli obaj zawsze posłuchają dowódcy, nieuczciwy A ich podzieli; jeśli zawsze go zignorują, naruszą warunek dotyczący uczciwego dowódcy. W tym zadaniu z trzema uczestnikami i jednym możliwym zdrajcą nie istnieje więc procedura bez podpisów, która zawsze się powiedzie. Brakuje informacji pozwalających rozróżnić przypadki, a nie szybszych komputerów. [1] [9]

W klasycznym modelu bez podpisów tolerowanie m możliwych zdrajców wymaga co najmniej n ≥ 3m+1 uczestników: czterech przeciw jednemu. Litera n oznacza wszystkich uczestników, a m maksymalną liczbę zdrajców, z którą system ma sobie poradzić. Nie wystarczy dodać głos i jednorazowo ustalić większość. OM(m) wielokrotnie przekazuje to, co uczestnicy usłyszeli, i ocenia wiadomości według wspólnych zasad. Przypadek bazowy OM(0) przyjmuje wartość dowódcy lub uzgodnioną wartość domyślną. Model zakłada znanych uczestników, bezpośrednie połączenia, poprawne doręczenie wysłanych wiadomości, znajomość bezpośredniego nadawcy oraz wykrywanie braku wiadomości. „Bez podpisów” nie znaczy więc „bez jakiegokolwiek uwierzytelnienia pochodzenia”. Bez tych założeń sama liczba cztery niczego nie gwarantuje. [1] [9]

Dzięki weryfikowalnemu podpisowi cyfrowemu, Digital Signature, B może pokazać C dowód tego, co dowódca rzeczywiście podpisał. Program tworzy taki podpis kluczem prywatnym, czyli tajną wartością liczbową. Inni sprawdzają go odpowiadającym mu kluczem publicznym, nie poznając klucza prywatnego. Zdrajca nie może niezauważenie zmienić rozkazu wiarygodnego uczestnika ani podrobić jego podpisu. Algorytm podpisanych wiadomości rozpowszechnia podpisane wartości i stosuje wspólną regułę wyboru. W tym modelu znika wskazany wymóg uczciwej większości, lecz pozostają założenia o niepodrabialności podpisów, doręczaniu i czasie rund. Dolev i Strong w 1983 roku dalej badali wymaganą liczbę rund. Poprawny podpis nie gwarantuje prawdziwości treści ani dostarczenia wiadomości na czas. Nie dowodzi też, że klucz prywatny nie został skradziony. Potwierdza pochodzenie konkretnej wiadomości, nie ogólną uczciwość nadawcy. [1] [3]

Gdy serwer nie odpowiada, pozostałe nie wiedzą, czy się zatrzymał, czy tylko ma bardzo wolne połączenie. Wynik FLP, opublikowany w 1985 roku przez Michaela Fischera, Nancy Lynch i Michaela Patersona, precyzuje tę niepewność. Proces oznacza tu działający program. Procedura deterministyczna przy tym samym stanie i tych samych danych wejściowych wykonuje ten sam następny krok, zamiast wybierać go losowo. W całkowicie asynchronicznym systemie bez znanej górnej granicy opóźnienia procedura deterministyczna nie gwarantuje zakończenia uzgadniania w każdym dopuszczalnym przebiegu, jeśli choć jeden proces może się zatrzymać wskutek awarii. Dotyczy to nawet niezawodnego doręczania bez ograniczenia opóźnień. Nie oznacza, że porozumienie nigdy nie powstanie. Praktyczne systemy dodają założenia czasowe, odpowiedni detektor awarii lub losowość. Przy podziale sieci czekanie może być bezpieczniejsze niż potwierdzanie sprzecznych wyników. [4] [13] [8]

Miguel Castro i Barbara Liskov opisali w 1999 roku Practical Byzantine Fault Tolerance, PBFT, dla usługi działającej na znanych replikach. Repliki to kopie usługi działające na różnych serwerach i na bieżąco przetwarzające te same żądania. Nie chodzi o odłożone pliki kopii zapasowej. Podstawowa konfiguracja n = 3f+1 toleruje f wadliwych replik. Spośród czterech serwerów jeden może być bizantyjski; dwie grupy po trzy mają co najmniej dwa wspólne serwery, w tym przynajmniej jeden wiarygodny. Wymagana grupa potwierdzeń to kworum. Samo nakładanie się grup nie wystarcza: ważne są reguły faz i zmiany lidera. Dokładniej, stan prepared wymaga żądania, wiadomości pre-prepare oraz 2f zgodnych wiadomości prepare od różnych replik innych niż replika główna. Potwierdzenie lokalne wymaga też 2f+1 wiadomości commit, ewentualnie z własną. Uwierzytelnianie, numery kolejności i punkty kontrolne przeciwdziałają fałszowaniu, powtórzeniom i nieograniczonemu rozrostowi dziennika. Bezpieczeństwo nie zależy od granic czasowych, ale postęp wymaga dodatkowych warunków dotyczących opóźnień. [5] [10] [11] [12]

Bitcoin nie ma z góry zamkniętej listy serwerów. Gdyby każde nowo utworzone konto miało głos, napastnik mógłby wyprodukować większość: to Sybil Attack. Proof of Work wiąże więc tworzenie bloków z pracą obliczeniową. Blok to pakiet transakcji dodawany do wspólnej historii. Full Node, czyli komputer z programem samodzielnie sprawdzającym reguły, najpierw odrzuca niepoprawne bloki, a potem wybiera poprawną gałąź o największej skumulowanej pracy. Bitcoin nie uruchamia OM ani PBFT; tymczasowe rozgałęzienia są częścią jego działania. Przy odpowiedniej przewadze uczciwej mocy i warunkach komunikacji kolejne potwierdzenia zmniejszają ryzyko przepisania historii, ale nie dają absolutnej nieodwracalności. Badania Bitcoin Backbone analizują te warunki: zgodność historii, wzrost łańcucha i udział bloków tworzonych przez uczciwych uczestników. [6] [7]

Przy stwierdzeniu „sieć osiąga konsensus” warto zapytać: kto może uczestniczyć, co kontroluje napastnik, jak długo mogą wędrować wiadomości i kiedy decyzja może się zmienić? Nawet Proof of Work nie usuwa wszystkich problemów. Eclipse Attack izoluje węzeł od uczciwych partnerów, cenzura pomija transakcje, a Selfish Mining polega na wstrzymywaniu publikacji wydobytych bloków. Pozostają błędy oprogramowania i możliwość przepisania części historii przy dostatecznej sile napastnika. Nawet większość mocy obliczeniowej nie zmusi jednak poprawnie działającego Full Node do przyjęcia bloku naruszającego jego reguły. Historia generałów uczy badać warunki porozumienia, zamiast ufać samej nazwie technologii. [6] [7] [8]