Le protocole de consensus Stellar a été décrit pour la première fois dans l'article de David Mazieres en 2015. Il s'agit d'un « système fédératif d'accord byzantin » qui permet aux réseaux informatiques décentralisés, sans leaders, d'atteindre efficacement un consensus sur une décision quelconque. Le réseau de paiement Stellar utilise le Stellar Consensus Protocol (SCP) pour maintenir un historique cohérent des transactions, visible par tous les participants.
Il est communément admis que les protocoles de consensus sont difficiles à comprendre. Le SCP est plus simple que la plupart d'entre eux, mais il partage néanmoins cette réputation, en partie à cause d'une idée erronée selon laquelle le « vote fédératif », consacré dans la première partie de l'article scientifique, est le SCP. Mais ce n'est pas le cas ! C'est simplement un élément essentiel qui est utilisé dans la seconde moitié de l'article pour créer le véritable protocole de consensus Stellar.
Cet article expliquera brièvement ce qu'est un « système d'accord », ce qui peut le rendre « byzantin » et pourquoi rendre un système byzantin « fédératif ». Nous expliquerons ensuite la procédure de vote fédératif décrite dans l'article sur le SCP, et enfin nous expliquerons le protocole SCP lui-même.
Systèmes d'accords
Un système d'accord permet à un groupe de participants de parvenir à un consensus sur un certain sujet, par exemple, ce qu'il faut commander pour le déjeuner.
Chez Interstellar, nous avons mis en place notre propre système d'accord pour le déjeuner : nous commandeons ce que dit notre responsable des opérations, John. C'est un système d'accord simple et efficace. Nous faisons tous confiance à John et croyons qu'il trouvera chaque jour quelque chose d'intéressant et de nutritif.
Mais que se passerait-il si John abusait de notre confiance ? Il pourrait unilatéralement décider que nous devrions tous devenir végétaliens. Dans une semaine ou deux, nous le renverserions probablement et confierions le pouvoir à Elizabeth. Mais que se passe-t-il si elle aime les avocats avec des anchois et pense que tout le monde devrait l'être ? Le pouvoir corrompt. Il vaut donc mieux trouver une méthode plus démocratique : un moyen de s'assurer que diverses préférences sont prises en compte, tout en garantissant un résultat clair et opportun, afin qu'il ne se retrouve pas dans une situation où personne ne commande le déjeuner ou cinq personnes passent des commandes différentes, ou que la discussion s'éternise jusqu'au soir.
Il semblerait que la solution soit simple : organiser un vote ! Mais cette impression est trompeuse. Qui va collecter les bulletins et communiquer les résultats ? Et pourquoi les autres devraient-ils croire ce qu'il dira ? Peut-être que nous pouvons d'abord voter pour un leader en qui nous avons confiance pour diriger le vote — mais qui dirigera ce premier vote ? Que se passe-t-il si nous ne parvenons pas à nous mettre d'accord sur un leader ? Ou si nous parvenons à un accord, mais que ce leader est retenu lors d'une réunion ou tombe malade ?
Des problèmes similaires se rencontrent dans les réseaux informatiques distribués. Tous les participants ou nœuds doivent convenir d'une certaine décision, par exemple, qui doit mettre à jour un fichier commun ou retirer une tâche de la file d'attente. Dans un réseau de cryptomonnaie, les nœuds doivent à plusieurs reprises choisir quelle histoire complète est celle qui s'applique, parmi plusieurs versions possibles qui entrent parfois en conflit. Cet accord réseau garantit au destinataire que la pièce est (a) valide (non contrefaite) et (b) qu'elle n'a pas encore été dépensée ailleurs. Cela garantit également qu'il pourra dépenser les pièces à l'avenir, car le nouveau destinataire aura les mêmes garanties pour les mêmes raisons.
Tout système de consensus dans un réseau informatique distribué doit être tolérant aux pannes : il doit donner des résultats cohérents, malgré des erreurs telles que des lignes de communication lentes, des nœuds non réactifs et un ordre de messages incorrect. Le système de consensus byzantin est en plus résistant aux erreurs «byzantines» : des nœuds fournissant de fausses informations, que ce soit par erreur ou dans une tentative délibérée de nuire au système ou d'en tirer un avantage. La tolérance aux pannes «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 décision — a son nom d'après , qui essayaient de coordonner une attaque. se trouve chez Anthony Stevens.
Considérons Alice, la propriétaire de la cryptomonnaie, qui doit choisir entre acheter une délicieuse glace chez Bob ou rembourser sa dette envers Carol. Peut-être qu'Alice veut payer les deux en même temps, en dépensant frauduleusement la même pièce. Pour cela, elle doit convaincre l'ordinateur de Bob que la pièce n'a jamais été versée à Carol, et convaincre l'ordinateur de Carol que la pièce n'a jamais été versée à Bob. Un système byzantin de consensus rend cela pratiquement impossible, en utilisant une forme de règle de la majorité appelée quorum. Dans un tel réseau, un nœud refuse de passer à une version particulière de l'histoire tant qu'il n'a pas vu qu'un nombre suffisant de nœuds pairs — un quorum — sont d'accord avec ce passage. Une fois que cela se produit, ils forment un bloc électoral suffisamment important pour convaincre les nœuds restants du réseau d'accepter leur décision. Alice peut forcer certains nœuds à mentir en son nom, mais si le réseau est suffisamment vaste, sa tentative sera étouffée par les voix des nœuds honnêtes.
Combien de nœuds sont nécessaires pour un quorum ? Au minimum, la majorité, ou plus précisément, une majorité qualifiée pour lutter contre les erreurs et la fraude. Mais pour compter la majorité, il faut connaître le nombre total de participants. Dans un bureau interstellaire ou pour des élections de district, ces chiffres sont faciles à obtenir. Mais si votre groupe est un réseau mal défini, où les nœuds peuvent entrer et sortir à volonté sans concertation avec un centre, alors il faut une système fédératif de consensus byzantin capable de déterminer des quorums non à partir d'une liste prédéfinie de nœuds, mais dynamiquement, à partir d'un instantané constamment changeant et inévitablement incomplet des nœuds à un moment donné.
Il peut sembler impossible de créer un quorum du point de vue d'un nœud dans un vaste réseau, mais c'est possible. Un tel quorum peut même garantir les résultats d'un vote décentralisé. Le document technique SCP montre comment le faire à l'aide d'une procédure appelée vote fédératif.
Pour les impatients
Le reste de l'article décrit plus en détail le vote fédératif et le protocole de consensus Stellar. Si les détails ne vous intéressent pas, voici un aperçu général du processus.
- Les nœuds organisent des tours de vote fédéraux sur les « nominés ». Un tour de vote fédéral signifie :
- Le nœud vote pour une proposition quelconque, par exemple, « Je propose la valeur V » ;
- Le nœud écoute les voix des pairs jusqu'à ce qu'il trouve celle qui peut « accepter » ;
- Le nœud recherche un « quorum » pour cette proposition. Le quorum « valide » le nominé.
- Une fois que le nœud peut valider un ou plusieurs nominés, il tente de « préparer » un « bulletin » à travers plusieurs tours de vote fédéral.
- Dès que le nœud est en mesure de vérifier la préparation du bulletin, il tente de l'engager avec encore plus de tours de vote fédéral.
- Une fois que le nœud peut confirmer l'engagement du bulletin, il peut « externaliser » la valeur de ce bulletin, en l'utilisant comme résultat de consensus.
Ces étapes incluent plusieurs tours de vote fédéral, qui ensemble forment un tour SCP. Voyons plus en détail ce qui se passe à chaque étape.
Vote fédéral
Le vote fédéral est une procédure pour déterminer si le réseau peut s’accorder sur une proposition. Lors d'un tour de vote, chaque nœud doit choisir une des nombreuses valeurs potentielles. Il ne peut le faire tant qu'il n'est pas certain que d'autres nœuds du réseau ne choisiront pas un résultat différent. Pour être sûrs de cela, les nœuds échangent un flot de messages dans les deux sens, afin que chacun a confirmé, que quorum nœuds prend le même la solution. Le reste de cette section explique les termes dans cette déclaration et comment se déroule toute la procédure.
Quorums et tranches de quorum
Commençons par définir le quorum. Comme nous l'avons discuté précédemment, dans un réseau décentralisé avec une adhésion dynamique, il est impossible de savoir à l'avance combien de nœuds il y a et donc combien sont nécessaires pour une majorité. Le vote fédéral résout ce problème en introduisant une nouvelle idée de tranche de quorum (quorum slice) : un petit ensemble de nœuds pairs en qui le nœud a confiance pour transmettre des informations sur l'état du vote au reste du réseau. Chaque nœud définit sa propre tranche de quorum (dont il devient membre de facto).
La formation du quorum commence par la tranche de quorum. Pour chaque nœud, les nœuds de sa tranche sont ajoutés. Ensuite, les membres des tranches sont ajoutés. ces nœuds et ainsi de suite. Au fur et à mesure de la progression, de plus en plus de nœuds apparaissent que vous ne pouvez pas ajouter, car ils sont déjà inclus dans le sous-ensemble. Lorsque plus aucun nœud nouveau n'est à ajouter, le processus s'arrête : nous avons formé un quorum par « fermeture transitive » (transitive closure) de l'ensemble de quorum du nœud initial.
Pour trouver un quorum à partir d'un nœud donné…
… nous ajoutons les membres de son sous-ensemble…
… puis nous ajoutons les membres des sous-ensembles de ces nœuds.
Nous continuons jusqu'à ce qu'il n'y ait plus de nœuds à ajouter.
Il n'y a plus de nœuds à ajouter. C'est un quorum.
En réalité, chaque nœud peut faire partie de plus d'un sous-ensemble. Pour former un quorum, choisissez seulement un des sous-ensembles et ajoutez des membres ; ensuite, choisissez n'importe quel sous-ensemble pour chaque membre et ajoutez des membres ce fichier) : du sous-ensemble, et ainsi de suite. Cela signifie que chaque nœud fait partie d'un certain nombre de quorums possibles.
Choisissez seulement un sous-ensemble de quorum à chaque étape.
Un quorum possible. Ou une alternative…
… nous choisissons d'autres sous-ensembles…
… (lorsque c'est possible)…
… crée un autre quorum.
Comment un nœud sait-il à quels sous-ensembles appartiennent les autres nœuds ? De la même manière qu'il obtient d'autres informations sur les autres nœuds : par les transmissions que chaque nœud diffuse dans le réseau lorsqu'il modifie son état de vote. Chaque diffusion inclut des informations sur les sous-ensembles du nœud émetteur. Le document technique SCP ne précise pas le mécanisme de communication. Les implémentations utilisent généralement pour garantir la diffusion des messages dans tout le réseau.
Rappelons que dans le système de consensus byzantin non fédératif, le quorum est défini comme la majorité de tous les nœuds. Le système de consensus byzantin a été conçu en se demandant : combien de nœuds malveillants le système peut-il tolérer ? Dans un système de N nœuds, conçu pour survivre à f défaillances (malversations), un nœud doit être en mesure de progresser en recevant des réponses de N−f pairs, puisque f d'entre eux peuvent ne pas fonctionner. Mais en recevant des réponses de N−f pairs, on peut supposer que tous les f pairs (dont le nœud n'a pas reçu de réponse) sont en réalité honnêtes. Ainsi, les malveillants sont f parmi les N−f pairs (dont une réponse a été obtenue). Pour que les nœuds parviennent à un consensus, la majorité des autres nœuds doit être honnête, c'est-à-dire qu'il nous faut que N−f soit supérieur à 2f ou N > 3f. Donc généralement, un système conçu pour survivre à f pannes aura au total N=3f+1 nœuds et une taille de quorum de 2f+1. Une fois qu'une proposition franchit le seuil du quorum, les autres membres du réseau sont convaincus que toutes les propositions concurrentes échoueront. Ainsi, le réseau converge vers un résultat.
Mais dans le système de consensus byzantin fédératif, il ne peut non seulement pas y avoir de majorité (car personne ne connaît la taille totale du réseau), mais le concept de majorité est totalement inutile ! Si l'adhésion au système est ouverte, alors quelqu'un peut obtenir la majorité en menant une soi-disant attaque Sybil : en rejoignant plusieurs fois le réseau à travers différents nœuds. Alors pourquoi le coupage transitif de quorum peut-il être appelé quorum, et comment est-il capable de réprimer les propositions concurrentes ?
Techniquement, il n'y a aucun moyen ! Imaginez un réseau de six nœuds, où deux groupes de trois sont isolés dans des coupes de quorum l'un par rapport à l'autre. Le premier sous-groupe peut prendre une décision dont le second n'entendra jamais parler, et vice versa. Pour ce réseau, il n'y a aucun moyen d'atteindre un consensus (à part par hasard).
C'est pourquoi SCP exige que pour le vote fédératif (et pour l'application des théorèmes importants de l'article), le réseau doit posséder une propriété appelée intersection de quorum.. Dans un réseau avec cette propriété, tout quorum que l'on peut construire se chevauche toujours au moins en un nœud. Pour déterminer les sentiments prédominants du réseau, c'est aussi efficace que d'avoir une majorité. Cela signifie intuitivement que si un quorum s'accorde sur l'énoncé X, aucun autre quorum ne pourra jamais s'accorder sur quelque chose d'autre, car il inclura nécessairement un nœud du premier quorum qui a déjà voté pour X.
S'il existe un chevauchement de quorum dans le réseau…
… alors tout deux quorums que vous pouvez construire…
… se chevaucheront toujours.
(Bien sûr, des nœuds qui se chevauchent peuvent s'avérer être des nœuds byzantins ou défectueux d'autres manières. Dans ce cas, le chevauchement des quorums n'aide pas le réseau à parvenir à un consensus. Pour cette raison, de nombreux résultats dans le document technique SCP reposent sur des hypothèses exprimées telles que le fait qu'il reste un chevauchement de quorums dans le réseau, même après la suppression de nœuds défectueux.. Pour simplifier, laissons ces hypothèses implicites pour le reste de l'article).
Il peut sembler peu raisonnable d'attendre qu'un réseau de nœuds indépendants puisse avoir un chevauchement de quorums fiable. Mais il y a deux raisons qui expliquent cela.
La première raison est l'existence même de l'internet. L'internet est un exemple parfait d'un réseau de nœuds indépendants avec un chevauchement de quorums. La plupart des nœuds sur internet ne sont connectés qu'à quelques autres nœuds locaux, mais ces petits ensembles se chevauchent suffisamment pour qu'il soit possible d'accéder à chaque nœud à partir de n'importe quel autre nœud par un chemin ou un autre.
La deuxième raison est spécifique au réseau de paiement Stellar (l'application la plus courante de SCP). Chaque actif dans le réseau Stellar a un émetteur, et les recommandations Stellar exigent que chaque émetteur désigne un ou plusieurs nœuds dans le réseau pour traiter les demandes de rachat. Il est dans votre intérêt d'inclure directement ou indirectement ces nœuds dans les slices de quorum pour chaque actif qui vous intéresse. Les quorums pour tous les nœuds concernés par cet actif se chevaucheront donc au moins dans ces nœuds de rachat. Les nœuds intéressés par plusieurs actifs incluront dans leurs slices de quorum tous les nœuds de rachat des émetteurs concernés, et ils chercheront à relier tous les actifs ensemble. De plus, tout actif qui n'est pas lié de cette manière à d'autres dans le réseau, et ne doit pas être lié — c'est ainsi conçu pour qu'il n'y ait pas de chevauchements de quorum dans ce réseau (par exemple, les banques de la zone dollar souhaitent parfois échanger avec les banques de la zone euro et les banques de la zone peso, donc elles se trouvent dans le même réseau, mais aucune d'entre elles ne se préoccupe du réseau séparé d'enfants échangeant des cartes de baseball).
Bien sûr, l'attente d'un chevauchement de quorums n'est pas une garantie. D'autres systèmes d'accords byzantins, par leur complexité, doivent en grande partie leur existence à la garantie des quorums. L'innovation importante de SCP est qu'elle décharge la responsabilité de la création de quorums de l'algorithme de consensus lui-même et la place au niveau de l'application. Ainsi, bien que le vote fédératif soit assez général pour voter sur n'importe quel sujet, sa fiabilité dépend en réalité du sens plus large de ces valeurs. Certains types d'utilisation hypothétiques peuvent ne pas être aussi pratiques pour créer des réseaux bien reliés que d'autres.
Vote, adoption et confirmation
Au cours d'un cycle de vote fédératif, un nœud commence facultativement à voter pour une certaine valeur V. Cela signifie la diffusion dans le réseau d'un message : « Je suis le nœud N, mes slices de quorums Q, et je vote pour V ». Lorsque le nœud vote de cette manière, il promet qu'il n'a jamais voté contre V et ne le fera jamais.
Dans les transmissions des nœuds pair-à-pair, chaque nœud voit comment les autres votent. Une fois qu'un nœud a collecté un nombre suffisant de ces messages, il peut suivre les coupes de quorums et essayer de trouver des quorums. S'il voit un quorum de pairs qui votent également pour V, il peut passer à l'acceptation de V et transmettre ce nouveau message sur le réseau : « Je suis le nœud N, mes coupes de quorum Q, et j'accepte V ». L'acceptation offre une garantie plus forte que le 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 du réseau n'acceptera jamais une autre option (théorème 8 dans le document technique SCP le prouve).
Bien sûr, il y a une forte probabilité qu'il n'y ait pas immédiatement de quorum de nœuds qui s'accordent sur V. D'autres nœuds peuvent voter pour d'autres valeurs. Mais un nœud a un autre moyen de passer du simple vote à l'acceptation. N peut accepter une autre valeur W, même s'il n'a pas voté pour elle et même s'il ne voit pas de quorum pour celle-ci. Pour qu'un changement de vote se produise, il suffit de voir un ensemble bloquant de nœuds ayant accepté W. Un ensemble bloquant est constitué d'un nœud de chacune des coupes de quorums de N. Comme son nom l'indique, il est capable de bloquer toute autre valeur. Si tous les nœuds de cet ensemble acceptent W, alors (selon le théorème 8), il ne sera jamais possible de former un quorum acceptant une autre valeur, et donc il est également sûr pour N d'accepter W.
Le nœud N avec trois coupes de quorums.
B-D-F est un ensemble bloquant pour N : il comprend un nœud de chacune des coupes de N.
B-E est également un ensemble bloquant pour N, car E apparaît dans deux coupes de N.
Mais un ensemble bloquant n'est pas un quorum. Ce serait trop facile de tromper le nœud N pour qu'il accepte la valeur désirée, si l'on parvenait à pirater un seul nœud dans chacune des coupes de N. Par conséquent, accepter une valeur n'est pas encore la fin du vote. Au lieu de cela, N doit confirmer la valeur, c'est-à-dire voir un quorum de nœuds l'acceptant. S'il va aussi loin, alors, comme le prouve le document technique SCP (dans le théorème 11), le reste du réseau finira également par confirmer la même valeur, donc N terminera le vote fédératif avec une valeur spécifique comme résultat.
Vote fédératif.
Le processus de vote, d'adoption et de confirmation constitue un tour complet du vote fédératif. Le protocole de consensus Stellar regroupe de nombreux de ces tours pour créer un système de consensus complet.
Protocole de consensus Stellar
Les deux propriétés les plus importantes d'un système de consensus sont sécurité et robustesse. Un algorithme de consensus est "sécurisé" s'il ne peut jamais donner des résultats différents à différents participants (l'historique de Bob ne contredira jamais celui de Carol). La "robustesse" signifie que l'algorithme produira toujours un résultat, c'est-à-dire qu'il ne sera jamais bloqué.
La procédure de vote fédératif décrite est sécurisée dans le sens où si un nœud confirme la valeur V, aucun autre nœud ne confirmera une autre valeur. Mais « ne pas confirmer une autre valeur » ne signifie pas qu'il confirmera nécessairement quelque chose. Les participants peuvent voter pour un si grand nombre de valeurs différentes qu'aucune d'entre elles n'atteindra le seuil d'adoption. Cela signifie qu'il n'y a pas de robustesse.
Le protocole de consensus Stellar utilise le vote fédératif de manière à garantir à la fois sécurité et robustesse. (Les garanties de sécurité et de robustesse du SCP ont une limite théorique. La construction choisit une très forte garantie de sécurité, sacrifiant une légère diminution de la robustesse, mais puisqu'il y a un temps suffisant, le consensus sera probablement atteint). En résumé, l'idée est de mener plusieurs votes fédératifs sur différentes valeurs jusqu'à ce qu'une d'elles passe complètement par toutes les phases de vote du SCP, décrites ci-dessous.
Les valeurs sur lesquelles le SCP vise à obtenir un consensus peuvent être l'historique des transactions, une commande de déjeuner ou autre chose, mais il est important de noter que ce ne sont pas les valeurs qui sont adoptées ou confirmées. Au lieu de cela, le vote fédératif se déroule sur des déclarations concernant ces valeurs.
Les premiers tours de vote fédératif se déroulent à l'étape de nomination (phase de nomination), sur un ensemble de déclarations du type « Je nomme V », potentiellement pour de nombreuses valeurs différentes de V. L'objectif de la nomination est de trouver une ou plusieurs déclarations qui passeront par l'adoption et la confirmation.
Après avoir trouvé des candidats vérifiables, le SCP passe à l'étape du vote, où l'objectif est de trouver une certaine bulletin (c'est-à-dire un conteneur pour la valeur proposée) et un quorum qui peut déclarer commit pour lui (commit). Si le quorum valide le bulletin, sa valeur est acceptée comme consensus. Mais avant qu'un nœud puisse voter pour le commit du bulletin, il doit d'abord confirmer l'annulation de tous les bulletins avec une valeur de compteur inférieure. Ces étapes — l'annulation des bulletins, pour trouver celui pour lequel un commit peut être confirmé — comprennent plusieurs tours de vote fédératif sur plusieurs propositions de bulletins.
Les sections suivantes décrivent plus en détail la nomination et le vote.
Nommer
Au début de l'étape de nomination, chaque nœud peut spontanément choisir une valeur V et voter pour l'affirmation « Je nomme V ». L'objectif à ce stade est de confirmer la nomination d'une certaine valeur par le biais du vote fédératif.
Il est possible qu'un nombre suffisant de nœuds vote pour des affirmations suffisamment variées, et aucune nomination ne puisse atteindre le seuil d'acceptation. Par conséquent, en plus de diffuser leurs propres votes de nomination, les nœuds « reflètent » les nominations de leurs pairs. Le reflet (echo) signifie que si un nœud vote pour la nomination V, mais voit un message d'un voisin votant pour la nomination W, alors il votera désormais pour la nomination à la fois de V et de W. (Tous les votes des pairs ne sont pas reflétés pendant la nomination, car cela peut entraîner une explosion de différents nominés. Le SCP inclut un mécanisme régulant ces votes. En résumé, il existe une formule pour déterminer le « prioritaire » d'un pair du point de vue d'un nœud, et seules les voix des nœuds à haute priorité sont reflétées. Plus la nomination dure longtemps, plus le seuil est bas, donc un nœud élargit l'ensemble de pairs dont il reflétera les votes. La formule de priorité inclut comme une des entrées le numéro de slot, donc un pair de haute priorité pour un slot peut être de basse priorité pour un autre, et vice versa).
Conceptuellement, l'avancement de à la fois V et W représente des voix fédératives distinctes, chacune pouvant indépendamment atteindre une adoption ou une confirmation. En pratique, les messages du protocole SCP regroupent ces voix séparées.
Bien que voter pour l'avancement de V constitue une promesse de ne jamais voter contre cet avancement, au niveau de l'application – dans ce cas SCP – il est défini ce que signifie « contre ». SCP ne voit pas d'affirmation qui contredit le vote « Je propose X », c'est-à-dire qu'il n'y a pas de message « Je suis contre la proposition X », donc le nœud peut voter pour la proposition de n'importe quelles valeurs. Beaucoup de ces nominations peuvent ne mener à rien, mais finalement, le nœud pourra accepter ou confirmer une ou plusieurs valeurs. Une fois le nominé confirmé, il devient un candidat.
La proposition de SCP utilisant le vote fédératif. Il peut y avoir plusieurs valeurs “B” proposées par des nœuds de même rang et « réfléchies » par un nœud.
La proposition de candidats peut mener à l'apparition de plusieurs candidats confirmables. Par conséquent, SCP exige que le niveau d'application fournisse une méthode pour combiner les candidats en un composite (composite). La méthode de combinaison peut être n'importe laquelle. L'essentiel est que si cette méthode est déterministe, alors chaque nœud combinera les mêmes candidats. Dans un système de vote pour le déjeuner, la « combinaison » 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 à rejeter. Par exemple, une sélection antérieure par ordre alphabétique). Dans le réseau de paiement Stellar, où se déroule le vote sur l'historique des transactions, la combinaison de deux nominés proposés implique la combinaison des transactions qu'ils contiennent et des dernières de leurs deux horodatages.
La description technique de SCP prouve (théorème 12) qu'à la fin de la phase de proposition, le réseau converge finalement vers un seul composite. Mais il y a un problème : le vote fédératif est un protocole asynchrone (comme SCP). En d'autres termes, les nœuds ne sont pas coordonnés dans le temps, mais seulement par les messages qu'ils envoient. Du point de vue d'un nœud, il n'est pas clair quand la prise en charge a pris fin phase de proposition. Et bien que tous les nœuds finissent par arriver au même composite, ils peuvent choisir différents chemins sur cette route, créant en cours de route différents candidats composites, sans jamais pouvoir dire lequel d'entre eux est final.
Mais c'est normal. La proposition n'est qu'une préparation. L'essentiel est de limiter le nombre de candidats pour atteindre un consensus, qui se produit lors du processus de vote (balloting).
Le vote
Un bulletin est une paire , où counter est un entier qui commence à 1, et value est un candidat de l'étape de proposition. Cela peut être le propre candidat du nœud ou un candidat d'un nœud voisin, accepté par ce nœud. En gros, lors du vote, plusieurs tentatives sont réalisées pour faire parvenir le réseau à un consensus sur un certain candidat dans un certain bulletin via de multiples votes fédératifs sur des affirmations concernant les bulletins. Les compteurs dans les bulletins suivent les tentatives réalisées, et les bulletins avec des compteurs plus élevés ont la priorité sur ceux avec des compteurs plus bas. Si le bulletin est bloqué, un nouveau vote commence, cette fois sur le bulletin .
Il est important de distinguer les valeurs (par exemple, quel devrait être le choix de déjeuner : pizza ou salades), les bulletins (paire counter-value) et déclarations sur les bulletins. Un tour SCP comprend plusieurs tours de vote fédératif, notamment sur les affirmations suivantes :
- « Je suis prêt à engager le bulletin B » et
- « J'annonce l'engagement du bulletin B »
Du point de vue de ce nœud, le consensus est atteint lorsque celui-ci trouve le bulletin B pour lequel il peut confirmer (c'est-à-dire trouver un quorum d'acceptation) l'affirmation « J'annonce l'engagement du bulletin B ». À partir de ce moment, il est sûr d'agir selon la valeur indiquée dans B - par exemple, passer cette commande de déjeuner. Cela s'appelle l'externalisation de la valeur. Une fois l'engagement du bulletin confirmé, le nœud peut être certain que tout autre nœud a réalisé l'externalisation de cette même valeur ou le fera obligatoirement à l'avenir.
Bien que, conceptuellement, de nombreux votes fédératifs soient réalisés sur des déclarations concernant divers bulletins, ils échangent un nombre relativement limité de messages, car chaque message encapsule un certain nombre de bulletins. Un message, par conséquent, promeut l'état de nombreux votes fédératifs simultanément, par exemple : « J'accepte l'engagement des bulletins dans la plage de à ».
Que signifient les termes « préparé » (prepared) et « engagement » (commit) ?
Un nœud vote pour l'engagement d'un bulletin lorsqu'il est convaincu que d'autres nœuds ne procéderont pas à l'engagement de bulletins avec d'autres valeurs. Être convaincu de cela est l'objectif de la préparation de la déclaration. Un vote disant : « Je suis prêt à m'engager sur le bulletin B » est une promesse de ne jamais procéder à l'engagement de bulletins inférieurs à B, c'est-à-dire avec un compteur plus bas (SCP exige que les valeurs dans les bulletins suivent un ordre spécifique. Donc, le bulletin est inférieur à si N1<N2, et aussi si N1=N2 et V1<V2). Ces bulletins inférieurs sont « annulés » (aborted) lors du vote préparatoire, tandis que B est considéré comme « préparé ».
Pourquoi « Je suis prêt à m'engager sur le bulletin B » signifie-t-il « Je promets de ne jamais permettre l'engagement de bulletins inférieurs à B » ? Parce que SCP définit abort comme l'opposé de commit. Le vote pour préparer un bulletin implique également un vote pour annuler certains autres bulletins, et, comme nous l'avons discuté précédemment, voter pour un seul élément est une promesse de ne jamais voter contre celui-ci.
Avant de transmettre un engagement, un nœud doit d'abord trouver un bulletin qu'il peut confirmer comme préparé. En d'autres termes, il procède à un vote fédératif sur le thème « Je suis prêt à m'engager sur le bulletin B », potentiellement pour de nombreux bulletins différents, jusqu'à ce qu'il trouve celui qui accepte le quorum.
D'où viennent les bulletins pour la préparation du vote ? D'abord, le nœud diffuse la préparation du vote pour , où C est le candidat composite, produit lors de l'étape de présentation. Cependant, même après le début de la préparation du vote, la présentation peut entraîner l'apparition de candidats supplémentaires qui deviendront de nouveaux bulletins. Par ailleurs, les pairs peuvent avoir différents candidats et peuvent former un ensemble bloquant qui accepte « Je suis prêt à valider le bulletin B2 », ce qui convaincra également le nœud de l'accepter. Enfin, il existe un mécanisme de temporisation qui génère de nouveaux cycles de vote fédératif sur de nouveaux bulletins avec des compteurs plus élevés, si les bulletins actuels sont bloqués.
Dès qu'un nœud trouve un bulletin B qui peut être confirmé comme préparé, il diffuse un nouveau message « Valider le bulletin B ». Ce vote indique aux pairs que le nœud ne renoncera jamais à B. En réalité, si B représente un bulletin , alors « Valider le bulletin » signifie un accord absolu pour voter pour la validation de chaque bulletin de à . Cette signification supplémentaire aide d'autres nœuds à rattraper un pair avec une validation, s'ils sont encore à des étapes antérieures du protocole.
À ce stade, il convient de souligner à nouveau qu'il s'agit de protocoles asynchrones. Ce n'est pas parce qu'un nœud envoie des votes pour une validation que ses pairs le font également. Certains d'entre eux peuvent encore voter sur des déclarations pour la préparation du vote, d'autres ont peut-être déjà externalisé la valeur. SCP explique comment un nœud doit traiter chaque type de message pair à pair indépendamment de sa phase.
Si le message « Je déclare un engagement <N,C> » ne peut pas être accepté ou confirmé, il y a une probabilité que le message <N+1,C> ou <N+2,C> soit accepté ou confirmé — ou, en tout cas, n'importe quel bulletin ayant la valeur C, et non toute autre valeur, puisque le noeud a déjà promis de ne jamais annuler <N,C>. Au moment où le noeud diffuse les voix pour l'engagement, ce sera C ou rien, selon la profondeur du consensus. Cependant, cela ne suffit pas encore au noeud pour externaliser C. Certains envahisseurs byzantins (composant moins que le quorum, basé sur nos hypothèses de sécurité) peuvent mentir au noeud. L'acceptation, puis la confirmation d'un certain bulletin (ou d'une plage de bulletins) donne enfin au noeud la certitude d'externaliser C.
Le vote SCP par le vote fédératif. Non montré : à tout moment, un minuteur peut se déclencher, augmentant le compteur dans le bulletin (et éventuellement produisant un nouveau composite des candidats supplémentaires avancés).
Et c'est tout ! Une fois que le réseau est parvenu à un consensus, il est prêt à le faire encore et encore. Dans le réseau de paiement Stellar, cela se produit environ toutes les 5 secondes : un exploit qui nécessite à la fois sécurité et résilience, garanties par SCP.
SCP peut y parvenir en s'appuyant sur plusieurs tours de vote fédératif. Le vote fédératif est rendu possible grâce au concept de coupes de quorum : ensembles de nœuds de même niveau auxquels chaque nœud a décidé de faire confiance comme partie de son quorum (subjectif). Cette configuration signifie qu'on peut parvenir à un consensus même dans un réseau à adhésion ouverte et des tromperies byzantines.
Lectures complémentaires
- Le document technique original SCP peut être trouvé , et projet de spécifications pour sa mise en œuvre.
- L'auteur original du protocole SCP, David Mazieres, l'explique de manière simplifiée (mais toujours technique) .
- Vous avez peut-être été surpris de ne pas trouver dans cet article les termes « minage » ou « preuve de travail ». SCP n'utilise pas ces méthodes, mais d'autres algorithmes de consensus le font. Zane Wisserpoon a écrit un .
- d'un réseau simple atteignant un consensus en un tour complet de SCP.
- Pour les lecteurs intéressés par les mises en œuvre SCP : voir , utilisé par le réseau de paiement Stellar, ou , que j'ai écrit pour une meilleure compréhension du SCP.
Source : habr.com
