VT2020-BFT-Fiche

Abstract

L'Utilisation de plus en plus rependue de systèmes distribués nous force à considérer le problème du consensus au sein d'un réseau. Comment un groupe de machine arrive t'il à s’accorder sur l'état d'une base de données quand chacune des machines du réseau en a sa propre version, que le réseau ne garantis aucune fiabilité et que les machines composant le réseau sont elles-mêmes faillibles?

Le Problème des deux Généraux

Définition

Soient deux armées A et B encerclant une armée C. A et B doivent se mettre d'accord sur un heure à laquelle attaquer C ou prendre la décision de se replier. Pour "gagner" il faut que les armées A et B attaquent simultanément ou se replient toute les deux. Si l'attaque est désynchronisée ou qu'une armée se replie tandis que l'autre attaque, la défaite est assurée. C'est donc le consensus entre A et B qui déterminera l'issue du combat.

Représentation du problème des deux généraux

Pour communiquer, A et B s'envoient des messagers qui doivent traverser le territoire adverse. On ne peut garantir que le messager arrivera à destination, ce n'est donc pas un canal de communication fiable. Il faut cependant trouver un protocole de communication permettant aux deux armées d'arriver à un accord.

Impossibilité

Si on considère un protocole inspiré de TCP et notamment des messages échangés lors de l'ouverture d'un connexion (SYN, SYN-ACK, ACK), on obtient un protocole qui se déroule comme suit:

Si lors du premier message A n'attends pas acquittement, il sera seul face à l'ennemi si son message est perdu. On trouve la situation inverse si A attends un acquittement mais pas B, si le deuxième message se perd, A continuera d'attendre pendent que B perd la bataille. En fait on peu continuer d'ajouter des message à ce dialogue pour acquitter les acquittements, l'engagement d'une armée ou de l'autre à rentrer dans la bataille repose toujours sur le dernier message de la conversation, et ce dernier peut toujours être perdu. Il n'y a pas de solution déterministe à ce problème.

Le Problème des Généraux Byzantins

Définition

Le problème des généraux Byzantins permet de généraliser le problème des deux généraux à un plus nombre n de généraux. File:ByzantineGenerals.jpg

Soient n généraux encerclant une ville, ils doivent s'accorder sur la stratégie à adopter pour leur assaut: attaquer ou se replier. Pour communiquer, ils s'envoient des messagers qui peuvent se faire capturer par l'ennemi ou même être remplacé par un messager à la solde de l'ennemi et transportant un message contrefait. De plus il est possible que des généraux soient des traîtres et tentent d’empêcher le consensus en envoyant des messages erronés aux autres généraux.

Pour gagner il faut que tout les généraux loyaux parviennent à un consensus, si seule une partie des généraux loyaux passent à l'attaque, la défaite et inévitable. Il faut donc un protocole permettant le consensus malgré la présence de traîtres et les canaux de communication peu fiables.

De ce problème vient le nom de panne byzantine, si sur un réseau un nœud présente un comportement byzantin c'est qu'il ne suit pas sa spécification et envoie des données erronées ou pas de données du tout. Il peut être vu comme dysfonctionnel par certains de ses voisins et comme fonctionnel par d'autres. Cela peut être le signe d'un problème matériel ou d'une action malveillante.

Applications Concrètes

La tolérance aux pannes byzantines est utile dans les systèmes distribués, par exemple:

• Redondance pour un système critique: Dans l’aérospatiale on trouve plusieurs exemple de BFT car certains systèmes critiques sont dupliqués pour réduire la probabilité de défaillance de l'appareil. Ces systèmes dupliqués doivent donc arriver à un consensus.
• Base de données distribuées: Répartir une base de données sur plusieurs data centers permet d'assurer redondance, tolérance au pannes et disponibilité il faut cependant que la base de données contenue dans chaque data center soit identique.
• BlockChain (ex: bitcoin): Le système bitcoin est un base de données décentralisée contenant toutes les transactions ayant eut lieu sur le réseau. Chaque utilisateurs a une version locale de cette liste de transaction et chaque utilisateur doit avoir la même version.

Solutions au Problème des Généraux Byzantins

Practical Byzantine Fault Tolerance

f: nombre maximal de fautes tolérées

n = 3f + 1: nombre de nœuds

Cet algorithme se décompose en 5 phases:

• REQUEST: Le client envoie une requête au nœud principal
• PREPREPARE: Le nœud principal diffuse la requête vers les autres nœuds
• PREPARE: Pour signifier qu'il on bien reçu la requête les nœuds broadcastent un message PREPARE contenant le hash de la requête.
• COMMIT: Quand une noeud reçoit 2f messages PREPARE correspondant au message PREPREPARE reçu précédemment il diffuse un message COMMIT contenant le hash de la requête.
• REPLY: Une fois 2f + 1 message COMMIT reçus si ceux-ci correspondent au message PREPREPARE, la requète est effectuée et le résultat est envoyé au client.

Le client après avoir reçu f +1 réponses similaire considérera qu'il s'agit de la bonne réponse.

BFT-SMART

BFT-SMaRt est une librairie Java open source. Elle facilite la réplication de données dans un réseau et propose une alternative robuste, multicore et modulaire à PBFT et UpRight.

Proof of Work

La BlockChain du bitCoin fonctionne de la manière suivante, chaque bloc contient une liste de transactions et le hash du bloc précédent. De ce fait on ne peut pas falsifier un bloc sans devoir falsifier les suivant. Pour rendre difficile la création et la modification d'un bloc, le bloc contient aussi une preuve de travail, il s'agit d'une valeur que le "mineur" doit trouver pour que le hash du bloc commence par un nombre donné de zéros (par exemple 30). Cette pratique rends très difficile la production de bloc (il faut en moyenne 10 minutes pour qu'un bloc soit ajouté à la blockchain). Il est cependant très facile de vérifier que la preuve de travail est bonne et ainsi valider le bloc.

Chaque utilisateur sur le réseau est à l'écoute de nouveau bloc créé par les mineurs pour pouvoir l'ajouter à sa propre copie de la blockchain. Dans le cas d'une tentative de fraude, un utilisateur donnée captera deux blocs contradictoires pour savoir lequel des deux blocs est frauduleux, il lui suffit d'attendre que plus de blocs soient "minés". Si une majorité des acteurs du réseau sont loyaux, des blocs s'ajouteront plus rapidement au bloc valide qu'au bloc contrefait, il suffira donc à l'utilisateur de considérer la chaîne la plus longue comme étant la chaîne valide. Pour que le faussaire puisse intégrer durablement un bloc contrefait à la blockchain, il faut qu'il soit capable de miner les blocs au moins aussi vite que tout les autres mineurs réunis.

VT2020

• Année : VT2020
• Sujet : BFT
• Slides :
• Auteurs : Alexandre SALMON