19. Mrz’20
Übersetzung des IOTA Blogartikel von Autor William Sanders und Luigi Vigneri, IOTA Foundation.
Dieser Artikel erklärt in einigen technischen Details den IOTA Congestion Control Algorithm (ICCA), der im IOTA 2.0 Protokoll (Coordicide) verwendet wird. Wir wollten diesen Überblick anbieten, um die Beziehung zwischen Zugang und Mana zu verdeutlichen, die in unserem vorherigen Beitrag über Mana angesprochen wurde. Außerdem sind wir uns bewusst, dass viele begierig sind, mehr über Coordicide zu erfahren, und dass Interessenvertreter aus dem gesamten IOTA-Umfeld von diesem Wissen profitieren. Das heißt, die in diesem Artikel enthaltenen Informationen sind kein “erforderliches Wissen”, um IOTA zu nutzen. Außerdem werden alle Aspekte, die in diesem Artikel besprochen werden, Teil unserer vollständigen Spezifikation sein. Wenn Sie Fragen haben, besuchen Sie bitte unseren Discord, um sie mit unseren Entwicklern und Forschern zu diskutieren. Die Congestion Control (dt. Überlastungskontolle) ist ein wichtiger und faszinierender Aspekt von Coordicide, daher hoffen wir, dass Sie diese Erklärung genießen.
Unser besonderer Dank gilt Bob Shorten und seinem Team am Imperial College London für ihre Arbeit bei der Mitentwicklung dieses wichtigen Algorithmus. Ihre Arbeit hat maßgeblich zur Entwicklung dieser wichtigen Komponente und zur Validierung ihres Betriebsverhaltens beigetragen.
Eine ausführliche Erklärung finden Sie in unserem ersten Artikel zu diesem Thema, der zur Präsentation auf dem 7th IEEE/IFIP Workshop on Security for Emerging Distributed Network Technologies angenommen wurde.
Was ist die Congestion Control (dt. Überlastungskontrolle) und warum benötigen wir sie?
In den meisten DLTs werden Informationen über das Netzwerk durch einen Prozess namens “Gossiping” weitergegeben (geklatscht), bei dem die teilnehmenden Nodes Messages von einem Nachbarn erhalten und diese dann an andere Nachbarn weiterleiten. Natürlich erhalten die Nodes viele Messages, so dass sie entscheiden müssen, welche dieser Messages sie an ihre Nachbarn weiterleiten und in welcher Reihenfolge sie dies tun. Ein Algorithmus zur Überlastungskontrolle trifft diese Entscheidungen.
Eine Überlastung tritt auf, wenn ein Netzwerk mehr Datenverkehr hat, als es bewältigen kann. Ohne eine angemessene Überlastungskontrolle kann das Netzwerk übersättigt werden und nicht mehr funktionieren, da die Nodes ihre Nachbarn mit mehr Messages überfluten können, als von einer einzelnen Node verarbeitet werden können. Durch die Entscheidung, welche Messages weitergeleitet werden sollen, wird ein Congestion Control-Algorithmus eingesetzt, um diese Überlastung zu verhindern. In einem unsharded DLT ist das Problem besonders akut, da jeder Netzwerkteilnehmer (“Node”) alle gültigen Transaktionen verarbeiten muss. Daher ist der Gesamtdurchsatz des Netzwerks (informell als Transaktionen pro Sekunde bezeichnet) letztlich durch die verfügbaren Ressourcen wie Internetanbindung, Geräteverarbeitung und Speicherkapazitäten begrenzt.
Da jedoch ein Congestion-Control-Algorithmus entscheidet, welche Messages weiter gesendet (geklatscht) werden, bestimmt er im Wesentlichen, wer Zugang zum Netzwerk hat; der Congestion-Control-Algorithmus hat einen tiefgreifenden Einfluss auf das Benutzererlebnis. Zu erklärung von”Coordicide”, möchten die Autoren den ICCA erklären, das im IOTA 2.0-Protokoll (Coordicide) verwendet wird.
Congestion Control ist ein sehr altes Thema, das intensiv untersucht wurde, als die Infrastruktur des Internets entwickelt wurde. Im Gegensatz zu den meisten Netzwerken haben DLTs jedoch sehr strenge Anforderungen, die die Congestion Control zu einem besonders schwierig zu lösenden Problem machen. Insbesondere müssen die folgenden Anforderungen erfüllt werden (es gibt noch weitere Anforderungen, auf die wir weiter unten näher eingehen, aber diese sind die wichtigsten):
- Fairer Zugang: der Netzwerkzugang muss proportional zu einer “knappen Ressource” gewährt werden
- Angriffsresistenz: böswillige Nodes können das Netzwerk nicht stören
- Konsistenz: alle Nodes müssen die gleichen Messages in ihr lokales Ledger schreiben
Blockchains lösen die Überlastungskontrolle, indem sie einige Mechanismen verwenden, um Anführer zu wählen, die Blöcke minen. Der Zugang ist fair, da die Rate, mit der ein Anführer gewählt wird, proportional zu seinem Einsatz oder seiner Hashing-Power ist. Da der Zugang nur auf die Anführer beschränkt ist, ist eine Überlastung nie möglich, auch nicht während eines Angriffs. Letztendlich wird ein Konsens erreicht, da Blockchains ein Konsensmodul haben, um einen Anführer zu wählen. Die Beschränkung des Zugriffs auf “Anführer” macht es für PoS- und PoW-Architekturen einfacher, zentralisiert aber den Zugang.
Da IOTA eine DAG und keine Blockchain verwendet, können (und wollen) wir keine Art von Anführer-Wahlprozess verwenden. Stattdessen verwendet der ICCA einen sogenannten Scheduler, der Messages auswählt, die “planmäßig” sind. Geplante Messages werden in den lokalen Tangle geschrieben und an die Nachbarn des Node weitergeleitet. Der Scheduler plant Messages mit einer konstanten Rate ein, wodurch sichergestellt wird, dass keiner der Nachbarn überlastet wird.
Nun können wir erörtern, wie der ICCA unsere drei oben genannten Hauptanforderungen – fairer Zugriff, Angriffsresistenz und Konsistenz – erreicht. Zunächst können wir sehen, dass jede Node lokal den Verkehr fair nach Mana plant. Es stellt sich heraus, dass dies auch global gilt und dass der Zugang fair nach Mana vergeben wird.
Was passiert, wenn ein Angreifer versucht, das Netzwerk zu spammen? Lokal verarbeiten Nodes die Messages des Angreifers nicht schneller als die zulässige Rate. Die Messages des Angreifers häufen sich und die Warteschlange wächst. Alle Nodes werden dies erkennen und den Angreifer aus dem Netzwerk verbannen. Natürlich gibt es zahlreiche andere Angriffsmethoden, die wir untersucht haben, aber der Scheduler ist schwer auszutricksen, so dass der Algorithmus recht widerstandsfähig gegen Angreifer ist.
Da der Scheduler niemals ehrliche Messages löscht, stellt der Algorithmus sicher, dass sie schließlich alle Nodes erreichen. Was passiert mit den von ihm ausgegebenen Messages, wenn ein Angreifer aus dem Netzwerk verbannt wird? Da das Verhalten des Angreifers erkennbar ist, werden die meisten Nodes den Angreifer gleichzeitig verbannen, um sicherzustellen, dass die Ledger nahezu identisch sind. Dann verfügt das Gossip-Protokoll über einen Mechanismus namens “Solidification”, der winzige Unterschiede in den Tangles korrigieren kann.
Im Folgenden finden Sie einen technischeren Überblick über den ICCA, da eine tiefere Analyse der Anforderungen präsentiert wird.
Anforderungen für jede DLT
Es gibt einige allgemeine Anforderungen und einige davon sind entscheidend für den Erfolg eines jeden DLT-Congestion-Control-Algorithmus: Konsistenz, fairer Zugriff, Auslastung, faire Latenzzeit und Angriffsresistenz.
Konsistenz
Konsistenz bedeutet, dass jede Node die exakt gleichen Messages in den Ledger schreibt. Wenn das Netzwerk überlastet ist, sind die Nodes möglicherweise gezwungen, einige Messages zu verwerfen, was zu Inkonsistenzen führt. Das Ziel des ICCA ist es, das Verwerfen von Messages auf ein Minimum zu reduzieren und die verbleibenden Inkonsistenzen durch Solidification Requests zu beheben. Ohne dies gibt es keinen Konsens.
Fairer Zugriff
Da die verfügbaren Netzwerkressourcen endlich sind, muss der Zugriff (äquivalent dazu der Durchsatz) in irgendeiner Weise eingeschränkt werden. In DLTs wird dies üblicherweise durch die Beschränkung des Zugangs durch eine “knappe Ressource” gewährleistet. Viele DLTs nutzen Energie als knappe Ressource, indem sie von Minern verlangen, PoW zu betreiben. Proof-of-Stake-DLTs verwenden oft den Token selbst als knappe Ressource; IOTA verwendet Mana (siehe Mana-Artikel).
Fairer Zugang bedeutet, dass alle Nodes einen fairen Anteil des Durchsatzes erhalten sollten. Es ist wichtig zu beachten, dass dieser Zugang linear proportional zur Menge des Manas sein muss: Wenn der Zugang sublinear vergeben wird – also immer weniger Zugang mit mehr Mana – dann werden große Akteure ihr Mana auf kleinere Nodes aufteilen, um unfairen Zugang zu erhalten. Wenn es superlinear ist – also mehr Zugang mit mehr Mana gewährt wird – dann haben große Inhaber einen Vorteil. Dies schafft Anreize für Nodes, ihre Ressourcen zu bündeln, wie bei Mining-Pools. Sowohl sublineare als auch superlineare Zugangsvergaben sind im Allgemeinen unfair und fördern ein Verhalten, das dem Netzwerk langfristig schaden könnte.
Auslastung
Wenn es eine Nachfrage gibt, wird das volle Potenzial des Netzwerks genutzt.
Denken Sie zum Beispiel an eine triviale Zugangskontrolle, bei der der Durchsatz jeder Node durch seinen prozentualen Mana-Anteil gedeckelt ist, sagen wir 10% Mana erlauben einem Benutzer maximal 10% der Bandbreite. Das wäre zwar fair, aber ineffizient: Wenn z.B. 95% des Manas offline sind, dann würde das Netzwerk mit 5% Kapazität arbeiten. Ein effizienter Mechanismus zur Überlastungskontrolle muss diese ungenutzte Kapazität umfunktionieren.
Die Kombination von Auslastung und Fairness ist kompliziert. Die Frage “Wie viel Mana brauche ich für X TPS” ist schwer zu beantworten. Aber denken Sie daran: Auslastung ist eine gute Sache! Ohne sie wäre das Netzwerk unbrauchbar.
Auslastung und Fairness bilden zusammen ein Konzept namens “Max-min-Fairness”. Dies ist ein wichtiges Konzept aus der klassischen Netzwerktechnik. Router, die Internet-Verkehr weiterleiten, brauchen genau diese Eigenschaften (stellen Sie sich vor, wenn Ihre lokalen Router diese Eigenschaften nicht hätten, wäre Ihr Heim-Internet unbrauchbar).
Faire Latenzzeit
Alle ehrlichen Benutzer sollten eine ähnliche Latenzzeit erfahren. Die Latenz ist die Zeit, die eine ausgegebene Message benötigt, um sich an alle Nodes zu verbreiten. Diese Latenzzeit muss sowohl für ein gutes Benutzererlebnis als auch für die Stabilität des Protokolls gering sein.
Die Benutzererfahrung sollte für sich selbst sprechen; niemand mag Verzögerungen. Für die Stabilität des Protokolls wäre es jedoch ein perverser Anreiz, vom Algorithmus abzuweichen, wenn die Latenzzeit für verschiedene Benutzer dramatisch unterschiedlich wäre. Die Bestrafung der Latenz von böswilligen Nodes ist aus spieltheoretischer Sicht gut. Wenn sich die Latenz der Nodes bei schlechtem Verhalten erhöhen würde, würden sie bestraft und daher zum guten Verhalten ermutigt.
Angriffsresistent
Diese oben genannten Eigenschaften müssen für ehrliche Nodes auch dann gelten, wenn ein Angreifer versucht, das System zu knacken. Die Nodes haben einen Anreiz, ihren Zugang zu erhöhen und ihre Latenzzeit zu verringern. Abweichungen sollten unmöglich sein oder bestraft werden.
IOTA Congestion Control Algorithmus (ICCA)
Der IOTA Congestion Control Algorithm (ICCA) rationalisiert den Transaktionsprozess, um die Auswirkungen einer möglichen Überlastung zu minimieren und den Schreibzugriff auf den Ledger zu regulieren. Der ICCA erreicht dies durch seine drei Teile: den Scheduler, den Rate Setter und den Blacklister.
Der Scheduler bestimmt, welche Transaktionen in den Ledger geschrieben und geklatscht werden. Der Rate Setter verwendet einen klassischen AIMD-Algorithmus (Additive Increase Multiplicative Decrease), um die Rate jedes Einzelnen anzupassen. Blacklisting zensiert Nodes, die das Netzwerk angreifen.
Dies ist – soweit wir wissen – der erste nicht Proof of Work, DAG-basierte Congestion Control Algorithmus, der im Bereich der Kryptowährungen veröffentlicht wurde. Er ist die neuartigste Komponente von Coordicide und ein Grundpfeiler des IOTA 2.0 Protokolls.
Von dem Netzwerk-Layer (siehe diesen Link zur Terminologie) kommen Messages über das Gossip-Protokoll von den Nachbarn an, werden auf Duplikate und ungültige Messages gefiltert und kommen im Posteingang an, wo sie sich in die Warteschlange gemäß der ausstellenden Node-ID einreihen. Der Posteingang empfängt auch Messages, die lokal vom Raten Setter der Node erstellt wurden. Der Blacklister überwacht die Warteschlangen des Posteingangs auf böswilliges Verhalten, und der Scheduler entscheidet, welche Messages den Posteingang verlassen dürfen. Nachdem eine Message eingeplant wurde, finden die folgenden Aufgaben gleichzeitig statt:
- Die Message wird an alle Nachbarn außer dem, von dem wir sie erhalten haben, gesendet (an die Netzwerkschicht zurückgegeben)
- Die entsprechende Anwendung (aus dem Applikations-Layer) wird aufgerufen, um die Nutzlast zu parsen
- Die Message wird in den lokalen Tangle “geschrieben”, wo sie als Tip betrachtet werden kann, von FPC abgestimmt wird, im Ledger verbucht wird, usw.
Scheduler
In dem ICCA schlagen wir die Verwendung einer modifizierten Version eines Deficit Round Robin-Schedulers vor. Abgesehen von der Tatsache, dass ein solcher Scheduler alle oben genannten Anforderungen erfüllt (d. h. Konsistenz, Auslastung, Fairness und Angriffsresistenz), haben wir uns für ihn entschieden, weil er leichtgewichtig ist. Er ist zum Beispiel die Standardoption, um eine sehr große Anzahl von Threads für den Linux-Kernel effizient zu handhaben.
Der Scheduler funktioniert folgendermaßen: Nachdem Messages empfangen wurden, werden sie im Posteingang abgelegt. Jeder Message wird eine “Arbeitsbewertung” zugewiesen, die darauf basiert, wie viele Ressourcen sie verbraucht. Größere Messages haben größere Punktzahlen, da sie mehr Bandbreite verbrauchen. Eine Message mit einer Transaktion, die 100 Signaturen enthält, hat eine höhere Punktzahl als eine Transaktion mit nur einer Signatur, da die Validierung der Signaturen mehr Ressourcen erfordert. Im Wesentlichen sorgt der Scheduler dafür, dass eine maximale Anzahl von Ressourcen pro Sekunde verbraucht wird. Die Forscher und Ingenieure, die dies entwickeln, haben völlige Freiheit, diese Arbeitsfunktion zu definieren, um den Algorithmus genau an die Bedürfnisse des IOTA-Netzwerks anzupassen.
Wenn Messages empfangen werden, werden sie von ihrer abgebenden Node in verschiedene Warteschlangen sortiert. Der Scheduler besucht jede Warteschlange, plant eine Anzahl von Messages basierend auf dem Mana (die “knappe Ressource”, die in IOTA verwendet wird), das die ausstellende Node besitzt, und geht dann zur nächsten Warteschlange über. Wenn eine Warteschlange leer ist, wird sie übersprungen; der Scheduler plant dann aus anderen Warteschlangen. Auf diese Weise werden die Messages aller Nodes proportional zu ihrem Mana verarbeitet, solange ihre Warteschlange nicht leer wird.
Der Posteingang der Nodes ist in Warteschlangen unterteilt, mit einer Warteschlange für jede Node im Netzwerk. Ein Defizit-Round-Robin-Scheduler kann Zehntausende von Warteschlangen effizient verarbeiten. Messages werden dann in die Warteschlange des Nodes gestellt, der die Message ausgegeben hat. Der Scheduler besucht jede nicht leere Warteschlange in einer deterministischen Reihenfolge. Jeder Warteschlange wird dieser Node eine Menge zugewiesen, die als “Guthaben” bezeichnet wird. Wenn der Scheduler eine Warteschlange besucht, fügt er proportional zum Mana der entsprechenden Knoten-ID einen bestimmten Prioritätswert hinzu. Anschließend werden Messages aus der Warteschlange dieser Node geplant. Jedes Mal, wenn eine Message geplant und weiterverarbeitet wird, wird die „Arbeitsbewertung“ der Messaget vom Guthaben abgezogen. Wenn keine Messages mehr aus der Warteschlange von N geplant werden können oder das Guthaben negativ wird, wechselt der Scheduler zur nächsten Warteschlange.
Derzeit planen wir Messages mit einer festen/maximalen voreingestellten Rate. Zurzeit analysieren und untersuchen wir verschiedene Möglichkeiten, diesen Schwellenwert dynamisch zu gestalten, so dass das Netzwerk durch Sharding natürlich skaliert werden kann.
Aber was passiert, wenn ein Angreifer oder ein egoistischer Node sich nicht an die Regeln des Schedulers hält? Nehmen wir an, dass eine egoistischer Node beschließt, nur seine eigenen Transaktionen weiterzuleiten. Das würde dazu führen, dass die entsprechende Warteschlange in den Posteingangspuffern der ehrlichen Nodes aufgebläht wird, was zu großen Verzögerungen nur für seine eigenen Transaktionen führt. Das Gleiche gilt für böswillige Nodes: Solange ehrliche Nodes dem defizitären Round-Robin-Scheduler folgen, würden Transaktionen von Angreifern nicht weitergeleitet werden.
Rate Setter
Woher weiß eine Node, wie viele Messages ausgeben werden können? Sie verwendet den Rate Setter. Basierend auf der Warteschlangenlänge verwendet der Rate Setter den AIMD-Algorithmus, um seine eigene Transaktionserzeugungsrate zu regulieren. Ein ähnlicher Algorithmus wird von Routern im Internet verwendet, um den Datenverkehr anzupassen.
Eine Node kann die Länge seiner eigenen Warteschlange überwachen. Wenn diese Warteschlange zu lang wird, weiß sie, dass zu viele Messages ausgegeben werden. Eine Node erhöht seine Ausgaberate langsam (Additive Erhöhung), bis seine Warteschlange zu lang wird. An diesem Punkt verringert die Node schnell seine Ausgaberate (Multiplikative Verringerung), um eine bevorstehende Überlastung zu verhindern. Auf diese Weise konvergiert der Rate Setter schließlich zu einer fairen Ausgaberate, abhängig von den aktuellen Datenverkehrsbedingungen.
Als zusätzlicher Vorteil sorgt der Rate Setter dafür, dass die Latenzzeit für Transaktionen, die von Nodes ausgegeben werden, die dem Protokoll folgen, gering ist. Nodes, die diesem Algorithmus nicht folgen, überfluten ihre Warteschlangen und erhöhen ihre Latenz. Auf diese Weise erhalten die Nodes einen Anreiz, den Rate Setter zu verwenden.
Was passiert, wenn böswillige Nodes den Rate Setter nicht verwenden? Was ist, wenn sie sich nicht um die Erhöhung der Latenz kümmern, z. B. bei einem Spam-Angriff? Die folgenden Abschnitte enthalten Sicherheitsmaßnahmen, die wir eingerichtet haben und die ausgelöst werden, bevor ein Angreifer der Konsistenz schaden kann.
Blacklisting
Was passiert, wenn die Node den Rate Setter nicht verwendet? Dann wird er seine Rate nicht reduzieren, wenn seine Warteschlange wächst, und so wird seine Warteschlange weiter wachsen. Da die anderen ehrlichen Nodes nur so viel Speicher haben, kann keine Warteschlange unendlich wachsen. Daher hat der ICCA den Blacklister, um die Länge der Warteschlangen zu begrenzen. Je nach Mana darf ein Node eine bestimmte Anzahl von Messages in der Warteschlange haben. Wenn diese Anzahl einen bestimmten Schwellenwert überschreitet, wird die Node vorübergehend auf eine schwarze Liste gesetzt, was bedeutet, dass für eine gewisse Zeit keine weiteren Transaktionen von diesem Node in den Posteingang aufgenommen werden. Wenn die Warteschlange einer Node zu explodieren beginnt, werden die neu eingehenden Messages für diese Node verworfen.
Rate-Control
Ein Angreifer kann versuchen, das Netzwerk mit großen Mengen an Spam zu überfluten, indem er direkt versucht, Hunderte von Nodes auf einmal zu überlasten. Zum Schutz vor solchen Angriffen verwenden wir einen Mechanismus namens Rate-Control (dt. Ratenkontrolle) als grobe Unterbrechung, der die Menge der Messages, die eine Node senden kann, physikalisch begrenzt. Dazu verwenden wir ein adaptives PoW als Ratenkontrollmechanismus. Für ehrliche Nodes ist die PoW-Schwierigkeit relativ gering. Wenn eine Node jedoch anfängt zu spammen, steigt die Schwierigkeit exponentiell an, was die Node physisch daran hindert, mehr Messages zu versenden. Dieser Mechanismus würde also verhindern, dass das System komplett überlastet wird.
So nützlich der Mechanismus zur Ratenkontrolle auch ist, er ist möglicherweise nicht notwendig. Das ICCA hat das Potenzial, so stark zu sein, dass dieses Modul überflüssig ist. In der ersten Version des Coordicide-Protokolls wollen wir jedoch den maximalen Schutz gewährleisten, und eine eventuelle spätere Verringerung oder Entfernung jeglicher PoW bleibt als zukünftige Optimierung übrig. Im GoShimmer-Testnetz werden wir das Zusammenspiel zwischen der adaptiven PoW-Ratensteuerung und dem ICCA untersuchen.
Null-Mana-Messages
Leider erfordert das ICCA, dass Nodes ein gewisses Mana haben müssen, um Messages ausgeben zu können, denn Nodes mit 0 Mana erhalten niemals Guthaben und ohne Guthaben werden ihre Messages nicht eingeplant. Dies ist wichtig, um billige Angriffe zu vermeiden: Ohne dies könnten Nodes mit niedrigem Mana einen Ansturm von Transaktionen erzeugen, wodurch das Netzwerk überlastet und die Konsistenz des Ledgers beeinträchtigt wird.
Wir können verschiedene Optionen anbieten, damit Null-Mana-Nodes in der Lage sind, ihre Transaktionen auszugeben. Eine Möglichkeit ist über einen Faucet, bei dem jede Node freiwillig sein ungenutztes Mana neuen Benutzern anbieten kann, die das Netzwerk ausprobieren wollen, für welchen Anwendungsfall auch immer sie im Sinn haben. Eine andere Möglichkeit ist die Nutzung des Mana-Marktes, auf dem man selbst bestimmen kann, wie und wann man Mana nach Bedarf mieten möchte. Eine weitere Methode besteht darin, Token zu kaufen und sie durch Verpfändung an die Nodes zu transferieren.
Schließlich untersuchen wir eine Möglichkeit, die minimale Mana-Schwelle dynamisch anzupassen, abhängig vom Prozentsatz des aktiven Manas und von den aktuellen Datenverkehrsbedingungen.
In Zeiten mit geringer Überlastung dürfen “validierte Low-Mana-Nodes” ihre Transaktionen ausgeben und werden von ehrlichen Nodes eingeplant. Ein “validierter Low-Mana-Node” ist eine Node, der die folgenden zwei Bedingungen erfüllt: Erstens, sein Mana ist kleiner als der minimale Mana-Schwellenwert; und zweitens, die Node hat kürzlich einen großen PoW durchgeführt. Wenn die Überlastung gering ist, lassen ehrliche Nodes vorübergehend Planungen von diesen validierten Low-Mana-Nodes zu. Sobald die Überlastung groß wird, können validierte Low-Mana-Nodes ihre Transaktionen nicht mehr ausgeben; sie müssen auf Zeiten mit geringer Überlastung warten.
Quellen
https://blog.iota.org/explaining-the-iota-congestion-control-algorithm/