Februar 18, 2019

Auf dem Tangle ausgeführt: Ein Marathon für zufällige Wanderer

Auf dem Tangle ausgeführt: Ein Marathon für zufällige Wanderer

Im heutigen Blog-Post werden wir uns die Reise von "zufälligen Wanderern" im Tangle genauer ansehen. Ähnlich wie in einem unserer vorherigen Beiträge zur Mischzeit im Tangle, sind wir daran interessiert zu verstehen, wie lange zufällige Wanderer laufen müssen, um einen Tip auszuwählen und - was noch wichtiger ist - wie lange es dauert, bis sie ihr Ziel erreichen. Für diese Analyse werden wir verschiedene Tangles simulieren, und für jedes werden wir 100.000 zufällige "Spaziergänger" ausgehend von der Genesis Transaktion freilassen und deren Geschwindigkeit messen, in der sie einen zufälligen Weg (Random Walk) auf dem Tangle durchführen. Dieser Artikel setzt ein grundlegendes Verständnis für den Aufbau des Tangles und die Wahrscheinlichkeitstheorie voraus, da wir uns mit Themen wie dem Parameter α (parameter α), direkten Genehmigern (direct approvers,) und Wahrscheinlichkeitsdichtefunktionen (probability density functions = PDF) beschäftigen. Wenn Sie mit diesen Themen nicht vertraut sind, empfehlen wir Ihnen, sich zuerst darüber zu informieren.

Wir beginnen damit zu definieren, was wir unter Geschwindigkeit genau verstehen. Betrachten Sie den Tangle mit N Transaktionen. Jeder Transaktion weisen wir eine ID in dem Netzwerk, gemäß dem Zeitpunkt der Ankündigung, zu. D. h. die Genesis-Transaktion hat die ID 1, die erste Transaktion die die Genesis genehmigt, hat die ID 2 und so weiter. Wir können davon ausgehen, dass diese Transaktionen jeweils zu den Zeitpunkten t_1 <t_2 <… <t_N an das Netzwerk gemeldet werden. Wir definieren die folgenden Mengen:

  • distance(x-y) = ID_y - ID_x
  • velocity(x-y) = distance(x-y) / steps

Grundsätzlich definieren wir den Abstand zwischen zwei Transaktionen x und y als die Anzahl der Transaktionen, die innerhalb des Intervalls zwischen t_x und t_y an das Netzwerk propagiert wurden. In ähnlicher Weise definieren wir die Geschwindigkeit eines zufälligen Wanderers, der von einer Transaktion x zu einer Transaktion y gewandert ist, als die vom Wanderer zurückgelegte Entfernung, geteilt durch die Gesamtzahl der Schritte die zum Abschluss dieses Übergangs erforderlich waren.

Um Ihnen eine grafische Darstellung dieser Konzepte zu ermöglichen, können wir uns dieses Beispiel ansehen:

Erstens erinnern wir uns daran, dass ein zufälliger Spaziergänger von der Vergangenheit in die Gegenwart geht, also durchquert er den Tangle in entgegengesetzter Richtung zu den Beziehungenpfeilen zwischen den Transaktionen. Hier beginnt unser "Random Walker" mit der Transaktion 1 und geht dann zur Transaktion 2 über. Während dieses Übergangs wird die zurückgelegte Entfernung durch Subtrahieren der ID der aktuellen Transaktion (2) von der ID der Starttransaktion (1) errechnet, also ist das Ergebnis 2 -1 = 1. Nach den nächsten Schritten können wir sehen, dass der "Random Walker" beim Übergang von Transaktion 2 zu 6 und von Transaktion 6 zu 7 eine Entfernung von 4 bzw. 1 zurücklegt hat. Somit beträgt die Geschwindigkeit unseres "Random Walkers" durchschnittlich 2 Transaktionen pro Schritt.

Hier ist ein anderes Beispiel.

Wie im vorherigen Beispiel beginnt unser Zufallsläufer seine Reise von der Transaktion mit der ID 1 und erreicht die Spitze mit der ID 7. Diesesmal wählt der Zufallsläufer jedoch einen anderen Pfad. Er durchquert den Tangle, indem er die Transaktionen 1, 3, 4, 5 und 7 durchläuft und eine Entfernung von 6 Transaktionen in 4 Schritten abdeckt. Damit hat er eine durchschnittliche Geschwindigkeit von 1,5 Transaktionen pro Schritt.

Nachdem wir wissen was wir unter Geschwindigkeit verstehen, können wir folgende Frage stellen: Wie groß ist die Wahrscheinlichkeit, dass ein zufälliger Spaziergänger eine bestimmte Geschwindigkeit hat? Intuitiv hängen sowohl die Entfernung als auch die Geschwindigkeit davon ab, welchen "direkten Genehmiger"(direct aprover) ein zufälliger Spaziergänger wählt, um den nächsten Übergang durchzuführen. Insbesondere wenn wir eine Transaktion x betrachten. Wir können seinen direkten Genehmiger nach seiner Ankunftszeit als 1. , 2. , 3. ,… und letzter Genehmiger sortieren, genau wie in diesem Beispiel:

Da der erste Genehmiger eine kleinere ID, als der letzte Genehmiger hat (dh der erste Genehmiger wurde vor dem letzten Genehmiger dem Netzwerk übergeben), werden sowohl die zurückgelegten Entfernungen als auch die Geschwindigkeiten unseres zufälligen Gehers kleiner sein, da der den Übergang x zum ersten Genehmiger kleiner ist, als der Übergang von x bis zum letzten Genehmiger.

Wir können diese Intuition durch einige Simulationen bestätigen. Der Einfachheit halber betrachten wir ein Tangle, das gemäß der einheitlichen Zufallsspitzenauswahl (uniform random tip selection = URTS) mit einer Ankunftsrate von λ = 100 gebaut wurde. Wenn unser Tangle eine Größe von 100.000 Transaktionen erreicht hat, setzen wir 100.000 "Random Walkers" los und messen deren Geschwindigkeit für folgende Varianten:

  1. Während er einen unbeeinflussten, zufälligen Gang durchführt (URW, d. h. ein zufälliger Gang mit Parameter α = 0);
  2. Während eines Laufs, der immer zum ersten direkten Genehmiger übergeht (untere Geschwindigkeitsgrenze);
  3. Während eines Laufs, der immer zum letzten direkten Genehmiger wechselt, sobald mehr als ein direkter Genehmiger vorhanden ist (d. h. wir verwerfen Transaktionen, die nur einen Genehmiger haben, andernfalls wäre das ein Übergang zum ersten Genehmiger) (obere Geschwindigkeitsgrenze);

Bei allen Transaktionen messen wir auch die Entfernung zwischen jeder Transaktion und ihren direkten Genehmigern. Anschließend zeichnen wir die Wahrscheinlichkeitsdichtefunktion (probability density function = PDF), die Sie in der folgenden Abbildung sehen können.

Hier zeigen wir das PDF der Geschwindigkeit. Datenpunkte wurden auf Transaktionseinheiten normiert (d.h. geteilt durch λ). Blaue und orangefarbene Linien sind gemessene Geschwindigkeiten, wenn Zufallsläufer immer zum ersten Genehmiger bzw. zum letzten Genehmiger vorrücken. Diese Kurven sind wichtig, weil sie eine untere und obere Geschwindigkeitsbegrenzung ergeben. Die grüne Kurve ist die Geschwindigkeit einer URW und ist die, die unsere vorherige Frage beantwortet. Zu guter Letzt ist die rot gestrichelte Linie die Entfernung zwischen den einzelnen Transaktionen und ihren direkten Genehmigern. Das gibt uns Informationen über die Struktur des Tangles. Genauer gesagt, zeigt es die Wahrscheinlichkeitsverteilung an, wie lang die Verbindungen sind, die zwei Transaktionen miteinander verbinden.

Wir haben gesehen, was die Geschwindigkeit eines Zufallsläufers bei einem unvoreingenommenen Spaziergang ist entsprechend α = 0. Jetzt werfen wir einen Blick auf die durchschnittlichen Geschwindigkeiten, der voreingenommenen "zufälligen Wanderern" für verschiedene Werte von α. Für dieses Experiment betrachten wir einige Tangle, die jeweils mit unterschiedlichen Werten für α und die eingehende Transaktion-Rate λ gebaut wurden. Wir messen dann die durchschnittliche Entfernung und Geschwindigkeit.

Hier können wir die durchschnittliche Entfernung (links) und die Geschwindigkeit (rechts) als Funktion von λ sehen. Die Diagramme zeigen die x-Achse im logarithmischen Maßstab. Der Durchschnitt von Entfernung und Geschwindigkeit nimmt ab, sobald die Werte für α und λ erhöht werden. Dieses Ergebnis hängt von dem Einfluss ab, den sowohl α als auch λ auf die Struktur des Tangles haben. Je größer der Parameter α ist, desto wahrscheinlicher werden zufällige Spaziergänger zu Transaktionen mit einem höheren kumulativen Gewicht. Wie in unserem Blogpost über direkte Genehmiger erörtert, führt eine Änderung von α außerdem zu einer Änderung der Anzahl direkter Genehmiger, was auf eine höhere Wahrscheinlichkeit von Verbindungen innerhalb einer kürzeren Entfernung schließen lässt. In ähnlicher Weise werden durch Erhöhen von λ mehr Transaktionen innerhalb derselben Zeiteinheit h angekündigt, was zu einer höheren Wahrscheinlichkeit führt, Verbindungen mit kürzeren Entfernungen herzustellen.

Zu wissen, wie lange und wie schnell (oder langsam) unsere zufälligen Wanderungen ablaufen, kann bei analytischen Näherungen des Parasitenkettenangriffs (parasite chain attack) sehr nützlich sein. Dies ist auch nützlich, wenn Sie den Tangle in Gruppen aufeinanderfolgender Transaktionen aufteilen, so dass jeder Random Walker ungefähr eine Transaktion in jedem Abschnitt durchläuft. Darüber hinaus kann es helfen, besser zu verstehen, wie der Rechenaufwand für die Ausführung von zufälligen Spaziergängen verteilt wird.

Mit diesem Thema beschäftigt sich derzeit unser Forschungsteam . Insbesondere interessieren wir uns für die folgenden Fragen:

  1. Können wir eine analytische Formel finden, die das PDF der Geschwindigkeit beschreibt?
  2. Wie ändert sich die Geschwindigkeit, wenn zufällige Spaziergänger in Rückwärtsrichtung gehen (d. H. Von der Gegenwart in die Vergangenheit)? Dies kann zum Beispiel nützlich sein, wenn der Fall eines zufälligen Spaziergangs betrachtet wird, in dem eine Transaktion eine bestimmte Bedingung nicht erfüllt.
  3. Gibt es eine Beziehung zwischen der der Geschwindigkeit und der Wahrscheinlichkeit, dass ein Tip zurückbleibt (d. H. zu einem permanenten Tip wird)?

Wir werden an diesen Fragen sowie an der Beziehung zwischen Geschwindigkeit und dem Angriff der Parasitenkette arbeiten. In der Zwischenzeit sind Sie alle herzlich eingeladen, Fragen zu stellen und dieses Themen hier oder in unserem Discord Channel zu diskutieren.


Quelle: https://blog.iota.org/running-on-the-tangle-a-marathon-of-random-walkers-99517d9b51a0