L'impossibilité d'une équité parfaite dans l'ordre des transactions

Pendant des décennies, la recherche sur les systèmes distribués, en particulier dans le consensus byzantin et la réplication de machines d’état (SMR), s’est concentrée sur deux objectifs principaux : la cohérence et la vivacité. La cohérence signifie que tous les nœuds s’accordent sur la même séquence de transactions, tandis que la vivacité garantit que le système continue d’ajouter de nouvelles transactions. Cependant, ces propriétés n’empêchent pas les acteurs malveillants de modifier l’ordre des transactions après leur réception.

Dans les blockchains publiques, cet écart dans les garanties de consensus traditionnelles est devenu un problème sérieux. Les validateurs, constructeurs de blocs ou séquenceurs peuvent exploiter leur rôle privilégié dans l’ordre des blocs à des fins financières, une pratique connue sous le nom de valeur extractible maximale (MEV). Cette manipulation inclut le frontrunning rentable, le backrunning et le sandwiching de transactions. Étant donné que l’ordre d’exécution des transactions détermine leur validité ou leur rentabilité dans les applications DeFi, l’intégrité de l’ordre des transactions est essentielle pour maintenir l’équité et la confiance.

Pour combler cette faille de sécurité critique, la justice dans l’ordre des transactions a été proposée comme une troisième propriété essentielle du consensus. Les protocoles d’ordre équitable garantissent que l’ordre final des transactions dépend de facteurs externes et objectifs, tels que les temps d’arrivée (ou l’ordre de réception), et résistent à la réorganisation adversariale. En limitant le pouvoir qu’un proposeur de bloc a pour réorganiser les transactions, ces protocoles rapprochent les blockchains d’une transparence, d’une prévisibilité et d’une résistance au MEV accrues.

Le paradoxe de Condorcet et l’impossibilité d’une justice idéale

La notion la plus intuitive et la plus forte de justice est la Justice par réception-ordre (ROF). Définie de manière informelle comme « premier reçu, premier sorti », ROF stipule que si un nombre suffisant de transactions (tx) arrivent à une majorité de nœuds plus tôt qu’une autre transaction (tx′), alors le système doit ordonner tx avant tx′ pour l’exécution.

Cependant, atteindre cette « justice par ordre » universellement acceptée est fondamentalement impossible, sauf si l’on suppose que tous les nœuds peuvent communiquer instantanément (c’est-à-dire fonctionner dans un réseau externe instantané synchrone). Ce résultat d’impossibilité découle d’un lien surprenant avec la théorie du choix social, en particulier le paradoxe de Condorcet.

Le paradoxe de Condorcet montre que, même lorsque chaque nœud individuel maintient un ordre interne transitif des transactions, la préférence collective à travers le système peut aboutir à ce que l’on appelle des cycles non transitifs. Par exemple, il est possible qu’une majorité de nœuds reçoivent la transaction A avant B, une majorité reçoive B avant C, et une majorité reçoive C avant A. Ainsi, les trois préférences majoritaires forment une boucle (A→B→C→A). Cela signifie qu’aucun ordre unique et cohérent des transactions A, B et C ne peut satisfaire simultanément toutes les préférences majoritaires.

Ce paradoxe démontre pourquoi l’objectif d’atteindre parfaitement la Justice par réception-ordre est impossible dans des réseaux asynchrones, ou même dans des réseaux synchrones partageant une horloge commune si les délais du réseau externe sont trop longs. Cette impossibilité oblige à adopter des définitions de justice plus faibles, telles que la justice par lot.

Hedera Hashgraph et la faille du timestamp médian

Hedera, qui utilise l’algorithme de consensus Hashgraph, cherche à approcher une notion forte de justice par réception (ROF). Il le fait en attribuant à chaque transaction un timestamp final calculé comme la médiane des timestamps locaux de tous les nœuds pour cette transaction.

Cependant, cela est intrinsèquement sujet à manipulation. Un seul nœud adversaire peut délibérément fausser ses timestamps locaux et inverser l’ordre final de deux transactions, même lorsque tous les participants honnêtes les ont reçues dans le bon ordre.

Considérons un exemple simple avec cinq nœuds de consensus (A, B, C, D et E) où le nœud E agit de manière malveillante. Deux transactions, tx₁ et tx₂, sont diffusées dans le réseau. Tous les nœuds honnêtes reçoivent tx₁ avant tx₂, donc l’ordre final attendu devrait être tx₁ → tx₂.

In dans cet exemple, l’adversaire assigne à tx₁ un timestamp ultérieur (3) et à tx₂ un timestamp antérieur (2) pour fausser la médiane.

Lorsque le protocole calcule les médianes :

• Pour tx₁, les timestamps (1, 1, 4, 4, 3) donnent une médiane de 3.
• Pour tx₂, les timestamps (2, 2, 5, 5, 2) donnent une médiane de 2.

Étant donné que le timestamp final de tx₁ (3) est supérieur à celui de tx₂ (2), le protocole sort tx₂ → tx₁, inversant ainsi l’ordre vrai observé par tous les nœuds honnêtes.

Cet exemple simplifié montre une faille critique : La fonction médiane, bien qu’apparaissant neutre, est paradoxalement la cause réelle de l’injustice car elle peut être exploitée par un seul participant malhonnête pour biaiser l’ordre final des transactions.

En conséquence, le « timestamping équitable » souvent vanté par Hashgraph est une notion étonnamment faible de justice. Le consensus Hashgraph ne garantit pas la justice par réception et dépend plutôt d’un ensemble de validateurs autorisés plutôt que de garanties cryptographiques.

Obtenir des garanties pratiques

Cependant, pour contourner l’impossibilité théorique démontrée par Condorcet, les schémas pratiques d’ordre équitable doivent relâcher la définition de la justice d’une certaine manière.

Les protocoles Aequitas ont introduit le critère de Justice par ordre de bloc (BOF), ou justice par lot. BOF stipule que si suffisamment de nœuds reçoivent une transaction tx avant une autre tx′, alors tx doit être livré dans un bloc avant ou au même moment que tx′, ce qui signifie qu’aucun nœud honnête ne peut livrer tx′ dans un bloc après tx. Cela relâche la règle de « doit être livré avant » (la exigence de ROF) en « doit être livré au plus tard ».

Considérons trois nœuds de consensus (A, B et C) et trois transactions : tx₁, tx₂, et tx₃. Une transaction est considérée comme « reçue plus tôt » si au moins deux des trois nœuds (une majorité) l’observent en premier.

If nous appliquons un vote majoritaire pour déterminer un ordre global :

• tx₁ → tx₂ (accepté par A et C)
• tx₂ → tx₃ (accepté par A et B)
• tx₃ → tx₁ (accepté par B et C)

Ces préférences créent une boucle : tx₁ → tx₂ → tx₃ → tx₁. Dans cette situation, il n’existe pas d’ordre unique pouvant satisfaire tout le monde en même temps, ce qui rend impossible la justice stricte par réception-ordre.

BOF résout cela en regroupant toutes les transactions conflictuelles dans le même lot ou bloc au lieu d’imposer qu’une précède l’autre. Le protocole sort simplement :

Bloc B₁ = {tx₁, tx₂, tx₃}

Cela signifie que, du point de vue du protocole, les trois transactions sont traitées comme si elles avaient eu lieu en même temps. À l’intérieur du bloc, un bris d’égalité déterministe (tel qu’une valeur de hachage) décide de l’ordre précis dans lequel elles seront exécutées. En faisant cela, BOF garantit l’équité pour chaque paire de transactions et maintient la cohérence du journal final des transactions pour tous. Chacune est traitée au plus tard après celle qui la précède.

Ce petit mais important ajustement permet au protocole de gérer les situations où les ordres de transaction entrent en conflit, en regroupant ces transactions conflictuelles dans le même bloc ou lot. Importamment, cela ne conduit pas à un ordre partiel, car chaque nœud doit toujours s’accorder sur une séquence linéaire unique de transactions. Les transactions à l’intérieur de chaque bloc sont toujours organisées dans un ordre fixe pour l’exécution. Dans les cas où aucun conflit de ce type n’apparaît, le protocole atteint encore la propriété plus forte de justice par réception-ordre.

Bien qu’Aequitas ait réussi à atteindre la BOF, il a rencontré des limitations importantes, notamment une complexité de communication très élevée et une garantie de vivacité faible. La vivacité faible implique que la livraison d’une transaction n’est garantie qu’après la résolution complète du cycle de Condorcet auquel elle appartient. Cela peut prendre un temps arbitrairement long si les cycles « s’enchaînent ».

Le protocole Themis a été introduit pour appliquer la même propriété forte de BOF, mais avec une complexité de communication améliorée. Themis y parvient grâce à trois techniques : dégroupage par lots, ordonnancement différé et garanties intra-lot plus fortes.

Dans sa forme standard, Themis nécessite que chaque participant échange des messages avec la majorité des autres nœuds du réseau. La quantité de communication requise augmente avec le carré du nombre de participants. Cependant, dans sa version optimisée, SNARK-Themis, les nœuds utilisent des preuves cryptographiques succinctes pour vérifier la justice sans avoir besoin de communiquer directement avec chaque autre participant. Cela réduit la charge de communication pour qu’elle ne croisse que linéairement, permettant à Themis de s’adapter efficacement même dans de grands réseaux.

Supposons cinq nœuds (A–E) participant au consensus recevant trois transactions : tx₁, tx₂, et tx₃. En raison de la latence réseau, leurs ordres locaux diffèrent :

As dans Aequitas, ces préférences créent un cycle de Condorcet. Mais au lieu d’attendre que tout le cycle soit résolu, Themis maintient le système en mouvement en utilisant une méthode appelée dégroupage par lots. Elle identifie toutes les transactions faisant partie du cycle et les regroupe en un seul ensemble, appelé composante fortement connexe (SCC). Dans ce cas, les trois transactions appartiennent à la même SCC, que Themis sort en tant que lot en cours, nommé Lot B₁ = {tx₁, tx₂, tx₃}.

En faisant cela, Themis permet au réseau de continuer à traiter de nouvelles transactions même si l’ordre interne du Lot B₁ est encore en cours de finalisation. Cela garantit la vivacité du système et évite le blocage.

Vue d’ensemble :

L’idée d’une justice parfaite dans l’ordre des transactions peut sembler simple. Celui dont la transaction atteint le réseau en premier doit être traité en premier. Cependant, comme le montre le paradoxe de Condorcet, cet idéal ne peut pas tenir dans des systèmes distribués réels. Différents nœuds voient les transactions dans des ordres différents, et lorsque ces vues entrent en conflit, aucun protocole ne peut construire une séquence unique et « correcte » sans compromis.

Hashgraph de Hedera a tenté d’approcher cet idéal avec des timestamps médian, mais cette approche repose davantage sur la confiance que sur la preuve. Un seul participant malhonnête peut fausser la médiane et inverser l’ordre des transactions, révélant que le « timestamping équitable » n’est pas réellement équitable.

Les protocoles comme Aequitas et Themis avancent dans la réflexion en reconnaissant ce qui peut et ne peut pas être réalisé. Au lieu de poursuivre l’impossible, ils redéfinissent la justice de manière à préserver l’intégrité de l’ordre dans des conditions réseau réelles. Ce qui en ressort n’est pas un rejet de la justice, mais son évolution. Cette évolution trace une ligne claire entre justice perçue et justice vérifiable. Elle montre que l’intégrité réelle de l’ordre des transactions dans les systèmes décentralisés ne peut pas dépendre de la réputation, de la confiance des validateurs ou du contrôle permissionné. Elle doit provenir d’une vérification cryptographique intégrée au protocole lui-même.

Cet article ne contient pas de conseils ou recommandations en investissement. Chaque décision d’investissement ou de trading comporte des risques, et les lecteurs doivent effectuer leurs propres recherches avant de prendre une décision.

Cet article a une vocation informative générale et ne doit pas être considéré comme un conseil juridique ou en investissement. Les opinions, pensées et points de vue exprimés ici sont uniquement ceux de l’auteur et ne reflètent pas nécessairement ceux de Cointelegraph.

Cointelegraph ne cautionne pas le contenu de cet article ni aucun produit mentionné. Les lecteurs doivent faire leurs propres recherches avant d’agir concernant un produit ou une société mentionnée, et assumer l’entière responsabilité de leurs décisions.