Fluid limit of a distributed ledger model with random delay

Dit artikel analyseert de asymptotische gedrag van een DAG-model voor gedistribueerde ledgers met willekeurige vertragingen en toont aan dat het aantal bladeren en andere kenmerken kunnen worden benaderd door een vloeistoflimiet die wordt beschreven door een stelsel van vertraagde partiële differentiaalvergelijkingen.

De kern

Hier is een uitleg van het onderzoek in eenvoudig, alledaags Nederlands, met behulp van creatieve analogieën.

De Grote Idee: Een Digitale Boekhouding die Altijd Groeit

Stel je voor dat je een gigantisch, digitaal notitieboek hebt dat door duizenden mensen tegelijk wordt gebruikt. Dit is een gedistribueerd grootboek (zoals blockchain of IOTA). Iedereen kan er iets in schrijven, maar niemand mag de oude regels veranderen. Om een nieuwe regel toe te voegen, moet je eerst een zware puzzel oplossen (dit heet "Proof of Work").

In dit papier kijken de auteurs naar hoe snel en veilig dit systeem werkt als er veel mensen tegelijk iets willen schrijven, en als het oplossen van de puzzel willekeurig lang duurt (soms 1 minuut, soms 10 minuten).

Het Probleem: De "Wachtrij" van de Puzzels

In dit systeem zijn er twee soorten mensen:

1. De "Vrije" mensen: Die hebben hun puzzel opgelost en wachten om hun stukje papier in het boek te plakken.
2. De "Wachtende" mensen: Die zijn net begonnen met een puzzel, maar zijn nog niet klaar.

Het probleem is dat als er te veel mensen tegelijk een puzzel oplossen, er een enorme "wachtrij" ontstaat van stukjes papier die nog niet zijn vastgeplakt. Als deze wachtrij te lang wordt, wordt het systeem onveilig (hackers kunnen dan makkelijker bedrog plegen).

De auteurs willen weten: Hoe groot wordt deze wachtrij als er oneindig veel mensen meedoen?

De Oplossing: De "Vloeibare Voorspelling" (Fluid Limit)

In plaats van elke persoon in de menigte te tellen (wat onmogelijk is als er miljoenen zijn), gebruiken de auteurs een wiskundige truc. Ze kijken niet naar de individuele mensen, maar naar de stroom als geheel.

• De Analogie: Stel je voor dat je een bak met water hebt waar je druppels in laat vallen.
  • Als je naar één druppel kijkt, is het chaotisch en willekeurig.
  • Maar als je naar de hele stroom kijkt, zie je een gladde, voorspelbare beweging.
  • De auteurs hebben een formule bedacht (een "vloeibare limiet") die precies voorspelt hoe hoog het water (de wachtrij) zal stijgen, zelfs als de druppels (de puzzels) willekeurig lang duren.

Wat hebben ze ontdekt?

1. Het Systeem Stabiliseert: Zelfs als de puzzels willekeurig lang duren, zal het systeem op een bepaald punt een evenwicht vinden. De wachtrij groeit niet oneindig, maar blijft op een bepaald niveau hangen.
2. De Snelheid is Belangrijk: Hoe sneller de gemiddelde puzzel wordt opgelost, hoe kleiner de wachtrij blijft. Als mensen te langzaam zijn, stapelen de "onbevestigde" stukjes papier zich op.
3. De Voorspelling werkt: Hun wiskundige formule (de vloeibare limiet) is zo nauwkeurig dat ze de chaos van miljoenen individuele gebruikers kunnen samenvatten in een paar simpele lijnen op een grafiek.

Waarom is dit belangrijk?

Voor mensen die cryptomunten of veilige databases gebruiken, is dit cruciaal. Het geeft hen een manier om te voorspellen:

• "Als we 10.000 nieuwe gebruikers krijgen, wordt het systeem dan traag?"
• "Hoeveel tijd duurt het voordat een transactie veilig is?"

Door deze "vloeibare" formule te gebruiken, kunnen ingenieurs het systeem beter ontwerpen zonder dat ze eerst miljoenen jaren moeten wachten om te zien of het werkt. Ze kunnen het nu al op de computer simuleren en zien dat het systeem stabiel blijft, zelfs als de chaos toeneemt.

Kort samengevat: De auteurs hebben een manier gevonden om de chaos van een drukke digitale markt te vertalen naar een rustige, voorspelbare stroom, zodat we weten dat het systeem veilig blijft, zelfs als het enorm groeit.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Fluid limit of a Distributed Ledger Model with Random Delay" van J. Feng en C. King, vertaald en samengevat in het Nederlands.

Titel: Vloeistoflimiet van een gedistribueerd ledger-model met willekeurige vertraging

1. Probleemstelling en Context

Gedistribueerde ledgers (DL), zoals blockchain en IOTA, zijn gedecentraliseerde databases die transacties opslaan in een gerichte acyclische graaf (DAG). Een cruciaal aspect van deze systemen is het "Proof-of-Work" (POW) mechanisme, dat een vertraging introduceert tussen het moment waarop een blok (vertex) wordt gegenereerd en het moment waarop het daadwerkelijk aan de DAG wordt gekoppeld (geaccepteerd).

De bestaande literatuur heeft vaak geanalyseerde modellen met een vaste POW-duur. Echter, in realistische scenario's varieert de tijd die nodig is om POW te voltooien. Dit artikel adresseert de complexiteit die ontstaat wanneer:

1. De POW-duur stochastisch is (willekeurig verdeeld over een reeks mogelijke waarden).
2. Meerdere vertices gelijktijdig aankomen (batch arrivals).
3. De dynamiek van "tips" (niet-geattacheerde blokken) en "pending tips" (blokken die als ouder zijn geselecteerd maar nog niet voltooid) moet worden gemodelleerd.

Het centrale probleem is het analyseren van de asymptotisch gedrag van dit complexe stochastische systeem om de stabiliteit en beveiliging (verificatiesnelheid) van het ledger te begrijpen.

2. Methodologie

De auteurs ontwikkelen een wiskundig model dat de dynamiek van de DAG beschrijft en passen de vloeistoflimiet (fluid limit) methode toe.

• Modelopzet:

  • Het systeem wordt gemodelleerd als een discrete tijdproces met tijdstappen $t_n = n\epsilon$.
  • Er arriveren $N$ vertices per tijdstap met een aankomsttarief $\lambda = N/\epsilon$.
  • Elke vertex kiest een POW-duur $h_i$ uit een discrete set $\{h_1, ..., h_M\}$ met waarschijnlijkheid $p_i$.
  • Vertices selecteren ouders (parents) willekeurig uit de set van beschikbare "tips".
  • Er worden specifieke variabelen gedefinieerd om de staat van het systeem te volgen:
    • $L(t)$: Aantal tips.
    • $F(t)$: Aantal "free tips" (niet geselecteerd als ouder).
    • $W(t, u)$: Aantal "pending tips" met een resterende levensduur (Residual Lifetime - RLT) $u$.
    • Typen van pending tips worden onderscheiden op basis van de POW-duur die de RLT bepaalt.

• Afleiding van de Vloeistoflimiet:

  • De auteurs laten $\lambda, N \to \infty$ en $\epsilon \to 0$ gaan, terwijl de verhouding $N/\epsilon$ constant blijft.
  • Door de verwachte waarden van de update-regels te nemen en alleen de leidende orde-termen te behouden, worden de discrete stochastische vergelijkingen omgezet in een stelsel van vertraagde partiële differentiaalvergelijkingen (delayed PDEs).
  • Deze PDEs beschrijven de evolutie van de continue functies $l(t)$, $f(t)$ en $w_i(t, u)$, die de schaalbare limieten zijn van respectievelijk het aantal tips, free tips en pending tips.

• Bewijsstrategie:

  • Het bewijs van de convergentie (Theorema 3.1) maakt gebruik van een "separatie-techniek". De afwijking tussen het stochastische proces en de vloeistoflimiet wordt opgesplitst in twee delen:
    1. Fluctuaties: Het verschil tussen het stochastische proces en zijn conditionele verwachting (behandeld met martingaal-ongelijkheden, specifiek Azuma-Hoeffding).
    2. Deterministische fout: Het verschil tussen de conditionele verwachting en de vloeistoflimiet (behandeld door lagere-orde termen te verwaarlozen).
  • De Gronwall-lemma wordt toegepast om een bovenlimiet te vinden voor de totale afwijking over een tijdsinterval $[0, T]$.

3. Belangrijkste Bijdragen

1. Generalisatie naar Willekeurige POW: In tegenstelling tot eerdere werken (zoals [14]) die uitgingen van een vaste POW-duur, introduceert dit artikel een model met multinomiaal verdeelde POW-duraties. Dit maakt het model realistischer voor systemen zoals IOTA.
2. Batch-Aankomsten: Het model staat toe dat meerdere vertices gelijktijdig aankomen, wat leidt tot een nieuwe uitdrukking voor de vloeistoflimiet die batch-dynamiek en willekeurige vertragingen combineert.
3. Gedetailleerde Typologie van Tips: De auteurs onderscheiden tips niet alleen in "free" en "pending", maar categoriseren pending tips verder op basis van hun verwachte resterende levensduur en het type POW dat hen beïnvloedt. Dit biedt inzicht in de risicoprofielen van verschillende tips.
4. Rigoureuze Convergentiebewijzen: Het artikel levert een strikt wiskundig bewijs dat het geschaalde stochastische proces convergeert naar de oplossing van het stelsel van vertraagde PDEs, met expliciete waarschijnlijkheidsbounden voor de afwijking.

4. Resultaten

• Existentie en Uniekheid: Er wordt bewezen dat het stelsel van vertraagde PDEs een unieke oplossing heeft onder geschikte beginvoorwaarden.
• Convergentie: Theorema 3.1 stelt dat de kans dat de afwijking $g(T)$ tussen het stochastische proces en de vloeistoflimiet groter is dan een kleine $\delta$, exponentieel afneemt naarmate $\lambda$ (aankomsttarief) en $N$ (batchgrootte) toenemen.
  • Formeel: $P(g(T) > \delta) \to 0$ wanneer $\lambda, N, \epsilon^{-1} \to \infty$.
• Stabiele Toestand (Equilibrium): Voor het geval van twee mogelijke POW-duraties ($M=2$) wordt een analytische oplossing voor de evenwichtstoestand afgeleid.
  • In de stabiele toestand geldt: $f(t) = w(t) = l(t)/2$.
  • Het aantal tips $l(t)$ hangt af van de verwachte POW-duur ($\sum p_i h_i$). Een kortere verwachte POW-duur leidt tot een snellere attachering en dus een lager aantal wachtende tips.
• Simulaties: Numerieke simulaties bevestigen dat het geschaalde stochastische proces zich bijna deterministisch gedraagt en nauwkeurig wordt voorspeld door de vloeistoflimiet, zelfs bij variabele POW-duraties.

5. Significance en Toekomstperspectief

• Beveiligingsinzicht: De vloeistoflimiet biedt een krachtig hulpmiddel om de verificatiesnelheid van transacties te voorspellen. Aangezien de veiligheid van een DL afhangt van hoe snel een transactie wordt bevestigd (geattacheerd), stelt dit model onderzoekers in staat om de impact van willekeurige vertragingen op de beveiliging te kwantificeren.
• Schaalbaarheid: De methode is schaalbaar en kan worden uitgebreid naar protocollen met meer dan twee ouders per vertex of andere distributies voor POW-duraties.
• Toekomstige Richtingen: De auteurs wijzen op de noodzaak om dit model uit te breiden met:
  • Adversariale aanvallen: Analyse van hoe kwaadaardige actoren (bijv. double-spending) het systeem beïnvloeden in een DAG-omgeving.
  • Communicatievertragingen: Integratie van netwerklatentie naast POW-vertragingen.
  • Convergentiesnelheid: Onderzoek naar hoe snel het systeem convergeert naar de stabiele toestand bij willekeurige POW.

Conclusie:
Dit artikel levert een fundamentele bijdrage aan de wiskundige theorie van gedistribueerde ledgers door een robuust model te ontwikkelen dat willekeurige POW-vertragingen en gelijktijdige aankomsten combineert. De afgeleide vloeistoflimiet (PDEs) fungeert als een nauwkeurige en beheersbare benadering voor het complexe stochastische gedrag, wat essentieel is voor het optimaliseren van de prestaties en beveiliging van toekomstige DAG-gebaseerde cryptosystemen.