Le problème des généraux byzantins étudie si les processus corrects peuvent prendre une décision commune lorsque les processus défaillants agissent arbitrairement et envoient des messages contradictoires à différents destinataires. La formulation de Lamport, Shostak et Pease de 1982 prouve la borne de 3m+1 participants pour tolérer m traîtres avec des messages oraux sans signatures et décrit des algorithmes récursifs pour les messages oraux et signés. Ces résultats supposent des conditions précises; ils ne désignent pas tout consensus de chaîne de blocs.
Lamport, Shostak et Pease ont publié l'allégorie dans ACM TOPLAS en juillet 1982 pour expliquer la cohérence interactive des systèmes répliqués. Des généraux séparés doivent choisir un plan alors qu'un traître peut transmettre des affirmations différentes. Une faute byzantine dépasse une panne franche : le composant peut mentir, équivoquer, omettre ou paraître correct seulement à certains observateurs. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
L'article sépare IC1, tous les lieutenants loyaux exécutent le même ordre, et IC2, si le commandant est loyal ils exécutent son ordre. Les notions modernes apparentées sont accord ou sûreté, validité et terminaison ou vivacité. Elles n'ont de sens qu'avec un modèle réseau, des hypothèses d'authentification et une borne de fautes. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Dans le modèle oral, le destinataire connaît l'expéditeur direct, détecte l'absence et chaque paire communique, mais un traître peut envoyer plusieurs valeurs. OM(m) relaie récursivement puis applique une majorité déterministe. Tolérer m processus byzantins exige au moins 3m+1 participants, donc plus de deux tiers loyaux. À trois, un loyal ne peut distinguer commandant menteur et pair menteur. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Des signatures infalsifiables révèlent l'équivoque et empêchent de modifier l'ordre signé d'un loyal. L'algorithme relaie les valeurs signées inédites puis décide sur l'ensemble collecté. Sous les hypothèses idéales du papier, tout nombre de traîtres devient tolérable. Mais la signature prouve l'origine, pas la vérité, la livraison à temps ni l'intégrité d'une clé compromise; Dolev et Strong ont ensuite précisé les bornes de tours. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Garantir le progrès dépend du temps. Le résultat Fischer–Lynch–Paterson de 1985 montre qu’un système déterministe complètement asynchrone à messages, même avec un seul processus pouvant s’arrêter, admet une exécution où le consensus ne termine jamais. FLP ne dit pas que les systèmes réels ne s’accordent jamais. La vivacité exige des hypothèses supplémentaires, comme des bornes temporelles ultérieures ou un détecteur de fautes aux propriétés précises, ou un protocole aléatoire. Nommer un chef ne suffit pas. Lors d’une longue partition, un protocole sûr peut cesser de terminer des opérations. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT de Miguel Castro et Barbara Liskov (1999) applique l’accord byzantin à une machine à états répliquée. La configuration de base n = 3f+1 tolère f répliques byzantines. Être préparé comprend un pre-prepare du primaire et 2f messages prepare concordants; la confirmation locale exige cet état et 2f+1 messages commit concordants. Les intersections de quorums et les règles de changement de vue empêchent les confirmations contradictoires. Authentification, numéros de séquence, points de contrôle et changements de vue gèrent falsification, rejeu, croissance du journal et chef défaillant. Membres connus et finalité déterministe diffèrent d’un réseau ouvert Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin n’exécute ni OM ni PBFT et ne compte pas les nœuds nommés. Proof of Work, résistant aux identités Sybil, pondère les historiques par travail cumulé; chaque Full Node rejette indépendamment les blocs contraires au consensus et suit la chaîne valide ayant le plus de travail. Des bifurcations temporaires sont prévues. Sous hypothèses de majorité honnête du travail et de communication, la probabilité de remplacement diminue avec la profondeur, sans irréversibilité mathématique. Bitcoin Backbone formalise préfixe commun, croissance et qualité sous hypothèses explicites de travail adverse et de réseau. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Dire que Bitcoin résout le problème masque un changement de modèle. L’accord classique part d’un groupe fixe d’identités connues et d’une borne f; Bitcoin admet des pseudonymes changeants et une ressource rare externe. Ses garanties exigent toujours des hypothèses précises de livraison. Proof of Work limite les Sybils mais n’empêche ni attaques éclipse, censure, minage égoïste, bogues, ni réorganisation par majorité de hachage. Le modèle de menace doit préciser adversaire, temps, membres et finalité; le seul mot BFT ne suffit pas. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Pour une vision complète, lisez aussi Nakamoto consensus, Proof of Work, Règles de consensus, Double dépense, Bitcoin, Finality.