Tolérance aux pannes et fautes byzantines

La question de départ

Sept caissiers, dans sept villes, tiennent chacun une copie du même registre. Un matin, l'un d'eux ne répond plus. Un autre répond, mais dit « oui » à la caissière de Douala et « non » à celle de Garoua pour la même question. Ces deux incidents se ressemblent-ils ? Les traiter de la même façon serait une erreur grave.

Les types de fautes

Le nom vient du « problème des généraux byzantins » (Lamport, Shostak et Pease, 1982) : des généraux doivent décider ensemble d'attaquer ou non, alors que certains sont traîtres et mentent.

Une faute byzantine n'est pas forcément malveillante : un bit corrompu en mémoire, un bogue logiciel ou une configuration erronée produisent aussi des comportements arbitraires. Mais en sécurité, on suppose le pire : un adversaire qui connaît le protocole.

Pourquoi la seconde coûte plus cher

Face à une panne franche, un nœud fiable peut raisonner : « ce qu'il m'a dit était vrai ». Il peut seulement manquer d'informations. Face à un byzantin, rien de ce qu'il dit n'est digne de confiance, et il peut dire des choses différentes à chacun (on appelle cela de l'équivocation). Il faut donc recouper les témoignages, et il en faut davantage.

Exemple détaillé : trois nœuds, sans signatures

Trois nœuds A, B, C qui s'échangent des messages oraux (sans signatures : chacun relaie ce qu'il a entendu, sans preuve). A veut savoir si C a voté « oui » ou « non ».

• Si C est en panne franche : A n'entend rien de C. A sait qu'il manque une voix.
• Si C est byzantin : C dit « oui » à A, et « non » à B. A interroge B : B répond « C m'a dit non ». A voit deux versions, mais il ne peut pas savoir si c'est C qui ment ou B : de son point de vue, la contradiction est symétrique. Sans signatures, avec trois nœuds et un fautif, impossible de trancher. Avec des signatures, le diagnostic devient possible (voir ci-dessous), mais la leçon 3 montre qu'un protocole à quorum a quand même besoin d'au moins 4 nœuds.

Rôle des signatures (atelier 105)

Si les messages sont signés, B ne peut pas mentir sur ce que C a dit : il ne peut présenter que des messages réellement signés par C. Mais cela n'empêche pas C de signer « oui » pour A et « non » pour B. Une signature prouve qui a dit quoi, pas que ce qui est dit est vrai ni unique. En revanche, deux messages contradictoires signés par C constituent une preuve d'équivocation : tout le monde peut vérifier que C s'est contredit. C'est la base de la punition automatique (slashing) dans certains protocoles. Avec des signatures, A peut donc constater la contradiction de C, mais seulement après coup : la décision a pu être prise entre-temps.

Tolérer des pannes franches : 2f + 1

Si l'on suppose seulement des pannes franches, une majorité suffit : avec n = 2f + 1 nœuds, f peuvent tomber et les f + 1 restants forment encore une majorité. Trois nœuds tolèrent 1 panne ; cinq en tolèrent 2. C'est le modèle des protocoles de réplication comme Paxos ou Raft. Il suppose qu'aucun nœud ne ment.

À vous

Dans quorum-sim, réglez 7 validateurs et passez-en un en « hors ligne », puis un autre en « byzantin ». Comparez le comportement du quorum : le nœud hors ligne retire une voix ; le byzantin peut en fournir une fausse ou contradictoire.

Ce que cela ne garantit pas

Classer un incident comme panne franche est une hypothèse : un nœud silencieux peut être byzantin (il se tait volontairement), et un nœud lent peut passer pour mort (leçon 1 de l'atelier 107).

En bref

• Panne franche : le nœud se tait, ne ment pas. Byzantin : comportement arbitraire, y compris dire des choses différentes à chacun.
• Les signatures attribuent les messages mais n'empêchent pas l'équivocation ; elles la rendent prouvable.
• Pannes franches seules : 2f + 1 nœuds. Fautes byzantines : plus, comme on va le voir.

La question de départ

Quatre validateurs doivent décider quel bloc est le prochain. Combien de voix faut-il pour que la décision soit définitive ? Si on dit « la majorité simple, 3 sur 4 », est-ce suffisant face à un byzantin ? Pour répondre, il faut deux notions précises.

Sûreté et vivacité

• Sûreté (safety) : « il ne se passe jamais rien de mauvais » ; ici, deux nœuds honnêtes ne décident jamais de deux valeurs différentes pour la même position.
• Vivacité (liveness) : « il se passe finalement quelque chose de bon » ; ici, le système finit par décider.

Ce sont deux propriétés indépendantes. Un système qui ne décide jamais est sûr (il ne se contredit pas) mais n'est pas vivant. Les protocoles BFT classiques sont conçus pour qu'il vaille mieux s'arrêter que se contredire : face à des pannes franches ou à un réseau défaillant, on perd la vivacité avant la sûreté. Mais face à plus de f nœuds byzantins, les deux peuvent être perdues en même temps (leçon 3).

Le concept : le quorum

Un quorum est un ensemble de nœuds dont l'accord suffit à valider une étape. Une règle simple : une valeur est décidée quand elle est confirmée par un quorum de taille q.

Deux exigences contradictoires pèsent sur q :

1. q ne doit pas être trop grand : le système doit avancer même si f nœuds se taisent. Donc q ≤ n − f.
2. q ne doit pas être trop petit : deux quorums doivent forcément partager un nœud honnête, sinon deux valeurs contradictoires pourraient être décidées en parallèle.

Exemple détaillé : quatre validateurs, f = 1

n = 4, un byzantin possible, q = 3 (nous justifierons ce choix en leçon 3).

• Deux quorums de 3 parmi 4 partagent au moins 3 + 3 − 4 = 2 nœuds.
• Au plus 1 est byzantin : au moins 1 des 2 est honnête.
• Un nœud honnête ne vote qu'une fois par position : il ne peut pas confirmer deux valeurs différentes. Donc les deux quorums ne peuvent pas décider deux valeurs différentes. La sûreté est préservée.

Avec q = 2 sur 4 : deux quorums disjoints {A, B} et {C, D} existent, chacun pourrait décider une valeur différente. Sûreté perdue même sans faute.

Exemple détaillé : sept validateurs, f = 2

n = 7, q = 5. Deux quorums partagent au moins 5 + 5 − 7 = 3 nœuds ; au plus 2 sont byzantins, donc au moins 1 honnête. Et le système vit : 7 − 2 = 5 nœuds répondent encore, c'est juste un quorum.

Quorum et lecture de l'état

Une fois la valeur décidée par un quorum, un client qui interroge un quorum rencontrera au moins un nœud honnête qui l'a vue, mais il ne sait pas lequel est honnête. Il lui faut f + 1 réponses identiques pour être sûr qu'au moins l'une vient d'un nœud honnête. C'est ce qui permet à un client de vérifier sans faire confiance à un seul serveur.

Ce que cela ne garantit pas

• Un quorum garantit la sûreté si le nombre de nœuds byzantins ne dépasse pas f. Au-delà, les garanties s'effondrent (leçon 3).
• Un quorum n'assure pas la vivacité si le réseau est trop lent ou coupé : on peut attendre longtemps. Une absence de décision n'est pas forcément une attaque.
• Un quorum prouve que « assez de nœuds ont voté », pas que la valeur décidée est valide : la validité est vérifiée par chaque nœud honnête avant de voter.

À vous

Dans quorum-sim, réglez 7 validateurs, 2 byzantins : le quorum de 5 est-il atteignable ? Passez-en un troisième en byzantin ou hors ligne et regardez ce qu'indique l'outil.

En bref

• Sûreté = jamais deux décisions contradictoires ; vivacité = on finit par décider. Indépendantes.
• Un quorum q doit satisfaire q ≤ n − f (vivacité) et deux quorums doivent partager un nœud honnête (sûreté).
• Avec n = 4, f = 1 : q = 3. Avec n = 7, f = 2 : q = 5.

La question de départ

On lit partout : « un protocole BFT tolère jusqu'à un tiers de nœuds byzantins ». D'où vient ce tiers ? Pourquoi pas la moitié, comme pour les pannes franches ? Et à quelles conditions est-ce vrai ?

Les hypothèses (à lire avant le raisonnement)

Le raisonnement par comptage ci-dessous vaut pour le modèle suivant :

1. n nœuds, dont au plus f sont byzantins (le reste est honnête).
2. Les nœuds honnêtes suivent le protocole ; les byzantins peuvent tout faire, y compris se coordonner.
3. Le réseau peut retarder les messages, mais un message entre nœuds honnêtes finit par arriver. Nous voulons que la sûreté tienne même sans borne de délai, et la vivacité tienne quand le réseau finit par se comporter (hypothèse dite de synchronie partielle).
4. Les messages sont authentifiés (un nœud ne peut pas se faire passer pour un autre). Il peut en revanche dire des choses différentes à chacun. Des signatures transférables n'abaissent pas, en synchronie partielle, le nombre de nœuds nécessaires.
5. Le protocole est déterministe, sur une machine à états répliquée.

Dans d'autres modèles, les bornes diffèrent : par exemple, avec un réseau synchrone (délais bornés et connus) et des signatures infalsifiables, le problème des généraux peut se résoudre pour un nombre de traîtres plus grand, selon l'article de 1982 ; sans signatures, ce même article donne la borne n > 3f. Et dans un réseau purement asynchrone, aucun protocole déterministe ne peut garantir la terminaison (tout en restant sûr) si ne serait-ce qu'un nœud peut tomber en panne (résultat de Fischer, Lynch et Paterson, 1985) : c'est pourquoi on suppose une synchronie partielle pour la vivacité.

Attention à la portée de ce qui suit : le comptage montre ce qu'exige une règle de décision par quorum. La borne n ≥ 3f + 1 est aussi établie pour tout protocole (Lamport, Shostak et Pease, 1982, sans signatures en réseau synchrone ; Dwork, Lynch et Stockmeyer, 1988, en synchronie partielle) par un argument d'indistinguabilité que nous ne reproduisons pas.

Le raisonnement par comptage

On cherche la taille q d'un quorum et le nombre n de nœuds. Deux contraintes :

• Vivacité : on doit pouvoir décider même si les f byzantins se taisent. Seuls n − f nœuds répondent, donc q ≤ n − f.
• Sûreté : deux quorums quelconques se recoupent en au moins 2q − n nœuds. Parmi eux, f peuvent être byzantins, il faut donc qu'au moins un soit honnête : 2q − n ≥ f + 1, soit q ≥ (n + f + 1) ÷ 2.

On enchaîne : (n + f + 1) ÷ 2 ≤ q ≤ n − f, ce qui exige (n + f + 1) ÷ 2 ≤ n − f, c'est-à-dire n + f + 1 ≤ 2n − 2f, d'où n ≥ 3f + 1.

Pour n = 3f + 1, la taille de quorum compatible est q = 2f + 1.

Pourquoi 3 nœuds ne tolèrent pas 1 byzantin

n = 3, f = 1. Il faudrait q ≤ 2 (vivacité) et 2q − 3 ≥ 2, soit q ≥ 2,5 (sûreté) : impossible. Concrètement : A et B sont honnêtes, C est byzantin. A ne peut pas attendre C (il peut se taire), donc il décide avec {A, C} ; B décide de même avec {B, C}. C vote X avec A et Y avec B : deux décisions contradictoires, et le seul nœud commun aux deux quorums, C, est fautif. Ce raisonnement vaut même avec des messages signés.

Le tiers « en pourcentage »

n ≥ 3f + 1 s'écrit f < n ÷ 3 : le protocole est sûr tant que strictement moins d'un tiers des nœuds sont byzantins. Dans les chaînes à preuve d'enjeu, n est remplacé par la part d'enjeu (l'enjeu, ou stake, désigne les jetons que chaque validateur met en garantie ; les voix sont pondérées) : l'hypothèse devient « moins d'un tiers de l'enjeu est byzantin ».

Convention : dans cet atelier, une décision exige strictement plus des deux tiers des voix (q = 2f + 1 quand n = 3f + 1). D'autres descriptions de protocoles (voir l'atelier 109) disent « deux tiers » sans préciser si c'est strict ou inclusif ; la différence compte précisément à un tiers exactement.

Que se passe-t-il au-delà de f ?

n = 4, f toléré = 1, mais deux nœuds byzantins B1 et B2, et deux honnêtes H1 et H2. Quorum q = 3. B1 et B2 votent « X » avec H1, formant le quorum {B1, B2, H1}, et votent « Y » avec H2, formant {B1, B2, H2}. Les deux quorums se recoupent en {B1, B2} : deux décisions contradictoires pour une même position. La sûreté est perdue. Le seuil n'est pas une zone de confort : au-delà, la garantie disparaît totalement.

Le papier fondateur de la tolérance pratique aux fautes byzantines est celui de Castro et Liskov, Practical Byzantine Fault Tolerance (OSDI 1999), qui travaille dans ce modèle avec n ≥ 3f + 1.

Ce que cela ne garantit pas

• La borne dit « si au plus f fautifs » ; elle ne dit pas que moins de f fautifs est probable. Qui contrôle la proportion de nœuds fautifs ? Dans un réseau ouvert, c'est la question de l'identité des validateurs (preuve d'enjeu, autorisation).
• Elle ne couvre pas les attaques contre le réseau lui-même (partitions fabriquées, atelier 107).
• Elle ne dit rien de la validité des transactions, de la performance, ni de la décentralisation.

En bref

• Contraintes : q ≤ n − f (vivacité) et 2q − n ≥ f + 1 (sûreté) donnent n ≥ 3f + 1 et q = 2f + 1.
• Hypothèses : au plus f byzantins, messages authentifiés, sûreté sans borne de délai, vivacité en synchronie partielle.
• Au-delà de f byzantins, la sûreté peut être perdue, pas seulement dégradée.

La question de départ

Un réseau à preuve d'enjeu annonce : « sûr tant que moins d'un tiers de l'enjeu est byzantin ». Combien coûte, en argent, de dépasser ce seuil ? La réponse « un tiers de la valeur totale » est un point de départ, pas un résultat.

Ce que chaque fraction de l'enjeu permet (dans le modèle de la leçon 3)

Le seuil exact : la sûreté est garantie pour b < n ÷ 3. À b = n ÷ 3 exactement (quand la division est exacte), avec un quorum strictement supérieur aux 2/3, la sûreté tient encore mais la vivacité est perdue ; au-delà, la sûreté n'est plus garantie. Avec une règle inclusive « au moins 2/3 », en revanche, exactement un tiers de fautifs suffit déjà à perdre la sûreté.

Exemple détaillé

Réseau fictif : 2 400 000 jetons mis en enjeu au total, un jeton valant 3 unités fictives.

• Un tiers de l'enjeu : 2 400 000 ÷ 3 = 800 000 jetons.
• Prix naïf : 800 000 × 3 = 2 400 000 unités.

Cette valeur est un plancher théorique, pas un prix. Pourquoi ?

1. Acheter fait monter le prix. Si le marché est peu profond, acquérir 800 000 jetons coûte plus que 3 par jeton (glissement).
2. L'enjeu peut être verrouillé : jetons en période de retrait, détenus par des gens qui ne vendent pas, ou non achetables.
3. Le calcul dépend de la façon d'acquérir. Si l'attaquant rachète des jetons déjà mis en enjeu, le total reste 2 400 000 et il lui faut 800 000. S'il ajoute de l'enjeu neuf, le total augmente : il lui faut x tel que x ÷ (2 400 000 + x) ≥ 1 ÷ 3, soit x ≥ 1 200 000 jetons, 50 % de plus.
4. La sanction (slashing) : si le protocole détruit l'enjeu pris en flagrant délit d'équivocation (preuve de la leçon 1), l'attaque coûte l'enjeu perdu en plus.
5. Le gain : l'attaquant ne dépense que si le gain espéré dépasse le coût. Un seuil est aussi une question d'incitations, pas seulement de mathématiques.

Corrompre au lieu d'acheter

On peut aussi corrompre des validateurs qui détiennent déjà 800 000 jetons : le coût est alors le pot-de-vin, pas le prix des jetons. Si un petit nombre de gros validateurs concentre l'enjeu, il suffit parfois d'en convaincre peu. La concentration de l'enjeu est donc une mesure de sécurité autant que le montant total.

Ce que cela ne garantit pas

Rester sous le tiers garantit les propriétés du protocole dans son modèle. Cela ne protège pas d'un bug d'implémentation, d'une clé de validateur volée (atelier 105) ou d'une partition (atelier 107) qui placerait des honnêtes du mauvais côté.

En bref

• À un tiers de l'enjeu, un attaquant peut bloquer ; au-delà, avec le réseau, il peut parfois contredire. Au-delà des deux tiers, il décide.
• Seuil théorique ≠ prix : glissement, verrouillage, pot-de-vin, sanction et gain comptent.
• Acquérir 1/3 par rachat coûte 1/3 du total ; en ajoutant de l'enjeu neuf, il faut 1/2 du total existant.