Le protocole de consensus stellaire a été décrit pour la première fois dans un article scientifique de 2015 par David Mazier. Il s'agit d'un «système fédéral de l'accord byzantin», qui permet aux réseaux informatiques décentralisés sans dirigeants de parvenir efficacement à un consensus sur toute décision. Le réseau de facturation Stellar utilise le protocole de consensus Stellar (SCP) pour conserver un historique des transactions cohérent que tous les membres voient.

Les protocoles de consensus sont considérés comme difficiles à comprendre. Le SCP est plus simple que la plupart d'entre eux, mais partage toujours cette réputation - en partie à cause de l'idée erronée que le «vote fédéral», auquel la première moitié de l'article scientifique est consacré, est le SCP. Mais ce n'est pas le cas! Ceci est juste un élément de construction important, qui dans la seconde moitié de l'article est utilisé pour créer le protocole de consensus stellaire réel .

Dans cet article, nous décrivons brièvement ce qu'est un «système d'accords», ce qui peut le rendre «byzantin» et pourquoi rendre le système byzantin «fédéral». Ensuite, nous expliquons la procédure de vote fédéré décrite dans l'article du SCP, et expliquons enfin le protocole SCP lui-même.

Systèmes d'accord

Le système d'accords permet à un groupe de participants de parvenir à un consensus sur un sujet, par exemple, quoi commander pour le déjeuner.

Chez Interstellar, nous avons mis en place notre propre système de restauration: nous commandons ce que dit notre directeur des opérations, John. Il s'agit d'un système d'accord simple et efficace. Nous faisons tous confiance à John et croyons que chaque jour, il trouvera quelque chose d'intéressant et de nutritif.

Mais que faire si John abuse de notre confiance? Il peut à lui seul décider que nous devrions tous devenir des végétaliens. Dans une semaine ou deux, nous allons probablement le renverser et remettre l'autorité à Elizabeth. Mais soudain, elle aime les avocats aux anchois et pense que tout le monde devrait devenir comme ça. Le pouvoir corrompt. Par conséquent, il est préférable de trouver une méthode plus démocratique: un moyen de s'assurer que les différentes préférences sont prises en compte, tout en garantissant un résultat rapide et sans ambiguïté afin que personne ne commande le déjeuner ou que cinq personnes passent des commandes différentes, ou que la discussion se prolonge jusqu'au soir.

Il semblerait que la solution soit simple: voter! Mais c'est une impression trompeuse. Qui collectera les bulletins de vote et communiquera les résultats? Et pourquoi les autres devraient-ils croire ce qu'il dit? Peut-être pouvons-nous d' abord voter pour le leader en qui nous avons confiance pour diriger le vote - mais qui dirigera ce premier vote? Et si on n'arrive pas à s'entendre sur un leader? Ou si nous sommes d'accord et que ce leader est coincé dans une réunion ou part en congé de maladie?

Des problèmes similaires se retrouvent dans les réseaux informatiques distribués. Tous les participants ou nœuds doivent se mettre d'accord sur une solution, par exemple, à qui revient de mettre à jour le fichier partagé ou de retirer la tâche de la file d'attente de traitement. Dans un réseau de crypto-monnaie, les nœuds doivent à plusieurs reprises choisir à quoi ressemble l'histoire complète parmi plusieurs versions possibles qui sont parfois en conflit. Cet accord de réseau donne au destinataire la garantie que la pièce est (a) valide (non contrefaite) et (b) non encore dépensée ailleurs. Il garantit également qu'il pourra dépenser des pièces à l'avenir car le nouveau destinataire aura les mêmes garanties pour les mêmes raisons.

Tout système de correspondance dans un réseau informatique distribué doit être tolérant aux pannes: il doit donner des résultats cohérents, malgré les erreurs, telles que les lignes de communication lentes, les nœuds non réactifs et l'ordre des messages incorrect. Le système d'accords byzantin est en outre résistant aux erreurs «byzantines»: des nœuds qui fournissent de fausses informations, que ce soit à cause d'une erreur ou dans une tentative délibérée de saper le système ou d'obtenir un avantage. La résilience «byzantine» - la capacité de faire confiance à une décision de groupe, même lorsque certains membres du groupe peuvent mentir ou ne pas suivre les règles de la prise de décision - est appelée la parabole des généraux de l'Empire byzantin qui ont tenté de coordonner l'attaque. Anthony Stevens a une bonne description .

Considérez le propriétaire de la pièce cryptographique Alice, qui doit choisir entre acheter une délicieuse glace de Bob et payer la dette de Carol. Peut-être qu'Alice veut payer les deux à la fois, dépensant frauduleusement la même pièce. Pour ce faire, elle doit convaincre l'ordinateur de Bob que la pièce n'a jamais été payée à Carol et convaincre l'ordinateur de Carol que la pièce n'a jamais été payée à Bob. Le système byzantin de conventions rend cela pratiquement impossible en utilisant une forme de règle de majorité appelée quorum . Un nœud dans un tel réseau refuse de basculer vers une certaine version de l'historique jusqu'à ce qu'il constate qu'un nombre suffisant de nœuds homologues - un quorum - accepte une telle transition. Dès que cela se produit, ils formeront un bloc électoral suffisamment grand pour forcer les nœuds de réseau restants à approuver leur décision. Alice peut faire mentir certains nœuds en son nom, mais si le réseau est suffisamment grand, sa tentative sera supprimée par les voix de nœuds honnêtes.

Combien de nœuds sont nécessaires pour un quorum? Au minimum, une majorité, ou plutôt une majorité qualifiée, pour lutter contre les erreurs et les fraudes. Mais pour calculer la majorité, vous devez connaître le nombre total de participants. Au bureau d'Interstellar ou aux élections de district, ces chiffres sont faciles à reconnaître. Mais si votre groupe est un réseau mal défini dans lequel les nœuds peuvent entrer et sortir comme vous le souhaitez sans coordination avec le centre, alors vous avez besoin d'un système d'accord byzantin fédéral qui peut déterminer les collèges non pas à partir d'une liste de nœuds prédéterminée, mais dynamiquement, à partir d'un environnement en constante évolution et inévitablement incomplet. instantané des nœuds à un certain moment.

Il peut ne pas sembler possible de créer un quorum en termes d'un seul nœud dans un réseau étendu, mais c'est possible. Un tel quorum peut même garantir les résultats d'un vote décentralisé. Le livre blanc du SCP montre comment procéder en utilisant une procédure appelée vote fédéré .

Pour les impatients

Le reste de l'article détaille le vote fédéral et le protocole de consensus stellaire. Si vous n'êtes pas intéressé par les détails, voici un aperçu général du processus.

1. Les nœuds mènent des tours de scrutin fédéral sur les «candidats». Un tour de scrutin fédéral signifie:
   
   • Le nœud vote pour toute déclaration, par exemple, "Je propose la valeur de V";
     
   • Le nœud écoute les voix des fêtes jusqu'à ce qu'il en trouve une qui puisse «recevoir»;
     
   • Le nœud recherche un «quorum» pour cette déclaration. Le quorum «confirme» le candidat.
2. Dès qu'un nœud peut confirmer un ou plusieurs candidats, il essaie de «préparer» un «scrutin» à travers plusieurs tours de scrutin fédéral.
   
3. Dès que le nœud est en mesure de vérifier l'état de préparation du scrutin, il essaie de le nourrir avec encore plus de tours de scrutin fédéré.
   
4. Une fois qu'un site peut confirmer l'engagement d'une newsletter, il peut «externaliser» la valeur de cette newsletter, en l'utilisant par consensus.

Ces étapes comprennent plusieurs tours de scrutin fédéré, qui forment ensemble un tour de SCP. Nous examinerons plus en détail ce qui se passe à chaque étape.

Vote fédéré

Le vote fédéré consiste à déterminer si un réseau peut se mettre d'accord sur une proposition. Lors d'un tour de scrutin, chaque nœud doit sélectionner l'une des nombreuses valeurs possibles. Il ne peut pas faire cela tant qu'il n'est pas sûr que les autres nœuds du réseau ne choisiront pas un résultat différent. Pour en être sûr, les nœuds échangent une série de messages dans les deux sens afin que tout le monde confirme que le quorum des nœuds prend la même décision . Le reste de cette section explique les termes de cette phrase et comment se déroule toute la procédure.

Quorums et tranches de quorum

Commençons par définir un quorum. Comme nous l'avons vu ci-dessus, dans un réseau décentralisé à appartenance dynamique, il est impossible de savoir à l'avance le nombre de nœuds et, par conséquent, la quantité nécessaire pour la plupart. Le vote fédéré résout ce problème en introduisant une nouvelle idée de tranche de quorum: un petit ensemble de nœuds homologues auxquels le nœud fait confiance pour transmettre des informations sur l'état du vote dans le reste du réseau. Chaque nœud définit sa propre tranche de quorum (dont il devient membre en fait).

La formation du collège commence par une réduction du collège. Pour chaque nœud, des nœuds de sa tranche sont ajoutés. Ensuite, des membres de tranche de ces nœuds sont ajoutés , etc. Au fur et à mesure que vous continuez, de plus en plus de nœuds apparaissent que vous ne pouvez pas ajouter, car ils sont déjà inclus dans la tranche. Lorsqu'il n'y a plus de nouveaux nœuds à ajouter, le processus s'arrête: nous avons formé un quorum par «fermeture transitive» en coupant le quorum du nœud initial.


Pour trouver le quorum à partir de ce nœud ...


... ajouter des membres à sa tranche ...


... puis ajoutez des membres de tranche à ces nœuds.


Continuez jusqu'à ce qu'il n'y ait plus de nœuds à ajouter.




Pas de nœuds à ajouter à gauche. Ceci est un quorum.

En fait, chaque nœud peut entrer dans plus d'une tranche. Pour former un quorum, sélectionnez une seule des tranches et ajoutez des membres; puis sélectionnez une tranche pour chaque membre et ajoutez des membres à cette tranche et ainsi de suite. Cela signifie que chaque nœud est membre de nombreux collèges possibles.


Sélectionnez une seule tranche de quorum à chaque étape.






Un quorum possible. Ou une alternative ...


... sélectionnez d'autres tranches ...




... (si possible) ...


... crée un autre quorum.

Comment un nœud sait-il dans quelles tranches se trouvent les autres nœuds? De la même manière que les autres informations sur les autres nœuds: des transmissions que chaque nœud diffuse au réseau lorsque son statut de vote change. Chaque diffusion comprend des informations sur les tranches du nœud émetteur. Le document technique du SCP ne spécifie pas de mécanisme de communication. Les implémentations utilisent généralement le protocole Gossip pour garantir la diffusion des messages sur le réseau.

Rappelons que dans un système byzantin non fédéral d'accords, un quorum est défini comme la majorité de tous les nœuds. Le système byzantin d'accords a été développé du point de vue de la question: combien de nœuds malhonnêtes le système peut-il supporter? Dans un système de N nœuds conçu pour survivre à f pannes (astuces), le nœud devrait être capable de progresser en recevant une réponse de N - f pairs, car f d'entre eux peuvent ne pas fonctionner. Mais ayant reçu une réponse de N - f pairs, nous pouvons supposer que tous les f pairs (dont le nœud n'a pas reçu de réponse) sont réellement honnêtes. Ainsi, f de N - f pairs (desquels une réponse est reçue) sont malveillants. Pour que les nœuds parviennent au même consensus, la majorité des nœuds restants doivent être honnêtes, c'est-à-dire que nous avons besoin que N - f soit supérieur à 2f ou N> 3f. Donc, généralement, un système conçu pour survivre aux défaillances f aura un total de N = 3f + 1 nœuds et une taille de quorum de 2f + 1. Dès que la proposition franchit le seuil de quorum, le reste du réseau est convaincu que toute proposition concurrente échouera. Le réseau converge donc vers le résultat.

Mais dans un système fédéral byzantin d'accords, non seulement il ne peut y avoir de majorité (car personne ne connaît la taille globale du réseau), mais le concept de majorité est généralement inutile! Si l'appartenance au système est ouverte, alors quelqu'un peut obtenir la majorité en conduisant simplement la soi-disant attaque Sibyl: en rejoignant à plusieurs reprises le réseau via plusieurs nœuds. Alors, pourquoi la fermeture transitive d'une tranche peut-elle être qualifiée de quorum et comment est-elle capable de supprimer les offres concurrentes?

Techniquement, pas question! Imaginez un réseau de six nœuds, où deux triplets sont isolés dans des tranches de quorum l'un de l'autre. Le premier sous-groupe peut prendre une décision dont le second n'entendra jamais et vice versa. Il n'y a aucun moyen pour ce réseau de parvenir à un consensus (sauf par hasard).

Par conséquent, SCP requiert que le réseau ait une propriété appelée croisement de quorum pour le vote fédéré (et pour l'application d'importants théorèmes d'article). Sur un réseau avec cette propriété, deux quorums qui peuvent être construits se chevauchent toujours dans au moins un nœud. Déterminer l'humeur du réseau est aussi bon que d'avoir la majorité. Intuitivement, cela signifie que si un quorum est d'accord avec la déclaration X, aucun autre quorum ne pourra jamais être d'accord avec autre chose, car il inclura nécessairement un nœud du premier quorum qui a déjà voté pour X.


Si le réseau a une intersection de collèges ...


... puis deux quorums que vous pouvez construire ...


... se croiseront toujours.





(Bien sûr, les nœuds qui se chevauchent peuvent s'avérer être de type byzantin ou mauvais à d'autres égards. Dans ce cas, les quorums qui se croisent n'aident pas du tout le réseau à s'entendre. intersection de quorums même après suppression des nœuds défectueux . Pour simplifier, nous laissons ces hypothèses implicites dans la suite de l'article).

Il peut sembler déraisonnable de s'attendre à ce que dans un réseau de nœuds indépendants une intersection fiable de quorums soit possible. Mais il en est ainsi pour deux raisons.

La première raison est l'existence d'Internet lui-même. Internet est un exemple idéal de réseau de nœuds indépendants avec intersection de quorums. La plupart des sites sur Internet ne se connectent qu'à quelques autres sites locaux, mais ces petits ensembles se chevauchent suffisamment pour rendre chaque site accessible à partir de tous les autres sites sur un itinéraire particulier.

La deuxième raison est spécifique au réseau de paiement Stellar (l'utilisation la plus courante de SCP). Chaque actif du réseau Stellar a un émetteur, et les recommandations Stellar exigent que chaque émetteur désigne un ou plusieurs nœuds du réseau pour traiter les demandes de remboursement. Il est dans votre intérêt d'inclure directement ou indirectement ces nœuds dans des tranches de quorum pour chaque actif qui vous intéresse. Ensuite, les quorums de tous les nœuds intéressés par cet actif se chevaucheront au moins dans ces nœuds de remboursement. Les nœuds intéressés par plusieurs actifs incluront dans leurs tranches de quorum tous les nœuds de remboursement des émetteurs respectifs, et ils s'efforceront de combiner tous les actifs ensemble. De plus, tous les actifs qui ne sont pas connectés de cette manière avec d'autres sur le réseau et ne doivent pas être connectés - il est conçu de manière à ce qu'il n'y ait pas de dépassement de quorum pour ce réseau (par exemple, les banques de la zone dollar veulent parfois commercer avec des banques de la zone euro et des banques de la zone de peso, ils sont donc sur le même réseau, mais aucun ne se soucie d'un réseau séparé d'enfants vendant des cartes de baseball).

Bien sûr, attendre l' intersection des collèges n'est pas une garantie . D'autres systèmes d'accord byzantins doivent en grande partie leur complexité à la garantie des collèges. Une innovation importante de SCP est qu'il supprime la responsabilité de créer des collèges à partir de l'algorithme de consensus lui-même et l'amène au niveau de l'application. Ainsi, bien qu'un vote fédéré soit suffisamment général pour voter sur n'importe quelle question, sa fiabilité dépend en fait de manière critique de la signification plus large de ces valeurs. Certaines utilisations hypothétiques peuvent ne pas être aussi pratiques pour construire des réseaux bien connectés que d'autres.

Vote, acceptation et confirmation

Lors du tour de scrutin fédéral, le nœud commence éventuellement à voter pour une valeur de V. Cela signifie que le message est envoyé au réseau: «Je suis le nœud N, mes tranches de quorum sont Q et je vote pour V». Lorsqu'un nœud vote de cette façon, il promet qu'il n'a jamais voté contre V et ne le fera jamais.

Dans les diffusions à partir de nœuds d'égal à égal, chaque nœud voit comment les autres votent. Dès que le nœud recueille un nombre suffisant de ces messages, il peut suivre les tranches de quorum et essayer de trouver des quorums. S'il voit un quorum de pairs qui votent également pour V, il peut alors accepter V et diffuser ce nouveau message au réseau: «Je suis le nœud N, mes tranches sont le quorum Q et j'accepte V». L'acceptation offre une garantie plus forte qu'un simple vote. Lorsqu'un nœud vote pour V, il ne peut jamais voter pour d'autres options. Mais si un nœud accepte V, aucun nœud sur le Web n'acceptera jamais une autre option (le Théorème 8 dans le livre blanc technique SCP le prouve).

Bien sûr, il est très probable qu'il n'y aura pas immédiatement un quorum de nœuds d'accord avec V. D'autres nœuds peuvent voter pour d'autres valeurs. Mais pour le site, il y a une autre façon de passer du simple vote à l'acceptation. N peut prendre une valeur différente de W, même s'il n'a pas voté pour lui, et même s'il ne voit pas de quorum pour cela. Pour décider de changer de voix, il suffit de voir un ensemble de nœuds bloquants qui ont accepté W. Un ensemble de blocage est un nœud dans chacune des tranches des quorums de N. Comme son nom l'indique, il peut bloquer toute autre valeur. Si tous les nœuds d'un tel ensemble acceptent W, alors (par le théorème 8) il ne sera jamais possible de former un quorum en supposant une valeur différente, et donc il est également sûr d'accepter W.


Node N avec trois tranches de quorums.


BDF est un ensemble de blocage pour N: il comprend un nœud de chacune des N tranches.


BE est également un ensemble de blocage pour N, car E apparaît dans deux tranches de N.

Mais un ensemble de blocage n'est pas un quorum. Il serait trop facile d'inciter le nœud N à accepter la valeur souhaitée s'il suffit de casser un seul nœud dans chacune des tranches N. Par conséquent, l'adoption de la valeur n'est pas la fin du vote. Au lieu de cela, N doit confirmer la valeur, c'est-à-dire voir le quorum des nœuds qui le reçoivent. S'il va aussi loin, alors, comme le prouve le livre blanc du SCP (dans le théorème 11), le reste du réseau finira également par confirmer la même valeur, donc N mettra fin au vote fédéré avec une valeur spécifique comme résultat.


Vote fédéré.

Le processus de vote, d'acceptation et de confirmation est un tour complet de vote fédéré. Le Protocole de consensus stellaire rassemble bon nombre de ces cycles pour créer un système de consensus complet.

Protocole de consensus stellaire

Les deux caractéristiques les plus importantes d'un système consensuel sont la sécurité et la capacité de survie . L’algorithme de consensus est «sûr» s’il ne peut jamais donner des résultats différents à différents participants (une copie de l’histoire de Bob ne contredira jamais Carol). "Vitalité" signifie que l'algorithme produira toujours un résultat, c'est-à-dire qu'il ne restera pas bloqué.

La procédure de vote fédéré décrite est sûre en ce sens que si un nœud confirme la valeur de V, aucun autre nœud ne confirme l'autre valeur. Mais «ne confirme pas un autre sens» - cela ne signifie pas qu'il confirmera nécessairement quelque chose. Les participants peuvent voter pour tant de valeurs différentes que rien n'atteint le seuil d'acceptation. Cela signifie qu'il n'y a pas de vote fédéral.capacité de survie .

Le Protocole de consensus stellaire utilise le vote fédéré d'une manière qui garantit à la fois la sécurité et la vitalité. (Les garanties de sécurité et de survie des SCP ont une limite théorique. La conception choisit une garantie de sécurité très forte, sacrifiant un léger affaiblissement de la survie, mais avec suffisamment de temps, un consensus est susceptible d'être atteint.) En résumé, l'idée est de mener plusieurs votes fédérés sur plusieurs valeurs jusqu'à ce que l'une d'entre elles passe complètement par toutes les phases du vote SCP décrites ci-dessous.

Les valeurs par lesquelles SCP s'efforce de parvenir à un consensus peuvent être un historique des transactions ou une commande de déjeuner, ou autre chose, mais il est important de noter que ce ne sont pas les valeurs acceptées ou confirmées. Au lieu de cela, le vote fédéré a lieu sur les revendications de ces valeurs .

Les premiers tours de scrutin fédéré ont lieu lors de la phase de nomination, sur un ensemble de candidatures «Je nomme V», éventuellement pour de nombreuses valeurs différentes de V.Le but de la nomination est de trouver une ou plusieurs candidatures qui passent par l'acceptation et la confirmation.

Après avoir trouvé des candidats confirmés, SCP passe à la phase de vote, où le but est de trouver un bulletin de vote(c'est-à-dire un conteneur pour la valeur proposée) et un quorum qui peut déclarer un commit pour cela (commit). Si un quorum engage un scrutin, sa valeur est prise comme consensus. Mais avant que le nœud ne puisse voter pour la validation du scrutin, il doit d'abord confirmer l' annulation de tous les scrutins avec une contre-valeur inférieure. Ces étapes - annulation des scrutins pour en trouver un pour lequel vous pouvez confirmer l'engagement - comprennent plusieurs tours de scrutin fédéré sur plusieurs bulletins de vote.

Les sections suivantes décrivent plus en détail la nomination et le vote.

Nomination

Au début de la phase de nomination, chaque nœud peut spontanément sélectionner la valeur V et voter pour la déclaration «Je nomme V». L'objectif à ce stade est de confirmer la nomination d'une certaine valeur par un vote fédéral.

Peut-être qu'un nombre suffisant de nœuds votent pour des déclarations assez différentes, et aucune nomination ne peut atteindre le seuil d'adoption. Par conséquent, en plus de diffuser leurs propres votes de candidats, les nœuds «reflètent» les nominations de leurs pairs. La réflexion (écho) signifie que si le nœud vote pour la nomination de V, mais voit un message du voisin votant pour la nomination de W, maintenant il votera pour la nomination de V et W. (Tous les votes des pairs ne sont pas reflétés pendant la nomination parce que cela peut conduire à une explosion de différents candidats. SCP comprend un mécanisme de régulation de ces voix. En bref, il existe une formule pour déterminer la "priorité" de la fête du point de vue du nœud, et seuls les votes des nœuds à priorité élevée sont reflétés. Plus l'extension a lieu, plus le seuil est bas, donc le nœud se développe un ensemble de fêtes dont il reflètera les voix.La formule de priorité en tant que l'une des données d'entrée comprend le numéro d'emplacement, de sorte qu'un homologue de priorité élevée pour un emplacement peut être de faible priorité pour un autre, et vice versa).

Sur le plan conceptuel, la nomination en parallèle des deux V et W sont des votes fédéraux distincts, chacun séparément pouvant obtenir l'acceptation ou la confirmation. En pratique, les messages de protocole SCP regroupent ces voix individuelles ensemble.

Bien que voter pour la candidature V soit une promesse de ne jamais voter contre la candidature V, au niveau de la candidature - dans ce cas, SCP - il est défini ce qui signifie «contre». SCP ne voit pas de déclaration qui contredit le vote «Je nomme X», c'est-à-dire qu'il n'y a pas de message «Je suis contre la nomination X», de sorte que le nœud peut voter pour la nomination de valeurs. Beaucoup de ces nominations ne mèneront à rien, mais en fin de compte, le nœud pourra accepter ou confirmer une ou plusieurs valeurs. Une fois le candidat confirmé, il devient candidat .


Nomination du SCP par vote fédéré. Il peut y avoir de nombreuses valeurs «B» poussées par les pairs et «reflétées» par le pair.

La nomination des candidats peut entraîner la confirmation de plusieurs candidats. Par conséquent, SCP requiert que la couche application fournisse une méthode de combinaison des candidats en un seul composite.(composite). La méthode de l'union peut être n'importe quoi. L'essentiel est que si cette méthode est déterminée, chaque nœud réunira les mêmes candidats. Dans le système de vote pour le déjeuner, «association» peut simplement signifier le rejet d'un des deux candidats. (Mais de manière déterministe: chaque nœud doit choisir la même valeur à réinitialiser. Par exemple, une sélection antérieure par ordre alphabétique). Dans le réseau de paiement Stellar, où l'historique des transactions est voté, la combinaison des deux candidats proposés implique de combiner les transactions qu'elles contiennent et le dernier de leurs deux horodatages.

La description technique de SCP prouve (Théorème 12) qu'à la fin de la phase d'extension, le réseau finit par converger vers un seul composite. Mais il y a un problème: le vote fédéré est un protocole asynchrone (comme SCP). En d'autres termes, les nœuds ne sont pas coordonnés dans le temps, mais uniquement en fonction des messages qu'ils envoient. Du point de vue du nœud, on ne sait pas quand la phase d'extension s'est terminée . Et bien que tous les nœuds finiront par arriver au même composite, ils peuvent choisir des itinéraires différents en cours de route, créant différents candidats composites en cours de route, et ils ne peuvent jamais dire lequel est final.

Mais c'est normal. La nomination n'est qu'une préparation. L'essentiel est de limiter le nombre de candidats pour parvenir à un consensus qui intervient lors du scrutin .

Bulletin de vote

Un bulletin d'information est une paire de <compteur, valeur>, où compteur est un entier qui commence par 1, et la valeur est un candidat de l'étape de nomination. Il peut s'agir du propre candidat d'un nœud ou d'un candidat voisin adopté par ce nœud. En gros, pendant la course, des tentatives répétées sont faites pour forcer le réseau à atteindre un consensus sur un candidat lors d'un scrutin en tenant potentiellement de nombreux votes fédéraux sur les demandes de scrutin. Les compteurs dans les bulletins de vote gardent une trace des tentatives faites, et les bulletins de vote avec des compteurs supérieurs ont priorité sur les bulletins de vote avec des compteurs inférieurs. Si le bulletin <compteur, valeur> est bloqué, un nouveau vote commence, maintenant sur le bulletin <compteur + 1, valeur>.

Il est important de distinguer les valeurs(par exemple, quelle devrait être la commande pour le déjeuner: pizza ou salade), bulletins de vote (une paire de contre-valeur) et déclarations sur les bulletins de vote. Le tour du SCP comprend plusieurs tours de scrutin fédéré, en particulier sur de telles déclarations:

• «Je suis prêt à engager le bulletin B» et
  
• «Je déclare un engagement au Bulletin B»

Du point de vue de ce nœud, un consensus est atteint quand il trouve le Bulletin B pour lequel il peut confirmer (c'est-à-dire trouver un quorum qui accepte) la déclaration «Je déclare un engagement envers le Bulletin B». Désormais, vous pouvez agir en toute sécurité sur la valeur spécifiée en B - par exemple, passer cette commande pour le déjeuner. Cela s'appelle externaliser la valeur. Une fois l'acceptation du scrutin confirmée, le nœud peut être sûr que tout autre nœud a externalisé la même valeur ou l'engagera définitivement à l'avenir.

Bien que, conceptuellement, de nombreux votes fédérés aient lieu sur les candidatures à de nombreux scrutins différents, ils n'échangent pas autant de messages car chaque message encapsule un certain nombre de scrutins. Un message, par conséquent, fait la promotion de l'état de nombreux votes fédérés à la fois, par exemple: «J'accepte des commissions de vote allant de <min, V> à <max, V>».

Que signifient les termes «préparé» et «engager»?

Un nœud vote pour valider un scrutin lorsqu'il est convaincu que d'autres nœuds ne valideront pas de scrutin avec des valeurs différentes. Convaincre ceci est le but de la préparation de la déclaration. Un vote qui dit "Je suis prêt à valider le bulletin B" est une promesse de ne jamais valider un bulletin inférieur à B, c'est-à-dire avec un compteur inférieur (SCP exige que les valeurs dans les bulletins aient un certain ordre. Ainsi, Le bulletin <N1, V1> est inférieur à <N2, V2> si N1 <N2, et aussi si N1 = N2 et V1 <V2). Ces petits bulletins de vote sont «abandonnés» lors du vote préparatoire, tandis que B est considéré comme «préparé».

Pourquoi «Je suis prêt à engager le bulletin B» signifie-t-il «Je promets de ne jamais engager de scrutin inférieur à B»? Parce que SCP définit l'abandon comme l'opposé de la validation. Voter pour la préparation d'un bulletin de vote implique également de voter pour annuler certains autres bulletins de vote et, comme nous l'avons vu plus haut, voter pour une chose est une promesse de ne jamais voter contre.

Avant de diffuser le commit, le site doit d'abord trouver le bulletin, qu'il peut confirmer tel qu'il a été préparé. En d'autres termes, il tient un vote fédéral sur «Je suis prêt à m'engager dans le Bulletin B», peut-être pour de nombreux scrutins différents, jusqu'à ce qu'il en trouve un qui accepte le quorum.

D'où proviennent les bulletins de vote? Premièrement, le nœud diffuse les préparatifs du vote pour <1, ​​C>, où C est le candidat composite produit au stade de la nomination. Cependant, même après le début des préparatifs de vote, la nomination peut conduire à l'apparition de candidats supplémentaires qui deviendront de nouveaux scrutins. Pendant ce temps, les pairs peuvent avoir des candidats différents, et ils peuvent former un ensemble de blocage qui accepte «Je suis prêt à engager le bulletin B2», ce qui convaincra le nœud de l'accepter aussi. Enfin, il existe un mécanisme de temporisation qui génère de nouveaux tours de scrutin fédéré sur les nouveaux bulletins de vote avec des compteurs plus élevés si les bulletins de vote actuels sont bloqués.

Dès que le nœud trouve le Bulletin B, qu'il peut confirmer comme préparé, il diffuse un nouveau message, «Bulletin B Commit». Ce vote indique aux pairs que le nœud n'abandonnera jamais B. En fait, si B est un bulletin de vote <N, C>, alors "Commit Bulletin <N, C>" signifie un consentement inconditionnel à voter pour la préparation de chaque bulletin de vote de <N, C> à <∞, s>. Cette valeur supplémentaire aide les autres nœuds à rattraper un commit, s'ils sont encore aux premiers stades du protocole.

À ce stade, il convient de souligner une fois de plus qu'il s'agit de protocoles asynchrones. Ce n'est pas parce qu'un nœud envoie des votes pour un commit que ses pairs le font aussi. Certains d'entre eux peuvent encore voter sur les candidatures en vue du vote, d'autres peuvent avoir déjà externalisé le sens. SCP explique comment un nœud doit traiter chaque type de message homologue, quelle que soit sa phase.

Si le message «Je déclare un commit <N, C>» ne peut être accepté ou confirmé, c'est-à-dire la probabilité d'acceptation ou de confirmation du message <N + 1, C> ou <N + 2, C> - ou, en tout cas, tout bulletin avec une valeur de C, et pas d'autre, puisque le nœud a déjà promis de ne jamais annuler <N, C>. Au moment où le nœud diffusera les votes pour le commit, ce sera C ou rien, selon jusqu'où ira le consensus. Cependant, cela ne suffit pas pour que le nœud extériorise C. Certains festins byzantins (moins d'un quorum, sur la base de nos hypothèses sur la sécurité) peuvent mentir au nœud. L'adoption puis la confirmation d'un certain scrutin (ou plage de scrutin) est ce qui donne au nœud la confiance pour finalement externaliser C.


SCP passant par le vote fédéré. Non illustré: à tout moment un chronomètre peut fonctionner, augmentant le compteur dans le bulletin de vote (et, éventuellement, produisant un nouveau composite à partir de candidats supplémentaires désignés).

Et c'est tout! Une fois que le réseau est parvenu à un consensus, il est prêt à le faire encore et encore. Sur le réseau de facturation Stellar, cela se produit environ toutes les 5 secondes: un exploit qui nécessite à la fois la sécurité et la capacité de survie, garantie par SCP.

Le SCP peut y parvenir en s'appuyant sur plusieurs tours de scrutin fédéré. Le vote fédéré a été rendu possible grâce au concept de tranches de quorum: des ensembles de nœuds homologues auxquels chaque nœud a décidé de faire confiance dans le cadre de son quorum (subjectif). Cette configuration signifie que vous pouvez atteindre un consensus même sur un réseau à adhésion ouverte et tromperie byzantine.

Lectures complémentaires

• Le document technique SCP original peut être trouvé ici , et voici le projet de spécifications pour sa mise en œuvre.
  
• L'auteur original du protocole SCP, David Mazier, simplifie (mais toujours techniquement) l'explique ici .
  
• Vous avez peut-être été surpris de ne pas trouver les termes «exploitation minière» ou «preuve de travail» dans cet article. SCP n'utilise pas ces méthodes, mais certains autres algorithmes de consensus le font. Zane Witherspoon a écrit une revue accessible des algorithmes de consensus .
  
• Une description étape par étape d'un réseau simple qui parvient à un consensus dans un cycle complet de SCP.
  
• Pour les lecteurs intéressés par les implémentations SCP: voir le code C ++ utilisé par le réseau de paiement Stellar, ou le code Go que j'ai écrit pour une meilleure compréhension de SCP.