Résumé Technique : Approvisionnement Adversarial dans les Blockchains

Énoncé du Problème

L'article aborde le défi de l'approvisionnement adversarial dans les protocoles de blockchain, spécifiquement dans le contexte des conceptions émergentes qui exploitent l'asymétrie computationnelle entre l'exécution et la vérification des tâches (par exemple, les preuves à connaissance nulle, ou SNARKs). Dans ces systèmes, un protocole doit déléguer des tâches computationnelles coûteuses (comme la génération d'une preuve de validité pour un bloc) à un ensemble de $n$ preuveurs pseudonymes et non fiables.

Le problème central consiste à concevoir un mécanisme qui :

1. Incite au moins un preueur à exécuter la tâche (assurant la vivacité).
2. Minimise la perte économique dans le pire des cas où jusqu'à $n-h$ preueurs sont adverses (Byzantins) et peuvent s'écarter du protocole pour provoquer une défaillance de vivacité (aucune preuve délivrée) ou induire un surpaiement.
3. Opère sans confiance, car les preueurs n'ont aucune réputation et ne peuvent s'engager de manière crédible à des actions futures.

Les auteurs modélisent cela comme un problème de conception de mécanisme où le concepteur du protocole cherche à minimiser la somme des paiements effectués et de la pénalité $C$ encourue si aucune preuve n'est délivrée, en supposant qu'un adversaire contrôle un sous-ensemble de preueurs et agit pour maximiser la perte du protocole.

Méthodologie

Les auteurs formalisent le problème en utilisant un cadre théorique des jeux :

• Configuration : Il y a $n$ preueurs, dont $h$ sont honnêtes. Le coût de génération d'une preuve est normalisé à 1. Si aucune preuve n'est produite, le protocole subit une pénalité de vivacité $C$.
• Modèle Adversarial : L'adversaire peut corrompre jusqu'à $a = n-h$ preueurs. L'adversaire observe le mécanisme et choisit le comportement du pire des cas (soit refuser de délivrer des preuves pour déclencher la pénalité $C$, soit délivrer des preuves pour manipuler les paiements).
• Objectif : Minimiser la perte du pire des cas $\ell(p, s)$, définie comme le coût total attendu (paiements + pénalité) sous la stratégie adverse du pire des cas, sous la contrainte que le mécanisme soit incitatif (les preueurs honnêtes maximisent leur utilité en suivant le protocole).

Pour rendre le problème traitable, les auteurs :

1. Déduisent une fonction de borne inférieure $g(s)$ sur la perte optimale du protocole, paramétrée par le vecteur de stratégie $s$ (la probabilité que chaque preueur délivre une preuve). Cette borne suppose un adversaire « affaibli » qui choisit entre deux stratégies extrêmes : agir entièrement honnêtement ou refuser entièrement de délivrer.
2. Analysent les minimiseurs de cette borne inférieure, les caractérisant soit comme des Équilibres de Comité Uniforme Désigné (un leader déterministe + un comité de randomisateurs) soit comme des Équilibres de Comité Symétriques (un comité de randomisateurs sans leader désigné).
3. Investiguent l'implémentabilité : déterminer si une règle de paiement existe qui induit ces équilibres tout en atteignant le coût de la borne inférieure.
4. Étendent l'analyse pour inclure les paiements négatifs (brûlage/mise en jeu), où les preueurs déposent une garantie qui peut être confisquée si le protocole détecte une attaque.

Contributions et Résultats Clés

1. Caractérisation des Équilibres Optimaux

L'article démontre que les minimiseurs de la borne inférieure $g(s)$ sont exclusivement de deux types :

• Équilibres Désignés : Un preueur est désigné pour délivrer avec une probabilité de 1, tandis qu'un comité de taille $k$ délivre avec une probabilité $s \in (0, 1)$.
• Équilibres Symétriques : Un comité de taille $k$ délivre avec une probabilité $s$, et aucun preueur unique n'est désigné.

2. Garanties d'Approximation

• Approximation Additive 1 : Les auteurs démontrent que pour toute règle de paiement et tout équilibre, il existe un équilibre désigné dont la perte est au plus d'une unité (le coût d'une seule preuve) supérieure à la perte optimale (Théorème 3.1).
• Implémentabilité : Tous les équilibres désignés sont implémentables avec une règle de paiement simple (Lemme 3.4). En revanche, les équilibres symétriques ne sont implémentables que sous des conditions spécifiques (par exemple, lorsque $C$ est suffisamment grand par rapport à $n$ et $h$), et nécessitent souvent des structures de paiement complexes ou des paiements négatifs pour être réalisables.

3. Échelle Asymptotique

• Échelle Logarithmique : La perte du pire des cas de l'équilibre désigné optimal évolue selon $O(\frac{\log C}{\tau})$, où $\tau = h/n$ est la fraction de preueurs honnêtes. Cela indique que même avec une fraction fixe d'adversaires, le coût du protocole ne croît que logarithmiquement avec la sévérité de la pénalité de vivacité.
• Impact de la Mise en Jeu (Staking) : L'introduction d'une mise totale $B$ (garantie) améliore considérablement l'échelle. Si $B$ est proportionnel à $C$, la perte évolue selon $O(1/\tau)$, devenant effectivement constante par rapport à $C$.

4. Dynamiques de Transition

L'article analyse la transition entre l'optimalité désignée et symétrique en fonction de $C$ (ampleur de la pénalité) et de $\tau$ (fraction d'honnêteté).

• Pour un petit $C$ ou un $\tau$ élevé, le mécanisme désigné est optimal.
• Pour un $C$ très grand, le mécanisme symétrique devient optimal dans l'analyse de la borne inférieure.
• Cependant, en raison des contraintes d'implémentabilité, le mécanisme désigné reste souvent le choix pratique même dans des régimes où la borne inférieure symétrique est plus faible, car la solution symétrique peut nécessiter des paiements négatifs qui sont irréalisables ou complexes à mettre en œuvre.

Importance et Recommandations Pratiques

L'article soutient que les résultats théoriques fournissent des orientations concrètes pour les concepteurs de protocoles blockchain, en particulier pour les zk-EVM (Machine Virtuelle Ethereum à Connaissance Nulle) et autres marchés de délégation vérifiable.

• Recommandation : Les auteurs recommandent fortement d'adopter l'équilibre optimal de comité uniforme désigné. Cette conception désigne un seul « leader » (ou travailleur principal) pour produire la preuve de manière déterministe, soutenu par un comité de « backups » qui produisent des preuves avec une probabilité calculée $s$.
• Justification :
  1. Simplicité : La règle de paiement est intuitive et ressemble aux mécanismes de consensus existants (par exemple, consensus basé sur un leader avec comités de validation).
  2. Proximité de l'Optimalité : La perte est au plus d'un coût de preuve éloignée de l'optimum théorique, ce qui est négligeable compte tenu des coûts de preuve actuels (souvent des fractions de dollar).
  3. Robustesse : Elle gère efficacement le comportement adverse du pire des cas, évoluant logarithmiquement avec la pénalité $C$.
  4. Faisabilité : Contrairement aux mécanismes symétriques qui peuvent nécessiter des paiements de type loterie complexes ou des paiements négatifs (brûlage) pour être optimaux, les mécanismes désignés sont toujours implémentables avec des paiements positifs.

L'article conclut que bien que les mécanismes symétriques soient théoriquement intéressants et optimaux dans des régimes asymptotiques spécifiques, le mécanisme désigné offre le meilleur équilibre entre optimalité théorique, implémentabilité et familiarité pour la communauté blockchain. Les auteurs notent que leur modèle s'applique largement à tout problème de délégation sans permission impliquant des défaillances de vivacité, y compris l'inférence IA vérifiable et les calculs basés sur les TEE.