Byzance, la capitale de l'ancien Empire romain d'Orient, était autrefois l'une des villes les plus puissantes et les plus riches du monde. Cependant, en raison de son vaste territoire, Byzance était souvent confrontée à des invasions externes et à des rébellions internes. Pour défendre ses frontières, Byzance envoya plusieurs armées, chacune commandée par différents généraux. Parvenir à un consensus entre ces généraux est devenu un défi important.
Le problème des généraux byzantins entretient une relation étroite avec la blockchain. Un réseau blockchain est un réseau distribué où les nœuds, à l'instar des généraux byzantins, doivent parvenir à un consensus sur les transactions et les données dans un environnement réseau peu fiable.

Problème des Deux Généraux

Le problème des deux généraux est un cas particulier du problème des généraux byzantins. Le problème et sa preuve de l'impossibilité ont été proposés pour la première fois par E.A. Akkoyunlu, K.Ekanadham et R.V. Huber dans leur article de 1975 "Some Constraints and Trade-offs In The Design of Network Communications." En 1978, Jim Gray a officiellement nommé ce problème le "problème des deux généraux" dans son livre "Notes on Data Base Operating Systems." À l'origine, il était utilisé pour analyser les problèmes liés à l'obtention d'un consensus par la communication sur un lien de communication peu fiable. Il est maintenant couramment utilisé pour illustrer les problèmes de cohérence et de consensus dans les systèmes distribués.

Définition du problème :
Deux armées du pays A, chacune dirigée par un général, se préparent à attaquer une armée du pays B. L'armée du pays B est encerclée dans une vallée, avec les deux armées de A stationnées sur les collines de chaque côté de la vallée. Cependant, le seul chemin entre les deux armées de A passe par la vallée. L'armée de B est plus forte que chacune des armées de A individuellement, mais si les deux armées de A attaquent ensemble, elles peuvent vaincre l'armée de B.
Problème : Peut-on concevoir un algorithme permettant aux deux généraux des armées de A de s'accorder sur une attaque simultanée ? L'algorithme peut inclure l'envoi et la réception de messages.
Solution : Le problème classique des deux généraux est insoluble. Il n’y a pas de protocole qui puisse garantir que les deux armées de A coordonneront avec succès leur attaque. Cependant, dans les systèmes pratiques, les problèmes peuvent être résolus de manière relativement fiable, comme avec le mécanisme de « poignée de main à trois voies » dans le protocole TCP.

Problème des généraux byzantins

Le problème des généraux byzantins a été proposé pour la première fois par Leslie Lamport, lauréat du prix Turing en 2013, dans son article de 1982 intitulé « Le problème des généraux byzantins ». Le problème décrit comment assurer la cohérence dans les systèmes distribués en présence d’un comportement malveillant, tel que la falsification de messages.
Plusieurs armées de l'Empire byzantin entourent une ville ennemie, chacune étant dirigée par un général. Les armées byzantines ne pouvaient communiquer que par l'intermédiaire de messagers. Après avoir observé les forces ennemies, les généraux byzantins doivent parvenir à la même conclusion : seulement si plus de la moitié des armées byzantines attaquent ensemble peuvent-elles capturer la ville et remporter la victoire.

Solution: Si le nombre de généraux (nœuds) dans un système byzantin est Z et le nombre de généraux non fiables (traîtres) est X, alors seulement lorsque Z ≥ 3X + 1, un protocole de tolérance aux fautes byzantines (BFT) peut garantir la cohérence du système.
Dans les systèmes pratiques, les défaillances provoquant des nœuds non réactifs sont classées comme des "Défaillances de Crash", tandis que les nœuds qui contrefont ou altèrent les messages sont classés comme des "Défaillances Byzantines".

Classification de l'algorithme de consensus

Les systèmes de blockchain sont un type de système distribué, en particulier les chaînes publiques comme Bitcoin et Ethereum, qui sont composées de nombreux nœuds de réseau hautement décentralisés et mutuellement méfiants. Le mécanisme de consensus de la blockchain garantit que le système de blockchain atteint constamment la cohérence des données sans fourches.
En fonction du type de tolérance aux fautes, les algorithmes de consensus peuvent être classés en algorithmes de tolérance aux fautes non-Byzantins (CFT) et en algorithmes de tolérance aux fautes byzantins (BFT).

Algorithmes de tolérance aux fautes non-byzantines

Dans les systèmes distribués, les algorithmes de tolérance aux fautes non-byzantines garantissent la fiabilité de l'ensemble du système distribué lorsque les nœuds subissent des défaillances du système ou des interruptions non planifiées (fautes non-byzantines). Cependant, lorsque des nœuds malveillants contrefont ou manipulent les données, les algorithmes de tolérance aux fautes non-byzantines ne peuvent pas garantir la fiabilité du système. Ces algorithmes sont principalement utilisés dans des systèmes distribués d'entreprise fermés et contrôlés. Les algorithmes de tolérance aux fautes non-byzantines les plus représentatifs comprennent l'algorithme Paxos et l'algorithme Raft.

Algorithmes de tolérance aux fautes byzantines

Les algorithmes de tolérance aux fautes byzantines permettent à un système distribué de garantir la fiabilité même si les nœuds rencontrent n'importe quel type de faute, tant que le nombre de nœuds défectueux n'excède pas une certaine proportion. En d'autres termes, tant que le nombre de nœuds défectueux (en raison de fautes non byzantines ou byzantines) est inférieur à une certaine proportion du nombre total de nœuds, les algorithmes de tolérance aux fautes byzantines peuvent garantir la fiabilité du système. En raison de la présence de nombreux nœuds réseau non dignes de confiance dans les systèmes de blockchain tels que Bitcoin et Ethereum, les algorithmes de tolérance aux fautes byzantines sont principalement utilisés dans les mécanismes de consensus de la blockchain. Les algorithmes de tolérance aux fautes byzantines les plus représentatifs comprennent PBFT (Tolérance aux fautes byzantines pratiques), PoW (Preuve de travail) et PoS (Preuve d'enjeu).