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

TR#92-15, Computer Science Department, Hebrew University. C'est également bien connu dans l'industrie. Il n'est pas possible pour un système asynchrone d'assurer à la fois la sécurité (la garantie que tous les nœuds non malveillants finiront par s'entendre sur les progrès réalisés) et la vivacité (la capacité de continuer à progresser) avec un nombre de défaillances malveillantes supérieur à ce nombre..

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.

ils pourraient simplement éliminer celui qu’ils verraient en premier Et que se passe-t-il si nous avons des participants potentiellement malveillants ?

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.

un participant honnête honore un chèque et qu'un participant honnête honore l'autre.

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.

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

É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.

C’est l’exigence de sécurité.

C'est la condition de la vivacité.

h >= t > (h/2) + d h > (h/2) + d (h/2) > d d < (h/2) Ainsiun tiers ou plus des nœuds soient malhonnêtes soit la vivacité.