August 20, 2019

Konsens im IOTA-Tangle - FPC

Konsens im IOTA-Tangle - FPC

Dies ist der erste Beitrag in einer Reihe von Beiträgen, in denen die in IOTA Coordicide beschriebenen Konsensprotokolle erläutert werden.

Das Hauptziel dieser Reihe ist es, die Community besser über aktuelle Forschungsergebnisse auf dem Laufenden zu halten und interessante Forschungsfragen zu erklären, die gute Chancen haben, durch Coordicide Zuschüsse finanziert zu werden. Du wirst sehen, das das Thema ziemlich umfangreich ist und es viele Verbindungen und Abhängigkeiten zu anderen Teilen des Coordicide-Projekts gibt.

Angesichts dieser Komplexität werden wir versuchen, nur wenige Punkte gleichzeitig zu erklären und uns auf die Fragen zu konzentrieren, die derzeit untersucht werden. Wir möchten jedoch darauf hinweisen, dass IOTA bereits über alle wichtigen Bestandteile für eine effiziente und sichere Lösung für den Coordicide verfügt.

Die verbleibenden Fragen beziehen sich auf die Optimierung der Lösung, zum Beispiel:

  • Sicherheit erhöhen
  • Steigerung der Nachhaltigkeit (z. B. Verringerung der Nachrichtenkomplexität, Verringerung des PoW)
  • TPS erhöhen
  • Zeit verringern, bis zur Endgültigkeit
  • Erhöhung der Flexibilität der Implementierung, für zukünftige Herausforderungen

Kommen wir nun zum Thema: Wir wollen verstehen, worum es bei diesem „Konsens“ geht.

Warum Konsens?
Verteilte Konsensalgorithmen ermöglichen es vernetzten Systemen, sich in Situationen, in denen eine dezentrale Entscheidungsfindung schwierig oder gar unmöglich ist, auf einen erforderlichen Status oder eine erforderliche Meinung zu einigen.

Distributed Computing ist von Natur aus unzuverlässig. Durch das Erreichen eines Konsenses kann ein verteiltes System als eine Einheit arbeiten. Die Bedeutung dieser Herausforderung beruht auf ihrer Allgegenwart, bei der Fehlertoleranz eines der grundlegendsten Aspekte ist.

Häufige Beispiele sind: Replizierte Dateisysteme, Uhrzeitsynchronisation, Ressourcenzuweisung, Aufgabenplanung und nicht zuletzt verteilte Ledger (DLTs).

Verteilte Systeme bilden ein umfassendes und klassisches Thema in der Informatik, und dasselbe gilt auch für die zugehörigen Konsensprotokolle: Eine elegante Einführung in das Thema, findest du unter Funktionsweise von verteiltem Konsens.

Die vorhandenen Konsensprotokolle sind im wesentlichen die klassischen Protokolle - z.B. diejenigen, die auf PAXOS basieren - und der jüngste Wegbereiter: der Nakamoto-Konsens. Beide Protokolle unterliegen schwerwiegenden Einschränkungen/Nachteilen.

Die klassischen Protokolle haben eine quadratische Nachrichtenkomplexität, erfordern genaue Mitgliederkenntnisse und sind gegen Störungen ziemlich zerbrechlich. Das Nakamoto-Protokoll ist dagegen robust und erfordert keine speziellen Mitgliedschaften. Es ist jedoch auf PoW angewiesen, was zu bekannten Problemen wie "mining races" und Nichtskalierbarkeit führt.

Wie wird ein Konsens im IOTA-Tangle erreicht?
Lasst uns zunächst auf den Nakamoto-Konsens zurückblicken. Eine brillante Idee des Nakamoto-Konsenses besteht darin, den Konsens nicht deterministisch oder probabilistisch zu machen. Anstatt, dass sich alle Nodes des (verteilten) Systems auf die Richtigkeit eines Wertes einigen, stimmen sie der „Wahrscheinlichkeit“ zu, dass dieser Wert korrekt ist.

Die Rolle des Führers in traditionellen Konsens Protokollen, wird von dem Node übernommen, der ein gegebenes Rechenpuzzle am schnellsten löst. Dieser Gewinner, fügt der Blockchain einen neuen Block hinzu. Auf diese Weise baut das (verteilte) Netzwerk die ständig wachsende Blockchain auf und stimmt der Gültigkeit der längsten Kette, oder der Kette mit den meisten kumulativen Schwierigkeiten zu.

Warum ist dieser Konsens also probabilistisch? Um zu wissen, dass eine bestimmte Transaktion als gültig betrachtet wird, beispielsweise in 100 Tagen, müssen wir wissen, dass die längste Kette in 100 Tagen diese bestimmte Transaktion enthält.

Mit anderen Worten: Wir sind an der Wahrscheinlichkeit interessiert, dass die längste Kette in 100 Tagen diese Transaktion enthält. Die Wahrscheinlichkeit, dass eine Transaktion nicht zurückgesetzt wird steigt, wenn der Block, der diese Transaktion enthält, „tiefer“ in der Kette verankert ist.

In der Bitcoin-Blockchain wird beispielsweise empfohlen zu warten, bis eine Transaktion sechs Blöcke tief in der Blockchain ist. Nach dieser Zeit ist die Wahrscheinlichkeit, dass eine Transaktion zurückgesetzt wird, sehr gering.
Dieser Effekt gilt auch für den Tangle. Je tiefer - oder "eingehüllter" - eine Transaktion ist, desto endgültiger wird sie sein. In der folgenden Abbildung wird die dunkelgrüne Transaktion von allen hellgrünen Transaktionen überprüft. Wenn die Anzahl der hellgrünen Transaktionen zunimmt, konvergiert die Wahrscheinlichkeit, dass die dunkelgrüne Transaktion in der Zukunft valide ist, gegen 1.

Aber Moment, der Tangle unterscheidet sich von einer Blockchain! Während die Blockchain zwei widersprüchliche Transaktionen nicht enthalten darf, kann das Tangle vorübergehend schon solche widersprüchlichen Transaktionen enthalten. Daher kann es vorkommen, dass ein böswilliger Teilnehmer zwei in Konflikt stehende Transaktionen an verschiedenen Stellen des Tangle anfügt, z. B. das dunkelgrüne und das orangefarbene Quadrat im obigen Bild.

Diese Transaktionen können für kurze Zeit im Tangle "überleben", bis ehrliche Nodes den Konflikt erkennen. Sobald ein solcher Konflikt erkannt wurde, entscheiden die Nodes, welche Transaktion ausgewählt werden soll. Im obigen Beispiel wird die dunkelgrüne Transaktion vom Tangle "stärker umhüllt" und sollte schließlich von allen Nodes genehmigt werden.

Damit der Tangle zu einem echten Konsensprotokoll wird, müssen wir uns aber, für einen der widersprüchliche  Transaktionen entscheiden. Diese Entscheidung sollte unter Verwendung eines Konsensprotokolls getroffen werden.

Sind wir hier im Kreis gegangen? Zum Glück nicht: Die Coordicide Lösung schlägt zwei weitere Konsensprotokolle vor:

Der Rest dieses Beitrags widmet sich einer kurzen Einführung in den FPC und erklärt, wie man zu einem Konsens kommt, wenn es darum geht zu entscheiden, ob eine einzelne Transaktion gültig ist oder nicht.

In einem zukünftigen Blog-Beitrag werden wir uns dann damit befassen, warum dies ausreicht, um einen Konsens im Tangle zu erzielen, und wir werden die Endgültigkeit von Transaktionen im Tangle erörtern.

Was ist FPC?
Die FPC ist ein führendes probabilistisches binäres Konsens Protokoll, mit geringer Kommunikationskomplexität, das robust in einer byzantinischen Infrastruktur ist - siehe Originalartikel von Serguei Popov und Bill Buchanan.

Lasst uns schauen, was all diese Begriffe wirklich bedeuten, und zunächst eine leichtere Version der FPC vorstellen, die einfach zu implementieren ist und bereits die meisten wichtigen Funktionen enthält.

Wir gehen davon aus, dass im Netzwerk n Nodes mit 1,2,…, n indiziert sind. Jede Node, die wir haben, hat eine Meinung oder einen Zustand. Wir bezeichnen s_i (t) für die Meinung des Nodes i zum Zeitpunkt t. Meinungen nehmen die Werte {0,1} an; Deshalb sprechen wir von einem binären Konsens.

Die Grundidee dafür ist die Mehrheitsentscheidung. In jeder Runde fragt jeder Node k zufällige Nodes ab und passt seine Meinung auf die Mehrheit der abgefragten Nodes an. So einfach ist das! Diese einfache Mehrheitsentscheidung erweist sich jedoch als anfällig für fehlerhafte Nodes und für böswillige Angreifer. Es braucht also eine zusätzliche Zutat, nämlich eine zusätzliche Zufälligkeit, um sie robust zu machen.

Genauer gesagt, bei jedem Schritt wählt jeder Node k zufällige Nodes C_i aus, fragt ihre Meinungen ab und berechnet die durchschnittliche Meinung

Wir bezeichnen 𝝉 𝝉 [0,1] als ersten Schwellenwert, der eine gewisse Asymmetrie des Protokolls zulässt, ein weiteres Thema, das wir in naher Zukunft behandeln werden. Darüber hinaus führen wir eine "zusätzliche Zufälligkeit" ein; Es sei U_ {t}, i = 1, 2, ... i. Zufallsvariablen mit Gesetz Unif (𝜷, 1- 𝜷) für einige Parameter 𝜷 𝜷 [0,1 / 2].

Zu jeder Zeit verwendet jeder Node i die Meinungen von k zufälligen Nodes, um seine eigene Meinung zu aktualisieren:

und für t > 0:

Es ist wichtig, dass in jeder Runde jede Node eine andere zufällige Menge an Nodes befragen und dass die Zufallsvariablen U_t auch in jeder Runde aktualisiert werden.

Wir führen eine lokale Beendigungsregel ein, um die Kommunikationskomplexität des Protokolls zu verringern. Jede Node behält seine Zählervariable cnt bei, die jeweils um 1 erhöht wird, wenn sich seine Meinung nicht ändert, und auf 0 gesetzt wird, sobald sich seine Meinung ändert.

Sobald der Zähler eine bestimmte Schwelle 1 erreicht, d. H. Cnt ≥ 1, betrachtet der Node den aktuellen Zustand als endgültig. Der Node sendet daher keine Anfragen mehr, beantwortet aber weiterhin eingehende Anfragen. Die nächsten Grafiken zeigen typische Entwicklungen der Variablen cnt für jede Node mit l = 5, k = 10 und anfänglichen Meinungen von 90% Einsen und 10% Nullen.

Im linken Bild ist das Protokoll nicht gestört, aber im rechten Bild versuchen 20% der Node in böswilliger Absicht, die Mehrheit der ehrlichen Nodes umzustimmen. In beiden Fällen stimmen am Ende alle ehrlichen Nodes der anfänglichen Mehrheit zu.


Wir möchten das Merkmal der allgemeinen Zufallsschwellenwerte der FPC hervorheben und eine erste Analyse der FPC für verschiedene Arten von Parametereinstellungen und Angriffsstrategien unter Simulation der FPC durchführen.

Auswirkung der zufälligen Schwellenwerte

Die Bedeutung der Unsicherheit im Krieg wurde von Carl von Clausewitz eingeführt:

Krieg ist das Reich der Unsicherheit; Drei Viertel der Faktoren, auf die sich das Kriegsgeschehen stützt, sind in einen Nebel größerer oder geringerer Unsicherheit gehüllt. Ein sensibles und diskriminierendes Urteil ist erforderlich; Eine geschickte Intelligenz, um die Wahrheit herauszufinden.

- Carl von Clausewitz, 1873

Was hat das alles mit den zufälligen Schwellenwerten in der FPC zu tun? Bei einfacher Mehrheit würden diese Schwellenwerte nur 0,5 betragen. Eine erfolgreiche Angriffsstrategie könnte darin bestehen, die ηs der ehrlichen Nodes um 0,5 zu halten, um eine Konvergenz des Protokolls zu verhindern (wir werden später einen so erfolgreichen Angriff sehen). Die Idee von Popov und Buchanan war, dem System "Lärm" oder "Nebel" hinzuzufügen, um die Informationsunsicherheit für die potenziellen Angreifer zu erhöhen.

Warum ist das alles so wichtig? In einer Situation ohne böswillige Nodes ist die Verteilung der ηs nahezu normal:

Bereits in einer ungestörten Situation können die Meinungen der ehrlichen Nodes nahe an einer 50: 50-Situation bleiben. Zufällige Effekte, die durch die zufällige Abstimmung verursacht werden, führen jedoch schließlich zu einer Konvergenz des Protokolls. Diese Situation ist in einer byzantinischen Infrastruktur völlig anders.

Betrachten wir eine gegnerische Strategie, bei der die ehrlichen Nodes in zwei gleich große Gruppen unterschiedlicher Meinungen unterteilt werden, die zu einer folgenden Verteilung der ηs unter den ehrlichen Nodes führen:

Wie kann ein Gegner dies erreichen?

Der Angreifer wartet, bis alle ehrlichen Nodes Meinungen von allen anderen ehrlichen Nodes erhalten haben. Der Angreifer berechnet dann den Median dieser Zwischen-ηs. Der Gegner versucht nun, den Median des η nahe bei 0,5 zu halten, indem er versucht, die Varianzen des η zu maximieren.

Wie kann die FPC einen solchen Angriff verhindern? Durch Ersetzen der deterministischen Schwelle (rot, gestrichelt) durch zufällige Schwellen (blau, gestrichelt). In der folgenden Grafik steht jede blaue Linie für eine zufällige Schwelle einer bestimmten Runde. Da diese Schwellenwerte zufällig sind, kann der Gegner nicht vorhersehen, wie die ehrlichen Nodes aufgeteilt werden müssen, um die 50:50-Situation zu bewahren. Der beste Weg ist, sie immer noch um den Wert 0,5 zu teilen.

Sobald jedoch eine blaue Linie (in r3 im Bild unten) weit genug von der roten Linie entfernt ist, verliert der Angreifer die Kontrolle über die ehrlichen Nodes und das Protokoll wird beendet.

In der folgenden Animation kann man das Verhalten und das Ergebnis des Protokolls sehen, wenn diese gegnerische Strategie ohne Zufälligkeit (Schwelle = 0,5) angewendet wird und nachdem die Zufälligkeit hinzugefügt wurde. Wie du siehst, gelingt es dem Gegner, die Nodes für längere Zeit in der Schwebe zu halten. Schlimmer noch, das Netzwerk ist seiner Meinung nach gespalten - was zu einem Vertragsbruch führt. Nachdem die zusätzliche Zufälligkeit eingeführt wurde, wird das Protokoll jedoch schnell und einheitlich abgeschlossen.

Laufende Arbeit und nächste Schritte

Lasst uns zum Schluss noch einmal auf einige Punkte zurückkommen, an denen IOTA derzeit arbeitet, und einige Beispiele für zukünftige Kooperationen aufzeigen:

  1. Momentan führen wir gründliche Simulationen durch, um verschiedene Angriffsstrategien für verschiedene Arten von Netzwerktopologien zu untersuchen. Die Ergebnisse ermöglichen es uns, die optimale Menge an Zufälligkeit und Auswahl der Protokollparameter zu identifizieren. Wir untersuchen auch die Robustheit der FPC gegenüber Ausfällen und Störungen der Zufallsschwelle.
  2. Die in Simulationen ermittelten Konvergenzgrenzen der FPC sind weitaus besser als die theoretisch von Popov und Buchanan ermittelten. Verschiedene Parametereinstellungssimulationen zeigen, dass es ein sogenanntes „Cut-Off-Phänomen“ gibt. Informell bedeutet dies im Wesentlichen, dass das Protokoll mit hoher Wahrscheinlichkeit m Schritte benötigt, um einen Konsens zu erzielen, und dass es sehr unwahrscheinlich ist, dass das Protokoll mehr als m Schritte benötigt. Theoretische Ergebnisse in dieser Richtung wären sehr willkommen.
  3. Die tatsächliche Implementierung der FPC hängt von der Reputation der Nodes ab. Da der Ruf oder das Mana der Nodes in anderen Teilen des Coordicide-Projekts eine herausragende Rolle spielt, werden wir in einem zukünftigen Blog-Beitrag mehr darüber schreiben. Auf jeden Fall wird dieses zusätzliche Feature das Protokoll sicherer gegen verschiedene Arten von Angriffen machen.
  4. Die oben in der FPC untersuchten Parameter wurden zu Beginn des Protokolls in Stein gemeißelt. Um jedoch die Sicherheit zu erhöhen und gleichzeitig die Komplexität der Nachrichten zu verringern (was wie ein Wunder klingt), untersuchen wir angepasste Versionen der FPC. Wenn beispielsweise η eines Nodes in der Nähe von 0,5 liegt, kann der Nodes entscheiden, die Anzahl der Abfragen zu erhöhen, während er in der Nähe von 1 entscheidet, entweder die Anzahl der Abfragen des nächsten Schritts zu verringern oder die Abfrage sofort zu beenden.
  5. Heutzutage wird maschinelles Lernen in einer Vielzahl von Bereichen eingesetzt, wo es seine Überlegenheit gegenüber herkömmlichen regelbasierten Algorithmen zeigt. Wir planen, maschinelles Lernen nicht nur zur Erkennung fehlerhafter und böswilliger Nodes einzusetzen, sondern auch die schädlichsten Angriffsstrategien mithilfe von verstärktem künstlichen Lernens zu ermitteln.

Wir freuen uns darauf, dich auf die aufregende Reise vom Coordicide mitzunehmen und hoffen, dass du die Entwicklung dieses Projekts so wie wir genießen kannst.

Wie immer freuen wir uns über eure Kommentare und Fragen in #tanglemath in unserem Discord. Ihr könnt auch eine intensivere wissenschaftliche Zusammenarbeit mit uns eingehen und ein Stipendium beantragen.

Der Autor ist kein Mitglied der IOTA-Stiftung. Er schrieb diesen Blogpost in Zusammenarbeit mit den Mitgliedern der IOTA-Forschungsgruppe.


Quelle: https://blog.iota.org/consensus-in-the-iota-tangle-fpc-b98e0f1e8fa