Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers

Technische Samenvatting: Game-theoretische Analyse van Transactiekeuze in DAG-gebaseerde Gedistribueerde Ledgers

Probleemstelling
In DAG-gebaseerde gedistribueerde ledger-technologieën (DLT's) stellen meerdere validators gelijktijdig blokken voor om de doorvoer te verbeteren. Deze parallelisatie introduceert echter de uitdaging van transactiecyclussen, waarbij meerdere validators dezelfde transactie selecteren, wat leidt tot inefficiënties aangezien redundante opnames de systeemgebruikswaarde niet verhogen. Huidige systemen vertrouwen vaak op naïeve heuristieken voor transactiekeuze, zoals uniforme of evenredige selectie, zonder rigoureus te analyseren of deze strategieën Nash-evenwichten (NE) vormen onder specifieke fee-toewijzingsmechanismen. Bovendien blijft de interactie tussen fee-verdelingsmodellen en validatorprikkels in een gedecentraliseerde, niet-coöperatieve setting onderbelicht. Dit artikel vult deze lacune op door de symmetrische gemengde Nash-evenwichten voor transactiekeuzestrategieën af te leiden onder twee verschillende fee-toewijzingsmechanismen en hun prestaties te evalueren tegenover naïeve benchmarks.

Methodologie
De auteurs modelleren het transactiekeuzeproces als een eenmalig spel (korte-termijnmodel) met $N$ validators en een eindige pool van $m$ transacties met variërende fees. Elke validator selecteert een subset van $b$ transacties om op te nemen in hun blok. De studie richt zich op twee fee-toewijzingsmechanismen:

1. Random Fee Allocation (RFA): Als meerdere validators een transactie opnemen, wordt de fee willekeurig toegewezen aan precies één van hen. Dit mechanisme is typerend voor Proof-of-Work (PoW)-systemen met totale ordening (bijvoorbeeld GHOSTDAG).
2. Collaborative Fee Sharing (CFS): Als ten minste één validator een transactie opneemt, wordt de fee gelijk verdeeld onder alle $N$ validators. Dit mechanisme is typerender voor Byzantine Fault Tolerance (BFT)-achtige protocollen.

De auteurs maken gebruik van een game-theoretisch kader om symmetrische Nash-evenwichten af te leiden. Zij stellen eerst een algemeen theoretisch resultaat vast (Stelling IV.1) dat het NE karakteriseert met behulp van een strikt dalende functie $f(p)$ die het verwachte aandeel van beloningen voorstelt. Gezien het feit dat het direct inverteren van $f(p)$ voor RFA computatie-intensief is, stelt het artikel een efficiënte, op optimalisatie gebaseerde aanpak voor met gebruikmaking van de Karush-Kuhn-Tucker (KKT)-voorwaarden. Dit transformeert de afleiding van het evenwicht in een concave optimalisatieprobleem dat oplosbaar is via geprojecteerde gradiëntafstijging.

De prestaties van de afgeleide evenwichten worden numeriek geëvalueerd tegenover twee naïeve benchmarks:

• Random Transaction Selection (RTS): Uniforme selectie.
• Proportional Transaction Selection (PTS): Selectiekans evenredig aan transactiefees.

De metrieken omvatten Effectieve Transactiedoorvoer (verwacht aantal unieke opgenomen transacties) en Effectieve Fee-doorvoer (totaal verwachte ontvangen beloningen). Simulaties maken gebruik van een Zipf-achtige fee-verdeling om scheve fee-structuren te modelleren.

Belangrijkste Bijdragen

1. Afleiding van Symmetrische Nash-evenwichten: Het artikel biedt de eerste expliciete afleiding van symmetrische gemengde Nash-evenwichten voor zowel RFA- als CFS-modellen in een eenmalig transactiekeuzespel.
2. Efficiënte Berekeningsmethode: De auteurs introduceren een concave optimalisatiekader met gebruikmaking van KKT-voorwaarden om deze evenwichten efficiënt te berekenen, waarmee de computationele onberekenbaarheid van directe inverteringsmethoden wordt overwonnen, met name voor het RFA-model.
3. Vergelijkende Prestatieanalyse: Door middel van numerieke simulaties toont de studie aan dat het NE van het Collaborative Fee Sharing (CFS)-mechanisme consistent hogere fee-doorvoer en beloningen bereikt dan het NE van Random Fee Allocation (RFA), vooral onder scheve fee-verdelingen.
4. Benchmarking van Naïeve Strategieën: De analyse onthult dat hoewel CFS-NE optimaal is voor fee-omzet, de Proportional Transaction Selection (PTS)-heuristiek vaak beter presteert dan het RFA-NE qua beloningen. In scenario's waar CFS niet haalbaar is (bijvoorbeeld in permissionless PoW-systemen), dient PTS als een robuust alternatief dat de prestaties van het RFA-evenwicht kan benaderen.

Resultaten
Numerieke evaluaties onder variërende parameters (aantal transacties, maximale fee en fee-scheefheid) leveren de volgende inzichten op:

• Fee-doorvoer: Het CFS-evenwicht maximaliseert consistent de fee-doorvoer in alle geteste scenario's. De PTS-strategie presteert ook goed en overtreft het RFA-evenwicht aanzienlijk. Omgekeerd levert het RFA-evenwicht vaak lagere fee-doorvoer op dan zelfs de uniforme (RTS)-strategie.
• Transactiedoorvoer: Er bestaat een afweging tussen fee-maximalisatie en transactiediversiteit. De uniforme strategie (RTS) bereikt de hoogste effectieve transactiedoorvoer door botsingen te minimaliseren via een gelijkmatige kansverdeling. Dit gaat echter ten koste van lagere fee-doorvoer. Het CFS-evenwicht, terwijl het fees maximaliseert, resulteert in de laagste effectieve transactiedoorvoer omdat validators zich concentreren op transacties met hoge fees, wat leidt tot hogere botsingspercentages voor die specifieke items.
• Invloed van Scheefheid: Naarmate fee-verdelingen schever worden (hogere Zipf-parameter), vergroot het prestatieverschil. CFS en PTS behouden een superieure fee-doorvoer, terwijl RFA moeite heeft, wat de inefficiëntie ervan bij het hanteren van diverse fee-structuren benadrukt.

Betekenis en Beweringen
Het artikel beweert dat de bevindingen bruikbare inzichten bieden voor het ontwerpen van transactiekeuze- en prikkelmechanismen in DAG-gebaseerde DLT's. Door de Nash-evenwichten te karakteriseren, tonen de auteurs aan dat intuïtieve strategieën (zoals uniforme selectie) niet altijd optimaal zijn en dat de keuze van het fee-toewijzingsmechanisme validatorgedrag en systeemprestaties fundamenteel verandert.

Specifiek suggereert het werk dat:

• CFS superieur is voor omzet: Als het primaire doel het maximaliseren van fee-omzet is, is CFS met de bijbehorende evenwichtsstrategie het meest effectieve mechanisme.
• RFA inherente inefficiënties heeft: Het RFA-mechanisme, gebruikelijk in PoW-systemen, leidt tot evenwichten die kunnen worden overtroffen door eenvoudige heuristieken zoals proportionele selectie, wat wijst op een misalignement tussen individuele prikkels en collectief welzijn in dergelijke ontwerpen.
• Praktische Heuristieken: Voor protocollen waar CFS niet haalbaar is (bijvoorbeeld vanwege het ontbreken van een bekende validatorset in permissionless omgevingen), biedt proportionele selectie een waardevolle heuristiek die de evenwichtsprestaties van RFA benadert zonder complexe evenwichtsberekening te vereisen.

De auteurs houden een bescheiden scope aan en erkennen dat de studie beperkt is tot een eenmalig model met statische fees en homogene latenties. Zij merken op dat het uitbreiden van deze analyse naar meertraps, sequentiële spellen met dynamische fees en heterogene netwerkomstandigheden een noodzakelijke stap blijft voor toepasbaarheid in de echte wereld. Het artikel stelt geen nieuwe protocolimplementaties voor, maar biedt eerder een theoretische en numerieke basis voor het evalueren van bestaande en toekomstige prikkelstructuren.