Aléatoire public et balises d'aléatoire

Aléatoire public est un composant essentiel de nombreux protocoles de sécurité du monde réel. Dans certaines applications, telles que les jeux d'argent et les jeux multijoueurs, le hasard ajoute du plaisir. Dans d'autres applications, le caractère aléatoire offre un moyen équitable d'allouer des ressources non divisibles, allant des cartes vertes à l'affectation des juges des tribunaux de circuit aux affaires, en passant par le classement dans les tournois sportifs. Il est également utilisé pour allouer négatif ressources, comme les vérifications fiscales ou le contrôle de sécurité secondaire à l'aéroport.

Traditionnellement, nous comptions sur des autorités de confiance pour générer un caractère aléatoire pour ces protocoles, mais dans le monde du Web3, nous devrons faire mieux. Dans cet article, nous explorerons des approches pour créer un caractère aléatoire publiquement vérifiable via balises aléatoires distribuées puis discutez de certaines applications en chaîne. (La partie II, qui est à venir, se concentrera spécifiquement sur l'élection du chef, tout en fournissant une évaluation des approches d'élection du chef suppléant.) 

Propriétés recherchées

Générer des nombres aléatoires est une tâche notoirement subtile. Par exemple, de nombreuses clés cryptographiques ont été divulguées parce qu'elles repose sur un générateur de nombres aléatoires défectueux (dont le mur de Cloudflare lampes à lave aurait servi d'atténuation créative). C'est juste aléatoire privé, cependant, lorsqu'une seule partie doit le générer et l'utiliser.

Le hasard public, en revanche, est un processus multipartite, ce qui ajoute considérablement à la difficulté. Un bon protocole pour produire de l'aléatoire public aura les propriétés de sécurité suivantes :

• Impartial: Aucun attaquant, ou coalition d'attaquants, ne devrait être en mesure de biaiser la sortie. 
• Fiable: Aucun attaquant ne devrait pouvoir empêcher le protocole de produire une sortie.
• Vérifiable : : N'importe qui peut facilement vérifier la sortie du protocole et devrait voir la même sortie que tout le monde.
• Imprévisible: Si le protocole produit une sortie au moment T₁, personne ne devrait pouvoir prédire quoi que ce soit sur la sortie avant un certain temps T₀<T₁, idéalement avec T₀ très proche de T₁.

L'impartialité est une propriété plus faible que l'imprévisibilité car tout protocole imprévisible doit être non biaisé. Les informaticiens diraient que l'impartialité réduit à l'imprévisibilité, car si vous pouvez biaiser, vous pouvez prédire. Mais parfois, nous voudrons raisonner à leur sujet séparément car ils peuvent reposer sur des hypothèses différentes - par exemple, une majorité malhonnête pourrait prédire le résultat, mais pas le biaiser.

En plus de ces propriétés, le protocole doit être efficace pour s'exécuter et produire un grand nombre de bits aléatoires. (En pratique, il est souvent suffisant pour les applications de produire 128 bits aléatoires, en les utilisant pour amorcer un générateur de nombres pseudo-aléatoires [PNRG] pour produire plus de bits selon les besoins. Cependant, l'imprévisibilité doit tenir pour que chaque bit individuel de la sortie soit utilisable pour un tel applications telles que les loteries ou les allocations de ressources.) Le protocole devrait également idéalement être efficace en termes de coûts de communication et de calcul.

Différents protocoles peuvent atteindre ces propriétés dans des conditions différentes. Par exemple, certains protocoles pourraient être impartiaux par n'importe quelle coalition de f₁ nœuds malveillants et imprévisibles par toute coalition de f₂<f₁ nœuds malveillants. Il existe également différents degrés de biais. Par exemple, dans certains protocoles, un participant peut être en mesure de biaiser la sortie d'"un bit", ce qui signifie qu'il peut choisir entre l'une des deux sorties possibles. D'autres attaques pourraient leur permettre de réparer complètement la sortie. En règle générale, cependant, nous ne voulons tolérer aucun biais (ou prévisibilité).

L'idéal cryptographique : Rbalises andomness

Les cryptographes commencent souvent par réfléchir à une solution idéale à leurs problèmes. Dans le cas du hasard public, un balise aléatoire est un service idéalisé qui produit régulièrement une sortie aléatoire satisfaisant à toutes les exigences de sécurité nécessaires.

Une telle balise de hasard idéalisée, similaire à d'autres abstractions cryptographiques - telles que les oracles aléatoires ou le modèle de groupe générique - n'existe pas dans le monde réel. Mais c'est un objectif utile à atteindre et un modèle utile pour raisonner sur les protocoles qui reposent sur le hasard public. 

Nous pouvons considérer quelques approximations d'une balise d'aléatoire idéale.

• Balises centralisées: L'approche la plus simple pour générer un bon caractère aléatoire consiste à utiliser un tiers centralisé avec des services tels que Balise aléatoire NIST or Random.org, qui génère un caractère aléatoire à partir du bruit atmosphérique et est accrédité pour une utilisation dans les jeux d'argent. Cette dépendance vis-à-vis d'un tiers sape complètement la philosophie de la décentralisation. En effet, dans l'exemple ci-dessus, nous devons être sûrs que les organisations concernées génèrent correctement l'aléatoire, sans aucune preuve cryptographique.
• Affichages aléatoires physiques: De nombreuses loteries traditionnelles s'appuient sur un affichage public, qui peut inclure, par exemple, une personne atteignant un conteneur de balles de ping-pong portant des numéros différents. Malheureusement, ceux-ci sont souvent facilement manipulables. Par exemple, certaines balles peuvent être placées au congélateur ainsi que on peut dire au sélecteur de choisir les froids.
• Balises naturelles: Une idée courante consiste à utiliser des phénomènes naturels aléatoires comme la météo ou le rayonnement de fond cosmique comme balise. Malheureusement, toutes les sources proposées ne fournissent pas un consensus fort. Différents observateurs verront des valeurs légèrement différentes, ce qui nécessite de réintroduire une partie de confiance pour prendre une mesure officielle, avec tous les inconvénients d'une balise centralisée.
• Balises semi-centralisées: Une meilleure approche serait d'obtenir le caractère aléatoire de En-têtes de bloc Bitcoin directement ou de cours de clôture des actions, ce qui est plus facile à vérifier publiquement et plus difficile à contrôler complètement par une seule partie. Pourtant, des attaques subtiles existent toujours sur les deux blockchain de preuve de travail aléatoire ainsi que caractère aléatoire du cours de l'action. Avec les en-têtes de blockchain, par exemple, les mineurs peuvent choisir de retenir les blocs dont les en-têtes produisent une valeur de balise qu'ils n'aiment pas. Ou ils peuvent choisir de rompre les liens lorsque deux blocs en collision sont trouvés en fonction de leur sortie de balise préférée.

Balises aléatoires décentralisées (DRB)

Une approche naturelle des problèmes de balises centralisées consiste à concevoir un protocole cryptographique décentralisé pour produire un caractère aléatoire public. Ce problème ressemble un peu à la conception de protocoles de consensus décentralisés, mais en plus difficile. Non seulement tous les participants doivent s'entendre sur une sortie (le caractère aléatoire), mais il devrait être impossible pour un participant malveillant au protocole de biaiser ou de prédire la sortie.

Les protocoles conçus pour simuler une balise aléatoire sont appelés balises aléatoires distribuées (DRB). (D'autres noms incluent "distributed coin-flipping".) Le problème a été étudié pendant des décennies, avec célèbres résultats d'impossibilité prouvés dans les années 1980, mais l'intérêt a été ravivé à l'ère de la blockchain. Les DRB pourraient être utilisés pour fournir un caractère aléatoire en chaîne, ce qui serait un ingrédient clé pour des applications en chaîne équitables, sécurisées et transparentes.

L'approche classique : Commit-reveal protocols

Un protocole très simple en deux tours suffit pour un DRB dans le cas optimiste. Au tour 1, chaque participant i génère une valeur aléatoire r_i et publie un engagement cryptographique c_i=Commettre(r_i). Dans cette application, l'engagement peut simplement être une fonction de hachage comme SHA-256. Une fois l'engagement de chaque participant publié, il est verrouillé sur son choix de r_i, mais les engagements ne révèlent aucune information sur les contributions des autres participants. Au tour 2, chaque participant « ouvre son engagement » en publiant r_i. Toutes les valeurs aléatoires sont ensuite combinées, par exemple en les XORant ou (de préférence) en hachant leur concaténation.

Ce protocole est simple et produit une sortie de balise aléatoire tant qu'un seul des participants choisit son r_i au hasard. Malheureusement, il souffre d'un défaut classique : lorsque tous les participants sauf un ont révélé leur valeur aléatoire, le dernier participant est capable de calculer la sortie putative de la balise. S'ils ne l'aiment pas, ils peuvent refuser de publier leur valeur, annulant ainsi le protocole. Ignorer la contribution d'un participant fautif ne résout pas le problème, car cela donne toujours à un attaquant le choix entre deux sorties de balise (une calculée avec sa contribution et une sans).

Les blockchains offrent un remède naturel à ce problème : chaque participant peut être obligé de mettre des fonds sous séquestre qui sont saisis s'ils ne révèlent pas leur contribution aléatoire. C'était exactement l'approche adoptée par le classique RANDAO balise sur Ethereum. L'inconvénient de cette approche est que la sortie peut toujours être biaisée, ce qui peut être financièrement intéressant pour l'attaquant si l'argent en séquestre est inférieur au montant d'argent circulant sur le résultat de la balise. Une meilleure sécurité contre les attaques biaisées nécessite de mettre plus de pièces sous séquestre.

Protocoles de validation-révélation-récupération

Au lieu d'essayer de forcer toutes les parties à révéler leur contribution aléatoire, certains protocoles incluent un mécanisme de récupération de sorte que même si une minorité de participants abandonne, le reste peut terminer le protocole. Il est important que le protocole produise le même résultat dans les deux cas, afin que les parties ne puissent pas biaiser le résultat en choisissant d'abandonner ou non.

Une approche pour y parvenir consiste à demander à chaque participant de fournir aux autres des parts de son secret, de sorte qu'une majorité d'entre eux puisse le reconstituer, en utilisant, par exemple, Le partage secret de Shamir. Une propriété importante, cependant, est que les autres peuvent vérifier que le secret engagé a été correctement partagé, ce qui nécessite l'utilisation d'une primitive plus forte appelée partage de secret publiquement vérifiable (PVSS).

Plusieurs autres mécanismes de récupération sont possibles, mais ils ont tous la même limitation. S'il y a N participants, et nous voulons de la résilience si un groupe de jusqu'à f nœuds abandonnent, alors il doit être le cas que n'importe quel groupe de Nf les participants peuvent calculer le résultat final. Mais cela signifie aussi une coalition malveillante de Nf les participants peuvent prédire le résultat à l'avance en simulant en privé le mécanisme de récupération. Cela peut également se produire lors du premier tour du protocole, période pendant laquelle une telle coalition pourrait modifier ses propres choix aléatoires et biaiser le résultat. 

Autrement dit, cela signifie que toute coalition de Nf les nœuds doivent inclure au moins un nœud honnête. Par simple algèbre, Nf > f, De sorte f < N/2, et ces protocoles exigent par nature une majorité honnête. Il s'agit d'une différence significative par rapport au modèle de sécurité original de validation-révélation, qui ne nécessite que f<N (au moins un participant honnête).

Ces protocoles nécessitent également souvent des coûts de communication importants pour partager les informations PVSS supplémentaires entre tous les nœuds à chaque exécution du protocole. La communauté des chercheurs a effectué un travail considérable sur ce problème au cours des dernières années, avec des propositions de recherche comprenant Partage Rand, Gratter, SecRand, HERBou Albatross, mais aucun ne semble avoir été déployé dans le monde réel.

Protocoles basés sur des fonctions aléatoires vérifiables

Réalisant qu'un groupe de Nf les participants peuvent calculer la valeur de balise aléatoire dans le protocole ci-dessus conduit à une approche un peu plus simple : partager une clé secrète à long terme entre N parties et demandez-leur de l'utiliser pour évaluer un fonction aléatoire vérifiable (VRF). La clé secrète est partagée via un t-hors de-N régime de seuil, de sorte que tout t les participants peuvent calculer le VRF (mais une plus petite coalition ne le peut pas). Pour t=Nf, cela offre la même résilience à f nœuds malveillants comme les protocoles commit-reveal-recover décrits ci-dessus.

DFINITY pionnier de cette approche dans le cadre de leur protocole de consensus utilisant des signatures BLS à seuil (qui fonctionnent comme un VRF). Le autonome dand La balise aléatoire utilise essentiellement la même approche, avec un ensemble de participants seuil-BLS-signant un compteur à chaque tour. La Ligue d'entropie est une instance open source de drand produisant un caractère aléatoire toutes les 30 secondes à l'aide de 16 nœuds participants (à partir de septembre 2022), gérée par un mélange d'entreprises et de groupes de recherche universitaires. 

Un inconvénient de ces approches est que l'initialisation de la clé de seuil est relativement complexe, tout comme la reconfiguration de la clé lorsque les nœuds rejoignent ou quittent. Dans le cas courant, cependant, les protocoles sont très efficaces. 

Comme décrit ci-dessus, la simple signature d'une valeur de compteur n'ajoute aucun nouveau caractère aléatoire par tour, donc si un nombre suffisant de clés de participants sont compromises, le protocole sera prévisible à chaque tour futur.

VRF à maillons de chaîne moissonneuses-batteuses cette approche (en utilisant le NSEC5 VRF) avec une source externe de caractère aléatoire spécifiée par les parties demandant le caractère aléatoire, généralement un en-tête de chaîne de blocs récent dans la pratique. Ces données sont ensuite transmises via un VRF qui est géré par une partie ou limité à un groupe.

Ethereum's Chaîne de balise utilise actuellement des VRF basés sur BLS : le proposant de chaque tour ajoute sa valeur VRF au mélange. Cela permet d'économiser un cycle de communication par rapport au paradigme commit-reveal (en supposant qu'une clé publique BLS à long terme est enregistrée une fois), bien que cette conception hérite de certaines mises en garde de l'approche commit-reveal, y compris la possibilité de biaiser la sortie de la balise en retenant la sortie .

Protocoles basés sur la fonction de retard vérifiable

Enfin, une nouvelle direction prometteuse consiste à utiliser la cryptographie basée sur le temps, en particulier les fonctions de retard vérifiables (VDF). Cette approche promet de fournir une bonne efficacité et robustesse de la communication avec une résilience aux N-1 nœuds malveillants. 

Pour en revenir au protocole initial de validation-révélation, les engagements traditionnels peuvent être remplacés par engagements ponctuels pour éliminer le problème des participants refusant de révéler leur contribution aléatoire. Les engagements temporisés peuvent être ouverts efficacement par le committer d'origine ou par toute personne souhaitant calculer une fonction lente (essentiellement un VDF). Ainsi, si un participant abandonne un protocole de validation-révélation, son engagement peut toujours être ouvert par d'autres. Il est essentiel que le temps minimum pour ouvrir l'engagement soit suffisamment long pour que cela ne puisse pas être fait lors du premier tour (la phase de validation) du protocole, sinon des participants malveillants pourraient ouvrir les engagements des autres assez rapidement pour modifier leur propre contribution et biaiser le résultat .

Un protocole à un tour encore plus élégant est possible avec les VDF modernes : abandonnez complètement l'engagement. Chaque participant peut simplement publier sa contribution au hasard r_i, et le résultat final est une combinaison de la contribution de chaque participant, passée par un VDF. Le retard dans le calcul du VDF garantit que personne ne peut choisir son engagement d'une manière qui biaise la sortie finale. Cette approche a été proposée comme UNICORN par Arjen Lenstra et Benjamin Wesolowski en 2015, et a en effet été une application motivante clé dans le développement de VDF.

Cette approche a connu un certain déploiement pratique. Chia implémente une version de ceci dans le cadre de son protocole de consensus, en utilisant des VDF à carrés répétés dans des groupes de classes. Starkware mis en œuvre un balise basée sur VDF de preuve de concept à l'aide de VDF basés sur SNARK. Ethereum projette aussi à utiliser cette approche, en construisant un ASIC dédié pour calculer les VDF afin de générer un caractère aléatoire au niveau de la couche consensus.

***

Le caractère aléatoire public est un élément essentiel de nombreux protocoles, mais nous manquons toujours de DRB standard offrant une sécurité élevée. L'espace de conception est vaste et de nombreux hybrides et combinaisons des approches ci-dessus sont possibles. Par exemple, il est possible de combiner un protocole basé sur VRF avec un protocole basé sur VDF, ce qui ajoute une nouvelle entropie, par exemple, comme proposé par RandRunner. La chaîne Beacon d'Ethereum utilise actuellement des VRF, bien qu'elle puisse ajouter des VDF à l'avenir pour éliminer la possibilité de biais des attaques de retenue de bloc.

C'est aussi une question ouverte lorsque les protocoles à majorité honnête sont acceptables. Pour un groupe de participants relativement restreint et contrôlé – comme la League of Entropy – une hypothèse de majorité honnête est raisonnable. D'un autre côté, les protocoles qui ne nécessitent qu'un seul participant honnête ont un avantage inhérent - plus de participants ne peuvent qu'améliorer la sécurité. Cela signifie que ces protocoles peuvent potentiellement être déployés avec une participation ouverte et sans autorisation.

Dans la partie II, nous discuterons de l'application spécifique de l'élection aléatoire des leaders dans les protocoles de consensus, qui a des objectifs de conception légèrement différents et, par conséquent, a vu encore plus de protocoles et d'approches proposés.

***

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.