Protocoles BFT : PBFT et Tendermint

Le problème des généraux byzantins, formulé par Lamport, Shostak et Pease en 1982, pose la question suivante : un système distribué peut-il parvenir à un consensus lorsque certains participants envoient des messages contradictoires ? Le problème tire son nom de généraux byzantins qui doivent coordonner une attaque, mais peuvent compter parmi eux des traîtres envoyant des ordres divergents. Un système est tolérant aux fautes byzantines (BFT) s'il parvient à un consensus correct malgré la présence d'au plus fœuds malveillants parmi 3f+1 nœuds au total. BFT est la référence en matière de consensus pour les chaînes de blocs qui doivent garantir la sûreté face à des adversaires.

PBFT (Castro et Liskov, 1999) a été le premier protocole BFT pratique, démontrant que BFT pouvait fonctionner efficacement dans des systèmes réels. PBFT fonctionne par vues (termes), chacune ayant un primaire désigné (chef). En fonctionnement normal, trois phases sont exécutées : pré-préparation (le primaire diffuse la demande du client et le numéro de séquence), préparation (les répliques diffusent leur accord avec la séquence) et validation (les répliques diffusent une confirmation de validation). Une demande est exécutée lorsqu'une réplique recueille 2f+1 messages de validation concordants. PBFT garantit la sûreté et la vivacité si moins d'un tiers des répliques sont byzantines.

La principale limite de PBFT est sa complexité en messages de O(n^2) par demande : chacune des n répliques envoie des messages à toutes les autres pendant les phases de préparation et de validation. Pour n=100 répliques, chaque demande génère environ 10 000 messages. PBFT devient donc impraticable pour de grands ensembles de validateurs. La communauté de recherche sur BFT a consacré deux décennies à améliorer cette situation : BFT-SMART a réduit les constantes, HotStuff a atteint une complexité linéaire en messages grâce à un modèle de relais par le chef, et Tendermint a adapté les idées de PBFT à l'utilisation dans les chaînes de blocs publiques.

Lorsqu'un primaire PBFT est soupçonné d'être défaillant (expiration du délai d'attente), les répliques déclenchent un changement de vue. Chaque réplique diffuse un message de changement de vue contenant son état (les valeurs préparées de l'ancienne vue). Le nouveau primaire recueille 2f+1 messages de changement de vue, construit un message de nouvelle vue prouvant que la transition d'état est cohérente avec les valeurs précédemment validées, puis le diffuse. Les changements de vue sont coûteux — O(n^3) messages — et constituaient un goulot d'étranglement pratique. Des optimisations comme le certificat de changement de vue de PBFT et la conception de HotStuff avec traitement en continu répondent à ce problème.

Tendermint (2014, Kwon ; mise en production dans Cosmos en 2019) adapte PBFT aux environnements de chaînes de blocs publiques. Tendermint comporte trois phases par bloc : proposition (le chef diffuse le bloc proposé), pré-vote (les validateurs votent sur la proposition) et pré-validation (les validateurs votent pour valider le bloc après avoir observé deux tiers des pré-votes). Un bloc est validé lorsqu'un validateur recueille deux tiers des votes de pré-validation (un certificat de quorum, QC). Les validateurs deviennent proposants à tour de rôle, selon un ordre circulaire pondéré par la mise. Si un tour expire sans validation, les validateurs passent au tour suivant avec un vote nul.

Tendermint garantit une forte sûreté : un bloc validé est définitif et ne peut pas être révoqué tant que des validateurs détenant moins d'un tiers de la mise sont byzantins. Il s'agit d'une finalité synchrone : il n'y a plus de bifurcation après la validation. La vivacité exige un réseau partiellement synchrone : le protocole progresse dès que les délais des messages sont bornés, mais il n'exige pas un synchronisme permanent. Le compromis entre vivacité et sûreté est fondamental : Tendermint sacrifie la vivacité (il peut s'arrêter si le réseau se partitionne) pour garantir la sûreté, contrairement à des chaînes comme Bitcoin qui sacrifient la sûreté (en autorisant des bifurcations temporaires) au profit de la vivacité.

Le verrouillage des votes est un mécanisme essentiel de Tendermint. Lorsqu'un validateur envoie une pré-validation pour un bloc au tour r, il est verrouillé sur ce bloc. Lors des tours suivants, un validateur verrouillé ne peut effectuer un pré-vote que pour le bloc sur lequel il est verrouillé (ou un vote nul s'il reçoit la preuve que le bloc n'a pas été validé). Cela empêche les validations contradictoires entre les tours. Un validateur ne peut se déverrouiller que s'il reçoit, lors d'un tour ultérieur, un quorum de 2/3 pré-votes pour un autre bloc, ce qui prouve que le bloc initial n'a pas été validé.

La communication interchaînes de Cosmos (IBC) s'appuie sur la finalité instantanée de Tendermint pour les transferts interchaînes. Un client léger Tendermint suit l'ensemble des validateurs et la dernière validation (un en-tête de bloc accompagné de signatures de pré-validation des deux tiers). Pour vérifier un paquet provenant de la chaîne A, le module IBC de la chaîne B vérifie le certificat de quorum, c'est-à-dire que les deux tiers des validateurs de la chaîne A ont signé l'en-tête de bloc concerné. La sécurité d'IBC dépend ainsi de la garantie BFT de Tendermint : un transfert interchaînes est définitif dès que le bloc source est validé.

HotStuff (Yin et al., 2018 ; à la base de LibraBFT/DiemBFT de Facebook, aujourd'hui utilisé par Aptos et Sui) atteint une complexité de O(n) messages par tour de consensus grâce à une topologie en étoile : tous les validateurs envoient leurs votes au chef, qui les agrège en une signature à seuil (QC, certificat de quorum), puis diffuse la QC. HotStuff utilise une conception en chaîne à trois phases, dans laquelle les preuves de sûreté s'étendent sur trois QC consécutifs, ce qui permet le traitement en continu. Cette complexité linéaire rend HotStuff pratique pour 100 à 300 validateurs, comme dans les déploiements d'Aptos et de Sui.

Les chaînes de blocs d'entreprise (Hyperledger Fabric, Besu, Quorum) utilisent un consensus BFT pour les réseaux avec permission où l'identité des validateurs est connue. Le service de classement fondé sur Raft de Hyperledger Fabric fournit une tolérance aux pannes par arrêt (et non byzantines) pour les consortiums de confiance. L'étape BFT prévue par Fabric cible SmartBFT, une mise en œuvre sous forme de bibliothèque. R3 Corda utilise un groupe de notaires avec BFT-SMART pour empêcher la double dépense. Le choix entre CFT et BFT reflète les hypothèses de confiance : BFT est nécessaire lorsque les validateurs peuvent être adverses, tandis que CFT suffit lorsqu'ils sont simplement peu fiables.

Comprendre BFT exige de savoir quelles attaques il peut contrer et lesquelles lui échappent. BFT gère les validateurs qui émettent des messages contradictoires à différents pairs, ainsi que ceux qui s'arrêtent ou deviennent silencieux. Il ne gère pas les attaques Sybil : un attaquant qui contrôle un tiers des validateurs en créant de fausses identités peut compromettre la sûreté. C'est pourquoi les chaînes BFT publiques utilisent une pondération par la mise dans la preuve d'enjeu : acquérir un tiers de la mise coûte réellement de l'argent, ce qui assure une résistance aux attaques Sybil. BFT suppose également que les messages finissent par être livrés (synchronisme partiel) : une partition du réseau qui dure plus longtemps que le délai d'attente de vivacité peut arrêter la chaîne.

Quelle est la fraction maximale de validateurs qui peuvent être byzantins dans un protocole BFT standard tout en maintenant la sûreté ?

Les protocoles BFT garantissent le consensus malgré la présence d'au plus un tiers de validateurs malveillants. PBFT (1999) a démontré que BFT était pratique, mais présente une complexité en messages de O(n^2). Tendermint adapte PBFT aux chaînes de blocs avec une finalité instantanée et un verrouillage des votes. HotStuff atteint une complexité de O(n) grâce aux certificats de quorum fondés sur des signatures à seuil et est utilisé par Aptos et Sui. IBC de Cosmos utilise la finalité instantanée de Tendermint pour les transferts interchaînes vérifiés. Les chaînes de blocs d'entreprise utilisent BFT-SMART ou Raft selon qu'elles s'attendent à des fautes byzantines ou simplement à des arrêts.