Élection du leader à partir de balises aléatoires et d'autres stratégies

L'élection du leader dans un contexte blockchain vise à sélectionner le participant qui déterminera le prochain bloc à ajouter à la blockchain. En règle générale, un validateur est choisi par emplacement parmi l'ensemble des validateurs et obtient le droit d'étendre la chaîne avec un nouveau bloc dans cet emplacement. (Nous supposons que les validateurs gardent une heure précise et se mettent d'accord sur le numéro de créneau actuel.) Dans cet article, nous explorons des stratégies pour élection aléatoire du chef dans les protocoles de consensus. (Pour en savoir plus sur le caractère aléatoire en général, consultez notre article précédent, Aléatoire public et balises d'aléatoire, Où nous avons étudié des protocoles autonomes pour générer un caractère aléatoire publiquement vérifiable et imprévisible.) 

Pourquoi l’élection du chef est importante

L’élection de dirigeants honnêtes et actifs est cruciale pour la croissance saine de la chaîne. Les validateurs malveillants ne devraient pas pouvoir biaiser le processus d’élection des dirigeants pour devenir eux-mêmes leaders plus fréquemment. Dans le cas contraire, la production de blocs pourrait tomber entre les mains de parties capables de censurer les transactions ou d’arrêter complètement la blockchain. Dans les protocoles de consensus de type chaîne la plus longue, un leader produisant un bloc invalide (ou aucun bloc) pourrait provoquer une bifurcation temporaire de la chaîne. Dans les protocoles de consensus de type BFT, un mauvais leader déclenche un sous-protocole de changement de vue qui entraînera une surcharge de communication. 

L’alternative aux élections en commission

L'élection du comité est un problème connexe, où l'objectif est de sélectionner un sous-ensemble uniformément aléatoire de validateurs d'une certaine taille fixe. k. Cette fonctionnalité est utile en soi car des sous-comités sont souvent nécessaires dans les paramètres de blockchain pour réduire la taille de l'ensemble des validateurs afin d'accélérer le consensus (parmi de nombreux exemples, citons Le tri d'Algorand ainsi que Sélection du comité d'Ethereum). Mais l'élection du comité est également utile pour l'élection du leader, permettant aux validateurs d'éviter de réexécuter un protocole d'élection du leader si le leader élu ne se présente pas. Si, à la place d'un chef, un comité est élu dans un ordre fixe, le deuxième membre du comité peut devenir chef si le premier n'est pas disponible. 

Les propriétés d'un bon protocole électoral

Dans un protocole d’élection de dirigeants, les dirigeants doivent être imprévisibles. Si un attaquant découvre qui est le prochain leader, il pourrait lancer une attaque par déni de service (DoS) contre lui pour l'empêcher de publier un blocage. L’attaquant pourrait alors éliminer le prochain leader et ainsi de suite, mettant ainsi un terme à la blockchain. L’imprévisibilité pourrait également être renforcée pour garantir que le validateur lui-même n’apprenne pas quand il va diriger, ce qui pourrait être important pour la prévention de la corruption.

Le processus d'élection du chef doit avoir les trois propriétés suivantes :

• Équité: chaque validateur honnête a une probabilité de 1/N être élu parmi un ensemble de N validateurs (une notion détendue de l'équité de la théorie des jeux permet construire une élection de chef même en présence d'une majorité malveillante mais avec une limite inférieure non constante sur le nombre de tours).
• Imprévisibilité: l'adversaire ne connaît le prochain leader qu'un certain temps T avant que le leader n'annonce le bloc suivant.
• Unicité: exactement un leader est choisi dans chaque emplacement.

Élection secrète du chef

L'élection secrète d'un chef est une élection imprévisible avec T = 0. Dans ce processus, le leader n'est connu de personne jusqu'à ce qu'il publie le bloc. Cela élimine complètement la fenêtre d'une attaque DoS : avant que le leader ne se révèle, l'attaquant ne sait pas qui attaquer, ce qui fait que sa meilleure stratégie est une supposition aléatoire. Et une fois que le leader a publié son blocage, il est trop tard pour attaquer car le leader a déjà rempli sa responsabilité envers le protocole. 

La notion « après que le leader a publié son bloc » est en fait une simplification, car nous n'avons pas de diffusion instantanée dans le monde réel. Un attaquant disposant d'une position forte sur le réseau pourrait remarquer un leader diffusant un bloc en premier et être capable de corrompre rapidement le leader, de créer un bloc différent et de lancer la diffusion d'origine. 

Bien qu’il s’agisse d’un modèle d’attaquant très puissant, des défenses ont été proposées contre lui. Algorand a proposé le modèle d'effacements, dans lequel le leader est effectivement capable d'effacer la clé nécessaire à la signature du bloc dans son emplacement before il est donc vraiment trop tard pour attaquer au moment où le leader entreprend une action publique. Thaddeus Dryja, Quanquan C. Liu et Neha Narula, trois chercheurs du MIT Media Lab, proposé que le leader calcule un VDF sur son bloc avant la diffusion, garantissant ainsi qu'un attaquant adaptatif ne peut pas construire un autre bloc valide à temps pour le faire accepter pour le slot souhaité.

Autres méthodes d'élection 

Le processus d'élection d'un chef le plus simple est tournoi à la ronde, où les dirigeants sont élus selon un ordre déterministe. Bien que cette approche soit prévisible et donc sujette aux attaques DoS, elle convient aux systèmes autorisés où les validateurs disposent d'une bonne protection DoS.

Un leader peut également être élu à l'aide d'un résultat d'un sondage externe. balise aléatoire, s'il y en a un disponible et dont la sécurité est fiable. Malheureusement, il est difficile pour les participants au consensus d'exécuter eux-mêmes un protocole de balise aléatoire distribuée (DRB), car ceux-ci supposent généralement une notion de diffusion ou de consensus fiable, ce qui nécessite à son tour l'élection d'un leader, introduisant une dépendance circulaire.

Courant élection du leader à Ethereum est une bonne étude de cas. Chaque nouveau leader calcule une sortie de fonction aléatoire vérifiable (VRF) (une signature BLS sur le numéro d'époque) et XOR la ​​valeur dans le mix. La valeur du mix à la fin de l'époque i définit les dirigeants et les sous-comités pour la durée de l'époque i+2. Les dirigeants et leur emploi du temps sont prévisibles une époque à l’avance (actuellement ~6.4 minutes). Le protocole est sujet aux atteintes à l'équité, dans la mesure où le dernier dirigeant peut choisir de publier ou de retenir sa contribution au mélange et ainsi influencer d'un tout petit peu le résultat des prochaines élections. Si le dernier  k les dirigeants s’entendent, ils peuvent introduire k  des éléments de partialité et rendent plus probable l'élection d'utilisateurs malveillants. La Fondation Ethereum travaille activement sur des techniques plus avancées d’élection des dirigeants, dont nous discutons ci-dessous.

Élection du chef basée sur le VRF

Une autre approche, lancée par Algorand, Est un Élection du chef basée sur le VRF, qui implique que chaque validateur calcule en privé une sortie VRF et vérifie si la sortie tombe en dessous d'un seuil. Cette procédure filtre déjà la plupart des validateurs, puisque le seuil est choisi de telle sorte qu'il est peu probable qu'il tombe en dessous. Les quelques validateurs restants révèlent leurs sorties VRF, et celui avec la valeur VRF la plus basse est élu. Cette approche permet d'obtenir une imprévisibilité (ou un secret) parfaite, mais elle ne garantit pas l'unicité. Certains validateurs pourraient ne pas recevoir de messages de tous les dirigeants potentiels et pourraient supposer que le mauvais leader a remporté l'élection, ce qui obligerait ces validateurs à se séparer de la chaîne principale. 

L'évaluation VRF est périodiquement ensemencée avec la sortie d'une balise aléatoire pour rendre moins prévisible pour les validateurs eux-mêmes de voir quels créneaux vont-ils diriger. Cette propriété empêche un attaquant qui compromet silencieusement le validateur d'apprendre l'emplacement au moment où le validateur deviendra leader et de lancer une attaque lorsque le validateur est sur le point d'annoncer un blocage. Cette approche permet également de prévenir les attaques de corruption, dans lesquelles un validateur prouve à des parties externes qu'il sera leader dans un secteur particulier et récolte des pots-de-vin en échange de l'accomplissement d'une tâche en tant que leader (par exemple, bloquer une transaction).

De telles approches, où le nombre de dirigeants élus est une variable aléatoire, sont appelées Élection probabiliste du chef (PLÉ). Le PLE peut aboutir à ce qu'aucun dirigeant ne soit élu pour un créneau donné. Cela équivaut à élire un leader malveillant ou hors ligne dans la mesure où le créneau finira par être ignoré, réduisant ainsi l'efficacité du protocole de consensus.

Mais le plus grand inconvénient du PLE est que plusieurs dirigeants pourraient être élus, ce qui nécessiterait une sorte de procédure de départage. Les égalités présentent un risque pour le consensus, dans la mesure où un validateur ayant une contribution gagnante peut en faire part à seulement la moitié du réseau, provoquant potentiellement un désaccord chez le leader choisi. De plus, les processus de résolution des liens peuvent prendre plus de temps et de communication, ce qui nuit à l’efficacité. Dfinition, discuté plus en détail dans le premier message de cette série, utilise une balise aléatoire basée sur VRF pour élire un seul leader ; cependant, cela sacrifie l’imprévisibilité. Idéalement, tout processus de sélection d’un leader devrait éviter complètement les liens tout en restant imprévisible, ce qui nous amène au Saint Graal de ce domaine de recherche : l’élection secrète d’un leader.

Élection d'un chef secret unique 

L'objectif de Élection d'un chef secret unique (SSLE) consiste à sélectionner un leader unique parmi un ensemble de validateurs tout en maintenant l'équité et l'imprévisibilité. Protocol Labs a présenté la notion comme un problème de recherche, et Dan Boneh, informaticien de Stanford et conseiller en recherche sur la cryptographie a16z, avec Saba Eskandarian, Lucjan Hanzlik et Nicola Greco, ont ensuite proposé une définition formelle de SSLE. Cette propriété d'unicité évite les risques de consensus et les coûts d'efficacité découlant des procédures de départage. Concrètement, Sarah Azouvi, de Protocol Labs, et Danielle Cappelletti, du Politecnico di Torino, montrer que lorsque SSLE est utilisé par rapport à PLE dans un protocole à chaîne la plus longue, les blocs peuvent être finalisés beaucoup plus rapidement (25 % plus rapidement avec un adversaire contrôlant un tiers de la participation). Ainsi, développer un protocole SSLE pratique est un problème important.

Dans l'approche la plus courante, que nous appellerons basé sur la lecture aléatoire (utilisé à la fois dans le papier SSLE original et une proposition Ethereum SSLE), chaque validateur enregistre un Nonce cela semble aléatoire, mais ils peuvent prouver qu'ils leur appartiennent. Les noms occasionnels sont ensuite compilés dans une liste. La liste est mélangée de telle sorte que les noms occasionnels ne soient plus liés aux validateurs qui les ont soumis ; c'est-à-dire qu'étant donné la liste mélangée, aucun adversaire ne peut dire quel validateur a soumis quel nonce. Un index de liste est ensuite choisi en fonction d'un public balise aléatoire, et le leader se révèle en prouvant que le nonce à cet index de la liste mélangée leur appartient. 

Puisqu'un seul index est choisi, le protocole basé sur la lecture aléatoire génère toujours un unique chef. Étant donné que la balise aléatoire est conçue pour générer des valeurs uniformément aléatoires, le protocole est également juste: chaque validateur a une chance égale d'être élu. De plus, si le brassage est effectué correctement (c'est-à-dire uniformément de manière aléatoire) et que les noms occasionnels ne peuvent plus être liés aux identités des validateurs, ce protocole permet également d'obtenir imprévisibilité.

Le brassage est nécessaire car même si le simple fait de choisir un index dans la liste non mélangée sur la base d'une balise aléatoire donnerait déjà un caractère unique et équitable, l'imprévisibilité est plus difficile à atteindre : si un adversaire sait quel validateur a soumis quel cas occasionnel, il sait qui a soumis le cas occasionnel au moment choisi. index et peut identifier le leader. 

Les deux approches suivantes mélangent la liste de différentes manières. Le plus simple est le Proposition Ethereum SSLE, dans lequel n les validateurs soumettent leurs noms occasionnels via Tor pour dissocier les identités des validateurs de leurs noms occasionnels. Une fois que tous les validateurs se sont inscrits, la liste est mélangée à l'aide d'une balise aléatoire publique, et les validateurs deviennent les leaders dans l'ordre de la liste mélangée. Bien que ce système soit pratique – l'élection ne doit avoir lieu qu'une seule fois par n slots – cette dépendance à l’égard de Tor peut être indésirable (comme c’est le cas lorsque l’on s’appuie sur la sécurité de tout protocole extérieur). De plus, ce n'est pas parfaitement imprévisible : après le premier n-1 leaders se dévoilent, la finale nth le leader est connu.

Au lieu d'utiliser Tor, le document SSLE original demande à chaque validateur de s'inscrire pour les élections dans l'ordre en ajoutant son nom occasionnel à la liste, en mélangeant la liste et en re-randomisation les occasionnels. Cette re-randomisation signifie que chaque nom occasionnel est mappé à une nouvelle chaîne non liée, de sorte que le validateur auquel il appartient peut toujours prouver qu'il est propriétaire du nom occasionnel re-randomisé. La re-randomisation fait en sorte qu'un adversaire ne puisse pas dire dans quelle position un nonce particulier s'est retrouvé après le mélange, en supposant qu'au moins un mélangeur est honnête.

Bien que cette approche de brassage séquentiel du document SSLE original évite de s'appuyer sur Tor et obtienne les propriétés formelles de SSLE, elle est coûteuse : chaque fois qu'un nouveau validateur s'inscrit, il doit publier l'intégralité de la liste mélangée sur la blockchain, re-randomiser tous les occasionnels et fournir la preuve qu'ils l'ont fait honnêtement, ce qui se traduit par une quantité linéaire de communication par validateur. Avec un ensemble immuable de validateurs, cela doit être fait (amorti) une fois par élection, car le leader se réinscrit une fois qu'il a révélé la preuve pour une occasion. Le document propose un compromis réglable entre efficacité et prévisibilité : nous pouvons à la place mélanger uniquement un sous-ensemble plus petit de la liste, réduisant ainsi les coûts, si nous sommes prêts à permettre une petite quantité de prévisibilité. Il est difficile de trouver un bon équilibre entre efficacité et sécurité et, par conséquent, les protocoles SSLE ne sont pas encore largement utilisés dans la pratique. 

Idéalement, cette approche de brassage séquentiel peut également être utilisée pour résoudre le problème de l’élection du comité, en utilisant la balise aléatoire pour choisir k indices distincts dans la liste en tant que membres du comité. C'est une belle réussite, car le problème n'est pas résolu de manière triviale par les approches basées sur VRF, puisque l'exécution d'un protocole probabiliste basé sur VRF k les temps peuvent élire une taille de comité variable en fonction du caractère aléatoire. 

Autres approches de SSLE

Une autre approche basée sur la lecture aléatoire est SSLE adaptativement sécurisé de DDH. Cette construction est légèrement plus compliquée mais permet d'obtenir une notion de sécurité plus forte, protégeant contre un adversaire adaptatif dans le modèle d'effacements d'Algorand. Cet adversaire est adaptatif dans le sens où il peut choisir les validateurs à corrompre pendant le protocole, plutôt qu'avant le démarrage du protocole. 

Un autre défi du SSLE consiste à élire chaque validateur avec une probabilité proportionnelle à sa participation, plutôt qu'uniformément au hasard. Les protocoles basés sur le brassage peuvent naïvement y parvenir en permettant à chaque validateur d'enregistrer plusieurs occasionnels : un occasionnel pour chaque unité de mise qu'il détient. Cependant, le coût du brassage augmente linéairement avec le nombre d’unités mises en jeu. S, devenant très cher même pour des répartitions de mises réalistes. Un élégant SSLE basé sur MPC l'approche a une complexité qui augmente uniquement avec le log S, et cela évite également le besoin d'une configuration fiable ou d'une balise aléatoire. Cependant, par rapport aux approches basées sur le brassage, elle nécessite davantage de cycles de communication (logarithmique du nombre de participants) par dirigeant élu.

***

Nous avons résumé notre analyse dans ce tableau pratique.

	Équité	Imprévisibilité/ Secret*	Unicité
Tournoi à la ronde	✓	✗	✓
Balise aléatoire idéale	✓	✗	✓
Élection du leader d'Ethereum (actuel)	✗	✗	✓
Élection des dirigeants basée sur le VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* La balise round-robin est entièrement prévisible, mais dans le reste des balises ✗ signifie que la notion est réalisée jusqu'à un certain degré limité : la balise idéale-aléatoire est imprévisible mais l'adversaire apprend le résultat en même temps que le leader élu, donc le leader élu peut être attaqué avant d'annoncer un blocage ; La balise d'Etherum est imprévisible jusqu'à environ 6 minutes et peut être légèrement biaisée pour nuire à l'équité ; Algorand élit plusieurs dirigeants avec une faible probabilité.

SSLE est une direction prometteuse, qui atteint l'équité, l'imprévisibilité et l'unicité. Deux défis majeurs liés à son adoption sont l’efficacité et la capacité à s’adapter à des répartitions de participations non uniformes. De plus, les approches SSLE basées sur le shuffle que nous mettons en avant supposent l’existence d’une balise aléatoire impartiale, ce qui n’est pas simple à réaliser en pratique. Comme SSLE n'a été officiellement défini que récemment, nous verrons probablement des protocoles améliorés relever ses défis dans un avenir proche. 

***

Miranda Christ est doctorante en informatique à l'Université de Columbia, où elle est membre du Theory Group et Presidential Fellow. Elle est également stagiaire de recherche chez a16z crypto.

Joseph Bonneau est un partenaire de recherche chez a16z crypto. Ses recherches portent sur la cryptographie appliquée et la sécurité de la blockchain. Il a enseigné des cours de crypto-monnaie à l'Université de Melbourne, NYU, Stanford et Princeton, et a obtenu un doctorat en informatique de l'Université de Cambridge et des diplômes BS/MS de Stanford.

Valéria Nikolaenko est un partenaire de recherche chez a16z crypto. Ses recherches portent sur la cryptographie et la sécurité de la blockchain. Elle a également travaillé sur des sujets tels que les attaques à longue portée dans les protocoles de consensus PoS, les schémas de signature, la sécurité post-quantique et le calcul multipartite. Elle est titulaire d'un doctorat en cryptographie de l'Université de Stanford sous la direction du professeur Dan Boneh et a travaillé sur la blockchain Diem au sein de l'équipe de recherche centrale.

***

Rédacteur en chef: Tim Sullivan

***

Les opinions exprimées ici sont celles du personnel individuel d'AH Capital Management, LLC (« a16z ») cité et ne sont pas les opinions d'a16z ou de ses sociétés affiliées. Certaines informations contenues ici ont été obtenues de sources tierces, y compris de sociétés de portefeuille de fonds gérés par a16z. Bien qu'elles proviennent de sources considérées comme fiables, a16z n'a pas vérifié ces informations de manière indépendante et ne fait aucune déclaration quant à l'exactitude durable des informations ou à leur pertinence dans une situation donnée. De plus, ce contenu peut inclure des publicités de tiers ; a16z n'a pas examiné ces publicités et n'approuve aucun contenu publicitaire qu'elles contiennent.

Ce contenu est fourni à titre informatif uniquement et ne doit pas être considéré comme un conseil juridique, commercial, d'investissement ou fiscal. Vous devriez consulter vos propres conseillers sur ces questions. Les références à des titres ou à des actifs numériques sont uniquement à des fins d'illustration et ne constituent pas une recommandation d'investissement ou une offre de fournir des services de conseil en investissement. En outre, ce contenu n'est ni destiné ni destiné à être utilisé par des investisseurs ou des investisseurs potentiels, et ne peut en aucun cas être invoqué pour prendre une décision d'investir dans un fonds géré par a16z. (Une offre d'investissement dans un fonds a16z ne sera faite que par le mémorandum de placement privé, le contrat de souscription et toute autre documentation pertinente de ce fonds et doit être lu dans son intégralité.) Tous les investissements ou sociétés de portefeuille mentionnés, référencés ou décrits ne sont pas représentatifs de tous les investissements dans des véhicules gérés par a16z, et rien ne garantit que les investissements seront rentables ou que d'autres investissements réalisés à l'avenir auront des caractéristiques ou des résultats similaires. Une liste des investissements effectués par des fonds gérés par Andreessen Horowitz (à l'exclusion des investissements pour lesquels l'émetteur n'a pas autorisé a16z à divulguer publiquement ainsi que des investissements non annoncés dans des actifs numériques cotés en bourse) est disponible sur https://a16z.com/investments /.

Les tableaux et graphiques fournis ici sont uniquement à des fins d'information et ne doivent pas être utilisés pour prendre une décision d'investissement. Les performances passées ne représentent pas les résultats futurs. Le contenu ne parle qu'à la date indiquée. Toutes les projections, estimations, prévisions, objectifs, perspectives et/ou opinions exprimées dans ces documents sont susceptibles d'être modifiées sans préavis et peuvent différer ou être contraires aux opinions exprimées par d'autres. Veuillez consulter https://a16z.com/disclosures pour des informations supplémentaires importantes.