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

Sintesi Tecnica: Analisi Teorico-Giocosa della Selezione delle Transazioni nei Registri Distribuiti Basati su DAG

Enunciato del Problema
Nelle tecnologie di registro distribuito (DLT) basate su DAG, più validatori propongono blocchi concorrentemente per migliorare il throughput. Tuttavia, questo parallelismo introduce la sfida delle collisioni di transazioni, dove più validatori selezionano la stessa transazione, portando a inefficienze poiché inclusioni ridondanti non aumentano l'utilità del sistema. I sistemi attuali spesso si affidano a euristiche naive per la selezione delle transazioni, come la selezione uniforme o proporzionale, senza analizzare rigorosamente se queste strategie costituiscano equilibri di Nash (NE) sotto specifici meccanismi di allocazione delle commissioni. Inoltre, l'interazione tra modelli di distribuzione delle commissioni e incentivi dei validatori in un contesto decentralizzato e non cooperativo rimane sottostudiata. Questo articolo colma tale lacuna derivando gli equilibri di Nash misti simmetrici per le strategie di selezione delle transazioni sotto due distinti meccanismi di allocazione delle commissioni e valutandone le prestazioni rispetto a benchmark naive.

Metodologia
Gli autori modellano il processo di selezione delle transazioni come un gioco monostadio (modello miope) che coinvolge $N$ validatori e un pool finito di $m$ transazioni con commissioni variabili. Ogni validatore seleziona un sottoinsieme di $b$ transazioni da includere nel proprio blocco. Lo studio si concentra su due meccanismi di allocazione delle commissioni:

1. Allocazione Casuale delle Commissioni (RFA): Se più validatori includono una transazione, la commissione viene assegnata casualmente a esattamente uno di essi. Questo meccanismo è tipico dei sistemi Proof-of-Work (PoW) con ordinamento totale (ad esempio, GHOSTDAG).
2. Condivisione Collaborativa delle Commissioni (CFS): Se almeno un validatore include una transazione, la commissione viene distribuita equamente tra tutti gli $N$ validatori. Questo meccanismo è più tipico di protocolli simili alla Tolleranza ai Guasti Bizantini (BFT).

Gli autori impiegano un quadro teorico-giocoso per derivare equilibri di Nash simmetrici. Stabiliscono innanzitutto un risultato teorico generale (Teorema IV.1) che caratterizza l'NE utilizzando una funzione strettamente decrescente $f(p)$ che rappresenta la quota attesa di ricompense. Riconoscendo che l'inversione diretta di $f(p)$ per RFA è computazionalmente intensiva, l'articolo propone un approccio efficiente basato sull'ottimizzazione utilizzando le condizioni Karush-Kuhn-Tucker (KKT). Ciò trasforma la derivazione dell'equilibrio in un problema di ottimizzazione concava risolvibile mediante discesa del gradiente proiettata.

Le prestazioni degli equilibri derivati sono valutate numericamente rispetto a due benchmark naive:

• Selezione Casuale delle Transazioni (RTS): Selezione uniforme.
• Selezione Proporzionale delle Transazioni (PTS): Probabilità di selezione proporzionale alle commissioni delle transazioni.

Le metriche includono il Throughput Effettivo delle Transazioni (numero atteso di transazioni uniche incluse) e il Throughput Effettivo delle Commissioni (ricompense totali attese raccolte). Le simulazioni utilizzano una distribuzione delle commissioni di tipo Zipf per modellare strutture di commissioni sbilanciate.

Contributi Chiave

1. Derivazione di Equilibri di Nash Simmetrici: L'articolo fornisce la prima derivazione esplicita di equilibri di Nash misti simmetrici per entrambi i modelli RFA e CFS in un gioco di selezione delle transazioni monostadio.
2. Metodo di Calcolo Efficiente: Gli autori introducono un quadro di ottimizzazione concava che utilizza le condizioni KKT per calcolare questi equilibri in modo efficiente, superando l'intrattabilità computazionale dei metodi di inversione diretta, in particolare per il modello RFA.
3. Analisi Comparativa delle Prestazioni: Attraverso simulazioni numeriche, lo studio dimostra che l'NE del meccanismo di Condivisione Collaborativa delle Commissioni (CFS) raggiunge costantemente un throughput di commissioni e ricompense più elevato rispetto all'NE dell'Allocazione Casuale delle Commissioni (RFA), specialmente sotto distribuzioni di commissioni sbilanciate.
4. Benchmarking di Strategie Naive: L'analisi rivela che, mentre l'NE-CFS è ottimale per il ricavo delle commissioni, l'euristica di Selezione Proporzionale delle Transazioni (PTS) spesso supera l'NE-RFA in termini di ricompense. In scenari in cui il CFS non è fattibile (ad esempio, sistemi PoW permissionless), la PTS funge da alternativa robusta che può avvicinarsi alle prestazioni dell'equilibrio RFA.

Risultati
Le valutazioni numeriche sotto parametri variabili (numero di transazioni, commissione massima e sbilanciamento delle commissioni) producono le seguenti intuizioni:

• Throughput delle Commissioni: L'equilibrio CFS massimizza costantemente il throughput delle commissioni in tutti gli scenari testati. Anche la strategia PTS performa bene, superando significativamente l'equilibrio RFA. Al contrario, l'equilibrio RFA spesso produce un throughput di commissioni inferiore persino alla strategia uniforme (RTS).
• Throughput delle Transazioni: Esiste un compromesso tra massimizzazione delle commissioni e diversità delle transazioni. La strategia uniforme (RTS) raggiunge il throughput effettivo di transazioni più alto minimizzando le collisioni attraverso una distribuzione di probabilità uniforme. Tuttavia, ciò comporta un costo in termini di throughput di commissioni più basso. L'equilibrio CFS, pur massimizzando le commissioni, risulta nel throughput effettivo di transazioni più basso perché i validatori si concentrano sulle transazioni ad alta commissione, portando a tassi di collisione più elevati per quegli elementi specifici.
• Impatto dello Sbilanciamento: Man mano che le distribuzioni delle commissioni diventano più sbilanciate (parametro Zipf più alto), il divario di prestazioni si amplia. CFS e PTS mantengono un throughput di commissioni superiore, mentre RFA fatica, evidenziando la sua inefficienza nella gestione di strutture di commissioni diversificate.

Significato e Affermazioni
L'articolo afferma che i suoi risultati forniscono intuizioni attuabili per la progettazione di meccanismi di selezione delle transazioni e incentivi nei DLT basati su DAG. Caratterizzando gli equilibri di Nash, gli autori dimostrano che strategie intuitive (come la selezione uniforme) non sono sempre ottimali e che la scelta del meccanismo di allocazione delle commissioni altera fondamentalmente il comportamento dei validatori e le prestazioni del sistema.

Nello specifico, il lavoro suggerisce che:

• CFS è superiore per i ricavi: Se l'obiettivo primario è massimizzare il ricavo delle commissioni, il CFS con la sua strategia di equilibrio corrispondente è il meccanismo più efficace.
• RFA ha inefficienze intrinseche: Il meccanismo RFA, comune nei sistemi PoW, porta a equilibri che possono essere superati da euristiche semplici come la selezione proporzionale, indicando un disallineamento tra incentivi individuali e benessere collettivo in tali design.
• Euristiche Pratiche: Per protocolli in cui il CFS non è fattibile (ad esempio, a causa della mancanza di un insieme di validatori noto in ambienti permissionless), la selezione proporzionale offre un'euristica preziosa che approssima le prestazioni di equilibrio di RFA senza richiedere un calcolo complesso dell'equilibrio.

Gli autori mantengono un ambito modesto, riconoscendo che lo studio è limitato a un modello monostadio con commissioni statiche e latenze omogenee. Notano che estendere questa analisi a giochi sequenziali multiround con commissioni dinamiche e condizioni di rete eterogenee rimane un passo necessario per l'applicabilità nel mondo reale. L'articolo non propone nuove implementazioni di protocolli, ma fornisce piuttosto una base teorica e numerica per valutare le strutture di incentivi esistenti e future.