MonadBFT : un algorithme de consensus super-scalable

Monad est une blockchain de couche primaire totalement compatible avec la machine virtuelle d’Ethereum ou EVM. Elle offre un excellent compromis entre décentralisation et scalabilité. Dans cet article, nous allons étudier son algorithme de consensus : MonadBFT. C’est l’une des briques techniques lui permettant d’obtenir un haut débit de transactions, et une scalabilité extrême.

Monad eT les algorithmes BFT

L’algorithme de consensus MonadBFT entre, comme son nom l’indique, dans la catégorie des BFT, pour Byzantine Fault Tolerance ou « tolérant aux fautes byzantines ». Pour rappel, ce type de consensus permet de s’accorder sur l’état d’un système distribué en présence d’une certaine quantité de nœuds défaillants, corrompus voire malicieux, appelés « byzantins » en référence au célèbre théorème éponyme.

Cette tolérance est exprimée en fraction : un algorithme BFT ou PBFT permet de tolérer jusqu’à un tiers d’acteurs byzantins. Il existe une grande variété de consensus BFT, adaptés à différentes conditions réseau (synchronie, asynchronie, ou synchronie partielle).

L’un des mécanismes de ce type les plus connus dans l’industrie blockchain est HotStuff. Il fut tout d’abord développé pour Libra/Diem, la blockchain de Meta. Bien que ce produit ne soit jamais sorti sur le marché, HotStuff fut repris et amélioré par de nombreux chercheurs et développeurs de couches primaires.

C’est le cas de l’équipe de développement de Monad, qui s’est appuyée sur plusieurs améliorations dérivées de HotStuff pour concevoir MonadBFT.

Synchronie

Tout d’abord, il s’agit d’un algorithme partiellement synchrone. En d’autres termes, le délai des messages (en l’occurrence les transactions) au sein du système est variable mais borné. Le réseau peut donc fonctionner de manière asynchrone, mais finit toujours par être synchronisé après un temps fini. Il faut donc obtenir un consensus sur l’ordonnancement des transactions effectuées au sein du réseau, afin de mettre à jour le registre.

Avant d’entrer dans les détails de son fonctionnement, il nous faut évoquer ses caractéristiques principales :

• MonadBFT fonctionne grâce à la preuve d’enjeu – Proof-of-Stake ou PoS ;
• Le temps de bloc est d’une seconde ;
• La finalisation des transactions est achevée à chaque bloc créé. Une fois un bloc relié à la chaîne, il est impossible de revenir en arrière.

Chaque nœud validateur a un poids dépendant de son stake. Pour simplifier ce qui suit, nous partons du principe que chaque validateur a un stake identique. Le réseau est composé de n = 3f + 1 nœuds, f étant le nombre maximal de nœuds byzantins.

Fonctionnement de MonadBFT

On peut décomposer le processus de l’algorithme de consensus MonadBFT en deux phases. À l’instar de Diem4, c’est une version améliorée de HotStuff, qui en comporte trois. C’est un algorithme dit leader-based, c’est-à-dire qu’un nœud, le leader, est sélectionné à chaque ronde pour produire un bloc.

Proposition du bloc

Tout d’abord, le leader envoie un nouveau bloc aux autres validateurs. Il est accompagné soit d’un certificat de quorum (QC) soit d’un certificat de timeout (TC) qui concerne le bloc précédent. Vous allez comprendre la fonction de ces certificats ci-dessous.

Les validateurs vont ensuite vérifier que le bloc suit bien les règles du protocole et voter « oui » le cas échéant. Ces votes sont ensuite envoyés au leader pour la ronde suivante. Le leader va alors produire un certificat de quorum, en agrégeant les signatures de 2f + 1 validateurs. On parle ici de communication linéaire (cas « normal » ) : le leader envoie un bloc aux validateurs, qui envoient ensuite leurs votes directement au prochain leader.

Dans le cas d’un délai (timeout), un validateur ne recevant pas de bloc durant la période temporelle impartie diffuse un message signé de timeout à tous ses pairs. Ce message inclut également le certificat de quorum le plus élevé qu’il a observé. Dans ce cas, on parle de communication quadratique. Dans le cas où un validateur quelconque accumule 2f + 1 messages d’expiration, il les assemble pour produire un certificat d’expiration – timeout certificate ou TC. Ce certificat sera ensuite envoyé au prochain leader.

Finalisation

Pour la ronde k, chaque validateur finalise le bloc lorsqu’il reçoit un certificat de quorum pour le bloc k + 1. Le processus dans le cas commun peut donc être décomposé plus finement ainsi :

• Alice, leader de la ronde k, envoie un nouveau bloc à tous les validateurs, accompagné d’un QC ou d’un TC.
• Si 2f + 1 validateurs votent « oui » pour ce bloc et envoient leurs votes à Bob (leader de la ronde k + 1) alors le bloc k + 1 sera accompagné d’un QC pour la ronde k. Ce QC n’est cependant pas suffisant pour que Carole (validateur) soit sûre que le bloc k est bien relié à la chaîne. En effet, Bob pourrait être corrompu, et n’avoir envoyé ce bloc qu’à elle seule. En l’état, elle peut seulement voter pour le bloc k + 1 et l’envoyer à Charlie, leader de la ronde k + 2.
• Si 2f + 1 validateurs votent « oui » pour le bloc k + 1, alors Charlie produit un QC pour la ronde k + 1, et produit un bloc pour la ronde k + 2. Dès que Carole reçoit ce bloc, elle sait que le bloc de la ronde k produit par Alice est finalisé.

Comportement malicieux de Bob

Si Bob a envoyé un bloc invalide pour la ronde k + 1, ou qu’il a envoyé son bloc à moins de 2f + 1 validateurs, alors au moins f + 1 validateurs vont envoyer un message d’expiration (timeout) à leurs pairs (qui ne sont pas byzantins). Ainsi, au moins un des validateurs produira un message d’expiration pour la ronde k + 1. Charlie, le leader de la ronde k +2, produira alors un certificat d’expiration pour la ronde k + 1 avec sa proposition de bloc.

Cette procédure est appelée 2-chain commit rule (règle d’engagement pour deux chaînes) car dès qu’un validateur observe deux blocs certifiés B et B’, il peut choisir d’engager B et tous ses blocs parents sur la chaîne.

Ce mécanisme de secours (fallback) en cas de faute byzantine est une amélioration par rapport à la première version de Hotstuff.

Signatures à seuil

Afin de produire les certificats (QC et TC), MonadBFT utilise les signatures à seuil pour agréger les votes des validateurs. Plus précisément, il s’agit de signatures Boneh-Lynn-Shacham (BLS). Ce schéma d’agrégation de signatures est assez lent, c’est pourquoi MonadBFT ne l’utilise que pour les votes et les timeouts.

La validation de l’intégrité et de l’authenticité des messages repose sur les signatures sur courbes elliptiques (ECDSA), faciles à construire et à vérifier. Leur taille varie cependant de façon linéaire avec le nombre de signataires. Cela pose donc des problèmes de scalabilité pour produire les certificats, c’est pourquoi le schéma BLS est privilégié dans ce cas.

Le mempool de Monad

Sur Monad, le memory pool (l’espace mémoire dédié aux transactions en attente) est partagé entre les validateurs, jusqu’à la finalisation des transactions. Afin de diffuser les transactions en attente d’un mempool à celui d’un autre validateur, MonadBFT utilise le codage d’effacement.

Cette technique permet d’utiliser une fonction mathématique – la transformation de Fourier rapide – pour décrire un ensemble de chiffres, et retrouver ceux qui sont perdus. Elle est notamment employée pour corriger les erreurs de gravure de CD-Rom. Dans le cas de Monad, il s’agit d’améliorer l’efficacité du système. Cela permet de diffuser un arbre contenant les transactions en attente plus rapidement vers le mempool des autres validateurs.

Hachage des transactions

Toujours pour des raisons d’efficacité et de rapidité, les propositions de bloc des leaders ne comportent pas les transactions, mais seulement leur hash. Un bloc contenant un grand nombre de transactions serait lourd, et prendrait beaucoup de bande passante. Ainsi, les blocs ne contiennent que les hashes référençant les transactions, d’une taille de 32 octets. Il faut donc que tous les memory pools des validateurs contiennent les transactions concernées.

Exécution différée

Sur Monad, à l’instar de certaines blockchains modulaires comme Celestia, la couche de consensus est découplée de la couche d’exécution.

Concrètement, cela signifie que lorsque le consensus est atteint quant à l’état du registre, le nœud leader ou les validateurs n’ont pas encore exécuté les transactions. Le leader se contente de proposer un ordonnancement des transactions, sans connaître la racine d’état résultante. Il en va de même pour les validateurs qui reçoivent le bloc. C’est l’une des clés de voûte faisant de Monad une couche primaire très rapide et hautement scalable.

Les limitations d’Ethereum

Sur Ethereum, l’exécution est nécessaire pour obtenir un consensus. En effet, les nœuds doivent s’accorder à la fois sur les transactions incluses dans un bloc, mais aussi sur l’état résultant de leur exécution. Concrètement, le leader doit préalablement exécuter toutes les transactions du bloc avant de le proposer, et les validateurs doivent toutes les exécuter avant de voter.

C’est évidemment un mécanisme qui s’avère coûteux en temps et en gas. Les transactions doivent en effet être exécutées deux fois, tout en laissant le temps aux nœuds de communiquer plusieurs fois entre eux pour atteindre le consensus.

Ordonnancement déterministe

Sur Monad, tout part de l’idée qu’une fois les transactions ordonnancées, l’état résultant du système sera parfaitement déterminé. L’exécution est nécessaire pour obtenir cet état, mais la « réalité » de l’état est déjà déterminée par l’ordonnancement du leader.

Les nœuds de Monad n’ont ainsi pas besoin d’exécuter préalablement les transactions avant d’atteindre un consensus. Ils se contentent de s’accorder sur l’ordonnancement officiel au sein du bloc. Ils peuvent donc exécuter les transactions indépendamment les uns des autres pour le bloc n, tout en commençant la ronde de consensus pour le bloc n + 1. Cela présente deux avantages :

• Le budget en gas correspond au temps complet de production du bloc ;
• Le système est beaucoup plus tolérant aux variations de temps de calcul, car il suffit de suivre le consensus « en moyenne ».

On parle donc de « pipelined algorithm ».

Delayed Merkle Roots

Sur Ethereum, la réplication de l’état du système est assurée de façon stricte par la jonction entre consensus et exécution. Les nœuds exécutent les transactions, et s’accordent sur l’état du système par super-majorité. Cependant, cela limite fortement le débit du système.

Dans le cas de MonadBFT, deux problèmes pourraient se produire quant à la réplication de l’état du système :

• Un nœud malicieux omet volontairement des transactions, ou change arbitrairement des variables d’état ;
• Un nœud produit une erreur d’exécution.

C’est pour cela que les blocs de Monad sont accompagnés d’une racine de Merkle « délayée ». Pour rappel, un arbre de Merkle est une structure de données permettant de résumer un ensemble beaucoup plus grand. Grâce aux fonctions de hachage, seule sa racine suffit à prouver l’intégrité de l’ensemble.

Le délai en blocs peut être paramétré, il est fixé à 10. De la sorte, lorsque le système arrive à un consensus pour le bloc N, l’état au bloc N – D est déjà inclus dans une racine de Merkle M. Tous les logiciels clients légers peuvent envoyer des requêtes aux nœuds complets. Ils peuvent vérifier ainsi les preuves de Merkle pour les variables d’état du bloc N – D.

Un nœud commettant une erreur d’exécution pour le bloc N – D échouera donc à atteindre le consensus pour le bloc N. Il y aura alors un retour en arrière pour ce nœud, jusqu’au bloc N – D – 1. Il devra réexécuter les transactions du bloc N – D, puis celles du bloc N – D + 1, N – D + 2, etc.

Finalité des transactions

La finalisation des transactions sur Monad s’effectue donc en un bloc, soit 1 seconde. L’exécution quant à elle aura un temps de latence jugé inférieur à une seconde.

Il est impossible de réorganiser la chaîne, il n’y a donc pas de risque d’attaque de super-majorité. L’exécution intervient également chez les nœuds complets dans un délai très court. Cela permet à quiconque en déploie un de connaître le résultat d’une transaction très rapidement. Quant aux clients légers, ils peuvent requêter les nœuds complets afin de récupérer les preuves de Merkle et s’assurer du solde d’un compte. Le cas échéant, le délai sera de 10 blocs, comme expliqué ci-dessus.

Les frais sur Monad

La parallélisation du consensus et de l’exécution pourrait créer un vecteur de déni de service. Il s’agit du cas où les nœuds incluent une transaction provenant d’un compte n’ayant pas le gas nécessaire, car ils ne sont pas à jour quant à l’état du système.

Coût de transport

Les transactions nécessitent des frais supplémentaires, indépendamment du coût d’exécution, appelées « coût de transport ». Ils sont minimes, mais servent à prévenir le spam, tout en reflétant les coûts d’utilisation du réseau.

Dans le cas où une transaction ne comporte pas assez de gas pour couvrir ses coûts d’exécution, elle échouera. En outre, son coût d’exécution sera absorbé jusqu’au point de rupture. Il en est de même sur Ethereum : c’est nécessaire pour prévenir les vecteurs de déni de service.

Solde de réserve

Sur Monad, chaque adresse comporte deux soldes :

• Le solde de réserve utilisé pour couvrir les coûts de transport ;
• Le solde d’exécution servant à payer les coûts d’exécution de la transaction.

Les frais de transport sont tout d’abord déduits du solde de réserve lorsque la transaction est incluse dans un bloc. Ils sont ensuite déduits du solde d’exécution au moment de l’exécution, puis remboursés sur le solde de réserve, une fois le délai de blocs D (10) écoulé.

Le solde de réserve diminue donc en temps réel selon les transactions effectuées, pour s’assurer que les nœuds n’incluent dans les blocs que les transactions qui ont été payées. Chaque compte peut paramétrer ce solde. Par défaut, il s’agit d’un grand multiple du coût de transport (*200). Cela permet d’assurer aux utilisateurs qu’ils pourront envoyer un nombre important de transactions sans problème.

Monad : parallélisER les tâches pour un débit maximal

Vous savez désormais tout sur l’algorithme de consensus MonadBFT. Inspiré par DiemBFT, son fonctionnement en 2 phases et la séparation entre consensus et exécution des transactions change la donne en termes de débit et de scalabilité. Monad est ainsi une plateforme blockchain de couche primaire pouvant traiter jusqu’à 10000 transactions par seconde !

Dans l’article suivant, nous vous présenterons d’autres techniques de parallélisation au niveau de sa couche d’exécution. En attendant, pour en savoir plus, n’hésitez pas à consulter le site web officiel de Monad, et à rejoindre ses différents réseaux sociaux. Stay tuned !

• Twitter
• Discord
• Telegram