💻 computer science

Fast Deterministically Safe Proof-of-Work Consensus

Ce document présente Sieve-MMR, le premier protocole de blockchain entièrement sans permission qui atteint à la fois une sécurité déterministe et une latence attendue constante sans mécanismes externes en adaptant un protocole de Preuve d'Enjeu au cadre de la Preuve de Travail et en employant un nouvel algorithme de Tamis pour atténuer les attaques de voyage dans le temps.

Auteurs originaux : Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal

Publié 2026-06-04

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un registre numérique massif et mondial où n'importe qui peut s'inscrire ou partir à tout moment. C'est le monde des blockchains sans permission (comme Bitcoin). L'objectif est que tout le monde se mette d'accord sur l'ordre des transactions sans qu'un patron ne leur dise quoi faire.

Pendant longtemps, ces systèmes ont eu deux manières principales de fonctionner, toutes deux présentant de graves défauts :

La Preuve d'Enjeu (Proof of Stake - PoS) : Vous verrouillez de l'argent pour voter. Le problème ? Un attaquant peut acheter d'anciens comptes appartenant à des personnes parties il y a des années, ce qui permet de réécrire l'histoire à moindre coût. C'est ce qu'on appelle une « attaque à longue portée » (Long-Range Attack).
La Preuve de Travail (Proof of Work - PoW) : Vous résolvez des problèmes mathématiques complexes pour voter. Le problème ? Soit c'est incroyablement lent, soit cela repose sur une sécurité « probabiliste » (ce qui signifie qu'il existe une chance infime, mais non nulle, qu'un attaquant ait de la chance et puisse réécrire l'histoire).

Les auteurs de ce document, Sieve-MMR, ont construit un nouveau système qui prétend être le meilleur des deux mondes : il est rapide, sécurisé contre la réécriture de l'histoire, et n'a pas besoin d'aide extérieure (comme le consensus social ou des points de contrôle) pour être sûr.

Voici comment ils ont procédé, en utilisant des analogies de la vie quotidienne.

L'idée principale : Découpler le « Vote » du « Contrôle d'identité »

Considérez un protocole de consensus comme une réunion de quartier.

La Logique de Consensus (MMR) : C'est le processus de vote proprement dit. « Qui a le plus de voix ? Mettons-nous d'accord là-dessus. » Cette partie est rapide et intelligente, mais elle a été conçue à l'origine pour une ville où chaque personne possède une carte d'identité fixe et où tout le monde sait qui est présent.
Le Problème du Sans-Permission : Dans un système sans permission, les gens peuvent s'inscrire ou partir instantanément. Pire encore, un acteur malveillant peut prétendre être une personne qui a quitté la ville il y a 10 ans et ramener de vieux votes pour semer la confusion lors de la réunion actuelle. C'est l'« Attaque par Voyage dans le Temps » (Time-Travel Attack).

Les auteurs ont réalisé qu'ils pouvaient prendre la logique de vote rapide et intelligente (MMR) et l'envelopper dans une nouvelle couche de « garde de sécurité » (Sieve) qui gère le chaos des arrivées et des départs ainsi que les voyages dans le temps.

Le Vilain : Le Voyageur Temporel

Dans une réunion normale, si vous parlez, vous parlez maintenant.
Dans une blockchain sans permission, un acteur malveillant (nœud byzantin) peut faire quelque chose de sournois :

Il génère un tas de « votes » (problèmes mathématiques) en 2020.
Il les garde en réserve.
En 2026, il déverse tous ces vieux votes dans la réunion actuelle, en prétendant qu'ils viennent d'être exprimés à l'instant même.

Parce que le système voit un afflux de « votes » provenant du passé, il est confus quant à savoir qui détient réellement la majorité aujourd'hui. Cela brise la sécurité de la réunion.

Le Héros : Le Sieve (Le Tamis)

Pour arrêter ces voyageurs temporels, les auteurs ont inventé un nouveau filtre appelé Sieve. Considérez cela comme un videur de boîte de nuit qui vérifie les pièces d'identité, mais avec une nuance.

Comment fonctionne le Sieve :

Le Coffre (Coffer) : Chaque fois qu'un nœud envoie un message (un vote), il doit inclure un « coffre » (un sac) contenant les messages qu'il a reçus des messages du tour précédent.
La Preuve de Travail (DPoW) : Pour envoyer un message, vous devez résoudre un problème mathématique. Le temps nécessaire pour le résoudre est enregistré.
Le Filtre : Lorsque le Sieve reçoit un tas de messages, il examine les « coffres ».
- Si un message prétend provenir du « Tour 5 », mais que son coffre ne contient pas les messages du « Tour 4 » qui viennent d'être générés par des personnes honnêtes, le Sieve sait qu'il est faux.
- Analogie : Imaginez que quelqu'un prétende arriver à une fête en 2026. Mais quand vous regardez son album photo, les photos sont de 2020, et il n'a aucune photo des décorations de la fête installées hier. Le videur (Sieve) dit : « Vous êtes un voyageur temporel. Vous ne pouvez pas entrer. »

Le Sieve filtre ces messages « antiques », garantissant que seuls les messages générés récemment par des personnes qui étaient présentes récemment soient comptabilisés.

Les deux modes du Sieve

Le Sieve possède deux modes de fonctionnement, selon votre ancienneté à la fête :

L'Online-Sieve (L'Invité Régulier) : Si vous êtes à la fête depuis un certain temps, vous avez une liste des messages valides du dernier tour. Vous vérifiez simplement si les nouveaux messages correspondent à cette liste. C'est rapide et facile.
Le Bootstrap-Sieve (Le Nouvel Invité) : Si vous venez de rejoindre la fête, vous n'avez pas l'historique. Vous devez examiner l'intégralité de l'histoire de la fête depuis le début, construire une carte géante (un DAG) de qui a parlé à qui, et déterminer quels messages sont réels et quels messages sont des faux voyages dans le temps.
- Le revers de la médaille : Ce processus de « Nouvel Invité » est très lourd sur le plan computationnel (c'est comme résoudre un puzzle massif). Le document admet que c'est un obstacle pour une utilisation réelle actuellement, mais cela prouve que le concept fonctionne.

Le Résultat : Sieve-MMR

En superposant le Sieve (le garde de sécurité) sous le MMR (la logique de vote rapide), ils ont créé le Sieve-MMR.

Sécurité Déterministe : Contrairement à Bitcoin, où vous devez attendre et espérer que l'attaquant ne soit pas chanceux, ce système garantit la sécurité. Si les règles sont suivies, l'histoire ne peut pas être modifiée.
Latence Constante : C'est rapide. Le document affirme que les transactions peuvent être finalisées en un temps prévisible et court (environ 7 étapes), plutôt que d'attendre une « confirmation probabiliste ».
Pas d'Attaques à Longue Portée : Parce que le Sieve filtre les anciens messages, un attaquant ne peut pas acheter d'anciennes clés pour réécrire l'histoire.
Pas d'Aide Extérieure : Il n'a pas besoin d'un « consensus social » ou d'un point de contrôle centralisé pour être sûr. Il le fait tout seul, mathématiquement.

Les Limites (Les petits caractères)

Le document est honnête sur ce qu'il ne peut pas faire encore :

Bande passante : Cela nécessite que tout le monde communique avec tout le monde à chaque tour. Si le réseau devient immense, les embouteillages deviennent énormes (mise à l'échelle quadratique).
Le problème du « Nouvel Invité » : Le Bootstrap-Sieve (pour les nouveaux nœuds) nécessite de résoudre un problème mathématique très difficile sur l'ensemble de l'historique de la chaîne. C'est actuellement plus une preuve théorique qu'un outil prêt à l'emploi pour les nouveaux utilisateurs.
Réseau Synchrone : Il suppose que les messages arrivent rapidement et dans l'ordre, ce qui est une idéalisation du monde réel de l'internet, souvent désordonné.

Résumé

Le document présente le Sieve-MMR, une nouvelle façon de gérer une blockchain qui combine la vitesse et la certitude des systèmes de vote modernes avec la sécurité de la Preuve de Travail. Il résout le problème de l'« Attaque par Voyage dans le Temps » en utilisant un mécanisme de filtrage intelligent (le Sieve) qui garantit que seuls les votes frais et récents sont comptés, empêant ainsi les attaquants d'utiliser de vieilles données pour confondre le système. Bien qu'il doive franchir certains obstacles pratiques avant de pouvoir remplacer Bitcoin ou Ethereum, il prouve qu'une blockchain sans permission, rapide et parfaitement sécurisée, est théoriquement possible.

Résumé technique : Sieve-MMR, un protocole de consensus Proof-of-Work à sécurité déterministe et latence rapide

Problématique

Les blockchains sans permission font face à un compromis fondamental entre garanties de sécurité et performance. Les protocoles existants se répartissent généralement en deux catégories, le Proof-of-Stake (PoS) et le Proof-of-Work (PoW), qui souffrent tous deux de vulnérabilités spécifiques :

Vulnérabilités du PoS : Les protocoles PoS sont sensibles aux attaques de longue portée (long-range attacks), où des adversaires achètent des clés historiques pour fabriquer des historiques d'exécution alternatifs à faible coût. La défense contre ces attaques nécessite généralement des mécanismes externes (par exemple, un consensus social ou des points de contrôle sécurisés), ce qui mine la nature autonome du système.
Vulnérabilités du PoW : Les protocoles PoW traditionnels (comme Bitcoin) évitent les attaques de longue portée mais reposent sur des garanties de sécurité probabilistes. Cela laisse la possibilité qu'un attaquant réussisse à créer un historique alternatif. De plus, atteindre une sécurité déterministe dans le PoW a historiquement entraîné des protocoles excessivement lents (par exemple, une latence exponentielle) ou a nécessité des modèles restrictifs.

Le défi central abordé par cet article est l'« attaque de voyage dans le temps » (time-travel attack). Dans un environnement totalement sans permission, les protocoles à disponibilité dynamique (qui permettent aux nœuds de rejoindre ou de quitter le réseau) reposent sur des arguments d'intersection de quorum. Cependant, dans un environnement sans permission, des nœuds byzantins peuvent générer des messages dans un passé lointain, les stocker, puis les diffuser plus tard pour fausser le quorum perçu de nœuds corrects dans le présent. Ce « voyage dans le temps » invalide la logique d'intersection de quorum, rendant les protocoles standards à disponibilité dynamique non sécurisés sans hypothèses de confiance externes.

Méthodologie : Sieve-MMR

Les auteurs proposent Sieve-MMR, le premier protocole de diffusion à ordre total (TOB) Proof-of-Work entièrement sans permission qui atteint une sécurité déterministe et une latence constante attendue sans dépendre de mécanismes externes. Le système est construit sur deux couches distinctes :

1. La couche inférieure : Sieve et TTRB

La principale contribution technique est Sieve, un nouvel algorithme qui implémente une nouvelle primitive de diffusion appelée Time-Travel-Resilient Broadcast (TTRB).

Objectif : Le TTRB garantit que les messages livrés dans un tour donné ont été générés dans le tour immédiatement précédent, filtrant ainsi les messages « antiques » (voyageurs dans le temps).
Mécanisme : Sieve utilise une primitive de Proof-of-Work déterministe (DPoW). Il construit un graphe acyclique dirigé (DAG) d'évaluations DPoW où les messages sont des sommets et les arêtes représentent l'inclusion dans des « coffres » (coffers) (ensembles de messages du tour précédent inclus dans la charge utile d'un nouveau message).
Politiques de filtrage : Sieve emploie deux stratégies de filtrage pour élaguer le DAG et identifier les messages valides :
- Online-Sieve : Utilisé par les nœuds qui étaient actifs lors de l'étape précédente. Il filtre efficacement les messages en vérifiant si l'intersection du coffre d'un message et de l'ensemble des messages valides de deux étapes antérieures dépasse un seuil pondéré ( $1-\rho$ ).
- Bootstrap-Sieve : Utilisé par les nœuds rejoignant le système ou se rétablissant après une inactivité. Il effectue une analyse plus intensive sur le plan computationnel de l'ensemble de l'historique du DAG pour reconstruire l'ensemble des messages valides de l'étape précédente, garantissant que le nœud n'accepte pas de messages antiques qui pourraient fausser sa vision du quorum.
Hypothèses : Sieve suppose un réseau synchrone et que les adversaires contrôlent moins de la moitié ( $\rho \le 1/2$ ) de la puissance de calcul DPoW totale sur tout intervalle suffisamment long.

2. La couche supérieure : MMR

La logique de consensus est dérivée du protocole MMR (Malkhi et al.), un protocole PoS rapide et déterministement sûr conçu pour le modèle de « disponibilité dynamique ».

Intégration : En superposant MMR sur Sieve, les auteurs découplent la logique de consensus de la logique de participation sans permission. Sieve fournit les garanties de livraison de messages (TTRB) dont MMR a besoin pour maintenir l'intersection de quorum.
Élection de leader : Sieve-MMR utilise un composant d'élection de leader probabiliste basé sur l'oracle aléatoire DPoW pour déterminer sur quelle chaîne voter ou s'engager à chaque étape.

Principales contributions

Diffusion résiliente au voyage dans le temps (TTRB) : Une nouvelle abstraction de diffusion qui garantit une couche de messagerie immunisée contre les attaques de voyage dans le temps, assurant que les messages livrés sont causalement cohérents avec le tour actuel.
Algorithme Sieve : Un nouveau protocole implémentant le TTRB à l'aide d'une primitive DPoW boîte noire. Il introduit le concept de « coffres » (coffers) et d'élagage basé sur un DAG pour distinguer les messages actuels des messages antiques.
Protocole Sieve-MMR : Le premier protocole TOB entièrement sans permission qui atteint :
- Sécurité déterministe : Aucun mode de défaillance probabiliste concernant la sécurité (dans le modèle Dolev-Yao).
- Latence constante attendue : Les transactions sont validées en un nombre constant d'étapes (7 étapes attendues, 3 étapes dans le meilleur des cas).
- Aucune confiance externe : Il ne repose ni sur le consensus social ni sur des points de contrôle externes pour prévenir les attaques de longue portée.

Résultats et garanties

Sécurité : Sieve-MMR garantit la cohérence (tous les nœuds corrects valident des chaînes compatibles) et la progression (les chaînes finissent par croître). Il hérite de la capacité de MMR à tolérer un adversaire borné à $1/3$ dans la couche de consensus, tandis que Sieve lui-même tolère un adversaire borné à $1/2$ dans la couche de messagerie.
Latence : Le protocole atteint une latence constante attendue, une amélioration significative par rapport aux protocoles PoW déterministes précédents qui souffraient d'une latence exponentielle par rapport au nombre de participants.
Modèle de sécurité : Les affirmations de sécurité tiennent dans un modèle de type Dolev-Yao où les adversaires ne peuvent pas briser les primitives cryptographiques ou deviner les messages. Le protocole suppose un réseau synchrone et repose sur une diffusion de type all-to-all, entraînant des coûts de bande passante quadratiques par rapport au nombre de nœuds actifs.

Signification et limites

L'article positionne Sieve-MMR comme une étape théorique importante vers un consensus PoW pratique, rapide et sécurisé. Il démontre que la vulnérabilité au « voyage dans le temps », auparavant considérée comme une barrière fondamentale pour porter la latence faible aux contextes sans permission, peut être atténuée grâce au mécanisme Sieve.

Cependant, les auteurs font preuve de modestie quant au déploiement pratique immédiat, notant plusieurs obstacles :

Complexité computationnelle : La phase Bootstrap-Sieve nécessite de résoudre un problème de temps exponentiel sur l'historique d'exécution du protocole. Bien que les nœuds ne soient pas tenus de le faire dans un temps fixe, ils doivent le faire avant leur participation active, ce qui constitue une barrière importante pour les nouveaux nœuds.
Hypothèses réseau : Le protocole suppose un réseau synchrone et une communication all-to-all, ce qui peut ne pas passer à l'échelle efficacement dans des environnements internet asynchrones réels.
Surcharge de vérification : Vérifier les évaluations DPoW pour tous les messages peut être coûteux en termes de calcul, bien que les auteurs suggèrent la vérification par lots et les optimisations cryptographiques (comme les preuves à divulgation nulle de connaissance ou zero-knowledge proofs) comme remèdes futurs potentiels.

En conclusion, Sieve-MMR fournit un pont théorique entre les modèles de disponibilité dynamique et les modèles entièrement sans permission, prouvant que la sécurité déterministe et la latence constante sont réalisables dans un cadre PoW sans permission sans confiance externe, à condition que les contraintes de calcul et de réseau puissent être adressées.