Algorithme des Généraux Byzantins: Le Mode de Consensus des Blockchains Privées

Avec la question du défaut byzantin nous touchons au cœur des problématiques liées aux réseaux décentralisés reposant sur une blockchain.

Lorsque des ordinateurs sont organisés en réseau, il existe principalement deux types de défauts: le défaut d’un ordinateur pour des raisons purement matérielles (“Crash fail”) ou le fait qu’un ordinateur communique des informations incorrectes aux différents ordinateurs de manière intentionnelle ou non.

Ce dernier cas est connu sous le nom de défaut Byzantin (“Byzantine failure”). La question qui se pose est celle de savoir jusqu’à quel nombre de membres malintentionné est-il encore possible d’avoir confiance dans un mécanisme de consensus et donc dans la bonne santé d’un réseau décentralisé. Il est en effet possible d’atteindre un consensus honnête malgré l’existence de membres malveillant dont l’objectif est de nuire au réseau en l’empêchant d’atteindre ce consensus.

Les solutions imaginées ces vingt dernières années pour résoudre le problème du défaut Byzantin sont en effet largement reprises de nos jours pour développer des protocoles de consensus répondant aux attentes des applications de la blockchain.

1 – Le problème des généraux Byzantins:

L’exemple des « Généraux Byzantins » est généralement repris pour illustrer le “défaut Byzantin” et permettre de mieux comprendre les difficultés auxquelles est confronté un réseau décentralisé pour

Le problème des généraux byzantins a été mis en évidence pour la première fois par Leslie Lamport, Robert Shostak et Marshall Pease dans leur essai paru en 1982 et vise à illustrer les problèmes de communication et d’entente qui peuvent survenir entre les différents membres ou nœuds d’un même réseau.

Il faut imaginer un groupe de généraux dirigeant l’armée byzantine encerclant une ville ennemi et dont l’objectif est de mener une attaque coordonnée. Pour ce faire, un général décide du début de l’assaut et ordonne à son messager d’aller porter l’information aux autres généraux. Chaque général doit faire passer l’information qu’il reçoit aux autres généraux pour qu’ils disposent tous de la même information et lancent l’attaque en même temps. S’ils n’attaquent pas en même temps, ils sont certains de perdre la guerre.

Le problème se pose lorsqu’un ou plusieurs généraux sont malintentionnés et décident de transmettre une information qui n’est pas correcte comme avancer d’une heure l’attaque. La conséquence est qu’une partie des généraux va attaquer à une certaine heure et l’autre partie une heure après.

En science informatique (vous aurez compris que chaque général représente un ordinateur du réseau), il est nécessaire de mettre en place des algorithmes permettant de trouver une réponse commune malgré les membres malveillants, c’est-à-dire si nous reprenons notre exemple, de s’accorder sur un seul moment pour attaquer la ville.

2 – Les solutions proposées

Les algorithmes des Généraux Byzantins mieux connus sous le nom de “Byzantine Fault Tolerance algorythms” (“BFT”) sont très recherchés parce qu’ils garantissent de maintenir des propriétés de sécurité sur un réseau tant qu’un certain nombre de nœuds « f » sont défaillants.

Cette approche du système de consensus implique que l’identité de chaque membre soit connue, ce qui nécessite l’existence d’une entité centralisée en charge de la gestion de ces données. De ce point de vue, les protocoles basés sur un algorithme BFT sont plus adaptes a un modèle de blockchain dite “privées” ou nécessitant une autorisation (“permissioned”) et offrent une résistance beaucoup plus importante aux attaques.

Ce type de protocole présente l’avantage de la finalité de son consensus c’est dire qu’un block ajouté à la blockchain ne peut être remis en cause, comme c’est notamment possible avec le mécanisme de la Preuve du Travail (« Proof of Work »). En effet avec BFT il n’est pas possible de créer un “fork” sur la blockchain, ce qui permet d’aligner exécution et confirmation des transactions et ainsi accélérer considérablement leur réalisation.

 3 – Practical Byzantine fault tolerance: l’exemple d’Hyperledger

Le protocole de “Practical Byzantine Fault Tolerance” (“PBFT”) a été présenté pour la première fois dans un essai de Miguel Castro et Barbara Liskov publie en 1999. Ce protocole présente l’énorme avantage de pouvoir procéder des dizaines de milliers de transactions par secondes, ce qui est évidement essentiel pour être applicable à des réseaux de grande taille.

L’algorithme permet de maintenir des propriétés de sécurité tant que moins d’un tiers des nœuds ou répliques sont corrompus.

Le pattern de communication de base sous le protocole PBFT se réalise en plusieurs étapes:

1. REQUEST: Le client envoie un message incluant sa requête de service au serveur principal.
2. PRE-PREPARE: the serveur principal assigne un numéro à cette requête et envoie un message de PRE-PREPARE aux autres serveurs.
3. PREPARE: chaque serveur envoie à chacun des autres serveurs un message de “PREPARE”.
4. COMMIT: chaque serveur envoie à chacun des autre serveurs un message de “COMMIT”.
5. REPLY: une fois qu’un nombre suffisant de serveur s’accorde sur l’ordre de la requête, chaque serveur envoie sa réponse au client.

Si le client ne reçoit pas de réponse après une certaine période, il retransmet une requête à l’ensemble des répliques qui la transmettent au serveur principal. Si ce dernier ne met pas en œuvre cette requête dans une période donnée, les répliques vont considérer que le serveur principal fait défaut et vont lancer un “changement de vue” (“View change”) à l’ensemble des serveurs. Lorsqu’un nombre suffisant de répliques a lancé un “changement de vue”, ils sont en mesure de recevoir la prochaine requête en utilisant un serveur principal différent.

La performance du PBFT a été par la suite considérablement améliorée grâce à l’utilisation de “message authentification code” (MAC) qui permettent d’authentifier les différents serveurs plutôt que d’utiliser des signatures digitales.

Ce système est donc à la fois rapide et efficace mais aussi découplé de toute forme de participation dans le réseau (à l’inverse de Proof-of Stake), ce qui permet à des membres de petite taille de participer à la régulation du réseau s’ils ont été choisis pour le faire.

Un des problèmes majeurs repose toutefois sur le fait que les systèmes bases sur PBFT nécessitent que l’ensemble des parties du réseau s’accordent sur une liste exacte de participants. En effet, laisser le réseau ouvert lui ferait courir le risque d’une attaque dite “Sybil”, au cours de laquelle un attaquant peut créer un nombre important de nœuds en vue de dominer le système puisque les décisions sont prises si le vote atteint un certain quorum.

Le Practical Byzantine Fault Tolerance est donc particulièrement adapté aux réseaux de blockchain fermés et nécessitant une identification et une validation de chaque membres.

4 – Le Consensus d’Hyperldger:

1 – Le client créé une transaction et l’envoie à un pair en charge de la soumission (“submitting peer”) de sa requête. Le “submitting peer” peut ici être comparé au serveur principal que nous avons décrit plus haut.

2 – Le “submitting peer” prépare une transaction et l’envoie aux pairs en charge d’approuver les nouvelles transactions ou d’actionner les transactions existantes (“endorsing peer”). Ces “endorsing peer” peuvent être compares aux “répliques” également mentionnées plus haut.

3 et 4 – Le “submitting peer” collecte ensuite l’approbation et soumet la transaction au service du consensus (“consensus service”).

5 – Le “consensus service” distribue ensuite la transaction aux membres du réseau qui vont vérifier qu’elle ne contient pas d’erreur.

Source: Carlos Bruguera – Next Consensus Architecture Proposal

5 – The Ripple Ledger Consensus Process: vote base sur des probabilités

De manière très basique on peut considérer que Ripple créé un réseau de personnes ou d’entité s’attribuant les uns les autres des autorisations de crédit.

Un Serveur (appelons le “s”), qui est une entité ayant accès au Ripple Server Protocol et qui participe donc à la mise en œuvre du consensus (à l’inverse des Ripple Client Software qui ne peuvent que réaliser des transactions), dispose d’une “Unique Node List” or “UNL” (littéralement une “liste de nœud unique”). Seul le vote des Serveurs contenu sur cette liste de participant est pris en compte pour aboutir au consensus. Il s‘agit donc d’un sous-groupe des membres du network qui, lorsqu’il est pris collectivement, est considéré par “s” comme étant digne de confiance. A noter que le serveur “s” n’est pas oblige de donner sa confiance à un serveur individuellement.

Concrètement, l’Algorithme de Consensus du Protocole Ripple (“Ripple Protocol consensus algorithme” – “RPCA”), se déroule toutes les secondes en plusieurs étapes:

• Chaque serveur regroupe toutes les transactions valides qu’il a reçu avant le début du procédé de consensus dans un lot appelé “groupe de candidats” (“candidats set”) qu’il rend ensuite publique.
• Chaque serveur regroupe ensuite tous les groupes de candidats de tous les serveurs listes sur son “Uniq Node List” et vote sur l’exactitude de chacune de ces transactions.
• Les transactions qui reçoivent un pourcentage minimum de votre sont sélectionnés pour le vote suivant, si il y en a un. Les transactions ne réunissant pas le pourcentage suffisant sont rejetées et ajoute au “groupe de candidats” suivant.
• Le dernier vote demande que chaque transaction ait un minimum de 80% de vote de l’ensemble des serveurs de l’UNL à défaut de quoi la transaction ne peut être ajoute au registre (“Ledger”). Cela signifie que tant que 80% des serveurs présents sur la UNL est honnête, aucune transaction frauduleuse ne pourra être approuvée.

6 – Stellar Consensus Protocol (“SCP”): the Federated Byzantine Agreement

SCP est élaboré pour faire face au problème du “defaut byzantin” (“Byzantine failure”), en aboutissant à un consensus sans pour autant avoir à recueillir le consentement de l’ensemble des membres du réseau. C’est une différence importante avec les autres systèmes résistant au defaut byzantine mais qui nécessitent le consentement des nœuds du réseau pour y parvenir.

Plus précisément, SCP procède en 4 phases de la même manière que des protocoles comme Paxos. Les nœuds du réseau échangent une série de scrutins pour confirmer et finalement accepter une valeur. Pour cela, il détermine un quorum minimum, c’est à dire un nombre minimum de membres du réseau devant voter pour obtenir un accord. Chaque nœud choisit une ou plusieurs parts de quorum (“quorum slice”) et inclus dans chaque part des nœuds en qui il a confiance. Chacune de ces parts de quorum vont ensuite produire des intersections les uns par rapport aux autres.

Pour aboutir à un accord, le protocole SCP repose en effet sur une propriété appelle “l’intersection des quorums”. L’idée derrière ce concept et que chaque nœud qui est honnête dispose d’une topologie de réseau suffisamment forte pour aboutir à un consensus. Pour cela on part du principe que si on enlève les nœuds qui sont malveillants ainsi que les nœuds qui en dépendent et que l’intersection du quorum est maintenue, alors la topologie du network est forte.

Si vous avez aimé cet article, n’hésitez pas à le partager sur les réseaux sociaux!!