Aller au contenu
Financial Context Wiki

Problème des généraux byzantins : s’accorder malgré des messages contradictoires

Le problème demande comment des participants honnêtes peuvent s’accorder lorsque des participants défaillants envoient des informations contradictoires. Il faut distinguer la tâche d’accord, les canaux, l’authentification, la borne de pannes, le seuil, l’algorithme et le déploiement.

Mis à jour

À des fins éducatives uniquement ; ne constitue ni un conseil en investissement ni une recommandation d’investissement. Les investissements peuvent entraîner des pertes.

Réponse directe

Le problème des généraux byzantins demande comment des participants non défaillants qui communiquent par messages peuvent prendre une décision cohérente lorsque certains se comportent arbitrairement, notamment en envoyant des affirmations différentes à différents destinataires. Le récit militaire est une analogie de la cohérence interactive dans les systèmes distribués, ni un événement historique ni un algorithme précis de consensus blockchain.

Dans la formulation avec un général commandant, IC1 exige que tous les lieutenants loyaux exécutent le même ordre, tandis que IC2 exige que chacun exécute l’ordre du commandant lorsque celui-ci est loyal. L’accord seul ne suffit pas : une règle choisissant toujours la RETRAITE produirait un accord, mais violerait l’ordre valide d’ATTAQUE d’un commandant loyal.

Dans le modèle des « messages oraux » de l’article, avec au plus m traîtres, une solution n’existe que si n>3m, soit, pour un nombre entier de participants, n>=3m+1. Ce modèle suppose que les messages envoyés par les participants loyaux sont livrés correctement, que chaque destinataire connaît l’expéditeur et que l’absence d’un message attendu est détectable. « Oral » signifie qu’un contenu non authentifié peut être falsifié comme le compte rendu d’un autre participant, pas qu’un messager peu fiable peut disparaître pour toujours sans que cela soit détecté.

Le modèle des « messages signés » ajoute des signatures infalsifiables et publiquement vérifiables, ce qui modifie le résultat de résilience. Il ne rend pas le contenu signé véridique, ne garantit pas la livraison, ne résout pas la terminaison entièrement asynchrone, ne protège pas les clés volées et ne démontre pas la sûreté d’un protocole moderne. Le problème des généraux byzantins, le problème des deux généraux ou de l’attaque coordonnée, FLP, les protocoles BFT, la preuve de travail et la preuve d’enjeu sont des modèles ou constructions liés mais distincts.

Méthode d’analyse

  1. Définir la tâche d’accord. Préciser participants, entrées, sorties et propriétés exactes d’accord, de validité et de terminaison. Pour la formulation avec commandant, écrire explicitement IC1 et IC2 au lieu de dire seulement « atteindre le consensus ».
  2. Définir les identités et les canaux. Préciser si les messages point à point sont authentifiés, livrés de manière fiable, ordonnés, protégés contre le rejeu et attribuables ; si une omission est détectable ; et si la diffusion est une primitive ou une suite d’envois.
  3. Définir le modèle temporel. Distinguer synchronie à délai borné, synchronie partielle après un instant de stabilisation inconnu et asynchronie complète. Ne pas ajouter des messagers qui disparaissent à un modèle tout en conservant un théorème démontré pour un autre.
  4. Définir le budget de pannes. Noter le nombre total de participants n, le maximum de participants byzantins m, le caractère statique ou adaptatif de la corruption, et si les pannes incluent omission, équivoque, collusion, vol de clé ou canaux défaillants.
  5. Retracer récursivement l’information. Pour chaque participant loyal, lister les affirmations directes et relayées, y compris les chemins d’expéditeurs, les valeurs par défaut en cas d’absence et les règles déterministes de départage. Comparer ce que deux participants loyaux peuvent distinguer depuis leur vue locale.
  6. Vérifier ensemble théorème et algorithme. Faire correspondre bornes inférieures et suffisance au modèle oral ou signé exact, à la connectivité et au budget de pannes. Une inégalité de seuil n’est à elle seule ni une implémentation ni une preuve.
  7. Relier le modèle au déploiement. Vérifier le mécanisme OM(m), SM(m) ou autre du protocole déployé, les domaines de messages, tours, verrous, certificats, changements de membres, délais, comportement client, règle de finalité et politique de confirmation applicative.

La technique de preuve essentielle est l’indiscernabilité. Un participant loyal ne voit que ses messages locaux ; si deux exécutions lui paraissent identiques mais imposent des décisions différentes pour respecter la validité, aucune règle déterministe ne peut toujours choisir correctement. Les protocoles réussissent en ajoutant assez de participants indépendants, de preuves authentifiées, d’hypothèses temporelles, d’aléa ou d’autres structures afin de rendre les exécutions requises discernables ou de modifier la garantie.

Exemples détaillés

1. Pourquoi trois généraux à messages oraux ne tolèrent pas un traître

Prenons n=3 et m=1. La condition requise n>3m devient 3>3, ce qui est faux. Supposons que le commandant A dise au lieutenant B ATTACK et au lieutenant C RETREAT. B ne peut savoir si A est le traître qui envoie des ordres contradictoires ou si C est le traître qui rapporte faussement ce qu’a dit A ; C fait face à l’incertitude symétrique.

Tout choix déterministe qui préserve l’ordre d’un commandant loyal dans les exécutions correspondantes où A est loyal peut forcer B et C à choisir différemment lorsque A est traître. Relayer les messages ne crée pas une quatrième source indépendante : IC1 et IC2 ne peuvent donc pas être garantis ensemble.

2. Quatre généraux à messages oraux et un traître

Avec OM(1), n=4 et m=1, le commandant envoie un ordre aux trois lieutenants ; chacun relaie aux deux autres la valeur reçue ; chaque lieutenant loyal applique la même règle de majorité et la même valeur par défaut. Si le commandant est loyal et envoie v, un lieutenant loyal observe par exemple v, v et le possible x du traître, puis choisit v.

Si le commandant est l’unique traître, les trois lieutenants sont loyaux et relaient exactement ce que chacun a reçu. Ils reconstruisent donc le même ensemble d’affirmations du commandant et appliquent la même règle déterministe. Ils ne retrouvent peut-être pas la « véritable intention » du commandant, mais satisfont l’accord.

3. Borne générale des messages oraux

Pour n=7 et m=2, 7>6 est vrai : la condition sur le nombre de participants est satisfaite et la construction récursive à messages oraux peut tolérer au plus deux traîtres sous ses hypothèses. Pour n=6, 6>6 est faux. Pour n=10 et m=3, 10>9 est vrai. Respecter l’inégalité est nécessaire, mais il faut toujours des tours, relais, majorités, valeurs par défaut et canaux corrects.

4. Ce que changent les signatures

Dans un exemple à trois généraux avec SM(1), un commandant traître signe ATTACK pour B et RETREAT pour C. Les lieutenants loyaux relaient les deux ordres signés ; chacun obtient donc le même ensemble {ATTACK, RETREAT} et applique la même valeur par défaut spécifiée, par exemple RETREAT. L’équivoque du commandant est attribuable.

Dans ce modèle, les signatures empêchent que l’ordre d’un participant loyal soit falsifié ou modifié sans détection. Elles ne révèlent pas lequel des deux ordres représente la véritable intention d’un traître, ne garantissent pas une livraison ponctuelle et n’empêchent pas un attaquant contrôlant une clé privée légitime de signer les deux.

Risques et erreurs d’examen

Problème et modèle

  • Raconter l’allégorie sans conditions précises d’accord, de validité et de terminaison.
  • Présenter le problème comme un siège historique, un algorithme unique ou un synonyme de blockchain.
  • Le confondre avec le problème des deux généraux, centré sur la connaissance commune via un canal peu fiable.
  • Ajouter une perte permanente et indétectable des messages tout en citant un théorème dont les hypothèses orales l’excluent.
  • Appliquer n>3m à tout protocole authentifié, asynchrone, pondéré, sans permission ou fondé sur une ressource.
  • Assimiler panne par arrêt, omission, équivoque, calcul arbitraire, canal défaillant et compromission de clé.
  • Supposer que le nombre de participants correspond à des entités indépendantes, à l’enjeu, à la puissance de calcul ou au poids d’un comité.
  • Oublier la distinction entre commandant loyal et commandant traître dans la condition de validité.

Algorithme et implémentation

  • Ne vérifier que la majorité finale sans retracer les chemins récursifs des expéditeurs et la vue locale de chaque participant loyal.
  • Employer des valeurs par défaut, règles de départage, instantanés de membres ou ordres de messages différents selon les implémentations.
  • Accepter des messages sans les lier au protocole, à la chaîne, à la tâche, à la hauteur, au tour, à la valeur, à l’expéditeur et à l’époque d’adhésion.
  • Rejouer ou assembler des messages entre exécutions, tours, branches, réseaux ou changements de membres.
  • Supposer que les signatures prouvent vérité, fraîcheur, contexte d’autorisation, livraison, disponibilité ou garde honnête des clés.
  • Citer OM(m) ou SM(m) sans implémenter les tours, relais, vérifications et connexions nécessaires.
  • Ne tester qu’un emplacement du traître au lieu des cas commandant, lieutenant, collusion, omission et équivoque.

Déploiement et interprétation

  • Affirmer qu’un protocole de consensus « résout Byzance » sans préciser ses hypothèses de sûreté, de vivacité et de réseau.
  • Prendre l’accord sur des octets pour une preuve que l’exécution applicative ou un fait externe est correct.
  • Ignorer les clients, opérateurs, nuages, systèmes de clés ou mécanismes de gouvernance communs qui corrèlent des participants nominalement distincts.
  • Créditer des dépôts, créer des actifs pontés ou régler des actions irréversibles avant la condition de finalité requise.
  • Déduire décentralisation, sûreté des actifs, vérité juridique ou valeur d’un jeton d’une simple étiquette de tolérance aux pannes.

Idées reçues

  • Le problème se réduit à une attaque des 51 %. Il traite de comportements arbitraires et contradictoires sous un modèle d’accord défini ; les attaques par majorité de ressources dépendent de protocoles particuliers.
  • Une majorité suffit toujours. Dans le modèle classique des messages oraux, tolérer m traîtres exige plus de trois fois ce nombre de participants au total, pas seulement un honnête de plus que les traîtres.
  • Les signatures numériques prouvent qu’un message est vrai. Elles authentifient une clé et protègent l’intégrité ; une clé malveillante ou compromise peut toujours signer des contenus faux ou contradictoires.
  • La livraison peu fiable est déjà couverte par le résultat original des messages oraux. Celui-ci comporte des hypothèses explicites de livraison, d’identité de l’expéditeur et d’omission détectable ; d’autres modèles temporels et de canaux exigent d’autres résultats.
  • L’accord signifie que le système a découvert la réalité. Des nœuds loyaux peuvent s’accorder sur une sortie applicative invalide ou une donnée externe erronée si des règles de validation séparées ne l’empêchent pas.

Sujets connexes

Sources

Navigation

Rechercher dans le wiki...