Fluid limit of a distributed ledger model with random delay

Diese Arbeit analysiert ein DAG-Modell für verteilte Ledger mit zufälligen Verzögerungen, indem sie unter der Annahme unendlicher Ankunftsrate eine Fluid-Limit-Näherung durch verzögerte partielle Differentialgleichungen herleitet, die das asymptotische Verhalten und den stabilen Zustand des Systems beschreibt.

Das Wesentliche

Hier ist eine einfache Erklärung der Forschung von Feng und King, die sich mit der Mathematik hinter verteilten Ledger-Systemen (wie Blockchain oder IOTA) befasst, aber ohne komplizierte Formeln auskommt.

Das große Bild: Ein digitales Kassenbuch ohne Chef

Stellen Sie sich ein riesiges, digitales Kassenbuch vor, das nicht von einer Bank oder einer Firma geführt wird, sondern von Millionen von Menschen auf der ganzen Welt gemeinsam. Jeder kann Einträge machen, aber niemand darf etwas fälschen. Das nennt man ein Distributed Ledger (verteiltes Hauptbuch).

In der klassischen Blockchain (wie Bitcoin) ist dieses Buch wie eine lange Kette von Blöcken. Jeder neue Block hängt nur an den vorherigen. Das ist sicher, aber langsam, wie ein einziger Kassenbuchführer, der alle Transaktionen nacheinander abhaken muss.

Neuere Systeme wie IOTA nutzen jedoch eine DAG (gerichteter azyklischer Graph). Stellen Sie sich das nicht als Kette vor, sondern als ein riesiges, wachsendes Spinnennetz. Jeder neue Eintrag (ein "Block") verbindet sich mit mehreren vorherigen Einträgen. Das macht das System schneller und flexibler.

Das Problem: Der "Beweis der Arbeit" (POW) und die Verzögerung

Damit niemand das Buch manipuliert, muss jeder, der einen neuen Eintrag macht, zuerst eine kleine Rechenaufgabe lösen. Das nennt man Proof of Work (POW).

• Die Analogie: Stellen Sie sich vor, Sie wollen einen Brief in das Kassenbuch eintragen. Bevor Sie ihn abgeben können, müssen Sie erst ein kleines Rätsel lösen.
• Das Problem: Während Sie das Rätsel lösen, ist Ihr Eintrag noch nicht "sichtbar" für das Netz. Er hängt in der Luft. Erst wenn das Rätsel gelöst ist, wird er fest mit dem Netz verbunden.

In der echten Welt dauert das Lösen eines Rätsels nicht immer gleich lang. Manchmal ist es schnell, manchmal dauert es länger. Diese zufällige Verzögerung macht die Mathematik extrem schwierig.

Was haben die Forscher gemacht? (Der "Flüssigkeits-Test")

Die Forscher Feng und King wollten verstehen: Wie schnell wächst dieses Netz? Wie viele "offene" Einträge (die noch nicht bestätigt sind) gibt es zu einem bestimmten Zeitpunkt?

Wenn man versucht, jedes einzelne Rätsel und jede einzelne Person im Netz zu simulieren, wird der Computer verrückt, weil es zu viele Daten sind. Also haben die Forscher einen cleveren Trick angewendet: Sie haben das System wie eine flüssige Masse betrachtet, nicht wie einzelne Sandkörner.

Die Analogie des Wasserbeckens:
Stellen Sie sich das Netzwerk als ein großes Becken vor, in das Wasser (neue Einträge) hineingegossen wird.

1. Zufluss: Wasser fließt rein (neue Transaktionen).
2. Abfluss: Wasser fließt raus, wenn die Rätsel gelöst sind und die Einträge bestätigt wurden.
3. Der "Flüssigkeits-Limit": Anstatt zu zählen, wie viele Tropfen (Einträge) genau wann reinkommen, schauen die Forscher auf den Wasserstand. Sie haben mathematische Gleichungen aufgestellt, die beschreiben, wie sich der Wasserstand im Laufe der Zeit verändert, wenn das System sehr groß wird.

Diese Gleichungen sind wie eine Wettervorhersage für das Netzwerk. Sie sagen voraus, ob das Netz stabil bleibt oder ob sich zu viele unbestätigte Einträge (Wasser) stauen, was das System verlangsamen würde.

Die wichtigsten Erkenntnisse

1. Stabilität trotz Chaos: Auch wenn die Zeit, die zum Lösen der Rätsel benötigt wird, zufällig ist (manchmal kurz, manchmal lang), findet das System einen stabilen Zustand. Es pendelt sich ein.
2. Die "Spitzen" (Tips): In diesem Netz gibt es "Spitzen" – das sind die neuesten Einträge, die noch nicht von anderen bestätigt wurden. Die Forscher haben gezeigt, wie man die Anzahl dieser Spitzen vorhersagen kann.
   • Warum ist das wichtig? Wenn es zu viele Spitzen gibt, dauert es lange, bis eine Transaktion als "sicher" gilt. Wenn es zu wenige gibt, ist das Netz vielleicht nicht effizient genug.
3. Die Vorhersage stimmt: Die Forscher haben ihre mathematischen Vorhersagen (die "Flüssigkeits-Modelle") mit Computer-Simulationen verglichen. Das Ergebnis: Die einfache mathematische Vorhersage passt fast perfekt zu den komplexen Simulationen.

Warum ist das für uns wichtig?

Diese Arbeit ist wie eine Gebrauchsanleitung für die Zukunft.

• Sie hilft Ingenieuren zu verstehen, wie sie solche Netzwerke (wie IOTA) so bauen können, dass sie auch bei Millionen von Nutzern schnell und sicher bleiben.
• Sie zeigt, wie man das System so einstellt, dass Betrug (z. B. doppeltes Ausgeben von Geld) extrem unwahrscheinlich wird, selbst wenn die Rechenzeiten variieren.

Zusammenfassend: Die Autoren haben ein kompliziertes, chaotisches mathematisches Problem (ein wachsendes Spinnennetz mit zufälligen Verzögerungen) in eine saubere, vorhersagbare Flüssigkeit verwandelt. Damit können sie sagen: "Wenn wir die Parameter so einstellen, bleibt das System stabil und sicher." Das ist ein riesiger Schritt, um vertrauenswürdige digitale Systeme für die Zukunft zu bauen.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Fluid limit of a Distributed Ledger Model with Random Delay" von J. Feng und C. King auf Deutsch.

1. Problemstellung und Motivation

Das Paper befasst sich mit der mathematischen Analyse von Distributed Ledgers (DL), insbesondere von Systemen, die auf gerichteten azyklischen Graphen (DAG) basieren, wie z. B. IOTA (Tangle). Im Gegensatz zu Blockchain-Systemen, die eine lineare Kettenstruktur verwenden, erlauben DAGs, dass neue Blöcke (Vertices) parallel an mehrere existierende Blöcke angehängt werden.

Das zentrale Problem:
Die Dynamik solcher Systeme wird durch den Proof-of-Work (PoW)-Mechanismus und die damit verbundene Verzögerung beeinflusst. Wenn ein neuer Vertex erstellt wird, muss er einen PoW lösen, bevor er an den DAG angehängt werden kann.

• In früheren Modellen (z. B. [14]) wurde oft eine feste Dauer für den PoW angenommen.
• In der Realität ist die Dauer jedoch zufällig (stochastisch).
• Zudem können in realen Szenarien mehrere Transaktionen gleichzeitig eintreffen (Batch-Arrivals).

Die Herausforderung besteht darin, das asymptotische Verhalten des Systems zu verstehen, wenn die Ankunftsrate gegen Unendlich geht. Ein kritischer Sicherheitsaspekt ist die Anzahl der „Tips" (Blöcke, die noch nicht von zukünftigen Blöcken bestätigt wurden). Die Zeit, die ein Block benötigt, um bestätigt zu werden, hängt direkt von der Anzahl der Tips ab. Das Ziel ist es, eine deterministische Näherung (Fluid Limit) für das stochastische System unter Berücksichtigung zufälliger PoW-Dauern und simultaner Ankünfte zu finden.

2. Methodik

Die Autoren entwickeln ein mathematisches Modell und leiten daraus ein Fluid Limit (Flüssigkeitsgrenzwert) ab, das das Systemverhalten im Grenzfall beschreibt.

Modellannahmen:

• Zeitdiskretisierung: Die Zeit wird in Schritten $\epsilon$ diskretisiert. In jedem Schritt $t_n = n\epsilon$ kommen $N$ neue Vertices gleichzeitig an.
• Ankunftsrate: $\lambda = N/\epsilon$. Der Grenzwert wird betrachtet, wenn $\lambda, N, \epsilon^{-1} \to \infty$.
• PoW-Dauer: Jeder Vertex wählt unabhängig eine PoW-Dauer $h_i$ aus einer endlichen Menge $\{h_1, ..., h_M\}$ mit Wahrscheinlichkeit $p_i$. Dies modelliert eine multinomiale Verteilung.
• Parent-Selektion: Jeder neue Vertex wählt zwei Eltern (Parents) zufällig und gleichverteilt aus der Menge der aktuellen „Tips" (mit Zurücklegen).
• Zustandsvariablen:
  • $L(t)$: Gesamtzahl der Tips.
  • $F(t)$: Anzahl der „freien" Tips (noch nicht als Parent ausgewählt).
  • $W(t, u)$: Anzahl der „ausstehenden" Tips (pending tips), die als Parent ausgewählt wurden, aber noch ihren PoW abschließen müssen. Hier wird zusätzlich nach der Restlebensdauer (Residual Lifetime, RLT) $u$ und dem Typ $i$ (PoW-Dauer) differenziert.

Herleitung des Fluid Limits:

1. Update-Regeln: Zuerst werden stochastische Differenzengleichungen für die diskreten Variablen $F(t_n)$, $L(t_n)$ und $W(t_n, u)$ aufgestellt. Diese berücksichtigen das Ankommen neuer Blöcke, das Abschließen von PoWs und das Auswählen von Parents.
2. Erwartungswerte: Die Autoren betrachten die Erwartungswerte der Änderungen und behalten nur die führenden Terme (Leading Order Terms) bei, während sie Terme höherer Ordnung vernachlässigen.
3. Skalierung: Die Variablen werden skaliert ($f(t) = F(t)/\lambda$, $l(t) = L(t)/\lambda$, $w_i(t, u) = W_i(t, u)/N$).
4. Grenzübergang: Durch den Grenzübergang $\epsilon \to 0$ werden die Differenzengleichungen in ein System von verzögerten partiellen Differentialgleichungen (Delayed PDEs) umgewandelt.

Das resultierende System besteht aus:

• Einer ODE für die freie Tips-Dichte $f(t)$.
• Einer PDE mit Verzögerungen für die Gesamt-Tip-Dichte $l(t)$.
• Einer Transportgleichung mit Quelltermen für die Dichte der ausstehenden Tips $w_i(t, u)$ in Abhängigkeit von der Restlebensdauer.

3. Wichtige Beiträge

1. Erweiterung auf zufällige PoW-Dauern: Im Gegensatz zu vorherigen Arbeiten, die eine konstante PoW-Dauer annahmen, modelliert dieses Paper die PoW-Dauer als stochastische Variable. Dies führt zu einer signifikanten Komplexität, da der Zeitpunkt, an dem ein Tip seine Rolle als Tip verliert, nicht mehr deterministisch ist, sondern von der zufälligen Dauer abhängt.
2. Batch-Arrivals: Das Modell erlaubt das gleichzeitige Ankommen mehrerer Vertices ($N > 1$), was realistischere Szenarien abbildet als reine Poisson-Prozesse mit Einzelankünften.
3. Differenzierung nach Typen: Die Autoren führen eine neue Klassifizierung von ausstehenden Tips ein, basierend auf ihrer erwarteten verbleibenden Dauer und dem Typ des PoW. Dies ermöglicht eine präzisere Analyse der Sicherheitsrisiken (wie lange ein Tip unbestätigt bleibt).
4. Rigorose Konvergenzbeweise: Das Paper liefert einen strengen Beweis dafür, dass das stochastische Prozesssystem mit hoher Wahrscheinlichkeit gegen das deterministische Fluid Limit konvergiert.

4. Ergebnisse

Haupttheorem (Theorem 3.1):
Es wird gezeigt, dass die Differenz $g(T)$ zwischen dem skalierten stochastischen Prozess und dem Fluid Limit für ein festes Zeitintervall $[0, T]$ mit einer bestimmten Wahrscheinlichkeitsgrenze gegen Null konvergiert, wenn $\lambda, N, \epsilon^{-1} \to \infty$.
Die Wahrscheinlichkeit, dass die Abweichung einen Schwellenwert $\delta$ überschreitet, wird durch eine Summe von Exponentialtermen nach oben beschränkt, die von Parametern wie $\epsilon, \lambda, N$ abhängen. Dies bestätigt die Gültigkeit der Fluid-Limit-Näherung.

Steady-State-Analyse:

• Das Paper analysiert die Gleichgewichtszustände (stationären Zustand) der PDEs.
• Es wird gezeigt, dass im stabilen Zustand das Verhältnis von freien Tips zu Gesamt-Tips konstant ist ($f(t) = l(t)/2$ für den Fall von 2 Parents).
• Die Anzahl der Tips im Gleichgewicht hängt von den Parametern der PoW-Dauer ($p_i, h_i$) ab. Eine kürzere erwartete PoW-Dauer führt zu einer schnelleren Bestätigung und somit zu einer geringeren Anzahl an wartenden Tips.
• Die Ergebnisse stimmen mit früheren Befunden für Blockchain-Systeme überein, wenn man die PoW-Dauer als konstant annimmt, erweitern diese aber auf komplexere DAG-Strukturen.

Simulationen:
Numerische Simulationen bestätigen die theoretischen Vorhersagen. Die skalierten stochastischen Prozesse verhalten sich fast deterministisch und folgen eng den Kurven des Fluid Limits, selbst bei moderaten Werten für $N$ und $\lambda$.

5. Bedeutung und Ausblick

Wissenschaftliche Bedeutung:
Dieses Paper liefert einen wichtigen theoretischen Baustein für das Verständnis der Skalierbarkeit und Sicherheit von DAG-basierten Distributed Ledgers. Die Einführung des Fluid Limits mit zufälligen Verzögerungen ermöglicht es, das Systemverhalten ohne aufwendige Simulationen für große Netzwerke vorherzusagen. Die Methode der „verzögerten PDEs" ist ein mächtiges Werkzeug zur Analyse von Systemen mit Gedächtnis und zufälligen Latenzen.

Praktische Relevanz:

• Sicherheitsanalyse: Die Analyse der Tips-Anzahl und ihrer Verteilung gibt Aufschluss über die Bestätigungszeiten von Transaktionen. Ein hohes Maß an Tips kann auf eine langsame Bestätigung oder potenzielle Angriffe (Double Spending) hindeuten.
• Systemdesign: Die Ergebnisse helfen bei der Optimierung von Protokollen (wie IOTA Tangle), indem sie zeigen, wie sich Änderungen in der PoW-Schwierigkeit oder der Ankunftsrate auf die Stabilität des Netzwerks auswirken.

Zukünftige Richtungen:
Die Autoren schlagen vor, das Modell auf unbeschränkte Verteilungen der PoW-Dauer zu erweitern und die Auswirkungen von adversarialen Angriffen (böswilligen Akteuren) sowie Kommunikationsverzögerungen in DAG-Systemen zu untersuchen. Dies ist ein entscheidender Schritt, um die Robustheit solcher Systeme gegenüber realen Bedrohungen besser zu verstehen.

Zusammenfassend stellt dieses Paper einen rigorosen mathematischen Fortschritt dar, der die Lücke zwischen stochastischen Micro-Modellen von Distributed Ledgers und deterministischen makroskopischen Beschreibungen schließt, insbesondere unter realistischen Bedingungen zufälliger Verarbeitungszeiten.