Résumé Technique : Ordonnancement par Unanimité

1. Énoncé du Problème

Les applications blockchain possèdent souvent des préférences spécifiques concernant l'ordre d'exécution des transactions pour fonctionner correctement. Les exemples incluent les teneurs de marché automatisés (AMM) nécessitant que les mises à jour de prix des oracles précèdent les échanges (swaps), les bourses de carnet d'ordres ayant besoin que les annulations s'exécutent avant les ordres au marché, et les enchères on-chain exigeant que les offres soient traitées de la plus haute à la plus basse. Actuellement, l'ordonnancement des transactions est déterminé par la blockchain sous-jacente (par exemple, via les proposants de blocs ou les frais de priorité), ce qui peut ne pas correspondre aux exigences spécifiques de ces applications.

Les solutions existantes pour imposer un ordonnancement sacrifient souvent la composabilité — la capacité des applications à interagir librement sur un registre partagé. Par exemple, les PropAMMs (AMM dépendants d'oracles) sont réalisables sur Solana en raison de ses règles d'ordonnancement spécifiques mais difficiles à implémenter ailleurs ; des bourses comme Hyperliquid ont créé des chaînes isolées pour sécuriser leur logique d'ordonnancement ; et les rollups n'atteignent un contrôle de l'ordonnancement qu'en isolant les transactions de la couche de base. Ce document traite du défi consistant à accorder aux applications des droits de séquençage sans fragmenter la blockchain ni sacrifier la composabilité.

2. Méthodologie : Surcharge par Unanimité (Unanimity Override)

Le papier propose une règle d'ordonnancement au niveau du protocole appelée surcharge par unanimité. L'intuition centrale est que si toutes les applications impliquées dans une paire de transactions s'accordent sur leur ordre relatif, le protocole doit respecter cet accord. Si les applications sont en désaccord ou si les préférences résultantes forment un cycle, un mécanisme de repli résout le conflit.

Le Mécanisme

L'algorithme opère en deux étapes principales :

1. Relation d'Unanimité ($\succ_u$) : Une relation dirigée est construite où la transaction $x_i \succ_u x_j$ si et seulement si chaque application interagissant avec à la fois $x_i$ et $x_j$ classe $x_i$ au-dessus de $x_j$, et qu'au moins une application préfère strictement $x_i$ à $x_j$.

   • Cette relation est généralement incomplète (certaines paires ne sont pas classées) et non transitive (des cycles peuvent se former).
   • Les cycles surviennent spécifiquement lorsque des transactions interagissent avec plusieurs applications « d'opinion » (applications ayant exprimé des préférences strictes).

2. Rupture de Cycle (Repli) : Pour récupérer un ordre d'exécution total, le protocole doit briser les cycles. Le papier introduit une règle de déclassement (demotion) :

   • Composantes Cycliques : L'algorithme identifie les composantes fortement connexes maximales (cycles) dans le graphe d'unanimité.
   • Déclassement : Au sein d'une composante cyclique, la règle sélectionne un ensemble de transactions pour être « déclassées ». Crucialement, seules les transactions à opinions multiples (celles interagissant avec $\ge 2$ applications d'opinion) sont éligibles au déclassement.
   • Logique de Sélection : Le mécanisme de repli déclasse de manière itérative la transaction à opinions multiples ayant la plus faible valeur d'« ordre par défaut » (par exemple, la plus faible commission de priorité) jusqu'à ce que la composante devienne acyclique.
   • Relation Réparée ($\tilde{\succ}_u$) : Les transactions déclassées sont retirées des comparaisons d'unanimité au sein du cycle et placées en dessous de toutes les transactions non déclassées de cette composante. Leur ordre relatif est déterminé par l'ordre par défaut.
   • Achèvement : L'ordre partiel acyclique résultant est étendu à un ordre d'exécution total ($\succ_e$) en utilisant un tri topologique de Kahn inversé, utilisant l'ordre par défaut pour départager les égalités au sein des couches.

3. Modèle de Menace

L'analyse suppose une forme forte de résistance à la censure (les transactions ne peuvent pas être retenues). L'attaquant est modélisé comme un acteur capable de :

• Déployer de nouvelles applications avec des préférences arbitraires.
• Injecter des transactions dans le bloc avec des attributs spécifiques (ex: frais, application cible).
• Contrôler l'ordre par défaut ($U_d$) dans le pire des scénarios (ex: agissant en tant que proposant de bloc).
• L'attaquant ne peut pas modifier les transactions honnêtes ni changer les préférences des applications honnêtes existantes.

4. Résultats Clés et Garanties

Le papier dérive deux garanties primaires qui tiennent face à toute stratégie d'attaquant réalisable, y compris ceux contrôlant l'ordre par défaut :

Garantie 1 : La Garantie à Opinion Unique

Si une transaction $x$ interagit avec exactement une application d'opinion (une transaction à opinion unique), et que cette application préfère strictement $x$ à une autre transaction $y$ (qui peut elle-même interagir avec d'autres applications), alors $x$ s'exécutera avant $y$.

• Raisonnement : Puisque $x$ est à opinion unique, aucune autre application ne peut exprimer de préférence sur la paire $(x, y)$. Ainsi, le classement par unanimité coïncide avec la préférence de cette application unique. Comme la règle de repli ne déclasse jamais les transactions à opinion unique, cette préférence est préservée dans l'ordre d'exécution final.
• Signification : Cela étend les garanties des rollups isolés à la couche de base. Les applications peuvent sécuriser leurs transactions critiques (comme les mises à jour d'oracles ou les annulations) en s'assurant qu'elles n'interagissent qu'avec cette application spécifique, même si d'autres parties de la transaction touchent des contrats non-opinions.

Garantie 2 : La Garantie de la Région Gated (Gated Region)

Il existe un ensemble de transactions, $X^*$, nommé la région gated, qui est protégée contre le réordonnancement. Une transaction appartient à $X^*$ si :

1. Aucune transaction en dehors de $X^*$ (qu'elle soit préexistante ou injectable par l'attaquant) ne peut être classée au-dessus d'elle de manière unanime.
2. Le sous-graphe des relations d'unanimité restreint à $X^*$ est acyclique.

• Résultat : Aucun membre de $X^*$ n'est jamais déclassé. Par conséquent, si une transaction dans $X^*$ est unanimement classée au-dessus d'une autre, elle s'exécute en premier, quel que soit l'ordre de l'attaquant pour injecter des transactions ou contrôler l'ordre par défaut.
• Application : Cela protège les transactions telles que les mises à jour d'oracles provenant d'adresses désignées ou les annulations qui sont classées les plus hautes par tous les marchés concernés, à condition que la « porte » (l'ensemble des transactions pouvant les surclasser) ne puisse pas être franchie par l'attaquant.

Vulnérabilité : Transactions à Opinions Multiples

Le papier identifie que les transactions à opinions multiples (interagissant avec $\ge 2$ applications d'opinion) sont les seules vulnérables aux attaques de réordonnancement. Un attaquant peut construire un cycle impliquant une transaction cible à opinions multiples et injecter des transactions pour forcer le repli à la déclasser. Cependant, le papier note que si la cible est une transaction à opinion unique, une telle attaque est impossible.

5. Comparaison avec les Références

• Vs Ordre par Défaut Contrôlé par l'Attaquant : La surcharge par unanimité réduit strictement l'ensemble des paires de transactions réversibles par rapport à un système où l'attaquant a un contrôle total sur l'ordre du bloc.
• Vs Ordonnancement par Frais de Priorité : La comparaison est nuancée. La surcharge par unanimité protège les transactions à opinion unique et les transactions de la région gated indépendamment des frais. Cependant, pour les transactions à opinions multiples non protégées, le coût d'une attaque (ex: front-running) peut être plus élevé ou plus bas selon la topologie spécifique du cycle et la structure des frais. Le papier note que les attaques de griefing (réordonner les transactions honnêtes pour nuire à un concurrent) sont possibles sous la surcharge par unanimité mais impossibles sous un pur ordonnancement par frais de priorité.

6. Signification et Portée

Le papier affirme fournir un mécanisme qui élargit l'espace de conception des applications sur les blockchains sans sacrifier la composabilité.

• Préservation des Garanties : Il permet aux applications d'imposer des préférences d'ordonnancement (comme les mises à jour d'oracles avant les swaps ou les annulations avant les transactions) sans nécessiter l'isolement sur des chaînes séparées ou des rollups.
• Alignement des Incitations : Le mécanisme informe les expéditeurs à l'avance de quelles transactions sont sûres. Par exemple, dans une enchère on-chain, les enchérisseurs sont incités à garder leurs offres comme des transactions à opinion unique pour garantir qu'elles ne soient pas déclassées, assurant ainsi le bon fonctionnement de l'enchère.
• Contribution Théorique : Ce travail connecte l'ordonnancement des transactions à la théorie du choix social. Il reconnaît que la relation d'unanimité est non transitive (une conséquence du théorème d'impossibilité d'Arrow) et propose une règle d'agrégation paretienne spécifique qui sacrifie l'« indépendance des alternatives non pertinentes » pour obtenir un ordre d'exécution complet et acyclique.

Le papier conclut en notant que la définition des « ensembles d'interaction » (quelles applications une transaction touche) est un défi pratique. Il discute du compromis entre l'utilisation d'interactions déclarées (plus faciles à vérifier, mais potentiellement sur-estimant le statut de multi-opinion) et les interactions réelles (garanties plus fortes, mais nécessitant une solution de point fixe pour la cohérence). L'analyse actuelle suppose que les ensembles d'interaction sont donnés.