Der Tangle Konsensusalgorithmus

31. Jan'21

Die Quelle dieser Erklärungen ist der hervorragende Blogartikel von Autor Luka Stanisic.

Der Tangle ist so strukturiert, dass jeder Beobachter allein durch die Beobachtung des Tangles zu einem Schluss kommen kann, welche Transaktion gültig ist und welche nicht. Die Nodes berechnen lokal die Finalität der Transaktionen, die Konsensfindung kann wie folgt aufgeschlüsselt werden:

  • eine Node empfängt eine Transaktion;
  • und prüft lokal, ob diese gültig ist;
  • wenn die Node denkt, dass die Transaktion gültig ist, hängt sie diese an ihre Kopie des Tangles an und sendet die Transaktion an ihre Nachbarn weiter;
  • die Node nimmt die Transaktion in ihren Tip-Auswahl-Algorithmus auf, dass sind Tips (neue Transaktionen), die die Node als referenziert ansieht;
  • wenn eine Node einen Konflikt feststellt (2 Transaktionen, die versuchen, das gleiche Geld auszugeben), meldet sie dies;
  • wenn ein Konflikt gemeldet wird, stimmen die Nodes ab, um den Konflikt aufzulösen;
  • zu diesem Zeitpunkt denkt die Node entweder, dass die Transaktion noch gültig ist, oder sie weiß, dass es sich um eine Doppelausgabe handelt;
  • alle Nodes tun dies;
  • sie geben weiterhin Transaktionen aus, die sich auf die Transaktionen aus dem Tip-Auswahl-Algorithmus beziehen;
  • wenn eine Transaktion von FPC (Fast Probabilistic Consensus) als ungültig eingestuft wird (siehe unten), wählt der Tip-Auswahl-Algorithmus diese nicht aus;
  • die Node berechnet lokal, wie viele Nodes die Transaktion referenziert haben;
  • wenn dabei ein im Protokoll festgelegter  Schwellenwert erreicht wird, bestätigt die Node die Transaktion als endgültig, damit ist diese unumkehrbar;
  • dies wird für alle Transaktionen gemacht

 

Das Geniale an dem IOTAs Konsens im Vergleich zum Nakamoto-Konsens bei der Blockchain ist, dass bei IOTA die Nodes generell davon ausgehen, dass eine Transaktion gültig ist, abgestimmt wird nur über widersprüchliche Transaktionen. Bei der Blockchain und dem Nakamoto-Konsens fragen alle Nodes im Wesentlichen den Anführer, was wahr ist und sie verifizieren die Entscheidung des Anführers. Bei IOTA gibt es keine Anführer, alle Nodes geben zur gleichen Zeit Transaktionen aus.


Wenn Nodes annehmen, dass eine Transaktion gültig ist, überprüfen sie diese nur lokal und wenn sie gültig ist, fügen sie die Transaktion an ihre Kopie des Tangle an und geben sie an ihre Nachbarn weiter. Wenn die Nodes später eine doppelte Ausgabe entdecken, kümmern sie sich um die Lösung des Konflikts. Die Nodes verwenden dazu den FPC (Fast Probabilistic Consensus), um eine Einigung zu erzielen, die entsprechenden mathematischen Beweise dazu können hier genauer betrachtet werden. Nachfolgend die einfache Funktionsweise des FPC:

  • Wenn ein Konflikt gemeldet wird, müssen sich die Nodes darauf einigen, welche Transaktion gültig ist und welche nicht. Sie fragen zufällige Nodes nach ihrer Meinung und tun dies mehrfach in mehrere Abstimmungsrunden.
  • Wenn eine überwiegende Mehrheit der Nodes eine Transaktion bevorzugt, einigen sich alle darauf, dass sie mit hoher Wahrscheinlichkeit gültig ist.
  • Wenn keine signifikante Mehrheit von Nodes eine Transaktion bevorzugt, dann ist die Transaktion mit hoher Wahrscheinlichkeit ungültig.
  • Es werden nicht alle Nodes nach ihrer Meinung gefragt, sondern nur eine zufällige Teilmenge von Nodes.
  • Nodes mit mehr Consensus Mana haben ein größeres Mitspracherecht im Netzwerk. Sie werden häufiger abgefragt, daher ist ihre Meinung wertvoller als die Meinung von Nodes mit niedrigem Mana.
  • Nodes mit hohem Mana schreiben ihre Meinung in den Tangle und verbreiten sie. Sie tun dies, um den Nachrichten-Overhead auf ihrer Seite zu reduzieren, denn sie wissen, dass Nodes nach ihrer Meinung fragen werden, also geben sie diese nur einmal an und machen sie für alle sichtbar. Nodes mit niedrigem Mana tun dies nicht, weil nur eine kleine Anzahl von Nodes nach ihrer Meinung fragen wird, sodass es effizienter ist, diesen Nodes direkt zu antworten, anstatt die Meinung an alle Nodes zu gosippen (auszuplaudern), die ihre Meinung nicht einmal in Betracht ziehen werden.
  • Die Abstimmung wird für jede Node einzeln beendet, wenn sie ihre Meinung in N aufeinanderfolgenden Runden nicht mehr geändert hat.



Warum kann IOTA einen Konsens asynchron erreichen?

Das liegt an der Eigenschaft der Datenstruktur. Die Blockchain ist eine lineare Datenstruktur und hat eine Gesamtordnung der Transaktionen. Dort ist es wichtig, welche Transaktion zuerst kam. Die Nodes einigen sich nicht nur auf die Gültigkeit der Transaktionen, sondern auch auf die Reihenfolge dieser Transaktionen. Der Tangle ist eine nicht lineare Datenstruktur und hat keine totale Ordnung. Die Nodes einigen sich nur auf die Gültigkeit der Transaktionen und es ist ihnen egal, welche Transaktion die erste und welche die zweite innerhalb eines Zeitraums war. 

Es heißt innerhalb eines Zeitraums, weil innerhalb einer im Protokoll festgelegten Zeitspanne die Reihenfolge nicht bekannt ist, aber man kann eindeutig sagen, dass eine Transaktion heute und eine andere gestern stattgefunden hat. Ein Double Spend-Angriff (dt. Doppelausgabe) ist nur innerhalb dieses Zeitraums möglich, solange die Nodes nicht wissen, welche Transaktion zuerst angehängt wurde, in diesem Fall werden die Nodes zur FPC Abstimmung gezwungen. Sollte aber zwischen den beiden Transaktionen des Angreifers genügend Zeit verstrichen sein, wissen die Nodes, dass die zweite Transaktion später kam und diese wird dann ohne Abstimmung abgelehnt. 

Wie wird dieses Zeitfenster definiert, wenn die Reihenfolge nicht bekannt ist? Im Wesentlichen ist es ein Vielfaches der Netzwerkverzögerung (ich glaube, es ist das 2-fache der Netzwerkverzögerung). Nach dieser Zeit wissen Sie, dass alle Nodes die Transaktion erhalten haben. Wenn kein Konflikt gemeldet wurde, wissen Sie, dass ein Angreifer, der in der Zukunft eine Doppelausgabe versucht, die nach dem Zeitfenster stattfand, zurückgewiesen wird.

 


Tip-Auswahlalgorithmus

Ein weiterer wichtiger Teil des IOTA Konsenses ist der Tip-Auswahlalgorithmus. Tips sind neu hinzugefügte Transaktionen, welche noch nicht referenziert (bestätigt) wurden. Die Nodes wählen die Tips nach dem Zufallsprinzip aus und referenzieren sie (bis zu acht Stück) in ihren Transaktionen. Wenn eine Node eine Transaktion von seinem Nachbarn erhält, prüft sie, ob diese gültig ist und ob es einen Konflikt gibt. Wenn die Node die Transaktion akzeptiert, schaut sie, wer diese ausgestellt hat und auf welche Transaktionen sie verweist.

Dies ist ein wichtiger Punkt.

Diese Referenzen vermitteln der Node genügend Informationen, sodass sie die Meinung der ausstellenden Nodes kennt. Wenn die Node auf diese Weise genug Meinungen gesammelt hat, berechnet sie die Finalität der Transaktion. Die Meinung wird nach Mana gewichtet, wenn also ein im Protokoll festgelegter Schwellenwert erreicht ist, ist die Transaktion endgültig und nicht mehr umkehrbar. Es ist wichtig zu beachten, dass Transaktionen nur für eine begrenzte Zeit als Tips gelten. Wenn sie nicht innerhalb dieses Zeitraums referenziert werden, werden sie verwaist und aus dem Ledger-Status entfernt.

Konkurrierende Transaktionen erzeugen mehrere  Realitäten, aber nur eine Realität gewinnt. Die Nodes einigen sich zunächst auf eine Realität und bauen dann auf dieser auf, es ist die Realität, die genug Genehmigungsgewicht erhält, während andere Realitäten verworfen werden. Ein effizienter Weg, um Transaktionen zu behalten, die an verworfene Realitäten angehängt sind, ist die Verwendung des “approval reset switch” (dt. Genehmigungs-Rücksetzschalter). Auf diese Weise müssen diese Transaktionen nicht erneut an die gewinnende (Master-)Realität angehängt werden.

Hinweis: Bei der Blockchain minen alle gleichzeitig, bis eine Realität (Chain) die längste ist, diese  Realität gewinnt und ist gültig. Wenn der Nakamoto Consensus also Blöcke mit der Geschwindigkeit anhängen würde, mit der IOTA Transaktionen anhängt, könnte man nicht entscheiden, welche Realität (Chain) die längste ist und zu verschiedenen Zeiten wären es höchstwahrscheinlich verschiedene Realitäten. Man löst dies, indem man begrenzt, wie oft neue Blöcke erstellt und angehängt werden können. Bei IOTA warten Sie nur auf den FPC oder N Sekunden bis Transaktionen bestätigt werden.


Luka hat zu dem Thema auch das folgende Video erstellt.


Eine naive Herangehensweise, um die Finalität einer Transaktion zu berechnen, wäre, durch den Tangle zu gehen und zu sehen, wie viele einzelne Nodes die Transaktion referenziert haben. Summiert man deren Consens-Mana und wenn es größer als ein bestimmter Schwellenwert ist, ist die Transaktion endgültig. Dies ist jedoch ein ineffizienter Weg, um das Genehmigungsgewicht zu berechnen. Bei IOTA wird ein Konzept namens "Marker" verwendet, um das Genehmigungsgewicht effizient zu berechnen. Für diejenigen, die sich näher damit befassen wollen, schauen Sie bitte hier rein.

Das Schöne am Tangle und diesem Konsens-Mechanismus ist, dass eine Transaktion, wenn sie endgültig ist, irreversibel ist und man nicht zurückgehen und sie rückgängig machen kann. Beim Nakamoto-Konsens können Sie das. Man kann zurückgehen und neue Blöcke erzeugen und sobald diese Kette länger wird als die vorherige, gewinnt sie und die andere Kette wird verworfen, als wäre sie nie passiert. (Bei IOTA werden widersprüchliche Realitäten auch verworfen, aber diese Transaktionen wurden nie bestätigt.)

Transaktionen, die ehrlich sind, werden innerhalb von Sekunden bestätigt, weil die Nodes nicht über sie abstimmen werden. Es wird kein Konflikt entdeckt und sie werden schnell Genehmigungsgewicht anhäufen. Böswillige Akteure hingegen müssen länger warten, bis FPC den Konflikt auflöst, sodass sich die Nodes einigen müssen, wie der Tangle zu formatieren ist.


Für diejenigen unter euch, die sich fragen, ob ein Angreifer immer wieder konfliktbehaftete Transaktionen ausstellen und Nodes in einer Abstimmungsschleife halten kann?

Nein. Jeder Angreifer hat begrenzte Ressourcen, wie wir alle. Er kann nur versuchen, das Netzwerk mit den begrenzten TPS anzugreifen, die ihm im Verhältnis zum Mana, das er besitzt, zustehen. Er kann sich dafür entscheiden, seine TPS zu verschwenden, indem er versucht, sie doppelt auszugeben (er braucht 2 + Transaktionen pro Versuch), oder er kann sich dafür entscheiden, etwas Produktiveres zu tun, wie z.B. seine ungenutzten TPS gegen eine Rendite zu vermieten. So oder so, es ist seine Entscheidung und das Netzwerk wird jeden Versuch erfolgreich entschärfen.



Zuletz bearbeitet am 04.02.2021