Jest to pierwszy z serii postów wyjaśniających protokoły konsensusu opisane w IOTA Coordicide.
Głównym celem tej serii jest informowanie na bieżąco społeczności o najnowszych wynikach badań, a także wyjaśnianie interesujących pytań badawczych mających duże szanse na sfinansowanie z grantów Coordicide. Jak zobaczycie temat jest dość obszerny i istnieje wiele powiązań i zależności od innych części projektu Coordicide.
W obliczu tej złożoności postaramy się wyjaśnić tylko kilka punktów na raz i skupić się na zagadnieniach które są obecnie badane. To powiedziawszy zauważmy, że IOTA ma już wszystkie kluczowe składniki skutecznego i bezpiecznego rozwiązania dla Coordicide.
Pozostałe pytania dotyczące optymalizacji rozwiązań, na przykład:
- Zwiększone bezpieczeństwo
- Zwiększenie trwałości (np. zmniejszenie złożoności komunikatów, zmniejszenie mocy PoW)
- Zwiększenie TPS
- Skrócenie czasu finalizacji
- Zwiększenie elastyczności wdrożenia dla wyzwań w przyszłości
Przejdźmy do tego i zrozummy o co chodzi w tym „konsensusie”.
Dlaczego konsensus?
Rozproszone algorytmy konsensusu pozwalają systemom sieciowym uzgodnić wymagany stan lub opinię w sytuacjach w których zdecentralizowane podejmowanie decyzji jest trudne a nawet niemożliwe.
Przetwarzanie rozproszone jest z natury zawodne. Osiągnięcie konsensusu pozwala rozproszonemu systemowi działać jako jedna całość. Znaczenie tego wyzwania wynika z jego wszechobecności w której odporność na uszkodzenia jest jednym z najbardziej podstawowych aspektów.
Typowe przykłady to: replikowane systemy plików, synchronizacja zegara, przydział zasobów, planowanie zadań i ostatnie ale nie mniej ważne rozproszone rejestry.
Systemy rozproszone stanowią rozległy i klasyczny temat w informatyce i to samo dotyczy powiązanych protokołów konsensusu: zobacz Jak działa rozproszony konsensus w celu wprowadzenia do tego tematu.
Istniejące protokoły konsensusowe są zasadniczo protokołami klasycznymi – np. te oparte na PAXOS – i najnowszy przełomowy: konsensus Nakamoto. Oba protokoły mają poważne ograniczenia.
Klasyczne protokoły mają kwadratową złożoność komunikatów, wymagają dokładnej wiedzy członkowskiej i są raczej delikatne w stosunku do zakłóceń. Z drugiej strony protokół Nakamoto jest solidny i nie wymaga precyzyjnego członkostwa. Opiera się jednak na PoW co prowadzi do znanych problemów takich jak wyścigi górnicze i brak skalowalności.
Jak zatem osiągnąć konsensus w IOTA Tangle?
Spójrzmy najpierw na konsensus Nakamoto. Jednym genialnym pomysłem konsensusu Nakamoto jest uczynienie konsensusu niedeterministycznym lub probabilistycznym. Zamiast wszystkich węzłów (rozproszonego) systemu, które zgadzają się co do poprawności wartości, zgadzają się co do „prawdopodobieństwa” tej wartości.
Rolę lidera w tradycyjnych protokołach konsensusu przejmuje węzeł, który najszybciej rozwiązuje daną łamigłówkę obliczeniową; ten zwycięzca dodaje nowy blok do łańcucha bloków. W ten sposób (rozproszona) sieć buduje ciągle rosnący łańcuch i zgadza się co do ważności najdłuższego łańcucha lub łańcucha o największej kumulacji trudności.
Dlaczego więc ten konsensus jest probabilistyczny? Aby wiedzieć, że określona transakcja zostanie uznana za ważną powiedzmy 100 dni musimy wiedzieć, że najdłuższy łańcuch w ciągu 100 dni będzie zawierał tą daną transakcję.
Innymi słowy interesuje nas prawdopodobieństwo, że najdłuższy łańcuch w ciągu 100 dni będzie zawierał tą transakcję. Prawdopodobieństwo, że transakcja nie zostanie cofnięta wzrasta gdy blok zawierający tą transakcję „zapada głębiej” w łańcuch.
Na przykład w łańcuchu bloków bitcoinów zaleca się poczekać, aż transakcja znajdzie się głęboko w łańcuchu na sześć bloków. Po tej głębokości prawdopodobieństwo cofnięcia transakcji jest bardzo niskie.
Ten efekt dotyczy również Tangle. Im głębsza – lub bardziej „otoczona” przez Tangle – transakcja staje się bardziej ostateczna. Na poniższym przykładzie ciemnozielona transakcja jest zatwierdzana przez wszystkie jasnozielone transakcje. W miarę wzrostu liczby jasnozielonych transakcji prawdopodobieństwo, że ciemnozielona transakcja będzie w przyszłości Tangle zbiega się do 1.
Ale czekaj, Tangle różni się od blockchain! Chociaż blockchain nie może zawierać dwóch sprzecznych transakcji, Tangle może tymczasowo zawierać takie transakcje. Dlatego może być tak, że złośliwy gracz dołącza dwie sprzeczne transakcje w różnych częściach Tangle, takie jak ciemnozielone i pomarańczowe kwadraty na powyższym obrazku.
Transakcje takie mogą „przetrwać” w Tangle przez krótki czas, dopóki uczciwe węzły nie wykryją konfliktu. Po wykryciu takiego konfliktu węzły decydują którą transakcję wybrać. W powyższym przykładzie ciemnozielona transakcja jest „bardziej otoczona” przez Plątaninę i ostatecznie powinna zostać zatwierdzona przez wszystkie węzły.
Aby Tangle stał się prawdziwym protokołem konsensusu musimy decydować o sprzecznych transakcjach. Decyzję tę należy podjąć przy użyciu protokołu konsensusu.
Chodziliśmy tu w kółko? Na szczęście nie: Coordicide proponuje dwa inne protokoły konsensusu:
- Szybki Probabilistyczny Konsensus (FPC – Fast Probabilistic Consensus)
- Konsensus Komórkowy (CC – Cellular Consensus)
Pozostała część tego postu zostanie poświęcona krótkiemu wprowadzeniu do FPC i wyjaśnieniu jak osiągnąć konsensus, jeśli chodzi o decyzję czy pojedyncza transakcja jest ważna czy nie.
W przyszłym wpisie na blogu wyjaśnimy dlaczego jest to wystarczające do osiągnięcia konsensusu na poziomie Tangle, i omówimy finalizowanie transakcji w Tangle.
Czym jest FPC?
W wymyślnych słowach FPC jest bezbłędnym probabilistycznym binarnym protokołem konsensusu o niskiej złożoności komunikacyjnej, który jest solidny w Bizantyjskiej infrastrukturze – sprawdź oryginalny artykuł Sergueia Popova i Billa Buchanana.
Zobaczmy, co tak naprawdę oznaczają te wszystkie warunki i zacznijmy od przedstawienia lżejszej wersji FPC, która jest łatwa do wdrożenia i zawiera większość ważnych funkcji.
Zakładamy, że sieć ma n węzłów indeksowanych przez 1,2,…, n. Każdy węzeł i ma opinię lub stan. Oznaczamy s_i(t) dla opinii węzła i w czasie t. Opinie mają wartość {0,1}; dlatego mówimy o binarnym konsensusie.
Podstawową ideą jest głosowanie większością głosów. W każdej rundzie każdy węzeł wysyła kwerendy do losowych węzłów i ustala swoją opinię równą większości zapytanych węzłów. Proste! Jednak ta zwykła większość głosów okazuje się niestabilna wobec wadliwych węzłów i złośliwych atakujących. Potrzebuje dodatkowego składnika w rzeczywistości dodatkowej losowości aby był solidny.
Bardziej formalnie na każdym etapie każdy węzeł wybiera k losowych węzłów C_i, pyta o ich opinie i oblicza średnią opinię
Oznaczamy 𝝉 ∊ [0,1] pierwszy próg, który pozwala na asymetryczny charakter protokołu – kolejny temat którym zajmiemy się w najbliższej przyszłości. Ponadto wprowadzamy „dodatkową losowość”; niech U_ {t}, i = 1, 2,… będzie i.i.d. zmienne losowe z prawem Unif (𝜷, 1- 𝜷) dla niektórych parametrów 𝜷 ∊ [0,1 / 2].
Za każdym razem każdy węzeł i używa opinii z losowych węzłów, aby zaktualizować swoją opinię:
a dla t> 0:
Ważne jest aby w każdej rundzie węzeł sprawdzał inny losowy zestaw węzłów oraz aby zmienne losowe U_t były aktualizowane również w każdej rundzie.
Wprowadzamy lokalną regułę zakończenia, aby zmniejszyć złożoność komunikacji protokołu. Każdy węzeł przechowuje przeciwną zmienną cnt, która jest zwiększana o 1, jeśli jego opinia nie ulegnie zmianie, i jest ustawiona na 0, jeśli nastąpi zmiana opinii.
Gdy licznik osiągnie pewien próg l, tj. cnt≥1, węzeł uznaje bieżący stan za końcowy. Węzeł nie będzie zatem wysyłał żadnych zapytań ale nadal będzie odpowiadał na zapytania przychodzące. Kolejne wykresy pokazują typowe ewolucje zmiennej cnt dla każdego węzła przy l = 5, k = 10 i wstępne opinie 90% z 1 i 10% z 0.
Na lewym obrazku protokół nie jest zakłócany ale na prawym obrazie 20% węzłów złośliwie próbuje obrócić większość uczciwych węzłów. W obu przypadkach ostatecznie wszystkie uczciwe węzły zgadzają się na początkową większość.
Chcemy podkreślić funkcję typowych losowych progów FPC i zapoznać się z Symulacją FPC w celu pierwszej analizy FPC dla różnych rodzajów ustawień parametrów i strategii ataku.
Wpływ losowych progów
Znaczenie niepewności w wojnie wprowadził Carl von Clausewitz:
Wojna jest królestwem niepewności; trzy czwarte czynników na których opiera się akcja wojenna otacza mgła o większej lub mniejszej niepewności. Wymagany jest delikatny i dyskryminujący osąd; wykwalifikowana inteligencja, by wyczuć prawdę.
Carl von Clausewitz, 1873
Co to ma wspólnego z losowymi progami w FPC? Zwykłą większością głosów te progi byłyby równe 0,5. Owocną strategią ataku może być utrzymanie η uczciwych węzłów na poziomie około 0,5, zapobiegając konwergencji protokołu (później zobaczymy taki udany atak). Pomysły Popowa i Buchanana polegały na dodaniu do systemu „hałasu” lub „mgły”, aby zwiększyć niepewność informacji dla potencjalnych napastników.
Dlaczego to wszystko jest tak ważne? W sytuacji bez złośliwych węzłów rozkład η będzie zbliżony do rozkładu normalnego:
W niezakłóconej sytuacji opinie uczciwych węzłów mogą pozostać blisko sytuacji 50:50. Jednak losowe efekty spowodowane losowym głosowaniem ostatecznie prowadzą do konwergencji protokołu. Ta sytuacja jest zupełnie inna w bizantyjskiej infrastrukturze.
Rozważmy strategię przeciwnika która dzieli uczciwe węzły na dwie równe grupy różnych opinii co prowadzi do podziału η pomiędzy uczciwe węzły takie jak:
Jak więc przeciwnik może to osiągnąć?
Przeciwnik czeka aż wszystkie uczciwe węzły otrzymają opinie od wszystkich innych uczciwych węzłów. Przeciwnik następnie oblicza medianę tych pośrednich η. Teraz przeciwnik próbuje utrzymać medianę η na poziomie 0,5 próbując zmaksymalizować wariancje η.
W jaki sposób FPC może zapobiec takiemu atakowi? Przez zastąpienie progu deterministycznego (czerwony, przerywany) losowymi progami (niebieski, przerywany). Na poniższym wykresie każda niebieska linia oznacza losowy próg danej rundy. Ponieważ progi te są losowe, przeciwnik nie może przewidzieć jak podzielić uczciwe węzły aby zachować sytuację 50:50. Najlepszym sposobem jest podzielenie ich wokół wartości 0,5.
Jednak gdy niebieska linia (na r3 na zdjęciu poniżej) jest wystarczająco daleko od czerwonej linii, przeciwnik traci kontrolę nad uczciwymi węzłami i protokół się kończy.
W poniższej animacji możesz zobaczyć zachowanie i wynik protokołu kiedy ta strategia przeciwna jest stosowana bez losowości (próg = 0,5) i po dodaniu losowości. Jak widać, przeciwnikowi udaje się utrzymać węzły w stanie zawieszenia przez długi czas. Co gorsza, jego zdaniem sieć jest podzielona – co prowadzi do niepowodzenia umowy. Jednak po wprowadzeniu dodatkowej losowości protokół kończy się szybko i zgodnie.
Bieżąca praca i kolejne etapy
Na koniec – wróćmy jednak do niektórych punktów nad którymi obecnie pracuje IOTA i wskażmy kilka przykładów przyszłej współpracy:
- W tej chwili przeprowadzamy dokładne symulacje, aby zbadać różne strategie ataku na różne rodzaje topologii sieci. Wyniki pozwolą nam zidentyfikować optymalną ilość losowości i dobrać parametry protokołu. Badamy również odporność FPC na awarie i zakłócenia losowego progu.
- Granice zbieżności FPC uzyskane w symulacjach są znacznie lepsze niż granice uzyskane teoretycznie przez Popova i Buchanana. Różne symulacje ustawień parametrów pokazują, że istnieje tak zwane „zjawisko odcięcia”. Nieformalnie oznacza to zasadniczo, że protokół potrzebuje, powiedzmy m kroków z dużym prawdopodobieństwem osiągnięcia konsensusu i że jest bardzo mało prawdopodobne, że protokół potrzebuje więcej niż m kroków. Teoretyczne wyniki w tym kierunku byłyby bardzo mile widziane.
- Rzeczywista implementacja FPC będzie zależeć od reputacji węzłów. Ponieważ reputacja lub mana węzła odgrywa znaczącą rolę w innych częściach projektu Coordicide napiszemy o tym więcej w przyszłym blogu. W każdym razie ta dodatkowa funkcja sprawi, że protokół będzie bezpieczniejszy przed różnego rodzaju atakami.
- Parametry badane powyżej w FPC zostały ustawione na początku protokołu. Jednak w celu zwiększenia bezpieczeństwa i jednocześnie zmniejszenia złożoności wiadomości (co brzmi jak cud), badamy dostosowane wersje FPC. Na przykład, jeśli η węzła jest bliskie 0,5 węzeł może zdecydować o zwiększeniu liczby zapytań, a jeśli jest bliski 1, może zdecydować o zmniejszeniu liczby zapytań w następnym kroku lub natychmiast przerwać wysyłanie zapytań o wszystko.
- Obecnie uczenie maszynowe stosuje się w wielu różnych dziedzinach w których wykazuje wyższość nad tradycyjnymi algorytmami opartymi na regułach. Planujemy wykorzystać uczenie maszynowe nie tylko do wykrywania wadliwych i złośliwych węzłów ale także do identyfikacji najbardziej szkodliwych strategii ataku za pomocą uczenia wzmacniającego.
Z niecierpliwością czekamy na zabranie Cię w ekscytującą podróż po Coordicide oczami działu badań i mamy nadzieję, że będziesz zadowolony z rozwoju tego projektu tak jak my.
Jak zawsze chętnie przyjmujemy Twoje komentarze i pytania tutaj w komentarzach lub w #tanglemath na naszym Discord. Możesz także zaangażować się w intensywniejszą współpracę naukową z nami i ubiegać się o grant.
Autor nie jest członkiem fundacji IOTA. Napisał ten post na blogu we współpracy z członkami grupy badawczej IOTA.
Powyższy tekst jest tłumaczeniem postu z języka angielskiego który oryginalnie ukazał pod tym adresem.
