💻 computer science

Distance-Preserving Digests: A Primitive for BFT Consensus

Ce document présente les « résumés préservant la distance », une primitive utilisant des sommes vectorielles commutatives plutôt que des hachages résistants aux collisions pour permettre une finalité efficace en un seul tour et un consensus BFT évolutif à structure arborescente, en autorisant les validateurs à mesurer les désaccords d'état et à vérifier la cohérence sans synchronisation complète de l'état.

Auteurs originaux : Ryan Patrick Mercier

Publié 2026-05-18

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ryan Patrick Mercier

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 groupe massif de personnes tentant de s'accorder sur une seule liste de règles pour un jeu. Dans le monde de la blockchain et des réseaux sécurisés, ce groupe est appelé un « protocole de consensus ». Pendant des décennies, la méthode standard pour vérifier si tout le monde est d'accord consistait à comparer les listes de deux personnes en les transformant en un code unique et incassable (un « hachage »).

Voici le problème avec cette ancienne méthode : Elle détruit la nuance.

Si la Personne A a 19 éléments corrects sur 20, et que la Personne B a les 20 éléments corrects, l'ancienne méthode indique que leurs codes sont complètement différents. C'est comme dire qu'une liste avec une seule faute de frappe est tout aussi « fausse » qu'une liste sans aucun élément. Parce que le système ne peut pas distinguer entre « presque parfait » et « complètement cassé », il force tout le monde à s'arrêter, à renvoyer leurs listes entières et à attendre une correspondance parfaite avant de pouvoir avancer. C'est lent, coûteux et nécessite de très grands groupes de personnes pour être sûr.

Ce papier introduit un nouvel outil appelé Résumés préservant la distance. Imaginez-le comme un système de « correspondance floue » qui permet au groupe de voir à quel point ils sont proches de l'accord, plutôt que de simplement demander « Sommes-nous identiques ? ».

L'idée centrale : L'analogie de la « somme vectorielle »

Au lieu de transformer une liste de transactions en un code unique et rigide, le papier suggère de transformer chaque transaction en une petite flèche (un vecteur) dans un espace à 8 dimensions.

L'ancienne méthode : Si vous manquez un élément, votre code change complètement.
La nouvelle méthode : Si vous manquez un élément, votre « flèche » ne s'éloigne que très légèrement du centre. Si vous manquez dix éléments, elle s'éloigne davantage.

Cela permet au système de mesurer la distance.

Distance = 0 : Tout le monde a exactement la même liste.
Distance = Petite : Tout le monde manque un ou deux éléments (peut-être à cause d'une connexion internet lente).
Distance = Énorme : Quelqu'un ment ou a une liste complètement différente.

Trois grandes améliorations

Le papier affirme que ce simple changement résout trois maux majeurs dans la conception des blockchains :

1. La « voie rapide » pour l'accord

Ancienne méthode : Même si tout le monde est parfaitement d'accord, le système doit exécuter trois tours lents de vote pour être sûr.
Nouvelle méthode : Parce que le système peut voir que tout le monde est très proche (la distance est proche de zéro), il peut instantanément dire : « D'accord, vous êtes tous d'accord ! » et finaliser la décision en un seul tour. C'est comme un enseignant qui voit qu'une classe est prête à 99 % et dit : « Super, passons à la suite », au lieu d'attendre un vote formel.

2. Des équipes plus petites et plus profondes

Ancienne méthode : Pour être sûr, les groupes (comités) devaient être énormes (par exemple, 128 personnes). Si un petit groupe avait même quelques menteurs, tout le groupe pouvait échouer.
Nouvelle méthode : Parce que le système peut repérer les menteurs par leur « distance » (ils seront loin de la moyenne du groupe), il peut les exclure immédiatement. Cela signifie que vous pouvez avoir des groupes beaucoup plus petits (par exemple, 10 personnes) et être toujours sûr. Vous pouvez également construire des « arbres » plus profonds de ces groupes, permettant au réseau de mieux s'adapter à la croissance.

3. Réparer le désordre inter-chaînes

Ancienne méthode : Lorsque deux parties différentes d'une blockchain doivent communiquer, elles doivent généralement envoyer un message pour chaque transaction individuelle pour vérifier si elles correspondent. C'est comme vérifier chaque brique individuelle de deux murs différents pour voir s'ils sont identiques.
Nouvelle méthode : Elles échangent simplement leurs « résumés de distance ». Si les résumés correspondent, tant mieux. S'ils ne correspondent pas, le système utilise un « filtre de Bloom » spécial (comme une liste de contrôle rapide) pour trouver exactement quelles briques sont différentes et ne corriger que celles-ci. Cela réduit le coût de communication de 99 % dans de nombreux cas.

Comment cela fonctionne (le processus en deux phases)

Le papier décrit un protocole appelé Proxima qui utilise cet outil en deux étapes :

Phase 1 (La vérification « floue ») : Tout le monde envoie son résumé. Le système calcule la distance. Si tout le monde est proche, il saute le reste et finalise immédiatement. Si certaines personnes sont loin, le système demande seulement à ces personnes spécifiques d'envoyer leurs données manquantes (en utilisant l'astuce du filtre de Bloom).
Phase 2 (La vérification « dure ») : Une fois le groupe aligné, tout le monde signe un certificat final et incassable. Cela garantit que même si quelqu'un a tenté de tromper le système lors de la Phase 1, il ne peut pas falsifier la signature finale.

Les résultats

Le papier compare ce nouveau système (Proxima) à la norme industrielle actuelle (HotStuff) :

Vitesse : Sur un seul cœur de processeur, Proxima est environ 20 fois plus rapide (0,9 seconde contre 18 secondes) car il saute les tours inutiles.
Efficacité : Avec 100 000 validateurs, Proxima envoie 2,2 fois moins de messages que l'ancien système.
Sécurité : Les mathématiques prouvent que tant que moins de 33 % du groupe est malveillant, le système ne peut pas être trompé pour accepter deux règles différentes en même temps.

La conclusion

Ce papier propose de remplacer un système de vérification « rigide, tout ou rien » par un système « flexible, mesurant la distance ». En réalisant que « presque juste » est en fait une information utile, le système peut aller plus vite, utiliser des équipes plus petites et communiquer beaucoup moins, tout en maintenant le même niveau élevé de sécurité.

Résumé Technique : Résumés Préservant la Distance pour le Consensus BFT

1. Énoncé du Problème

Les protocoles de consensus tolérants aux pannes byzantines (BFT), notamment HotStuff, PBFT et Ethereum 2.0, reposent sur des hachages résistants aux collisions (par exemple, SHA-256) pour comparer les états des validateurs. Bien qu'efficaces pour prévenir la contrefaçon, cette approche détruit l'information de « distance ». Si deux validateurs s'accordent sur 19 transactions sur 20, leurs hachages sont totalement sans rapport, indistinguables de ceux de validateurs ne partageant aucune transaction. Cette limitation impose trois contraintes structurelles à la littérature BFT :

Synchronisation d'État Obligatoire : Les validateurs doivent synchroniser intégralement leur état avant de voter, car les hachages ne peuvent mesurer un accord partiel.
Qualité de l'Accord Inmesurable : Les protocoles ne peuvent détecter un accord unanime que lorsque tous les tours de vote sont terminés, imposant des latences fixes multi-tours même dans des conditions idéales.
Comités Hiérarchiques de Grande Taille : Pour assurer la sécurité dans un consensus en structure arborescente, les groupes feuilles doivent être suffisamment grands (par exemple, 128 validateurs dans Ethereum) pour satisfaire indépendamment le seuil de tolérance byzantine $2N/3$ , limitant ainsi la profondeur de l'arbre et l'évolutivité.

2. Méthodologie : Résumés Préservant la Distance

L'article introduit une primitive appelée Résumés Préservant la Distance pour remplacer les hachages résistants aux collisions lors de la comparaison d'états. La construction implique :

Vectorisation : Chaque transaction est hachée à l'aide de SHA-512. La sortie de 64 octets est divisée en 8 segments.
Mappage de Coordonnées : Chaque segment est traité comme un entier non signé, réduit modulo 10 000, puis divisé par 10 000 pour produire une coordonnée dans l'intervalle $[0, 1)$ .
Somme Commutative : Le résumé d'un validateur pour un ensemble de transactions $T$ est la somme vectorielle $D(T) = \sum_{tx \in T} v(tx)$ dans un espace à 8 dimensions.

Cette primitive possède trois propriétés que les hachages ne possèdent pas :

Distance Proportionnelle : La distance euclidienne entre deux résumés est proportionnelle au nombre de transactions différentes.
Résumé Exact : La moyenne pondérée d'un groupe de résumés est une représentation exacte de l'état agrégé du groupe, permettant de résumer un groupe de validateurs en une seule valeur compacte (76 octets) sans perte d'information.
Identification de Différences d'Ensemble : Lorsque les résumés diffèrent, une différence de filtre de Bloom permet à l'agrégateur d'identifier exactement quelles transactions manquent dans la vue d'un validateur, permettant une synchronisation ciblée sans échange d'état complet.

3. Contributions Clés et Applications

L'article démontre trois applications principales de cette primitive au sein d'un nouveau protocole nommé Proxima :

A. Protocole BFT en Deux Phases (Proxima)

Proxima fonctionne en deux phases :

Phase 1 (Filtrage par Distance) : Les validateurs envoient des résumés et des filtres de Bloom à un agrégateur. L'agrégateur regroupe les validateurs dans un seuil de distance. Si la variance du groupe est proche de zéro (indiquant un accord élevé), le protocole émet un certificat de finalité en tour unique (chemin rapide). Sinon, il pousse les transactions manquantes via la différence de Bloom.
Phase 2 (Engagement) : Les membres du groupe signent le hachage du bloc en utilisant des signatures BLS. L'agrégateur produit une signature agrégée.
Résultat : Contrairement à HotStuff, qui nécessite trois tours indépendamment de l'accord, Proxima atteint une finalité en tour unique lorsque les validateurs s'accordent.

B. Consensus en Structure Arborescente avec Petits Groupes

Puisque le filtrage par distance opère au niveau individuel plutôt que d'exiger un BFT au niveau du groupe, Proxima permet un consensus hiérarchique avec de petits groupes (par exemple, 10 validateurs).

Mécanisme : Les leaders feuilles filtrent les validateurs byzantins (qui sont loin de la référence) et rapportent la moyenne pondérée des validateurs honnêtes.
Résultat : Cela élimine le besoin de grands comités (128 validateurs) pour assurer la sécurité, permettant des arbres plus profonds (5 niveaux contre 2–3 niveaux) et réduisant la complexité des messages.

C. Vérification de Cohérence Inter-Shard

Les résumés permettent une vérification à coût constant entre les shards.

Mécanisme : Les shards voisins échangent des résumés des transactions de la zone de chevauchement. Si la distance est nulle, les états correspondent. Si elle est non nulle, la différence de Bloom identifie les transactions divergentes spécifiques pour résolution.
Résultat : Cela remplace la coordination par transaction du Commit en Deux Phases (2PC) ou des chaînes de reçus, réduisant la surcharge inter-shard de 99 % par rapport au 2PC à des taux de propagation de 95 %.

4. Résultats et Évaluation

L'article évalue Proxima par rapport à HotStuff, PBFT et la structure de comité d'Ethereum en utilisant des simulations avec $N=100\,000$ validateurs et 30 % de pannes byzantines.

Complexité des Messages : Proxima Tree utilise 2,2 fois moins de messages que HotStuff. Il s'agit d'une propriété structurelle non affectée par le parallélisme, dérivée de l'exécution en deux phases, du pré-filtrage des nœuds byzantins et du routage arborescent avec des résumés compacts.
Latence :
- Cœur Unique : Proxima atteint une finalité sur un seul cœur en ~0,9 seconde (902 ms) contre ~18 secondes pour HotStuff. La structure arborescente distribue l'agrégation BLS, maintenant le traitement du chemin critique à un niveau bas (9,9 ms).
- Multi-Cœur : Bien que l'agrégation BLS multi-cœur réduise l'écart (HotStuff chute à ~940 ms, Proxima Flat à ~220 ms), l'arbre conserve un avantage en temps BLS du chemin critique car les nœuds feuilles traitent très peu de signatures.
Surcharge Inter-Shard : À 95 % de propagation, la vérification basée sur les résumés utilise 99 % de messages en moins que le 2PC et 95 % de moins que les approches basées sur les reçus (NEAR Nightshade).
Sécurité : La sécurité est prouvée indépendante du regroupement de la Phase 1. Moins de $N/3$ validateurs byzantins ne peuvent pas provoquer de finalisation conflictuelle. La Phase 1 peut exclure des validateurs honnêtes (risque de vivacité), mais cela est borné par l'inégalité de Hoeffding pour être négligeable ( $<10^{-9}$ à $N$ pratique).

5. Signification et Revendications

L'article affirme que les résumés préservant la distance éliminent les trois contraintes fondamentales imposées par le hachage résistant aux collisions dans le BFT. En permettant la mesure de la qualité de l'accord, la primitive permet :

Chemins Rapides Optimistes : Les protocoles peuvent finaliser en un tour lorsque le consensus est élevé.
Hiérarchies Évolutives : Les arbres de consensus peuvent utiliser de petits groupes (taille 10) et des structures profondes, car la sécurité est maintenue via le filtrage par distance plutôt que par vote par groupe.
Sharding Efficace : La cohérence inter-shard peut être vérifiée à un coût constant par paire de shards, évoluant avec la divergence réelle plutôt qu'avec le volume total de transactions.

Les auteurs soulignent que, bien que la primitive soit une application connue du hachage sensible à la localité (LSH) dans les structures de données, son application à l'accord byzantin est nouvelle. La sécurité du système repose sur des hypothèses cryptographiques standard (signatures BLS et SHA-512), le filtre de distance servant de mécanisme de vivacité et d'optimisation plutôt que de mécanisme de sécurité. L'article conclut que cette approche offre une amélioration générale pour tout protocole BFT comparant des états via des hachages.