Archiv Skalierung IOTA Teil 2 – Entwirrung des Tangle

21. Apr’20

Übersetzung des Blogartikel von Autor Hans Moog, IOTA Foundation.

Hinweis: Sharding bezeichnet die Aufteilung einer Datenbank, daher ist in diesem Artikel oft von aufteilen oder splitten die Rede.

Um die im ersten Teil dieses Blogbeitrags erwähnten Probleme zu lösen, brauchen wir eine völlig andere Form des Shardings.

In den folgenden Abschnitten werden wir eine schrittweise Einführung in die Konzepte geben, die es IOTA ermöglichen, die Anzahl der Nodes unendlich zu skalieren, ohne die Sicherheit in den frühen Phasen der Adoption zu gefährden oder das es zu “Angebotsschocks” bei den Durchsatzanforderungen kommt.


Das Tangle teilt sich automatisch

Das Tangle ist nicht durch eine Blockgröße begrenzt, und jeder kann jederzeit neue Transaktionen anhängen, ohne sich auf etwas anderes als die beiden vorangegangenen Ereignisse, auf die dies referenziert, verlassen zu müssen. Das bedeutet, dass das Tangle im Wesentlichen nie voll ist und eine beliebige Anzahl von Transaktionen enthalten kann.

Wenn der Netzwerkdurchsatz die Verarbeitungskapazitäten der Nodes übersteigt, sehen und verarbeiten die Nodes unterschiedliche Transaktionen, je nachdem, wo im Netzwerk sie sich befinden und sehen daher auch unterschiedliche Tangle. Nodes mit ähnlichen Verarbeitungsfähigkeiten, die sich nahe beieinander befinden, werden eine ähnliche Auffassung haben.

Jeder Node wird seinen jeweiligen Teil des DAG validieren, der aus einer Teilmenge aller vorhandenen Transaktionen besteht. Dies ist die eigentliche Definition von Sharding: “Teilen Sie die Aufgaben auf und sorgen Sie dafür, dass jeder Node nur eine Teilmenge der Gesamtarbeit übernimmt.”

Das folgende Bild zeigt, wie solch ein natürliche aufgesplittetes Tangle in zwei Shards aussehen würde (die Hälfte der Transaktionen wird von der Hälfte der Nodes verarbeitet):

Dieser Prozess des splitten kann rekursiv erfolgen, so dass z.B. Shard 1 in weitere Shards zerfällt, wenn die Nodes nicht in der Lage sind, alle verbleibenden Transaktionen zu verarbeiten. Die verschiedenen Netzsegmente werden zu unterschiedlichen Zeiten, je nach dem tatsächlichen Durchsatz, mehr oder weniger augenblicklich aufgeteilt, ohne dass komplizierte Verhandlungen darüber geführt werden müssen, wann und wo aufgeteilt werden soll. Es hängt einfach davon ab, welche Transaktionen die Nodes verarbeiten können (agent-centric approach).

Sobald die Last sinkt, sind die verschiedenen Tangle theoretisch (siehe Probleme weiter unten) in der Lage, wieder miteinander zu verschmelzen, was zu einem System führt, das in der Lage ist, dynamisch auf unterschiedliche Netzwerkbedingungen und wachsende Akzeptanz zu reagieren.


Probleme mit diesem Ansatz

Diese Lösung ist zwar extrem einfach und erlaubt es dem Netzwerk theoretisch, auf eine beliebige Anzahl von Transaktionen pro Sekunde zu skalieren, sie hat aber auch einige sehr ernste Probleme:

  1. Die Nodes haben keine Vorstellung davon, für welchen Teil des Tangle sie verantwortlich sind. Folglich wäre es für die Benutzer schwierig zu wissen, welchen Node sie wählen müssen, wenn sie versuchen, auf ihre Gelder zuzugreifen.
  2. Es wird für die verschiedenen Shards schwierig, miteinander zu interagieren, da es keine objektive Vorstellung davon gibt, welche Shards überhaupt existieren.
  3. Da die verschiedenen Tangle die gleiche Geschichte, aber nicht die gleichen Validatoren haben, könnte man Gelder, die man vor der Teilung erhalten hat, doppelt ausgeben, und zwar für jeden Shard einzeln – siehe Bild:

Dieses Problem der doppelten Ausgaben ist ziemlich gravierend, da es sogar verhindert, dass die Tangle wieder zusammenwachsen (sobald die Belastung sinkt), was das volle Potenzial der Lösung untergräbt.

Der Grund für diese Probleme liegt jedoch nicht in der Struktur der DAG selbst (wie in diesem Video von RADIX behauptet), sondern in der Tatsache, dass sich das Tangle im Wesentlichen völlig unkontrolliert und zufällig aufteilt.


Lösung der genannten Probleme

Um diese Probleme zu lösen, müssen wir einen Weg finden, wie sich die Nodes auf nicht-zufällige und deterministische Weise aufteilen können. Das bedeutet, dass wir im Wesentlichen einen Mechanismus finden müssen, der es uns ermöglicht, Nodes und ihre Transaktionen einem bestimmten Ort im aufgeteilten Netzwerk zuzuordnen.

Um dies zu erreichen, bringen wir jeden Node und jede Transaktion dazu, eine Markierung zu tragen, die definiert, zu welchem Shard sie gehören (noch bevor irgendwelche Shards entstehen). Wenn die Notwendigkeit einer Aufteilung entsteht, splittet sich der DAG auf und der Ledger-Zustand teilt sich mit ihm.

Schauen wir uns das gleiche Beispiel an, aber diesmal mit jeder Transaktion, die eine Markierung (blau oder rot) trägt:

Anfänglich sind die Transaktionen der verschiedenen Shards “verwickelt”, aber nach dem splitten des Tangle werden die roten Nodes nur rote Guthaben und Transaktionen verfolgen und die blauen Nodes nur ihren entsprechenden Teil. Dieser einfache Mechanismus beseitigt die Möglichkeit, alte Gelder doppelt auszugeben, ohne eine komplizierte Form der Kommunikation zwischen den Shards einzuführen. Jeder Shard hat eine bestimmte Zuständigkeit, für die er verantwortlich ist, und ein Benutzer, der versucht, blaue Gelder im roten Shard auszugeben, wird einfach ignoriert. Dieser Mechanismus wird als State-Sharding bezeichnet.

In dem Beispiel haben wir Farben verwendet, aber die Markierungen sind eigentlich nur Zahlen, die durch eine Bit-Maske dargestellt werden können, die es dem Tangle erlaubt, beliebig oft zu sharden (eine 64-Bit-Markierung würde es uns zum Beispiel erlauben, mehr als 9 Quintillion-Shards zu erschaffen).

Die Shard-Markierung wird so etwas wie die Sharding-DNA einer Transaktion, die alle Informationen enthält, die sie benötigt, um ihre zukünftige Position in einem erwachsenen DAG zu bestimmen. In seinem kindlichen Zustand wird diese Information latent vorhanden sein, aber sie wird es dem Tangle ermöglichen, sich zuverlässig aufzuteilen, sobald der Bedarf entsteht.

Da die Ledger-Zustände der beiden Zweige niemals in Konflikt geraten können, können diese Shards jetzt sogar zu einem späteren Zeitpunkt, wenn die Belastung sinkt, wieder zusammenfließen.


Eine logisches Overlay-Mapping der “realen Welt”

Die Shard-Markierungen lösen alle oben genannten Probleme, aber darüber hinaus geben sie uns auch ein sehr leistungsfähiges Werkzeug an die Hand, mit dem wir ein Sharding-Layout entwerfen können, das die reale Welt als eine Art logisches Overlay-Mapping (dt. Überlagerungs-Kartieren) widerspiegelt, was letztlich bedeutet, dass wir den Zahlen, die die Shard-Markierungen darstellen, eine gewisse Bedeutung geben können.

Da wir ein Protokoll für das Internet der Dinge entwerfen, macht es sehr viel Sinn, eine geographische Kartierung zu verwenden, bei der die Shard-Markierungen in bestimmte Koordinaten auf diesem Planeten übersetzt werden. Auf diese Weise werden Nodes, die physisch nahe beieinander liegen, Teil desselben Shards sein.

Auf diese Weise werden nicht nur die Netzwerklatenzen innerhalb eines Shards reduziert, sondern auch die Kommunikation zwischen den Shards auf ein absolutes Minimum reduziert, da die meisten wirtschaftlichen Aktivitäten lokal stattfinden:

  • Ein Auto kauft Strom von einer Ladestation in der Nähe.
  • Die Leute kaufen Pizza in der Pizzeria um die Ecke.
  • und so weiter …

Dieses geographische Overlay-Mapping ist daher eine sehr gute Annäherung an die wirtschaftlichen Beziehungen in einer bestimmten Region.

Darüber hinaus ist diese Verwendung einer geographischen Kartierung eine gute Möglichkeit, mit großräumigen Netzwerksplits umzugehen. Wenn ein Netzwerksegment z.B. aufgrund von Dingen wie dem Dritten Weltkrieg offline geht, dann kann niemand chinesische Gelder in den USA ausgeben und umgekehrt. Die beiden getrennten Netzwerke haben daher eine höhere Chance, sich wieder zusammenzuschließen, sobald die Splittung aufgelöst ist.

Wenn die Shard-Markierungen alle genannten Probleme lösen … sind wir dann fertig? Noch nicht! Es gibt noch einige Probleme, die gelöst werden müssen:

  • Bevor wir Shard-Markierungen einführten, splitteten die Nodes automatisch auf der Grundlage ihrer eigenen Verarbeitungsmöglichkeiten. Dieser Mechanismus macht jedoch keinen Sinn mehr, da wir versuchen, die Nodes entsprechend ihrer Zugehörigkeit zu einer bestimmten Region aufzusplitten.
  • Die Nodes müssen daher eine Form von Konsens darüber haben, wann und wo sie gesplittet werden sollen. Dies ist ein kniffliges Problem, zumal die Nodes völlig unterschiedliche Verarbeitungsfähigkeiten haben und daher auch unterschiedliche Auffassungen darüber haben, wann der Zeitpunkt zum Splitten gekommen ist.


Das Tangle entwirren

Da wir die Mechanismen einfach halten wollen und nicht noch einen weiteren Konsensmechanismus auf dem Tangle einführen wollen, müssen wir einen anderen Ansatz finden, um mit diesem Problem umzugehen.

Wenn wir uns die Shard-Markierungen anschauen und was es eigentlich “bedeutet”, für jeden Shard separate Untermarkierungen zu haben, dann erkennen wir ziemlich schnell, dass es uns genau einen Vorteil bringt: Die verarbeitenden Nodes, d.h. die roten Shards, haben einen Weg, nur die roten Transaktionen zu identifizieren, herunterzuladen und zu verarbeiten, ohne dass sie mit Transaktionen von anderen Shards verwirrt werden.

Wenn der einzige Zweck der getrennten Sub-Tangle darin besteht, zusammenhängende Transaktionen zu trennen, dann können wir dasselbe erreichen, indem wir die Tip-Auswahl auf folgende Weise modifizieren:

Wenn wir eine neue Transaktion mit einer Shard-Markierung X anhängen, dann wählen wir einen Tip als Zweig, der eine Splitter-Markierung Y hat, wobei Y ≤ X und einen Stamm, der eine Shard-Markierung Z hat, wobei Z ≥ X.

Was wir am Ende erhalten, ist ein DAG, welcher entsprechend der Markierungen im Tangle vorpartitioniert ist. Wenn wir dem referenzierten Zweig folgen, können wir Transaktionen mit einer gleichen oder kleineren Markierung entdecken, und wenn wir dem Stamm folgen, können wir Transaktionen mit einer gleichen oder höheren Markierung entdecken – siehe Bild (mit Farben anstelle von Zahlen für die Markierungen):

Auch wenn das Diagramm nicht mehr in verschiedene Zweige aufgeteilt ist, können wir immer noch Transaktionen, die gleiche Markierungen tragen, auf die gleiche Weise identifizieren, verifizieren und verfestigen, als ob sie tatsächlich aufgeteilt wären.

Wenn das Tangle verfestigt wird, hören die Nodes auf, die fehlenden Transaktionen abzufragen, sobald sie eine Markierung erreichen, an der sie nicht interessiert sind, und betrachten diese Transaktionen einfach als verfestigt. Da der “blaue Ledger-Zustand” nur von “blauen Transaktionen” betroffen sein wird, hat das Ignorieren der roten Transaktionen keine nachteiligen Auswirkungen auf einen blauen Node.


Fluid Sharding

Die beschriebene Art und Weise, das Tangle zu entwirren, befreit nicht nur von der Notwendigkeit, einen Konsens darüber zu erzielen, wann und wo gesplittet werden soll, sondern gibt den Nodes auch die völlige Freiheit zu wählen, an welchem Teil des resultierenden DAG sie interessiert sind und wie viel des DAG sie sehen und verarbeiten wollen, ohne dass sie ein vorgegebenes Sharding-Layout benötigen.

IoT-Bausteine mit beschränkten Ressourcen können einen geringeren Teil des DAG überwachen als leistungsfähigere Nodes. Die Shards sind daher nicht mehr isolierte Datenblöcke, sondern zusammenhängende Bereiche, wobei die Nodes in der Lage sind, verschiedene Teile je nach ihrem Interesse (Standort in der realen Welt) zu validieren – siehe Bild:

Die grünen Kästchen stellen Nodes dar, die unterschiedliche “Standorte” und unterschiedliche Beobachtungsradien haben.

Beispiel: Eine Person, die zwischen Ost- und West-Berlin lebt, könnte sich entscheiden, der Hälfte von Ost- und der Hälfte von West-Berlin zu “folgen”, während eine Person, die im Zentrum von West-Berlin lebt, stattdessen nur West-Berlin folgen könnte.

Wir sind auch in der Lage, durch Änderung des Beobachtungsradius die Größe der beobachteten Shards entsprechend den Durchsatzanforderungen im Netzwerk anzupassen.

Beispiel: Nodes in einer Region mit sehr geringer wirtschaftlicher Aktivität könnten es sich leisten, ein viel größeren “Schard” des DAG zu überwachen als Nodes, die in einem dicht besiedelten Gebiet mit vergleichsweise mehr Transaktionen operieren.

Durch die Verwendung einer Prioritätswarteschlange für die empfangenen Transaktionen – die die empfangenen Transaktionen nach ihrer Entfernung vom Standort eines Nodes im Netzwerk sortiert – verringern die Nodes automatisch ihren Beobachtungsradius, wenn sie überlastet werden, wodurch Transaktionen von zu weit entfernten Nodes herausgefiltert werden. Sie werden daher sofort auf unterschiedliche Durchsatzanforderungen reagieren, ohne dass sie ein neues Sharding-Layout neu aushandeln oder Gebühren verwenden müssen, um zu entscheiden, welche Transaktionen ausgeführt werden sollen. Die Lösung wird Agenten-zentriert (agent-centric) und ermöglicht es uns, sofort auf unterschiedliche Belastungen im Netzwerk zu reagieren.


Schlussfolgerung

Wir haben ein paar sehr einfache Änderungen an der Funktionsweise des Tangle vorgenommen. Diese Änderungen ermöglichen es uns, die Transaktionen in der DAG zu entwirren und sie nach ihrer Beteiligung an den entsprechenden Shards zu gruppieren.

Anstatt einfach viele Tangle parallel laufen zu lassen (wie Blockchains), erlaubt uns diese neue Art des Fluid Shardings, weiterhin ein großen durchgehenden Tangle zu verwenden, das sich über die ganze Welt erstreckt und immer noch in der Lage ist, eine beliebig große Anzahl von Transaktionen pro Sekunde zu verarbeiten.

Am Anfang, wenn die Adoption noch gering ist, werden die meisten Nodes höchstwahrscheinlich alle Transaktionen sehen und verarbeiten, aber sobald die Adoption wächst und die Durchsatzanforderungen die Verarbeitungskapazitäten der Nodes übersteigen, werden wir sehen, wie die Nodes ihren Beobachtungsradius langsam verringern, um die höhere Last zu bewältigen.

Im 3. Teil dieses Blogbeitrags, der demnächst veröffentlicht wird, werde ich erklären, wie Transaktionen zwischen entfernten Shards funktionieren werden und wie ein durchgehendes Tangle es uns ermöglicht, einen ähnlichen Mechanismus wie eine Beacon Chain zu implementieren, jedoch ohne Beacon Chain, wodurch eine echte “unendliche” Skalierbarkeit (mit der Anzahl der Nodes) freigegeben wird.

Quellen

https://medium.com/@hans_94488/scaling-iota-part-2-untangling-the-tangle-3a6ed2303b3c