Problème des Généraux byzantins

L'énoncé classique

Le problème des Généraux byzantins est formalisé en 1982 par Leslie Lamport, Robert Shostak et Marshall Pease dans l'article The Byzantine Generals Problem. La métaphore :

Plusieurs généraux de l'armée byzantine assiègent une ville ennemie. Chacun commande une division postée autour de la cité. Pour gagner, ils doivent attaquer ou se retirer simultanément. S'ils sont divisés, ils perdent. Le problème : les généraux ne communiquent que par messagers, certains généraux peuvent être traîtres et envoyer des messages contradictoires à différents pairs. Comment s'accorder ?

C'est l'archétype du consensus en environnement adversarial.

Pourquoi c'est si difficile

Plusieurs obstacles s'empilent :

1. Pas de canal sécurisé direct entre tous les généraux.
2. Messagers peuvent être interceptés ou tués.
3. Certains généraux mentent et envoient des informations contradictoires à différents pairs.
4. Pas d'autorité centrale pour arbitrer.

Lamport démontre que pour qu'un consensus soit possible, il faut au moins 3f + 1 généraux dont f traîtres maximum. Avec 3 généraux dont 1 traître, c'est impossible. Avec 4 généraux dont 1 traître, c'est possible mais coûteux en communication.

Liens avec Bitcoin

Avant Bitcoin, les solutions au problème (PBFT, Paxos, Raft) supposaient un comité fixe et identifié de généraux. Cela ne marche pas pour une monnaie globale ouverte :

• Comment identifier les généraux ?
• Comment empêcher la création de faux généraux (Sybil attack) ?
• Comment récompenser la coopération sans autorité centrale ?

Satoshi Nakamoto, dans le white paper de 2008, propose une solution probabiliste et économique : la preuve de travail. Chaque général « vote » avec son hashrate, et la branche la plus longue de la chaîne représente le consensus. Plus la chaîne est longue, plus le consensus est solide.

Le génie de la PoW

L'innovation de Bitcoin est triple :

1. Identification sans autorité : pas besoin de comité, n'importe qui peut miner.
2. Sybil resistance : créer plus d'identités ne donne pas plus de poids, seul le hashrate compte.
3. Récompense alignée : les généraux honnêtes sont payés en BTC, les traîtres perdent leur électricité.

C'est la première solution pratique et ouverte au problème des Généraux byzantins.

Solution probabiliste vs déterministe

| Modèle | Finalité | Comité | Tolérance | Coût | |--------|----------|--------|-----------|------| | BFT classique | Déterministe | Fermé | f < n/3 | Communication O(n²) | | Bitcoin PoW | Probabiliste | Ouvert | < 51 % hashrate | Énergie + hardware | | PoS (Ethereum) | Probabiliste | Ouvert mais stakable | < 33 % stake | Capital + slashing |

Bitcoin ne garantit pas une finalité instantanée : une transaction est probabilistiquement irréversible après quelques confirmations. Cette finalité « molle » est ce qui permet l'ouverture du système.

Le théorème de Lamport en pratique

Lamport avait prouvé qu'un consensus byzantine-fault-tolerant nécessitait au moins 2/3 d'honnêteté. Bitcoin réduit ce seuil à 1/2 d'honnêteté du hashrate, mais au prix d'une finalité probabiliste et d'une consommation d'énergie réelle.

Importance historique

Le problème, longtemps considéré comme « insoluble en pratique pour un système ouvert et anonyme », a été résolu en 2008 par un anonyme via une combinaison ingénieuse de :

• Cryptographie (hash, signatures)
• Théorie des jeux (incitations économiques)
• Réseau P2P
• Difficulty adjustment

Bitcoin est devenu l'implémentation canonique de la solution au problème des Généraux byzantins en environnement adversarial ouvert.

À retenir

Le problème des Généraux byzantins n'est pas qu'un exercice théorique : c'est le défi central du consensus distribué. Bitcoin en propose une solution radicalement nouvelle, qui transforme la résistance à la censure et à la fraude en une propriété émergente d'incitations économiques alignées. Toute la suite de la blockchain est une variation sur ce thème fondateur.