Byzantine Generals Problem

Imaginez des troupes disposées autour d'une ville. Elles doivent attaquer ensemble ou se retirer ensemble ; agir séparément pourrait les mener au désastre. Le commandant envoie ses ordres, mais quelqu'un peut trahir les autres et leur donner des versions différentes. Comment les participants fiables peuvent-ils finalement agir de la même façon ? Il ne s'agit pas d'une bataille historique, mais d'une expérience de pensée sur des ordinateurs qui doivent conserver des données cohérentes. Plusieurs serveurs, les ordinateurs qui assurent un service commun, doivent, par exemple, décider de manière concordante si un paiement a déjà été traité. Recevoir une réponse ne suffit pas : les réponses doivent aboutir à une décision commune. [1] [9]

Leslie Lamport, Robert Shostak et Marshall Pease ont présenté cette formulation en juillet 1982, après leurs travaux de 1980 sur l'accord en présence de défaillances. Le traître représente un composant dont le comportement n'est plus prévisible. Un ordinateur ne se contente pas nécessairement de s'arrêter : il peut répondre correctement à un voisin et incorrectement à un autre, omettre des messages ou affirmer avoir vu autre chose. Une attaque comme un défaut logiciel peut l'expliquer. Une défaillance byzantine décrit ce que les autres observent, pas l'intention de l'appareil. BFT (Byzantine Fault Tolerance), pour tolérance aux défaillances byzantines, désigne la capacité à supporter ce comportement dans des conditions définies. [1] [2]

Le problème original pose deux conditions. IC1 exige que tous les subordonnés fiables acceptent le même ordre. IC2 ajoute que, si le commandant est fiable, ils doivent accepter l'ordre qu'il a réellement envoyé. Sans la seconde condition, « toujours se retirer » semblerait résoudre le problème, mais ignorerait un commandant honnête. En informatique, on distingue la sûreté, qui exclut des résultats contradictoires, de la vivacité, qui permet d'aboutir à un résultat. D'autres règles précisent quels résultats sont valides. Un registre cohérent ne prouve pas à lui seul qu'une affirmation saisie était vraie dans le monde extérieur. [1] [9]

Appelons A le commandant, et B et C ses subordonnés. C reçoit de A l'ordre d'attaquer, mais B lui dit que le commandant a ordonné la retraite. B ment-il, ou A a-t-il envoyé deux ordres différents ? Sans signature vérifiable après transmission, C peut être incapable de distinguer les situations. B peut rencontrer la même incertitude. Obéir toujours au commandant permet à un A malhonnête de les diviser ; l'ignorer toujours enfreint la condition prévue pour un commandant honnête. Dans ce problème à trois participants avec un traître possible, aucune procédure sans signatures ne réussit donc à tous les coups. Il manque des informations permettant de distinguer les cas, pas des ordinateurs plus rapides. [1] [9]

Dans le modèle classique sans signatures, tolérer m traîtres possibles exige au moins n ≥ 3m+1 participants : quatre pour un traître. Ici, n est le nombre total de participants et m le nombre maximal de traîtres que le système doit pouvoir supporter. Il ne suffit pas d'ajouter une voix et de compter une fois la majorité. OM(m) fait retransmettre ce que les participants ont entendu et évaluer les messages selon des règles communes ; son cas de base OM(0) reprend la valeur du commandant ou une valeur par défaut convenue. Le modèle suppose des participants connus, des liaisons directes, la bonne livraison des messages envoyés, l'identification de l'expéditeur immédiat et la détection des messages absents. « Sans signatures » ne signifie donc pas « sans aucune authentification de l'origine ». Sans ces hypothèses, le nombre quatre ne garantit rien. [1] [9]

Avec une signature numérique vérifiable, Digital Signature, B peut montrer à C ce que le commandant a réellement signé. Un programme crée cette signature avec une clé privée, une valeur numérique secrète. Les autres la vérifient avec la clé publique correspondante, sans connaître la clé privée. Un traître ne peut modifier discrètement l'ordre d'un participant fiable ni imiter sa signature. L'algorithme de messages signés diffuse des valeurs signées et applique une règle de sélection commune. Dans ce modèle, l'exigence précédente d'une majorité honnête disparaît, mais les hypothèses sur les signatures infalsifiables, la livraison et le calendrier des tours restent nécessaires. Les travaux de Dolev et Strong de 1983 approfondissent le nombre de tours requis. Même une signature valide ne garantit ni la véracité du contenu ni sa livraison à temps, et ne prouve pas que la clé privée n’a pas été volée. Elle établit l'origine d'un message, pas la fiabilité générale de son auteur. [1] [3]

Lorsqu'un serveur ne répond pas, les autres ignorent s'il s'est arrêté ou si sa connexion est simplement très lente. Le résultat FLP, publié en 1985 par Michael Fischer, Nancy Lynch et Michael Paterson, précise cette incertitude. Un processus désigne ici un programme en cours d’exécution. Une procédure déterministe effectue la même étape suivante pour un même état et une même entrée ; elle ne la choisit pas au hasard. Dans un système entièrement asynchrone, sans borne supérieure connue sur les délais, une procédure déterministe ne peut garantir la terminaison de l'accord pour toute exécution admissible dès lors qu'un seul processus peut s'arrêter sur panne. Cela vaut même avec une livraison fiable mais des délais non bornés. Cela ne signifie pas qu'un accord n'arrive jamais. Les systèmes pratiques ajoutent des hypothèses temporelles, un détecteur de défaillance adapté ou du hasard. Lors d'une partition du réseau, attendre peut être plus sûr que confirmer des résultats incompatibles. [4] [13] [8]

Miguel Castro et Barbara Liskov ont décrit en 1999 Practical Byzantine Fault Tolerance, PBFT, pour un service exécuté sur plusieurs répliques connues. Ces répliques sont des copies du service qui fonctionnent sur différents serveurs et traitent continuellement les mêmes requêtes. Ce ne sont pas des fichiers de sauvegarde mis de côté. La configuration de base n = 3f+1 tolère f répliques défaillantes. Sur quatre serveurs, un peut être byzantin ; deux groupes de trois ont au moins deux serveurs en commun, dont au moins un doit être fiable. Un ensemble d'approbations requis s'appelle un quorum. L'intersection ne suffit pas : les règles des phases et du changement de responsable comptent aussi. Plus précisément, l'état prepared exige la requête, un message pre-prepare et 2f messages prepare concordants de répliques distinctes autres que la réplique principale. La confirmation locale exige aussi 2f+1 messages commit, éventuellement celui de la réplique elle-même. Authentification, numéros de séquence et points de contrôle répondent aux falsifications, aux répétitions et à la croissance illimitée du journal. La sûreté ne dépend pas de bornes temporelles ; la progression exige toutefois des conditions supplémentaires sur les délais. [5] [10] [11] [12]

Bitcoin n'a pas de liste fermée de serveurs établie à l'avance. Si chaque compte nouvellement créé disposait d'une voix, un attaquant pourrait fabriquer une majorité : c'est une Sybil Attack. Proof of Work lie donc la production des blocs à un travail de calcul. Un bloc est un lot de transactions ajouté à l’historique commun. Un Full Node, un ordinateur équipé d’un logiciel qui vérifie lui-même les règles, rejette d'abord les blocs invalides, puis suit la branche valide ayant le plus de travail cumulé. Bitcoin n'exécute ni OM ni PBFT ; les bifurcations temporaires font partie de son fonctionnement. Avec une puissance honnête suffisante et des communications appropriées, davantage de confirmations réduisent le risque de réécriture sans créer d'irréversibilité absolue. Les travaux Bitcoin Backbone étudient ces conditions : accord des historiques, croissance de la chaîne et proportion de blocs que les participants honnêtes peuvent produire. [6] [7]

Devant l'affirmation « le réseau atteint un consensus », cherchez des réponses précises : qui peut participer, que contrôle l'attaquant, combien de temps les messages peuvent-ils prendre et quand une décision peut-elle changer ? Même Proof of Work ne supprime pas toutes les difficultés. Une Eclipse Attack isole un nœud de pairs honnêtes, la censure écarte des transactions et Selfish Mining repose sur la rétention de blocs minés. Restent les défauts logiciels et la possibilité de réécrire une partie de l'historique avec une puissance d'attaque suffisante. Pourtant, même une majorité de puissance ne peut forcer un Full Node correctement exécuté à accepter un bloc contraire à ses règles. L'histoire des généraux invite à examiner les conditions de l'accord plutôt qu'à faire confiance au nom d'une technologie. [6] [7] [8]