Fast Probabilistic Consensus (FPC) – Konsens im IOTA-Tangle

20. Aug’19

Übersetzung des Blogartikel vom Autor Sebastian Mueller, IOTA Foundation.

Dies ist der erste 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 über aktuelle Forschungsergebnisse auf dem Laufenden zu halten und interessante Forschungsfragen zu erklären, die gute Chancen haben, durch Coordicide-Zuschüsse (aus dem 5 Mio. Fond) finanziert zu werden. Wie Sie sehen werden, ist das Thema ziemlich umfangreich und es gibt viele Verbindungen und Abhängigkeiten zu anderen Teilen des Coordicide-Projekts.

Angesichts dieser Komplexität werden wir versuchen, jeweils nur einige Punkte zu erklären und uns auf 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 Coordicide verfügt.

Die verbleibenden Fragen beziehen sich auf die Optimalität der Lösung, zum Beispiel:

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

Warum Konsens?

Verteilte Konsensalgorithmen ermöglichen es vernetzten Systemen, sich in Situationen, in denen eine dezentrale Entscheidungsfindung schwierig oder sogar 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 einer der grundlegendsten Aspekte ist.

Häufige Beispiele sind: replizierte Dateisysteme, Uhrzeitsynchronisation, Ressourcenzuweisung, Aufgabenplanung und nicht zuletzt Distributed Ledger (verteilte Hauptbücher).

Verteilte Systeme bilden ein umfassendes und klassisches Thema in der Informatik, und dasselbe gilt für zugehörige Konsensprotokolle: Eine elegante Einführung in dieses Thema finden Sie unter Funktionsweise von verteiltem Konsens.

Bei den vorhandenen Konsensprotokollen handelt es sich im Wesentlichen um die klassischen Protokolle – z. B. auf PAXOS-Basis – und um den jüngsten Game-Changer: den Nakamoto-Konsens. Beide Protokolle unterliegen schwerwiegenden Einschränkungen.

Die klassischen Protokolle haben eine quadratische Nachrichtenkomplexität, erfordern präzises Mitgliedschaftswissen und sind eher anfällig für Störungen. Das Nakamoto-Protokoll hingegen ist robust und erfordert keine konkreten Mitgliedschaften. Sie stützt sich jedoch auf PoW, was zu bekannten Problemen wie Mining-Rennen und Nicht-Skalierbarkeit führt.

Wie wird ein Konsens im IOTA-Tangle erreicht?

Lassen Sie 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 Konsensprotokollen 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 die Kette eintaucht.

In der Bitcoin-Blockchain wird beispielsweise empfohlen, zu warten, bis eine Transaktion sechs Blöcke tief in der Blockchain ist. Nach dieser Tiefe ist die Wahrscheinlichkeit, dass eine Transaktion zurückgesetzt wird, sehr gering.

Dieser Effekt gilt auch für das Tangle. Je tiefer – oder “eingehüllt” – eine Transaktion wird, desto endgültiger wird sie. 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 stattfindet, gegen 1.

Aber warte, der Tangle unterscheidet sich von einer Blockchain! Während die Blockchain zwei widersprüchliche Transaktionen nicht enthalten darf, kann das Tangle vorübergehend solche Transaktionen enthalten. Daher kann es sein, dass ein böswilliger Spieler zwei in Konflikt stehende Transaktionen an verschiedenen Stellen des Tangle anfügt, wie 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 das Tangle zu einem echten Konsensprotokoll wird, müssen wir uns für widersprüchliche Transaktionen entscheiden. Diese Entscheidung sollte unter Verwendung eines Konsensprotokolls getroffen werden.

Sind wir hier im Kreis gegangen? Zum Glück nein: Coordicide schlägt zwei weitere Konsensprotokolle vor:

• der schnelle probabilistische Konsens (FPC) und
• der zelluläre Konsens (CC)

Der Rest dieses Beitrags widmet sich einer kurzen Einführung in 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 damit befassen, warum dies ausreicht, um einen Konsens auf der Ebene von Tangle zu erzielen, und wir werden die Endgültigkeit von Transaktionen im Tangle erörtern.

Was ist FPC?

In Phantasie Hinsicht ist die FPC ein führerlos probabilistisches binäres Konsens Protokoll niedriger kommunikativer Komplexität , die in einer byzantinischen Infrastruktur robust ist – Original Artikel von Serguei Popov und Bill Buchanan .

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

Wir gehen davon aus, dass im Netzwerk n Nodes mit 1,2,…, n indiziert sind . Jeder Node, den ich habe, hat eine Meinung oder einen Zustand. Wir bezeichnen s_i (t) für die Meinung des Nodes i zum Zeitpunkt t. Meinungen nehmen Wert in {0,1} ; Aus diesem Grund sprechen wir von einem binären Konsens.

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

Genauer gesagt, bei jedem Schritt wählt jeder Node k zufällige Node C_i aus , fragt ihre Meinungen ab und berechnet die mittlere 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; lassen U_ {t}, i = 1, 2, … sein Unabhängige und gleich verteilte Zufallsvariablen mit dem 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 ein Node eine andere zufällige Menge von Nodes abfragt 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. Jeder Node behält eine Zählervariable cnt bei , die um 1 erhöht wird, wenn sich seine Meinung nicht ändert, und auf 0 gesetzt wird, wenn sich die Meinung ändert.

Sobald der Zähler einen bestimmten Schwellenwert erreicht l , dh cnt≥1 , hält 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 jeden Node mit l = 5, k = 10 und anfänglichen Meinungen von 90% von 1 und 10% von 0 .

Im linken Bild ist das Protokoll nicht gestört, aber im rechten Bild versuchen 20% der Knoten in böswilliger Absicht, die Mehrheit der ehrlichen Nodes zu verwandeln. In beiden Fällen stimmen schließlich 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 mit den zufälligen Schwellenwerten in der FPC zu tun? Bei einfacher Mehrheit würden diese Schwellenwerte nur 0,5 betragen. Eine fruchtbare Angriffsstrategie könnte darin bestehen, die ηs der ehrlichen Node um 0,5 zu halten, um eine Konvergenz des Protokolls zu verhindern (wir werden einen solchen erfolgreichen Angriff später 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, die die ehrlichen Nodes in zwei gleich große Gruppen unterschiedlicher Meinungen unterteilt, was zu einer Aufteilung der ηs auf ehrliche Nodes führt:

Wie kann ein Gegner dies erreichen?

Der Gegner wartet, bis alle ehrlichen Nodes Meinungen von allen anderen ehrlichen Nodes erhalten haben. Der Gegner berechnet dann den Median dieser Zwischen- ηs. Nun versucht der Gegner, 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 Gegner die Kontrolle über die ehrlichen Nodes und das Protokoll wird beendet.

In der folgenden Animation können Sie 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 Sie sehen, gelingt es dem Gegner, die Node 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

Lassen Sie uns zu guter Letzt 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 Node ab. Da der Ruf oder das Mana des Node 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 eine angepasste Version des FPC. Wenn beispielsweise η eines Nodes in der Nähe von 0,5 liegt , kann der Node 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 bei zu beenden alle.
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 Lernen zu ermitteln.

Wir freuen uns darauf, Sie auf die aufregende Reise von Coordicide mit den Augen der Forschungsabteilung mitzunehmen, und hoffen, dass Sie die Entwicklung dieses Projekts so wie wir genießen werden.

Wie immer freuen wir uns über Ihre Kommentare und Fragen, entweder hier in den Kommentaren oder in #tanglemath auf unserer Discord. Sie können 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.

Quellen

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