Byzantine Fault Tolerance

Comment obtenir un consensus distribué même si une fraction des participants ment, triche, ou se comporte de façon arbitrairement bizarre.

Problème

Raft et Paxos supposent un modèle fail-stop : les nœuds tombent, mais ne mentent pas. Le modèle byzantin, introduit par Lamport, Shostak et Pease en 1982 (Byzantine Generals Problem), considère qu'une fraction des nœuds peut envoyer des messages contradictoires à différents pairs, falsifier des signatures, omettre des réponses ou collusionner. Dans ce modèle, comment N nœuds peuvent-ils décider d'une valeur unique malgré f malveillants ? Le résultat fondamental : il faut au moins 3f+1 nœuds pour tolérer f traîtres.

Forces

• Quorum : 3f+1 nœuds pour tolérer f byzantins (vs 2f+1 pour fail-stop).
• Coût communicationnel : O(N²) messages par décision dans PBFT — explose avec N.
• Cryptographie : signatures numériques obligatoires pour empêcher l'usurpation.
• Synchronie partielle : la sûreté tient toujours ; la liveness exige des fenêtres de synchronie.
• Performances : PBFT atteint quelques milliers de transactions/seconde sur 4-7 nœuds en LAN ; chute drastiquement au-delà.

Solution

PBFT (Castro & Liskov 1999) reste la référence pour les déploiements permissionnés (nœuds connus, identités vérifiées). Le protocole repose sur trois phases : pre-prepare (le primaire propose), prepare (les replicas diffusent ce qu'ils ont vu), commit (chacun s'assure qu'une majorité a accepté). Si le primaire est malicieux ou silencieux, un mécanisme de view change élit un nouveau primaire. Chaque message est signé. Variantes modernes : HoneyBadgerBFT (asynchrone), Tendermint (utilisé par Cosmos), HotStuff (utilisé par Diem/Libra et Aptos), Istanbul BFT (utilisé par Hyperledger Besu).

Structure

Client                  Replicas (R0=primary, R1, R2, R3)
   │                          │
   │ request ──────────────►  R0
   │                          │
   │                          R0 ── pre-prepare(n, req) ──► R1, R2, R3
   │                          │
   │                          R1, R2, R3 ── prepare(n) ──► all
   │                          │
   │                          R0, R1, R2, R3 ── commit(n) ──► all
   │                          │
   │ ◄────────────── reply ── R0, R1, R2, R3
   │
   │ Client waits f+1 matching replies before accepting.

Quorum: 2f+1 honest replies among 3f+1 total
Tolerance: f=1 → 4 nodes; f=2 → 7 nodes; f=3 → 10 nodes

Implémentation EDI

BFT n'est pas pertinent pour un hub EDI classique (les partenaires sont identifiés, signés, et la couche AS2/AS4 inclut déjà l'intégrité). Trois cas justifient son examen : (1) un consortium B2B fermé multi-acteurs où aucune partie ne fait confiance à l'opérateur central — typique de plateformes finance interbanque (R3 Corda, Hyperledger Fabric utilisent BFT pour leur ordering service) ; (2) un registre partagé de traçabilité supply chain (TradeLens, IBM Food Trust) où la falsification d'historique a des conséquences pénales ; (3) un futur réseau européen de carnets de produits numériques (DPP / passeport numérique du produit, règlement ESPR 2024) qui pourrait s'appuyer sur une couche BFT. Pour l'EDI commercial standard, la combinaison signature payload + audit log immuable est suffisante et moins coûteuse.

Anti-patterns

• Déployer BFT « parce que blockchain » alors qu'un audit log + signatures suffisent — surcoût inutile.
• BFT permissionless (Bitcoin, Ethereum PoS) sur des flux EDI commerciaux — incompatible avec les SLA temps de validation.
• Confondre PBFT et tolérance aux pannes simples — quorum mal dimensionné, sûreté perdue.
• Pas de rotation de leader — un primaire byzantin lent ralentit toutes les transactions sans déclencher view change.
• Croire que BFT élimine le besoin de TLS — la signature applicative ne protège pas contre l'analyse de trafic.

Patterns liés

• Paxos — consensus fail-stop, base théorique.
• Raft — consensus fail-stop pratique.
• Leader Election — sous-protocole de PBFT (view change).
• Event Sourcing — souvent combiné à BFT pour blockchains permissionnées.

Sources

• Lamport L., Shostak R., Pease M. — The Byzantine Generals Problem, ACM TOPLAS 1982. Le papier fondateur. lamport.azurewebsites.net
• Castro M., Liskov B. — Practical Byzantine Fault Tolerance, OSDI 1999. L'algorithme PBFT. pmg.csail.mit.edu
• Yin M. et al. — HotStuff: BFT Consensus in the Lens of Blockchain, PODC 2019. Base de Diem/Aptos.
• Hyperledger Fabric — Architecture documentation, ordering service BFT. hyperledger-fabric.readthedocs.io
• Tendermint Core — Tendermint BFT specification. docs.tendermint.com