20. Dez’19
Übersetzung des Blogartikel vom Autor Bartosz Kuśmierz, IOTA Foundation.
Am Anfang der englischen Wikipedia-Seite über Berserker steht:
Im altnordischen Schrifttum waren Berserker diejenigen, die in einer tranceartigen Wut gekämpft haben sollen, eine Eigenschaft, die später das moderne englische Wort berserk (bedeutet “wahnsinnig gewalttätig oder außer Kontrolle”) hervorbrachte. Berserker werden in zahlreichen altnordischen Quellen bezeugt.
Der Name Berserker wurde in der Forschungsarbeit „Fast Probabilistic Consensus within Byzantine Infrastructures (FPC-BI)” von Serguei Popov und William J. Buchanan als ein Begriff zur Beschreibung einer der Arten von böswilligen Akteuren, die versuchen, dass in dieser Abhandlung beschriebene binäre Wahlprotokoll zu beeinflussen adaptiert.
Um es schnell zusammenzufassen: Der Fast Probabilistic Consensus (FPC) ist ein führerloses Protokoll, das es einer Reihe von Nodes erlaubt, sich auf den Wert eines einzelnen Bits zu einigen. Das Protokoll ist in Epochen unterteilt, die als Runden bezeichnet werden. Das Herzstück des Protokolls ist die Tatsache, dass in jeder Runde jeder Node k andere Nodes nach ihrer aktuellen Meinung, d.h.: dem bevorzugten Wert des Bits, abfragt. Der Node bildet sich seine neue Meinung auf der Grundlage der Meinungen der abgefragten Nodes. Wenn ein Node in l aufeinanderfolgenden Runden die gleiche Meinung hat, dann kann er ziemlich sicher sein, dass diese Meinung von allen ehrlichen Nodes übernommen wird. Danach finalisiert der Node seine Meinung. Nodes, die ihre Meinung festgelegt haben, antworten immer noch auf die Anfrage, aber sie fragen keine anderen Nodes mehr ab. Ein wichtiges Merkmal des FPC-Protokolls ist der sogenannte Zufallsschwellenwert (engl. random threshold) – eine jeder Runde zugeordnete Zufallszahl, welche sich offenbart, wenn alle abgefragten Meinungen gesammelt wurden. Die neue Meinungsbildung hängt von dieser Zufallsschwelle ab. Dies bietet einen zusätzlichen Schutz vor den böswilligen Akteuren, da er/sie nicht vorhersagen kann, welcher Schwellenwert es sein wird. Der Grad der Zufälligkeit während des Protokolls wird durch den Parameter β geleitet. Dabei bedeutet β = 0,5, dass es keine Zufälligkeit im System gibt. Für weitere Details lesen Sie die folgenden Blog-Einträge: Simulationsstudie von FPC oder FPC Simulator.
Das FPC-Abstimmungsprotokoll ist eine der Grundlagen von Coordicide – dem Projekt der IOTA-Stiftung, das auf die Entfernung des Koordinators aus dem IOTA-Netzwerk ausgerichtet ist. Coordicide hofft Skalierbarkeit ohne Zentralisierung zu ermöglichen. Die FPC-Abstimmung ist die Grundlage des neuen Konsensmechanismus, der Sicherheit in den Tangle nach dem Entfernen des Koordinators bringt.
Das Protokoll entspricht der Byzantinischen Fehlertoleranz, d.h: es funktioniert auch dann, wenn ein Teil der Netzwerk-Nodes fehlerhaft arbeitet oder von einem Gegner kontrolliert wird, der den Konsens entweder verzögern oder brechen will. Das FPC-Papier unterscheidet zwischen zwei Arten von Angreifern:
Vorsichtiger Gegner: Jeder gegnerische Node muss in der gleichen Runde die gleiche Meinung vertreten, d.h. er muss auf alle Anfragen, die er in dieser Runde erhält, den gleichen Wert antworten.
Berserkerhafter Gegner: Ein gegnerischer Node kann bei verschiedenen Anfragen in der gleichen Runde unterschiedlich auf Dinge reagieren.
Das Verhalten des Berserker-Gegners kann als ein Zeichen von Wahnsinn interpretiert werden, das dem wahnsinnigen Verhalten legendärer skandinavischer Krieger ähnelt (daher der Name). Es hat sich jedoch gezeigt, dass dieser Wahnsinn eine Methode hat. Die mathematischen Beweise in der FPC-Publikation zeigen, dass das System anfälliger für die Angriffe der Berserker ist.
Dies wird auch durch das FPC-Simulationsdokument bestätigt (siehe Simulationsstudie des FPC). Die Wahrscheinlichkeit des Scheiterns der Vereinbarung (Situation, in der es keine einstimmige endgültige Entscheidung im System gibt) ist zwar immer noch gering, aber höher, wenn der Gegner eher berserkerhaft als vorsichtig ist. Ebenso hat der Berserker eine größere Chance, den Konsens zu verzögern (Abbruchfehler) und die Anzahl der ausgetauschten Nachrichten zwischen ehrlichen Netzwerkteilnehmern zu erhöhen. Dies kann mit einer Abbildung aus dem FPC-Simulationspapier veranschaulicht werden, in der die Autoren die Entwicklung der Meinungen im System vergleichen, wenn der Angreifer vorsichtig und berserkerhaft ist. Wir können sehen, dass das System den vorsichtigen Angreifern auch dann widerstehen kann, wenn die im FPC-Protokoll verwendete Zufallsschwelle ausgeschaltet ist (obere Abbildung). Allerdings wenn der Angreifer berserkerhaft ist, kann der Konsens unbegrenzt verzögert werden und nur die Hinzufügung von Zufälligkeit für den Schwellenwert kann das System dazu veranlassen, die Entscheidung zu treffen.
Obgleich im Rahmen der unendlichen Anzahl von Nodes die Wahrscheinlichkeit, dass es zu einem Übereinstimmungsfehler kommt, die zu einer Gabelung (Side Tangle) im System führen könnte, gleich Null ist. Für die realen Netzwerke, bei denen die Anzahl der Nodes endlich ist, kann diese Wahrscheinlichkeit positiv sein. Da wir die Wahrscheinlichkeit so gering wie möglich halten wollen, ist eine der Taktiken, die wir anwenden, dem Angreifer die Möglichkeit zu nehmen, sich berserkerhaft zu verhalten. Wir wollen sicherstellen, dass jede Spur des Berserker-Verhaltens schnell erkannt wird. Dann würde der Node, der sich nachweislich unehrlich verhält, von der Anfrageliste gestrichen und sein Ruf würde radikal herabgesetzt werden. (Stichwort: Mana)
Berserker-Erkennungsprotokoll
Das Erkennungsprotokoll ist in der Tat sehr einfach: wir erlauben den Nodes, den Austausch von Informationen über die Meinungen, die sie in den vorangegangenen Runden erhalten haben. Eine anschließende Analyse dieser Informationen kann dann das berserkerhafte Verhalten aufzeigen. Bei der Entdeckung von bösartigen Abstimmungsmustern würden die Nodes die Beweise weiter tratschen (Gossip), so das alle anderen ehrlichen Netzwerkteilnehmer den Berserker-Node ablehnen werden.
Eine genauere Beschreibung des Protokolls ist wie folgt:
Wir erlauben, dass jeder Node jeden anderen Node um eine Liste der Meinungen bitten kann, die während der vorherigen Runde der FPC-Abstimmung eingegangen sind. Wir nennen eine solche Liste v-list und wir können sie auf verschiedene Weise anfordern. Beispielsweise die vollständige Antwortnachricht auf die Anforderung einer v-list oder die Meinungen könnten aus den Meinungen in der aktuellen Runde und aus den eingegangenen Meinungen aus der vorherigen Runde zusammengesetzt werden.
Die Anforderung einer V-Liste wäre nicht zwingend erforderlich. Z.B. könnte auch jeder Node mit einer bestimmten Wahrscheinlichkeit danach fragen, wenn er die notwendige Bandbreite zur Verfügung hat. Außerdem können wir auf Protokollebene eine Obergrenze für diese Wahrscheinlichkeit festlegen, so dass Spamming von Anfragen nach v-lists erkannt werden kann. Wir bezeichnen diese Wahrscheinlichkeit, dass eine beliebige Anfrage eine Anfrage nach einer v-Liste enthält, mit p.
Nehmen wir an, dass ein Node y in der letzten Runde k Wahlstimmen erhalten hat, die von den Nodes z1,z2,z3,…,zk abgegeben wurden. Wenn ein Node x bei y eine v-Liste anfragt, dann sendet y die von z1,…,zk abgegebenen Wählerstimmen zusammen mit den Identitäten von z1,…,zk, aber ohne deren Unterschrift. Dies reduziert die Größe der Nachricht. Node x vergleicht die Meinungen in der von y eingereichten v-Liste mit anderen empfangenen v-Listen. Wenn x irgendeine Spur eines verdächtigen Verhaltens entdeckt, bittet er den Node y, ihm die zugehörigen Signaturen zu senden, die das bösartige Verhalten beweisen würden. Nachdem der ehrliche Node die Beweise gesammelt hat, tratscht der ehrliche Node die Beweise an das Netzwerk und der gegnerische Node wird von allen abgewiesen.
Um zu testen, wie zuverlässig diese Erkennungsmethode ist und wie hoch der Kommunikationsaufwand wäre, führen wir die folgenden Berechnungen durch.
Erwartete Anzahl von Runden vor der Entdeckung des Berserkers
Wir interessieren uns für die Wahrscheinlichkeit, einen berserkerhaften Gegner zu erkennen, da die Umkehrung dieses Wertes uns eine Schätzung gibt wie viele Runden benötigt werden, um bösartiges Verhalten zu erkennen. Wenn die Anzahl der Runden ausreichend klein ist, können wir daraus schließen, dass das Protokoll eine schnelle Erkennung eines berserkerhaften Angreifers ermöglicht.
Betrachten wir das folgende Szenario: Unter N ehrlichen Nodes gibt es einen einzelnen Berserker-Node. In der letzten Runde wurde der schädliche Node k-mal abgefragt, was die erwartete Anzahl der empfangenen Anfragen ist (wenn wir Nodes mit einheitlicher Wahrscheinlichkeit auswählen). Außerdem sendet er kf Wählerstimmen mit der Meinung 0 und (1-f) k Wählerstimmen mit der Meinung 1 an verschiedene Nodes im Netzwerk. Nennen wir die erste Gruppe G0 und die zweite Gruppe G1.
Die Wahrscheinlichkeit, dass ein ehrlicher Node x eine v-Liste von einem Node aus der Gruppe G0 anfordert, ist gleich pfk/N und p(1-f)k/N für G1. Beachten Sie, dass die Ereignisse des Empfangs von v-Listen von G0 und G1 nicht unabhängig voneinander sind. Die Berechnungen zeigen, dass bis zur niedrigsten Ordnung die Wahrscheinlichkeit, dass x V-Listen erhält, die die Erkennung des Berserkerknotens ermöglichen, ist gleich
Wenn N ehrliche Nodes dieser Prozedur folgen, dann ist bei Verwendung der Näherung (1-x)^a = 1-ax die Wahrscheinlichkeit, dass ein Node das berserkerhafte Verhalten erkennt, gleich
Der Angreifer wird als “maximal berserkerhaft” bezeichnet, wenn f=(1-f) =1/2. Zum Beispiel in einem System mit N=10000 Nodes, k=30 und p=0.1 beträgt die Entdeckungswahrscheinlichkeit ungefähr ≈ 0.02. In diesem Fall sollte der Berserker-Node nach etwa 50 Runden entdeckt werden. Unter der Annahme, dass die volle FPC-Abstimmung ≈ 15 Runden dauert, sollten Berserker-Nodes innerhalb von 4 vollen FPC-Abstimmungszyklen entdeckt werden.
Nachrichten-Overhead
Der Einfachheit halber nehmen wir hier an, dass es im Tangle ein Paar widersprüchlicher Transaktionen gibt. Der Nachrichten-Overhead zum Anwenden der Berserk-Erkennung ist dann wie folgt. Die ID eines Nodes benötigt 32 Bytes, die für diese Anwendung auf 6 Bytes komprimiert werden können. Die Meinung eines Nodes erfordert ein einziges Bit. Weiterhin sei angenommen, dass p = 0,1 und k = 30, dann wäre der Nachrichten-Overhead zum Senden der V-Liste zusammen mit der Abfrageantwort (es ist daher keine zusätzliche Signatur erforderlich) im Durchschnitt 1,8 Bytes. Dies sind deutlich weniger als 2500 Bytes, die voraussichtlich erforderlich sind, um Meinungen von allen k abgefragten Nodes bei dem FPC ohne Berserk-Erkennung zu erhalten. Wir schließen daraus, dass die Hinzufügung der Berserk-Erkennung zum FPC-Protokoll im Durchschnitt und in diesem speziellen Fall zu weniger als 1% größeren Nachrichten führen würde, was vernachlässigbar ist. In dem Fall, dass über mehr als einen Konflikt abgestimmt wird, würde der relative Nachrichten-Overhead für den Erkennungsmechanismus erhöht. Insbesondere erhöht jeder Konflikt den Overhead um ein Bit, während der Overhead für die Signaturen gleichbleibt. Da die Signaturkomponente im Vergleich zum Meinungsteil relativ groß ist, ist der Signaturteil der dominierende Faktor.
Verbesserungen: Vergleich der Meinungshistorie
Beachten Sie, dass in der oben dargestellten Analyse die Nodes die Meinungen aus einer einzigen, vorherigen Runde vergleichen. Wir können jedoch die Effizienz des Protokolls erhöhen, wenn die Nodes die Meinungen von mehr als nur der letzten Runde vergleichen, d.h. die Nodes können ganze Historien von Meinungen vergleichen und nicht nur die aktuelle und letzte Meinung. Unter Historie verstehen wir eine Liste aller Meinungen, die von einem bestimmten Node in aufeinanderfolgenden Runden erhalten wurden. Zum Beispiel, wenn ein Node in der m-ten Runde über einen bestimmten Konflikt abstimmt, besteht seine Historie aus m Bits und jede von ihnen entspricht der Meinung in einer der m Runden. Wenn ein solcher Node nach seiner aktuellen Meinung gefragt wird, würde er mit der m-Bit-Nachricht antworten, die später zur Erstellung von v-Listen verwendet werden würde.
Beachten Sie, dass Nodes die Historie von Meinungen unterschiedlicher Größe vergleichen könnten. Zum Beispiel, wenn ein Node x die Wahlhistorie vom selben Node y in der m1-ten und m2-ten Runde (m1 <m2) erhält, könnte er versuchen, Spuren des berserkerhaften Verhaltens auf den überlappenden m1-Runden zu finden. Mit dieser Methode erhöht sich die Effektivität der Berserkererkennung erheblich. Ein offensichtlicher Nachteil dieses Ansatzes wäre, dass wir, damit ein solches Protokoll funktioniert, von jedem in FPC abgefragten Node verlangen würden, dass er seine gesamte Meinungsgeschichte (zu einem bestimmten Konflikt) sendet. Diese Meinungshistorie würde mit jedem Wahlgang um ein Bit wachsen. Außerdem müssten die Nodes einen gewissen Speicherplatz zur Verfügung stellen, um sowohl die Historie ihrer eigenen Meinungen als auch die der Meinungen anderer Nodes zu speichern. Die zusätzlichen Kommunikationskosten sind jedoch nicht sehr hoch.
Schlussfolgerungen
Abschließend haben wir ein optionales Protokoll zur Erkennung von Berserkerhaften Gegnern vorgestellt, dass die Sicherheit des Protokolls verbessert. Die Abnahme der Wirksamkeit möglicher Angriffe führt wiederum zu einer verringerten Wahrscheinlichkeit von Übereinstimmungs- und Abbruchfehlern. Als weitere Verbesserung schlagen wir vor, dass Nodes auch mit der gesamten Historie der gesammelten Meinungen und nicht nur mit der neuesten Meinung abstimmen könnten. Wie wir gezeigt haben, würde dies die Nachrichtengröße nicht wesentlich verändern.
Wie immer, wenn Sie sich bei uns engagieren wollen, Kommentare, Fragen oder Feedback haben, zögern Sie bitte nicht, sich mit dem IOTA-Team auf unserem Discord-Server in Verbindung zu setzen.
Quellen
https://blog.iota.org/safety-of-the-tangle-berserk-detection-in-the-fpc-1a2545584daa