Résumé Technique : Les Périls du Parallélisme : Mécanismes de Frais de Transaction sous l'Incertitude d'Exécution

1. Énoncé du Problème

Les blockchains modernes passent d'une exécution sérielle à une exécution parallèle pour surmonter les goulots d'étranglement de la capacité causés par l'exécution plutôt que par le consensus. Si l'exécution parallèle (utilisée ou prévue par des chaînes comme Sui, Solana, Monad et Ethereum) augmente la capacité, elle introduit deux défis économiques critiques lorsque les transactions impliquent une incertitude d'exécution (contingence) et une contention de ressources :

1. Contingence d'Exécution et Allocation des Risques : Dans les langages de contrats intelligents expressifs (Turing-complets), l'utilisation des ressources d'une transaction (objets accédés) dépend souvent de l'état de la blockchain au moment de l'exécution (runtime), ce qui ne peut être connu avant l'exécution. Cela crée une tension entre le Risque Utilisateur (les utilisateurs paient trop pour des objets déclarés qui ne sont pas utilisés) et le Risque Planificateur (les planificateurs perdent des revenus lorsque la capacité réservée n'est pas payée en raison d'une sous-exécution).
2. Attaques par "Shill" sur le Calcul du Gas : Les mécanismes de calcul du gas (GCM) existants conçus pour les environnements parallèles (par exemple, la valeur de Shapley ou le temps de parcours proportionnel/Makespan) sont vulnérables à la manipulation rationnelle. Les utilisateurs et les planificateurs peuvent injecter des transactions "shill" (fausses) pour modifier stratégiquement le gas ou les frais calculés. Les utilisateurs peuvent réduire leurs frais en ajoutant des transactions parallèles inutiles, tandis que les planificateurs peuvent gonfler les frais en ajoutant une fausse contention.

L'article soutient que les conceptions actuelles ne parviennent pas à prendre en compte simultanément le parallélisme, l'incertitude d'exécution et la robustesse économique, ce qui conduit à des inefficacités et à des vulnérabilités exploitables.

2. Méthodologie et Modèle

Les auteurs formalisent un cadre pour analyser les mécanismes de frais de transaction (TFM) sous une exécution parallèle avec incertitude.

• Modèle de Transaction : Une transaction $tx$ est définie par des unités de calcul $t$, un frais de priorité $g$, et des ensembles de lecture/écriture déclarés $(R, W)$. Crucialement, les objets réellement accédés ($X_R, X_W$) peuvent être un sous-ensemble des ensembles déclarés selon le chemin d'exécution (contingence).
• Définitions des Frais : L'article distingue entre :
  • Frais Atteignables ($f_{att}$) : Le frais si tous les objets déclarés sont utilisés.
  • Frais de Base ($f_{base}$) : Le frais pour les seuls objets déterministes.
  • Frais Idéaux de l'Utilisateur ($f_{ui}$) : Le frais pour les objets exactement utilisés.
  • Frais Réellement Payés ($f_{act}$) : Le frais facturé.
• Métriques de Risque :
  • **Risque Utilisateur ($UR$) :**$f_{act} - f_{ui}$ (surpaiement).
  • **Risque Planificateur ($SR$) :**$f_{att} - f_{act}$ (revenu non réalisé).
• Modèle Adversaire : Les utilisateurs et les planificateurs sont modélisés comme des agents rationnels, économiquement motivés, capables d'insérer des transactions shill pour minimiser leurs coûts ou maximiser leurs revenus, respectivement.
• Analyse de Complexité : L'article utilise la théorie de la complexité (spécifiquement la P-complétude) pour analyser la difficulté de prédire l'utilisation des objets sans exécution.

3. Contributions Clés et Résultats

A. Impossibilité de l'Élimination Simultanée des Risques

L'article démontre un résultat d'impossibilité fondamentale : Aucun mécanisme ne peut éliminer simultanément le Risque Utilisateur et le Risque Planificateur sans pré-exécuter les transactions ou s'effondrer vers des frais constants.

• Théorème 1 : Si un planificateur est contraint par une limite de calcul $G$ (ne peut effectuer plus de travail que ce que le bloc permet), il est impossible de fixer les paiements de sorte que $UR=0$ et $SR=0$ pour toutes les entrées impliquant des transactions contingentes conflictuelles.
• Théorème 2 (P-complétude) : Décider si un objet spécifique est utilisé par une transaction contingente (le Problème de Décision d'Utilisation d'Objet) est P-complet. Cela implique que la vérification de l'utilisation d'un objet nécessite un travail séquentiel proportionnel au temps d'exécution, rendant l'analyse de l'utilisation par un planificateur "peu coûteuse" avant l'exécution informatiquement irréalisable.
• Compromis : Il existe un compromis linéaire inhérent. Réduire le risque utilisateur (facturer uniquement ce qui est utilisé) augmente le risque du planificateur (perte de revenus), et vice versa.

B. Caractérisation des Mécanismes de Division du Risque

Étant donné l'impossibilité, les auteurs caractérisent l'espace de conception via trois mécanismes canoniques de division du risque, paramétrés par $\alpha \in [0,1]$ :

1. Orienté Utilisateur ($\alpha=0$) : Les utilisateurs paient uniquement pour l'exécution réalisée ($f_{act} = f_{ui}$). Le planificateur supporte tout le risque.
2. Orienté Planificateur ($\alpha=1$) : Les utilisateurs paient pour tous les objets déclarés ($f_{act} = f_{att}$). L'utilisateur supporte tout le risque.
3. Équitable ("Even-Steven") ($\alpha=0.5$) : Le risque est partagé équitablement.
   L'article analyse ces cas sous différents modèles d'utilité du planificateur (Optimiste, Pessimiste, Médian) pour cartographier les implications de revenus.

C. Attaques par Shill et Résistance aux Frais (Shill-Proofness)

L'article identifie que les propriétés standards des GCM (comme l'inclusion d'ensemble) sont insuffisantes pour prévenir les attaques par shill en présence de contingence.

• Attaques par Shill d'Utilisateurs : Les utilisateurs injectent de fausses transactions pour réduire le gas ou les frais effectifs de leur véritable transaction.
• Attaques par Shill de Planificateurs : Les planificateurs injectent de fausses transactions pour augmenter le gas ou les frais facturés aux utilisateurs honnêtes.
• Résistance aux Frais (Fee-Based Shill-Proofness) : Les auteurs proposent de nouvelles définitions de la résistance aux attaques par shill basées sur les frais plutôt que sur le seul gas, en tenant compte des frais de priorité et de la contingence d'exécution. Ils prouvent que pour les mécanismes orientés utilisateur, la résistance aux attaques par shill n'est possible que si le frais est indépendant du planning (Théorème 3).

D. Le Mécanisme de Frais de Transaction Pondéré par les Objets (OW-TFM)

Pour résoudre ces problèmes, les auteurs proposent l'Object-Weighted Transaction Fee Mechanism (OW-TFM).

• Mécanisme : Les frais sont calculés sur la base du prix des objets déclarés par la transaction, où les prix des objets sont mis à jour en fonction de l'utilisation historique (similaire à l'EIP-1559).
• Paramétrage du Risque : Le mécanisme utilise un paramètre $\alpha$ pour déterminer la part que l'utilisateur paie pour les objets déclarés mais non utilisés ($\alpha \cdot \text{prix}$).
• Résistance au Shill : L'OW-TFM est démontré comme étant résistant aux attaques par shill sous certaines conditions. Comme les prix sont dérivés de l'utilisation des blocs passés, une transaction shill dans le bloc actuel ne peut pas abaisser le prix d'un objet pour le bloc actuel (elle ne peut qu'augmenter les prix futurs).
• Conditions : Le Lemme 4 établit un seuil pour $\alpha$ requis pour empêcher les attaques par shill des planificateurs, dépendant du ratio priorité/frais de base ($\pi_o$), de la réactivité du prix ($\eta$) et du ratio de rétention ($\gamma$).

4. Signification et Revendications

L'article affirme fournir les fondations rigoureuses pour évaluer et concevoir les mécanismes de frais pour les blockchains parallèles. Sa signification réside dans :

1. Identification des Limites Fondamentales : Il démontre que la tension entre l'équité pour l'utilisateur et le revenu du planificateur dans l'exécution parallèle n'est pas un défaut de conception, mais une conséquence fondamentale de l'incertitude d'exécution et de la complexité computationnelle.
2. Exposition des Vulnérabilités : Il révèle que les propositions existantes pour le calcul du gas parallèle (par exemple, les approches basées sur Shapley) sont vulnérables aux attaques rationnelles par shill, une menace jusqu'alors non traitée dans la littérature.
3. Fourniture d'un Cadre de Conception : Il offre un espace de conception principiel (le spectre $\alpha$) et un mécanisme concret (OW-TFM) qui permet aux concepteurs de systèmes de choisir explicitement leur stratégie d'allocation de risque tout en maintenant une résistance à la manipulation.
4. Pertinence pour l'Industrie : Les résultats s'appliquent directement et critiquent les conceptions des chaînes parallèles de premier plan (Sui, Monad, Solana) ainsi que la feuille de route d'Ethereum pour l'exécution parallèle via les listes d'accès.

Les auteurs maintiennent un ton modeste, notant que leur travail identifie des limitations et des compromis fondamentaux plutôt que de prescrire une solution unique "parfaite", reconnaissant qu'un déploiement pratique nécessite une considération supplémentaire des modèles d'exécution probabilistes et des détails spécifiques de mise en œuvre.