Le problème des généraux byzantins, conceptualisé par Leslie Lamport, Robert Shostak et Marshall Pease en 1982, est un casse-tête dans le domaine de l'informatique distribuée. Cette métaphore représente des généraux encerclant une ville ennemie et souhaitant coordonner une attaque. Ce problème a regagné de l'intérêt après la création du Bitcoin en 2008 par Satoshi Nakamoto, qui a proposé une solution novatrice à ce dilemme.
L'informatique distribuée est un domaine de l'informatique où des systèmes composés de plusieurs ordinateurs indépendants communiquent et coordonnent leurs actions par l'échange de messages pour atteindre un objectif commun. Ces systèmes sont souvent répartis géographiquement, permettant de traiter des tâches de manière plus efficace et résiliente.
Un exemple très connu d'informatique distribuée est le système de Google, qui utilise une architecture distribuée pour gérer les requêtes de recherche sur Internet. Ce système répartit les données et les traitements sur de nombreux serveurs et centres de données à travers le monde, permettant ainsi de traiter rapidement et efficacement des milliards de requêtes par jour.
Le problème des généraux byzantins est relativement simple à décrire. Des généraux de l'armée byzantine se trouvent autour d'une ville ennemie, chacun commandant ses propres troupes, et planifient une attaque coordonnée. Leur communication est limitée aux messagers oraux, et ils doivent s'accorder sur un plan d'attaque commun, visant à lancer l'assaut simultanément à un moment convenu, par exemple à l'aube, faute de quoi la défaite sera inévitable. Ils communiquent leurs intentions par les messages « attaque » pour confirmer l'action ou « retraite » pour l'annuler.
Cependant, parmi ces généraux, certains peuvent être des traîtres et chercher à semer le désordre. Ces traîtres peuvent envoyer des messages de retraite pour persuader les généraux loyaux de se retirer au moment crucial, risquant ainsi une défaite.
Le défi est de développer une stratégie ou un algorithme qui garantit que tous les généraux loyaux se mettent d'accord sur un plan d'action unifié, malgré la présence de traîtres qui chercheront à contrecarrer leurs plans.
La difficulté s'accroît si un commandant, à qui les généraux subordonnés doivent obéir, est lui-même un traître.
L'importance des pannes byzantines dans les systèmes modernes de synchronisation informatique est cruciale, notamment dans les domaines où la sécurité et la fiabilité sont primordiales. Le défi des généraux byzantins, illustré par la coordination nécessaire entre divers systèmes informatiques, se manifeste de façon prononcée dans l'industrie aéronautique. Par exemple, dans le cas de l'aéronautique, et spécifiquement pour des avions complexes comme le Boeing 777, la robustesse et la fiabilité des systèmes informatiques sont essentielles pour la sécurité des vols.
Ces systèmes doivent être conçus pour traiter des informations venant de différentes sources et pour prendre des décisions correctes même si certaines de ces informations sont erronées ou malicieusement altérées. L'architecture du Boeing 777, par exemple, utilise des principes de redondance et de vérification croisée pour prévenir les défaillances et garantir un fonctionnement fiable, ce qui est en quelque sorte une application de la tolérance aux pannes byzantines.
Ce problème de synchronisation est toutefois le plus visible dans les réseaux décentralisés, tels que ceux utilisés par les crypto-monnaies. Bitcoin, par exemple, repose sur un réseau distribué où chaque participant maintient une copie d'un registre de transactions, la blockchain qui nécessite un consensus fiable malgré la présence potentielle de participants malveillants.
Ces systèmes doivent résister aux pannes byzantines, où certains nœuds peuvent agir comme des traîtres, perturbant l'accord général. L'enjeu est donc de développer des algorithmes qui assurent un consensus même en présence de ces nœuds « byzantins ». Ce type d'algorithme est doté de ce que l'on appelle la tolérance aux pannes byzantines ou « byzantine fault tolerance » (BFT).
Dans le contexte de Bitcoin, qui facilite le transfert de valeurs, le défi est d'arriver à un accord sur la propriété des actifs de manière distribuée, sans dépendre d'une autorité centrale comme les banques, tout en empêchant que des acteurs malintentionnés compromettent le consensus.
La résolution du problème des généraux byzantins exige que plus des deux tiers des généraux soient loyaux, limitant ainsi la proportion de traîtres à moins d'un tiers. Avant l'avènement de technologies telles que Bitcoin, ce problème était abordé par des algorithmes de consensus dits « traditionnels », parmi lesquels se distingue le PBFT (Practical Byzantine Fault Tolerance). Cet algorithme permet à un réseau de traiter des milliers de requêtes par seconde avec une latence inférieure à une milliseconde.
Cependant, ces systèmes traditionnels présentent une vulnérabilité significative : ils nécessitent une sélection préalable des nœuds autorisés à participer au consensus. Cette sélection peut être réalisée via une preuve d'autorité, une liste blanche de nœuds, ou une preuve d'enjeu déléguée. En raison de cette approche fermée, le système devient vulnérable aux attaques externes, les nœuds validateurs étant explicitement identifiés et donc plus exposés aux menaces.
L'introduction du Bitcoin en 2008 a marqué un tournant avec la mise en avant de l'algorithme de consensus de Nakamoto, basé sur la preuve de travail. Ce mécanisme utilise des blocs de transactions qui s'ajoutent à une blockchain. Dans ce système, la validité d'une chaîne est déterminée par son accumulation d'énergie, souvent désignée comme « la chaîne la plus longue ». Bien que des divergences puissent survenir temporairement dans le consensus, les incitations économiques inhérentes au protocole encouragent la conformité. Les mineurs, responsables de la validation des transactions, sont incités à déployer leur capacité de calcul en échange de bitcoins, ce qui les motive à maintenir l'intégrité du réseau.
L'invention du Bitcoin représente une avancée significative dans la résolution du problème dit des généraux byzantins, non par une finalité absolue, mais par une approche probabiliste. Contrairement aux algorithmes classiques qui garantissent une conclusion définitive, le système Bitcoin admet que, bien qu'une transaction ne soit jamais totalement irréversible, sa permanence peut être estimée de manière fiable après l'ajout de plusieurs blocs dans la chaîne. Le protocole de Nakamoto, au cœur du Bitcoin, repose sur un principe moins restrictif que la majorité des systèmes traditionnels, nécessitant que seulement 50 % de la puissance de calcul soit honnête, plutôt que les 67 % habituels.
Cette caractéristique permet à Bitcoin de fonctionner efficacement avec un grand nombre de nœuds participant de manière ouverte, ce qui est crucial pour une application aussi délicate que la monnaie. En effet, la plupart des fonctions économiques sont régulées par un monopole étatique et toute concurrence est généralement sanctionnée. C'est pourquoi, Bitcoin a dû opérer en marge des lois établies pour survivre.
