Petite conversation sur les refroidisseurs d’eau, Ep. 12 : Tolérance aux pannes byzantine

et j’ai passé du temps à lire sur la blockchain, heureusement pas du point de vue des crypto-frères, mais plutôt par véritable curiosité quant à son fonctionnement réel. Et pendant que je parcourais ce terrier de lapin, je suis tombé sur un concept dont je n’avais jamais entendu parler auparavant. C’était Tolérance aux pannes byzantine.

En un mot, Byzantine Fault Tolerance est une propriété système qui permet à un système de continuer à fonctionner correctement, même lorsque certains acteurs malveillants sont inclus dans le système. Ce petit entretien sur les refroidisseurs d’eau portera donc sur la tolérance aux pannes byzantine : qu’est-ce que c’est, d’où elle vient, pourquoi elle est importante et comment la blockchain a fini par être l’une des solutions les plus élégantes à un très vieux problème.

Alors, jetons un coup d’œil !

des généraux byzantins aux ordinateurs

Ainsi, la tolérance aux pannes byzantine est une propriété du système qui doit son nom au problème suivant de la théorie des jeux, à savoir le Problème des généraux byzantins:

Un groupe de généraux byzantins a encerclé une forteresse. Ils doivent prendre une décision collective : attaquer ou battre en retraite. Les décisions de retraite et d’attaque peuvent fonctionner, mais seulement si tout le monde agit de manière coordonnée. Une attaque coordonnée réussit. Une retraite coordonnée réussit également. Mais si certains généraux attaquent tandis que d’autres battent en retraite, le résultat est la défaite.

La communication entre les généraux est universelle et les généraux ne peuvent communiquer qu’en s’envoyant des messagers. Cependant, certains généraux pourraient être des traîtres. En particulier, un traître non seulement vote dans le mauvais sens, mais tente également de tromper les autres généraux en envoyant des messages contradictoires aux différents généraux. Par exemple, un traître peut dire à un général d’attaquer et à un autre de battre en retraite, essayant délibérément de créer une scission. Pendant ce temps, les généraux loyaux n’ont aucun moyen de savoir à l’avance qui sont les traîtres.

Le problème est le suivant : est-ce possible, et si oui, comment et dans quelles conditions, une telle configuration de généraux peut-elle parvenir à un consensus ?

Ce problème a été formellement décrit pour la première fois par les informaticiens Leslie Lamport, Robert Shostak et Marshall Pease dans leur article de 1982. Et bien que le contexte soit médiéval et militaire, le problème décrit constitue l’un des défis les plus fondamentaux de l’informatique. C’est, Comment parvenir à un consensus fiable dans un système distribué lorsque certains participants peuvent envoyer de fausses informations ?

Dans un système informatique distribué, au lieu de généraux, nous avons nœuds: ordinateurs ou serveurs individuels, chacun détenant une copie d’un état partagé (une base de données, un grand livre, un enregistrement de transactions). Tous les nœuds d’un système distribué doivent s’entendre sur ce qu’est cet état de vérité partagé. Comme les généraux, ils communiquent en s’envoyant des messages, et comme les généraux, certains de ces nœuds peuvent être défectueux.

---

Mais pourquoi ne pas simplement voter ? Intuitivement, on peut supposer que chaque général pourrait simplement envoyer son vote (attaque ou retraite) à tous les autres généraux, puis compter les voix et faire ce que propose la majorité. Attaquez si plus de la moitié disent attaque, battez en retraite si plus de la moitié disent retraite.

Le problème est que cela ne fonctionne que si chaque général (nœud) fiducies les messages qu’ils reçoivent. Mais dans un tel réseau, des traîtres peuvent également être inclus, qui peuvent envoyer des votes différents à différents généraux, dans le but de créer une décision partagée. Le général A pourrait recevoir un message disant « Je vote l’attaque »tandis que le général B reçoit un message du même traître disant «Je vote le retrait». Ainsi, les généraux A et B pourraient se retrouver avec des idées différentes sur ce que la majorité du réseau a décidé de faire. En d’autres termes, nous ne pouvons plus nous fier uniquement au vote majoritaire, car la majorité pour chaque nœud peut compter différents messages. Et cette incapacité à parvenir à un consensus est un véritable problème pour ces hypothétiques généraux byzantins, tout autant que pour les réseaux informatiques distribués.

C’est essentiellement la définition de ce qu’est une faute byzantine. Une faute byzantine est une faute dans un système distribué où un composant ne tombe pas simplement en panne, mais se comporte de manière imprévisible. Cela signifie envoyer des informations contradictoires à différents nœuds, semblant fonctionner correctement pour certains nœuds alors qu’ils fonctionnent mal pour d’autres, produire activement de fausses sorties, etc. Néanmoins, une panne byzantine ne provient pas nécessairement d’un acteur malveillant du réseau, car elle peut également provenir de pannes électriques, de bogues logiciels ou de pannes matérielles qui amènent un nœud à produire des sorties arbitraires. Un nœud ayant un tel comportement est appelé nœud byzantin.

Quoi qu’il en soit, dans l’article original de 1982, les auteurs prouvent mathématiquement que pour un système avec n nœuds pour continuer leur fonctionnement normal (c’est-à-dire pour tolérer) f Noeuds byzantins (traîtres), au moins n ≥ 3f + 1 le nombre total de nœuds est nécessaire. En d’autres termes, si plus d’un tiers des nœuds sont byzantins, il est mathématiquement impossible pour un tel système d’atteindre un consensus de manière fiable, et il n’existe aucun algorithme permettant à un tel système de continuer à fonctionner. Un système qui a au moins deux tiers du total des nœuds non corrompus et peut également fonctionner normalement, atteignant un consensus, a la propriété de tolérance aux pannes byzantine, ou est appelé système tolérant aux pannes byzantine.

Et la blockchain ?

Pendant des décennies après l’article de 1982, la tolérance aux pannes byzantine est restée un problème théorique avec des solutions pratiques uniquement dans des environnements étroitement contrôlés comme les systèmes aérospatiaux, les centrales nucléaires ou tout autre endroit où chaque nœud pouvait être vérifié à l’avance et garantir que moins d’un tiers deviendrait malveillant. En d’autres termes, une certaine confiance était nécessaire entre les nœuds composant le réseau, donc même si certains nœuds se tournaient vers des traîtres, ces traîtres resteraient toujours en dessous du seuil des 1/3 (espérons-le).

1. Bitcoin et preuve de travail

Ce fut le cas jusqu’en 2008, date à laquelle le livre blanc Bitcoin a été publié, contourner complètement l’approche de vote classique. Contrairement aux réseaux distribués qui existaient jusqu’à présent, où le consensus était atteint par un vote majoritaire (espérons-le) de parties de confiance, le livre blanc Bitcoin proposait un mécanisme pour faire fonctionner un sans confiance système distribué. Cela signifie que, contrairement aux centrales nucléaires, où la confiance existait à l’avance entre les nœuds, Bitcoin peut fonctionner sans qu’aucun des nœuds ne se fasse confiancecar le mécanisme de consensus Bitcoin garantit lui-même les transactions.

Le mécanisme spécifique par lequel Bitcoin parvient à faire cela s’appelle Preuve de travail (PoW). Pour le dire simplement, PoW rend la participation au processus de consensus coûteuse en termes de calcul, et encore plus coûteuse (pratiquement impossible) le fait d’être un traître. Plus précisément, pour ajouter une nouvelle transaction, un nœud doit résoudre un casse-tête cryptographique qui nécessite d’énormes quantités de puissance de calcul. Ce puzzle est difficile à résoudre pour le nœud qui propose la transaction, mais facile pour les autres nœuds de vérifier si la solution du puzzle est correcte.

Un nœud traître qui souhaite corrompre le système et proposer une fausse transaction devrait refaire le travail de calcul, non seulement pour la transaction qu’il souhaite corrompre, mais pour chaque transaction ultérieure. C’est BEAUCOUP de calculs ! En plus de cela, il devrait le faire plus rapidement que le reste du réseau honnête réuni. En pratique, cela nécessiterait de contrôler plus de 50 % de la puissance de calcul totale du réseau, ce qui est extrêmement coûteux, voire pratiquement impossible. Ainsi, le coût de la tricherie dépasse tout avantage potentiel que l’on pourrait en attendre, ce qui la rend économiquement irrationnelle. Cela dit, même si PoW permet des transactions fiables dans un système décentralisé et sans confiance, il entraîne également des coûts et une latence élevés (les transactions Bitcoin peuvent prendre jusqu’à 10 minutes pour être finalisées), en raison des calculs massifs requis.

2. blockchains modernes et preuve de participation

S’appuyer davantage sur cela »ce qui rend économiquement irrationnel la triche » concept, mais aussi en essayant de rendre le système lui-même plus rapide, une autre approche consensuelle est Preuve de participation (PoS). PoS est utilisé sur la blockchain d’Ethereum depuis 2022, et sur d’autres blockchains modernes comme Solana et Sui. La logique derrière le PoS est la même que celle du PoW, mais au lieu de rendre la triche économiquement coûteuse indirectement via le calcul, elle la rend directement coûteuse en obligeant les nœuds du réseau à soumettre des garanties économiques. En particulier, dans une blockchain PoS, les validateurs (nœuds proposant des transactions) doivent verrouiller une quantité importante de token de la blockchain pour avoir la capacité de proposer et de vérifier des transactions. Si un nœud propose une transaction incorrecte, alors le système le pénalise et conserve une partie de la garantie soumise. La différence avec PoW est que dans PoS, le comportement byzantin est puni économiquement plutôt que rendu informatiquement irréalisable.

Une autre chose à propos du PoS est qu’il rend le système plus proche du BFT. Contrairement à Proof of Work, qui contourne complètement le modèle de vote classique BFT et fixe le seuil de corruption à 50 % de la puissance de calcul totale, Proof of Stake nous rapproche du cadre byzantin original de tolérance aux pannes. Dans un système PoS, les validateurs votent sur la validité des transactions en utilisant leurs jetons mis en jeu comme poids. Cela signifie que le seuil de 1/3 du document original de 1982 s’applique à nouveau : si plus d’un tiers de la valeur totale mise en jeu est contrôlé par des validateurs byzantins, le consensus peut s’effondrer. PoS est explicitement byzantin tolérant aux pannes au sens classique du terme, alors que PoW ne l’est pas – il résout simplement une version différente du même problème.

Dans mon esprit : BFT au-delà de la blockchain

Ce qui m’a le plus frappé chez BFT, c’est l’ancienneté du problème et le temps qu’il a fallu pour passer de la documentation du problème théorique aux solutions concrètes. En particulier, le problème est identifié et formalisé dans l’article original de 1982, mais le premier algorithme pratique pour le gérer dans des systèmes informatiques réels, appelé Practical Byzantine Fault Tolerance (PBFT), n’est apparu qu’en 1999. Et le premier système à le déployer réellement dans une configuration du monde réel (Bitcoin) n’est arrivé qu’en 2008.

L’autre chose à laquelle je continue de penser est à quel point le problème est universel. Au-delà de la blockchain, la tolérance aux pannes byzantine, ou plus généralement, le problème de parvenir à un consensus entre des participants potentiellement peu fiables, est omniprésent autour de nous. Chaque fois que vous avez plusieurs partis indépendants qui doivent se mettre d’accord sur quelque chose, et que vous ne pouvez pas leur faire entièrement confiance, vous avez une version du problème des généraux byzantins.

Dans les bases de données distribuées, les protocoles BFT garantissent qu’un cluster de serveurs de bases de données peut s’entendre sur l’état actuel des données même si certains serveurs sont corrompus ou envoient des informations erronées. Dans l’aérospatiale, les ordinateurs de contrôle de vol utilisent le vote de type BFT pour garantir qu’un seul capteur défectueux ne peut pas provoquer une panne catastrophique. Un comité prenant une décision avec des membres de mauvaise foi. Une chaîne d’approvisionnement dans laquelle certains fournisseurs peuvent envoyer des informations frauduleuses. Une configuration de formation d’IA distribuée dans laquelle certains appareils peuvent envoyer des mises à jour empoisonnées. Les généraux sont partout. La question est toujours la même : comment parvenir à un consensus fiable quand on ne peut pas faire confiance à tout le monde dans la salle ?

✨ Merci d’avoir lu ! ✨

---

Si tu es arrivé jusqu’ici, les pialgorithmes pourraient vous être utiles: une plateforme que nous avons créée qui aide les équipes à gérer en toute sécurité les connaissances organisationnelles en un seul endroit.

---

Vous avez adoré cet article ? Rejoignez-moi sur 💌 Sous-pile et 💼 LinkedIn

---

Toutes les images de l’auteur, sauf indication contraire