Opis Berserka na Wikipedii:
W pismach staronordyckich berserkami byli ci, o których mówiono, że walczyli w furii, cecha ta zrodziła współczesne angielskie słowo berserk (oznaczające „wściekłą przemoc lub brak kontroli”). Bereserkowie są opisywani w wielu źródłach staronordyckich.
Ta nazwa Berserker została zaadaptowana w pracy badawczej „FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures” (FPC) Serguei Popov i William J Buchanan jako termin opisujący jeden z typów złośliwych aktorów, którzy próbują wpływać na binarny protokół głosowania opisany w tym artykule.
Krótko mówiąc, Szybki Konsensus Probabilistyczny (FPC) jest protokołem bez przywództwa, który pozwala grupie nodów dojść do konsensusu w sprawie wartości jednego bitu. Protokół jest podzielony na epoki, które są nazywane rundami. Sercem protokołu jest to, że w każdej rundzie, każdy nod pyta k innych nodów o ich aktualną opinię, czyli: preferowaną wartość bitu. Nody tworzy swoją nową opinię na podstawie opinii nodów zapytanych. Jeśli dany nod posiada tę samą opinię podczas l kolejnych rund, to może być pewien, że opinia ta zostanie przyjęta przez wszystkie uczciwe nody po czym nod finalizuje swoją opinię. Nody, które sfinalizowały swoje opinie nadal odpowiadają na zapytania, jednak nie odpowiadają na zapytania innych nodów. Ważną cechą protokołu FPC jest tzw. próg losowy – losowy numer przypisany do każdej rundy, który jest ujawniany po zebraniu wszystkich zapytań o opinie. Od tego progu losowego zależy nowe tworzenie opinii. Zapewnia to dodatkową ochronę przed złośliwymi aktorami, ponieważ nie może on przewidzieć, co będzie progiem. Poziom losowości podczas protokołu jest kierowany przez parametr β. W szczególności β = 0,5 oznacza, że w systemie nie występuje losowość. Więcej szczegółów można znaleźć w następujących postach na blogu: Badanie symulacyjne FPC lub One Step Closer to Coordicide: IOTA Releases Fast Probabilistic Consensus Simulator.
Protokół głosowania FPC jest jednym z fundamentów Coordicide – projektu podjętego przez Fundację IOTA, który ma na celu usunięcie Koordynatora z sieci IOTA. Coordicide ma przynieść skalowalność bez centralizacji. Głosowanie FPC jest podstawą nowego mechanizmu konsensusu, który przynosi bezpieczeństwo Tangle. Protokół ten jest bizantyjski, tzn. działa nawet wtedy, gdy część węzłów sieci działa wadliwie lub jest kontrolowana przez przeciwnika, który zamierza albo opóźnić konsensus, albo go złamać. W dokumencie FPC rozróżnia się dwa rodzaje napastników:
- Ostrożny przeciwnik: każdy nod przeciwnika musi utrzymywać tę samą opinię w tej samej rundzie, tj. Odpowiadać taką samą wartością na wszystkie zapytania otrzymane w tej rundzie.
- Przeciwnik Berserk: nod przeciwnika może różnie reagować na różne pytania w tej samej rundzie.
Zachowanie Bereserka można interpretować jako oznakę szaleństwa, które przypomina szalone zachowanie legendarnych skandynawskich wojowników. Jednak, jak pokazano, istnieje sposób na to szaleństwo. Dowody matematyczne w dokumencie FPC ujawniają, że system jest bardziej podatny na ataki wykonywane przez berserków. Potwierdza to dodatkowo dokument symulacyjny FPC (patrz Studium symulacji FPC). Prawdopodobieństwo niepowodzenia porozumienia (sytuacja, w której nie ma jednomyślnej ostatecznej decyzji w systemie), choć nadal jest małe, jest wyższe, gdy przeciwnik jest bardziej szalony niż ostrożny. Podobnie berserker ma większą szansę na opóźnienie konsensusu (błąd zakończenia), a liczba wymienianych komunikatów między uczciwymi uczestnikami sieci wzrasta.
Można to zilustrować rysunkiem z dokumentu symulacyjnego FPC, w którym autorzy porównują ewolucję opinii w systemie, gdy atakujący jest ostrożny i szalony. Widzimy, że system jest w stanie wytrzymać ostrożnych napastników, nawet jeśli losowy próg używany w protokole FPC jest wyłączony (górna podkonfiguracja). Jednak gdy atakujący jest oszalały, konsensus może zostać opóźniony w nieskończoność i tylko dodanie losowości progu może spowodować, że system podejmie decyzję.
Chociaż w granicach nieskończonej liczby nodów prawdopodobieństwo niepowodzenia porozumienia, które mogłoby doprowadzić do rozwidlenia w systemie, wynosi zero, w rzeczywistych sieciach, w których liczba nodów jest skończona, prawdopodobieństwo to może być dodatnie. Ponieważ chcemy, aby był jak najmniejszy, jedną z zastosowanych przez nas taktyk jest odebranie atakującemu możliwości zachowania się w sposób szalony (Bereserk). Chcemy mieć pewność, że każdy ślad zachowania szaleńca zostanie szybko wykryty. Następnie nod, który okazał się zachowywać nieuczciwie, zostałby usunięty z listy zapytań, a jego reputacja zostałaby przekreślona.
Protokół wykrywania ataków Berserk
Protokół wykrywania jest w rzeczywistości bardzo prosty: pozwalamy nodom na wymianę informacji o opiniach otrzymanych w poprzednich rundach. Późniejsza analiza tych informacji może następnie ujawnić błędne zachowanie. Po wykryciu złośliwych wzorców głosowania, nody plotkują o dowodach w taki sposób, że wszyscy inni uczciwi uczestnicy sieci porzucają złego noda „berserka”.
Bardziej szczegółowy opis protokołu jest następujący:
Pozwalamy, aby każdy nod mógł poprosić każdy inny nod o listę opinii otrzymanych podczas poprzedniej tury głosowania FPC. Taką listę nazywamy v- listą i możemy poprosić o nią na kilka sposobów. Na przykład pełna odpowiedź na prośbę v– listy i opinie mogą składać się z opinii w bieżącej rundzie i opinii otrzymanych w poprzedniej rundzie. Żądanie v- listy nie byłoby obowiązkowe. Np. każdy nod mógłby również poprosić o to z pewnym prawdopodobieństwem lub jeśli ma dostęp do niezbędnej przepustowości pasma. Ponadto, możemy ustawić górną granicę tego prawdopodobieństwa na poziomie protokołu, tak aby można było wykryć spamowanie wniosków o v-listy. Oznaczamy to prawdopodobieństwo, że dowolne zapytanie zawiera żądanie v- listy o wartość p.
Przyjmijmy, że w ostatniej turze nody y otrzymał k głosów, zgłoszonych przez nody z1,z2,z3,…,zk. Jeśli nod x poprosi y o listę v, wówczas y wyśle głosy zgłoszone przez z1,…, zk wraz z tożsamościami z1,…, zk, ale bez podpisów. Zmniejsza to rozmiar wiadomości. Nod x porównuje opinie z v- listy przesłane przez y z innymi otrzymanymi v- listami. Jeśli x wykryje jakikolwiek ślad podejrzanego zachowania, poprosi nod y o wysłanie powiązanych z nim podpisów, które udowodnią złośliwe zachowanie. Po zebraniu dowodu, uczciwy nod rozpowiada o dowodach do sieci, a nod złośliwy zostanie usunięty przez wszystkich z listy.
Aby sprawdzić, na ile wiarygodna jest ta metoda wykrywania i jaki będzie koszt komunikacji, przeprowadzamy następujące obliczenia.
Oczekiwana liczba rund przed wykryciem berserka
Interesuje nas prawdopodobieństwo wykrycia złośliwego przeciwnika, ponieważ odwrotność tej wartości daje nam szacunkową liczbę, ile rund potrzeba do wykrycia złośliwego zachowania. Jeśli liczba rund jest wystarczająco mała, możemy stwierdzić, że protokół pozwala na szybkie wykrycie napastnika.
Rozważmy następujący scenariusz: wśród N uczciwych nodów jest jeden nod berserk. W ostatniej rundzie, zły nod został zapytany k razy, co jest oczekiwaną liczbą otrzymanych zapytań (jeśli wybierzemy nody z jednakowym prawdopodobieństwem). Ponadto wysyła on kf głosów z opinią 0 i (1-f) k głosów z opinią 1 do różnych nodów w sieci. Nazwijmy pierwszą grupę G0, a drugą G1.
Prawdopodobieństwo, że uczciwy nod x zażąda listy v od noda z grupy G0 jest równe pfk/N i p(1-f)k/N dla G1. Zauważ, że zdarzenia otrzymania listy v z G0 i G1 nie są niezależne. Obliczenia pokazują, że aż do najniższego poziomu, prawdopodobieństwo że x otrzyma v-listy pozwalające na wykrycie złego noda jest równe: pfk/N i p(1-f)k/N dla G1.
Jeśli N uczciwych nodów zastosuje się do tej procedury, to korzystając aproksymacji funkcji (1-x)^a = 1-ax, prawdopodobieństwo że jakiś nod wykryje zachowanie berserka jest równe:
Mówi się, że atakujący jest „maksymalnie szalony (bereserk)”, gdy f = (1-f) = 1/2 .
Na przykład w systemie z N=10000 nodów, k=30 i p=0,1 prawdopodobieństwo wykrycia wynosi około ≈ 0,02. W tym przypadku nod „berserk” powinien zostać wykryty po około 50 rundach. Zakładając, że pełne głosowanie FPC odbędzie się w ≈ 15 rundach, złośliwe nody powinny być wykryte w 4 pełnych cyklach głosowania FPC.
Obliczenie
Dla uproszczenia, zakładamy tutaj, że w Tangle znajduje się jedna para sprzecznych transakcji. W takim przypadku, aby zastosować detekcję przekłamań, należy wykonać następujące czynności. ID noda zajmuje 32 bajty, które mogą być skompresowane dla tej aplikacji do 6 bajtów; opinia noda wymaga jednego bitu. Ponadto załóżmy, że p=0,1 i k=30 wtedy obliczenie do wysłania v-listy wraz z odpowiedzią na zapytanie (nie wymaga więc dodatkowej sygnatury) wynosiłaby średnio 1,8 bajta. Jest to znacznie mniej niż 2500 bajtów, które mają być wymagane do otrzymania opinii od wszystkich k nodów zapytanych w FPC bez detekcji berserk. Dochodzimy do wniosku, że dodanie do protokołu FPC detekcji berserk spowodowałoby, ogólnie i w tym konkretnym przypadku, że wiadomości byłyby o 1% mniejsze niż większe, co jest nieistotne. W przypadku głosowania nad więcej niż jednym konfliktem, względne koszty ogólne mechanizmu wykrywania zostałyby zwiększone. Dokładniej rzecz biorąc, każdy konflikt zwiększa koszty ogólne o jeden bit, podczas gdy koszty ogólne związane z podpisami pozostają takie same. Ponieważ część dotycząca podpisów jest stosunkowo duża w porównaniu z częścią dotyczącą opinii, dominującym czynnikiem jest część dotycząca podpisów.
Ulepszenia: porównanie historii opinii
Należy zauważyć, że w przedstawionej powyżej analizie nody porównują opinie z jednej, poprzedniej rundy. Możemy jednak zwiększyć wydajność protokołu, gdy nody porównają opinie z więcej niż jednej rundy, tzn. mogą porównywać całe historie opinii, a nie tylko opinie bieżące i ostatnie. Przez historię rozumiemy listę wszystkich posiadanych opinii przez dany nod w kolejnych rundach. Na przykład, jeśli dany nod znajduje się w m-tej rundzie głosowania nad danym konfliktem, jego historia składa się z m- bitów i każdy z nich odpowiada opinii w jednej z m-rund. Gdy taki nod zostanie poproszony o wydanie swojej aktualnej opinii, odpowiedziałby komunikatem m bitów, który zostałby później użyty do skonstruowania v-listy.
Należy pamiętać, że nody mogą porównywać historie opinii różnej wielkości. Na przykład, gdy nod x otrzyma historię głosowania z tego samego noda y w rundach m1-ej i m2-ej (m1 <m2), może on próbować znaleźć ślady zachowań berserk na nakładających się rundach m1. Dzięki tej metodzie znacznie wzrasta skuteczność wykrywania berserków. Oczywistą wadą tego podejścia byłoby to, że aby taki protokół działał, wymagalibyśmy, aby każdy węzeł zapytany w FPC wysyłał całą swoją historię opinii (na temat konkretnego konfliktu). Ta historia opinii zwiększałaby się z każdą rundą głosowania o jeden bit. Co więcej, nody musiałyby przydzielić trochę pamięci, aby zachować zarówno historię swoich własnych opinii, jak i historię opinii innych węzłów. Jednak dodatkowe koszty komunikacji nie są zbyt wysokie.
Podsumowując
Przedstawiliśmy opcjonalny protokół do wykrywania złośliwych nodów (bereser), który zwiększa bezpieczeństwo protokołu. Zmniejszenie skuteczności możliwych ataków, prowadzi z kolei do zmniejszenia prawdopodobieństwa niepowodzenia porozumienia i rozwiązania umowy. Jako dalsze usprawnienie proponujemy, aby nody mogły głosować również z całą historią zebranych opinii, a nie tylko z opinią najnowszą. Jak pokazaliśmy, nie zmieniłoby to w znaczący sposób wielkości przekazu.
Jak zawsze, jeśli chcesz się z nami spotkać, masz jakieś uwagi, pytania lub opinie, nie wahaj się skontaktować z zespołem IOTA na naszym serwerze Discord.
Powyższy tekst jest tłumaczeniem postu z języka angielskiego który oryginalnie ukazał pod tym adresem.
