Le problème des généraux byzantins est une expérience de pensée en informatique théorique qui illustre la difficulté pour un ensemble d’acteurs (ordinateurs, nœuds) de parvenir à un consensus fiable dans un système distribué, surtout si certains de ces acteurs sont défaillants ou malhonnêtes (traîtres).

Qu’est-ce que le problème des généraux byzantins ?

Le scénario est le suivant : plusieurs généraux et leurs armées encerclent une ville ennemie et doivent décider collectivement d’attaquer ou de battre en retraite. Pour réussir, tous les généraux loyaux doivent s’entendre sur le même plan d’action. Les généraux communiquent uniquement par messagers. 

Le problème réside dans deux défis majeurs : 

• Communication incertaine : les messagers peuvent être interceptés ou retardés.
• Généraux traîtres : certains généraux (ou messagers) peuvent être des traîtres qui envoient de faux messages ou des messages contradictoires pour semer la confusion et empêcher un accord unanime.

L’objectif est de trouver un algorithme qui permette aux généraux loyaux d’arriver à un consensus, quelle que soit l’action des traîtres. Ce problème est fondamental en informatique distribuée, où il modélise la coordination de composants informatiques malgré des pannes arbitraires (“pannes byzantines”). 

Quelle est sa solution mathématique ? 

La solution au problème a été formalisée par Leslie Lamport, Robert Shostak et Marshall Pease dans un article fondateur. 

La principale conclusion mathématique est la suivante :

Un consensus ne peut être atteint que si le nombre de généraux loyaux est supérieur à deux fois le nombre de traîtres. Autrement dit, pour un système avec un total de 𝑁 généraux, il ne peut tolérer 𝐹 généraux traîtres que si  N ≥ 3F+1. 

Si cette condition n’est pas remplie (par exemple, un tiers ou plus des participants sont des traîtres), aucun algorithme déterministe basé uniquement sur l’échange de messages ne peut garantir un consensus fiable. 

Pour y parvenir, les auteurs ont proposé des algorithmes spécifiques, notamment : 

• L’algorithme de message oral (Oral Message Algorithm) : il repose sur des échanges de messages répétés (par récursion) pour s’assurer que chaque général reçoive suffisamment de confirmations d’ordres identiques. Il est prouvé qu’il fonctionne si la condition 𝑁 ≥ 3𝐹+1 est respectée.

• L’algorithme de message signé (Signed Message Algorithm) : il utilise la cryptographie, comme les signatures numériques, pour prouver l’authenticité de l’expéditeur et l’intégrité du message. Cela permet de démasquer plus facilement les traîtres qui tentent d’envoyer des messages contradictoires.

Dans le contexte moderne, le Bitcoin a été le premier système décentralisé à résoudre ce problème dans un environnement ouvert grâce à son mécanisme de preuve de travail (Proof of Work), qui rend la triche extrêmement coûteuse et permet d’atteindre la tolérance aux pannes byzantines (BFT). 

Application aux systèmes informatiques et à la blockchain 

Ce problème modélise les défis des réseaux décentralisés : 

• Absence d’autorité centrale : Les participants ne peuvent pas se fier à une seule source d’information de confiance.
• Communication non sécurisée : Les messages peuvent être perdus ou altérés.
• Acteurs malveillants : Certains nœuds du réseau peuvent agir de manière imprévisible ou malhonnête (appelées pannes byzantines).

La solution apportée par Bitcoin

Pendant des décennies, ce problème a posé un défi majeur pour les systèmes monétaires décentralisés. Bitcoin (ou plutôt Satoshi Nakamoto) a résolu le problème des généraux byzantins grâce à une combinaison de technologies, principalement son mécanisme de preuve de travail (Proof-of-Work) et la structure de la blockchain : 

• La preuve de travail rend coûteux le fait de proposer de faux blocs, décourageant les comportements malveillants.
• La règle de la chaîne la plus longue (le consensus) permet aux participants honnêtes de s’accorder sur une seule et unique version de la vérité, même si certains nœuds tentent de tricher.