Comprendre les bases de la blockchain: le défi des généraux byzantins. partie 1

La traduction de l'article a été préparée spécialement pour les étudiants du cours «High Load Architect» , qui commence ce mois-ci.

---

La blockchain est un système décentralisé composé de différentes entités qui agissent en fonction de leurs incitations et des informations dont elles disposent.

Chaque fois qu'une nouvelle transaction est diffusée sur le réseau, les nœuds peuvent inclure cette transaction dans une copie de leur registre ou l'ignorer. Lorsque la plupart des participants au réseau décident d'accepter un certain état, un consensus est atteint.

Un problème fondamental dans l' informatique distribuée et les systèmes multi-agents est d'obtenir la fiabilité globale du système en présence d'un certain nombre de processus inopérants. Souvent, cela nécessite que les processus coordonnent entre eux une certaine valeur qui sera nécessaire lors du calcul.

Ces processus sont décrits comme un consensus.

• Que se passe-t-il lorsqu'un participant décide de ne pas suivre les règles et d'intervenir dans l'état de son grand livre?
• Que se passe-t-il quand il y a beaucoup de tels participants dans le réseau, mais pas la majorité?

Pour qu'un protocole consensuel soit sécurisé, il doit être tolérant aux pannes.

Pour commencer, nous parlerons brièvement du problème insoluble de deux généraux. Ensuite, examinez le problème des généraux byzantins et discutez de la tolérance aux pannes byzantine dans les systèmes distribués et décentralisés. Et à la toute fin, parlons de la façon dont tout cela se rapporte à la technologie de la blockchain.

La tâche de deux généraux

Cette tâche, publiée pour la première fois en 1975 et nommée en 1978, décrit un scénario dans lequel deux généraux attaquent un ennemi commun. Le premier général est considéré comme le chef, et le second est le suiveur. L'armée de chaque général ne suffit pas à elle seule pour vaincre l'armée ennemie, ils doivent donc coopérer et attaquer en même temps. Ce scénario semble simple, mais il y a une mise en garde:

Pour qu’ils communiquent et s’accordent sur une heure, le premier général doit envoyer un messager à travers le camp ennemi, il doit délivrer un message avec l’heure du début de l’attaque au deuxième général. Cependant, il est probable que le messager sera capturé par des adversaires et que le message ne soit pas délivré. Cela conduira au fait que l'armée du premier général va attaquer, et la seconde restera en place.

Même si le premier message est délivré, le deuxième général doit confirmer (ACK (accusé de réception), noter la similitude avec la négociation à trois voies dans TCP ) qu'il a reçu le message, il renvoie donc le messager, reproduisant ainsi le scénario précédent où le messager peut être capturé . Cela se traduit par des accusés de réception sans fin, et à cause de cela, les généraux ne peuvent pas parvenir à un accord.

Il n'y a aucun moyen de garantir la deuxième condition, c'est-à-dire que chaque général est pleinement convaincu que l'autre est d'accord avec le plan d'attaque. Les deux généraux ignorent toujours si le messager a atteint son camarade.



Il a été prouvé que la tâche de deux généraux est insoluble.

La tâche des généraux byzantins

Décrite en 1982 par Lamport, Shostak et Piz, la version de ce problème s'est avérée être un point culminant. Elle décrit le même scénario, où au lieu de deux généraux, plus de généraux devraient s'entendre sur le moment de l'attaque. Une complication supplémentaire est qu'un ou plusieurs généraux peuvent être des traîtres, c'est-à-dire qu'ils peuvent mentir sur leurs intentions (par exemple, le général dit qu'il accepte d'attaquer à 09h00, mais ne le fait pas).

Le paradigme du leader-suiveur décrit dans la tâche de deux généraux se transforme en une installation de commandant subordonné. Pour parvenir à un consensus ici, le commandant et chaque subordonné doivent s'entendre sur la même solution (attaque ou retraite).

Traduction d'images:

La tâche des généraux byzantins. Le commandant général doit envoyer un ordre à ses n-1 subordonnés, tel que:

• Tous les généraux subalternes fidèles obéissent à un seul commandement.
• Si le commandant général est loyal, alors tous ses fidèles subordonnés obéissent à ses ordres.

Outre le deuxième point, un fait intéressant doit être souligné: si le commandant est un traître, il faut quand même parvenir à un consensus. En conséquence, tous les lieutenants ont un vote majoritaire.

L'algorithme de consensus dans ce cas est basé sur la signification de la plupart des décisions que les subordonnés voient.

Théorème: pour tout m , l'algorithme OM (m) atteint un consensus avec plus de 3 m de généraux et un maximum de m traîtres.

Cela signifie que l'algorithme peut atteindre un consensus alors que 2/3 des participants sont honnêtes. Si les traîtres sont supérieurs à 1/3, le consensus n'est pas atteint, les armées ne peuvent pas coordonner leurs attaques et l'ennemi gagne.

Algorithme OM (0)

1. Le commandant envoie sa valeur à chacun de ses subordonnés.
2. Chaque subordonné utilise la valeur qu'il reçoit du commandant ou utilise la valeur DELAY s'il ne reçoit aucune valeur.

Algorithme OM (m), m> 0

1. Le commandant envoie avec son importance à chacun des subordonnés.
2. Pour chaque i, soit vi la valeur que le ième subordonné reçoit du commandant, ou la valeur RESET sera utilisée si le subordonné ne reçoit aucune valeur. Le i-ème subordonné agit en tant que commandant dans l'algorithme OM (m-1) et envoie une valeur à chacun des n-2 subordonnés restants.
3. Pour chaque i, à condition que ji, soit vj la valeur que le i-ème subordonné a reçue du j-th subordonné à l'étape (2) (en utilisant l'algorithme OM (m-1)), ou utilise la valeur DELAY si n'a pas de sens. Le ième esclave utilise la valeur majoritaire (v1, ..., vn-1).

Lorsque m = 0, il n'y a pas de traîtres, chaque subordonné suit l'ordre. Pour m> 0, chaque choix final d'un subordonné provient de la partie prédominante de l'élection de tous les subordonnés.
Ce sera plus clair si vous regardez la situation du point de vue du second subordonné - que C soit le commandant, et L {i} est le i-ème subordonné.



OM (1): le subordonné 3 est un traître. La situation du point de vue du second subordonné.

Étapes:

1. Le commandant envoie v à tous ses subordonnés.
2. L1 envoie à L2 la valeur de v ou L3 envoie à L2 la valeur de x.
3. L2 ← majorité (v, v, x) == v

La décision finale est prise à la majorité des voix de L1, L2 et L3 et, par conséquent, un consensus est atteint.

Il est important de se rappeler que l'objectif est que la plupart des subordonnés choisissent la même solution, plutôt qu'une solution spécifique.

Regardons le cas où le commandant est un traître.



OM (1): Le commandant est un traître.

Étapes:

1. Le commandant envoie à L1, L2, L3 les valeurs de x, y, z, respectivement;
2. L1 envoie la valeur de x aux esclaves L2, L3 | L2 envoie à L1, L3 la valeur de y | L3 envoie à L1, L2 la valeur de z;
3. L1 ← majorité (x, y, z) | L2 ← plus (x, y, z) | L3 ← majorité (x, y, z)

Ils ont tous la même valeur, donc un consensus est atteint. Notez que même si les valeurs de x, y, z sont toutes différentes, la valeur majoritaire (x, y, z) est la même pour les trois subordonnés. Si x, y, z sont des ordres complètement différents, nous pouvons supposer qu'ils agiront selon le plan par défaut - RESET.

Pour regarder une approche pratique d'un exemple plus complexe avec 7 généraux et 3 traîtres, je vous suggère de lire cet article .

Tolérance aux pannes byzantine

La tolérance aux pannes byzantine est une caractéristique qui définit un système qui autorise une classe de défaillances qui appartient à la tâche des généraux byzantins. L'échec byzantin est la classe de types d'échec la plus complexe. Il n'implique aucune restriction et ne fait aucune hypothèse sur le type de comportement qu'un nœud peut avoir (par exemple, un nœud peut générer des données arbitraires, se présentant comme un participant honnête).

Les erreurs byzantines sont les plus difficiles à corriger. La tolérance aux pannes byzantine était nécessaire dans les systèmes de moteurs d'avion, dans les centrales nucléaires et dans pratiquement tous les systèmes dont les actions dépendent des résultats d'un grand nombre de capteurs. Même SpaceX le considère comme une exigence potentielle pour ses systèmes.

L'algorithme mentionné dans la section précédente correspond à la tolérance aux pannes byzantine jusqu'à ce que le nombre de traîtres dépasse un tiers de tous les généraux. Il existe d'autres options pour faciliter cette tâche, notamment l'utilisation de signatures numériques ou l'introduction de restrictions sur la communication entre pairs.

Comment tout cela est-il lié à la blockchain?

La blockchain sont des registres décentralisés qui, par définition, ne sont pas contrôlés par l'autorité centrale. En raison des valeurs qui y sont stockées, les attaquants ont une bonne incitation économique à tenter de commettre une erreur. Néanmoins, la tolérance aux pannes byzantine et, par conséquent, la solution du problème général byzantin pour la blockchain sont simplement nécessaires.

En l'absence de tolérance de panne byzantine, un pair peut transmettre et publier de fausses transactions, annulant complètement la fiabilité de la blockchain. Pour aggraver les choses, aucune autorité centrale ne peut assumer la responsabilité et réparer les dommages.

Lorsque le Bitcoin a été inventé, une avancée majeure a été l'utilisation de preuves de la solution probabiliste du problème des généraux byzantins. Il a été décrit en détail par Satoshi Nakamoto dans ce courriel .

Conclusion

Dans cet article, nous avons examiné quelques concepts de base du consensus dans les systèmes distribués.