Consensus byzantin tolérant aux pannes : Pourquoi un seuil de 33 %

Vous pouvez trivialement assurer la sécurité en ne faisant simplement aucun progrès. Et vous pouvez trivialement progresser de manière dangereuse en laissant simplement chaque nœud faire ce qu'il veut. Aucun de ces modes de fonctionnement n'est utile.

Prenons du recul pour rendre cette réponse plus utile :

Pourquoi avez-vous besoin d’un algorithme d’accord distribué ? Eh bien, vous en avez besoin dans les cas où il existe plusieurs manières pour un système de progresser valablement et vous avez besoin que tous les participants au système se mettent d'accord sur laquelle d'entre elles.

Prenons un exemple simple : j'ai 10 $ en banque et j'écris deux chèques de 10 $, un à Alice et un à Bob. L'un ou l'autre seul est valable, mais nous ne pouvons pas laisser les deux passer.

Si nous avions une autorité centrale, ils pourraient simplement éliminer celui qu’ils verraient en premier. Mais que se passe-t-il si nous ne voulons pas d’autorité centrale ou si nous ne voulons pas de point de défaillance unique ? Et que se passe-t-il si nous avons des participants potentiellement malveillants ?

Eh bien, vous pouvez simplement trier les chèques après les avoir représentés sous forme de données binaires. Mais c’est là que la composante asynchrone nous pique. Quand les trier ? Disons que je vois les deux chèques et que je les trie. Comment puis-je savoir qu'une seconde plus tard, je ne verrai pas de troisième chèque qui sera trié en premier ? Et peut-être que quelqu'un d'autre a déjà vu celui-là. Aie !

Nous avons donc les exigences suivantes :

1) Notre système est asynchrone.

2) Certains participants peuvent être malveillants.

3) Nous voulons la sécurité, c'est-à-dire que nous ne voulons pas qu'un participant honnête honore un chèque et qu'un participant honnête honore l'autre.

4) Nous voulons de la vivacité, c'est-à-dire qu'il n'est pas juste de simplement dire que nous n'encaissons jamais aucun chèque. Bien sûr, c'est sûr, mais pas utile. Nous voulons être sûrs de parvenir finalement à un accord sur les chèques à compenser.

Alors maintenant, la question se pose : combien de participants malhonnêtes pouvons-nous tolérer dans notre système asynchrone tout en garantissant à la fois la sécurité et la vivacité ?

Comme moyen simple d'obtenir l'essentiel de la preuve, même s'il n'est pas rigoureux :

Supposons que nous ayons n nœuds dont h sont honnêtes et d sont malhonnêtes. Évidemment, n = h + d. Le système doit maintenant parvenir à un consensus sur lequel des deux chèques doit être compensé.

Pensez au cas où tous les nœuds honnêtes sont répartis de manière égale dans les deux directions dans lesquelles le système pourrait progresser. Les nœuds malveillants pourraient dire à tous les nœuds honnêtes qu’ils sont d’accord avec eux. Cela donnerait aux nœuds h/2 + d un accord sur chacune des deux façons contradictoires dont le système pourrait progresser.

Dans ce cas, les nœuds honnêtes ne doivent pas progresser, sinon ils iront dans des directions différentes, perdant ainsi leur sécurité. Ainsi, le nombre de nœuds requis pour se mettre d’accord avant de pouvoir progresser doit être supérieur à la moitié du nombre de nœuds honnêtes plus le nombre de nœuds malveillants, sinon nous perdons la sécurité.

Si on appelle t le seuil nécessaire pour avancer, cela nous donne : t > (h/2) + d. C’est l’exigence de sécurité.

Mais les nœuds malveillants pourraient également ne pas parvenir à un accord. Ainsi, le nombre de nœuds requis pour se mettre d’accord avant de pouvoir progresser ne doit pas être supérieur au nombre de nœuds honnêtes, sinon nous perdrons notre vivacité.

Cela nous donne t = t. C'est la condition de la vivacité.

En combinant les deux résultats, nous obtenons :

h >= t > (h/2) + d h > (h/2) + d (h/2) > d d