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

Résumé technique : Analyse théorique des jeux de la sélection de transactions dans les registres distribués basés sur DAG

Énoncé du problème
Dans les technologies de registre distribué (DLT) basées sur les graphes acycliques dirigés (DAG), plusieurs validateurs proposent des blocs simultanément afin d'améliorer le débit. Cependant, ce parallélisme introduit le défi des collisions de transactions, où plusieurs validateurs sélectionnent la même transaction, entraînant des inefficacités car les inclusions redondantes n'augmentent pas l'utilité du système. Les systèmes actuels reposent souvent sur des heuristiques naïves pour la sélection de transactions, telles que la sélection uniforme ou proportionnelle, sans analyser rigoureusement si ces stratégies constituent des équilibres de Nash (EN) sous des mécanismes spécifiques d'allocation des frais. De plus, l'interaction entre les modèles de distribution des frais et les incitations des validateurs dans un cadre décentralisé et non coopératif reste sous-examinée. Cet article comble cette lacune en dérivant les équilibres de Nash mixtes symétriques pour les stratégies de sélection de transactions sous deux mécanismes d'allocation des frais distincts et en évaluant leurs performances par rapport à des références naïves.

Méthodologie
Les auteurs modélisent le processus de sélection de transactions comme un jeu à coup unique (modèle myope) impliquant $N$ validateurs et un pool fini de $m$ transactions avec des frais variables. Chaque validateur sélectionne un sous-ensemble de $b$ transactions à inclure dans son bloc. L'étude se concentre sur deux mécanismes d'allocation des frais :

1. Allocation aléatoire des frais (RFA) : Si plusieurs validateurs incluent une transaction, le frais est attribué aléatoirement à exactement l'un d'entre eux. Ce mécanisme est typique des systèmes de preuve de travail (PoW) avec ordre total (par exemple, GHOSTDAG).
2. Partage collaboratif des frais (CFS) : Si au moins un validateur inclut une transaction, le frais est réparti équitablement entre tous les $N$ validateurs. Ce mécanisme est plus typique des protocoles de type tolérance aux pannes byzantines (BFT).

Les auteurs emploient un cadre théorique des jeux pour dériver des équilibres de Nash symétriques. Ils établissent d'abord un résultat théorique général (Théorème IV.1) caractérisant l'EN à l'aide d'une fonction strictement décroissante $f(p)$ représentant la part espérée des récompenses. Reconnaissant que l'inversion directe de $f(p)$ pour le RFA est computationnellement intensive, l'article propose une approche efficace basée sur l'optimisation utilisant les conditions de Karush-Kuhn-Tucker (KKT). Cela transforme la dérivation de l'équilibre en un problème d'optimisation concave soluble par descente de gradient projetée.

La performance des équilibres dérivés est évaluée numériquement par rapport à deux références naïves :

• Sélection aléatoire de transactions (RTS) : Sélection uniforme.
• Sélection proportionnelle de transactions (PTS) : Probabilité de sélection proportionnelle aux frais de transaction.

Les métriques incluent le débit effectif de transactions (nombre espéré de transactions uniques incluses) et le débit effectif de frais (récompenses totales espérées collectées). Les simulations utilisent une distribution de type Zipf pour modéliser des structures de frais biaisées.

Contributions clés

1. Dérivation d'équilibres de Nash symétriques : L'article fournit la première dérivation explicite d'équilibres de Nash mixtes symétriques pour les modèles RFA et CFS dans un jeu de sélection de transactions à coup unique.
2. Méthode de calcul efficace : Les auteurs introduisent un cadre d'optimisation concave utilisant les conditions KKT pour calculer ces équilibres efficacement, surmontant l'intracabilité computationnelle des méthodes d'inversion directe, en particulier pour le modèle RFA.
3. Analyse comparative des performances : Grâce à des simulations numériques, l'étude démontre que l'EN du mécanisme de partage collaboratif des frais (CFS) atteint systématiquement un débit de frais et des récompenses supérieurs à ceux de l'EN de l'allocation aléatoire des frais (RFA), en particulier sous des distributions de frais biaisées.
4. Étalonnage des stratégies naïves : L'analyse révèle que si l'EN-CFS est optimal pour les revenus de frais, l'heuristique de sélection proportionnelle de transactions (PTS) surpasse souvent l'EN-RFA en termes de récompenses. Dans les scénarios où le CFS n'est pas réalisable (par exemple, les systèmes PoW sans permission), la PTS sert d'alternative robuste pouvant approcher la performance de l'équilibre RFA.

Résultats
Les évaluations numériques sous divers paramètres (nombre de transactions, frais maximum et biais des frais) produisent les insights suivants :

• Débit de frais : L'équilibre CFS maximise systématiquement le débit de frais dans tous les scénarios testés. La stratégie PTS performe également bien, surpassant significativement l'équilibre RFA. À l'inverse, l'équilibre RFA produit souvent un débit de frais inférieur, voire à la stratégie uniforme (RTS).
• Débit de transactions : Un compromis existe entre la maximisation des frais et la diversité des transactions. La stratégie uniforme (RTS) atteint le débit de transactions effectif le plus élevé en minimisant les collisions grâce à une distribution de probabilité égale. Cependant, cela se fait au prix d'un débit de frais plus faible. L'équilibre CFS, bien qu'il maximise les frais, résulte dans le débit de transactions effectif le plus faible car les validateurs se concentrent sur les transactions à hauts frais, entraînant des taux de collisions plus élevés pour ces éléments spécifiques.
• Impact du biais : À mesure que les distributions de frais deviennent plus biaisées (paramètre Zipf plus élevé), l'écart de performance s'élargit. Le CFS et la PTS maintiennent un débit de frais supérieur, tandis que le RFA peine, soulignant son inefficacité à gérer des structures de frais diversifiées.

Portée et affirmations
L'article affirme que ses résultats fournissent des insights exploitables pour la conception de mécanismes de sélection de transactions et d'incitations dans les DLT basées sur DAG. En caractérisant les équilibres de Nash, les auteurs démontrent que les stratégies intuitives (comme la sélection uniforme) ne sont pas toujours optimales et que le choix du mécanisme d'allocation des frais modifie fondamentalement le comportement des validateurs et la performance du système.

Plus spécifiquement, le travail suggère que :

• Le CFS est supérieur pour les revenus : Si l'objectif principal est de maximiser les revenus de frais, le CFS avec sa stratégie d'équilibre correspondante est le mécanisme le plus efficace.
• Le RFA présente des inefficacités inhérentes : Le mécanisme RFA, courant dans les systèmes PoW, conduit à des équilibres qui peuvent être surpassés par des heuristiques simples comme la sélection proportionnelle, indiquant un désalignement entre les incitations individuelles et le bien-être collectif dans de telles conceptions.
• Heuristiques pratiques : Pour les protocoles où le CFS n'est pas réalisable (par exemple, en raison de l'absence d'un ensemble de validateurs connu dans les environnements sans permission), la sélection proportionnelle offre une heuristique précieuse qui approxime la performance d'équilibre du RFA sans nécessiter de calcul d'équilibre complexe.

Les auteurs maintiennent une portée modeste, reconnaissant que l'étude se limite à un modèle à coup unique avec des frais statiques et des latences homogènes. Ils notent que l'extension de cette analyse à des jeux séquentiels multi-tours avec des frais dynamiques et des conditions de réseau hétérogènes reste une étape nécessaire pour l'applicabilité dans le monde réel. L'article ne propose pas de nouvelles implémentations de protocoles, mais fournit plutôt une fondation théorique et numérique pour évaluer les structures d'incitation existantes et futures.