Est-il possible de générer des nombres aléatoires si nous ne nous faisons pas confiance ? Partie 1

Hé Habr !

Dans cet article, je parlerai de la génération de nombres pseudo-aléatoires par des participants qui ne se font pas confiance. Comme nous le verrons ci-dessous, mettre en œuvre un « presque » bon générateur est assez simple, mais un très bon générateur est difficile.

Pourquoi serait-il nécessaire de générer des nombres aléatoires parmi des participants qui ne se font pas confiance ? Un domaine d’application concerne les applications décentralisées. Par exemple, une application qui accepte un pari d'un participant et double le montant avec une probabilité de 49 % ou l'enlève avec une probabilité de 51 % ne fonctionnera que si elle peut recevoir de manière impartiale un nombre aléatoire. Si un attaquant peut influencer le résultat du générateur de nombres aléatoires, et même augmenter légèrement ses chances de recevoir un paiement dans l'application, il la dévastera facilement.

Lorsque nous concevons un protocole de génération de nombres aléatoires distribués, nous souhaitons qu'il ait trois propriétés :

1. Il doit être impartial. En d’autres termes, aucun participant ne doit influencer de quelque manière que ce soit le résultat du générateur de nombres aléatoires.

2. Il doit être imprévisible. En d’autres termes, aucun participant ne devrait être capable de prédire quel nombre sera généré (ou de déduire l’une de ses propriétés) avant qu’il ne soit généré.

3. Le protocole doit être viable, c'est-à-dire résistant au fait qu'un certain pourcentage de participants se déconnectent du réseau ou tentent délibérément d'arrêter le protocole.

Dans cet article, nous examinerons deux approches : RANDAO + VDF et l'approche des codes d'effacement. Dans la partie suivante, nous examinerons en détail l’approche basée sur les signatures à seuil.

Mais d’abord, examinons un algorithme simple et couramment utilisé, viable, imprévisible, mais biaisé.

RANDAO

RANDAO est une approche très simple et donc assez couramment utilisée pour générer du hasard. Tous les participants au réseau sélectionnent d'abord localement un numéro pseudo-aléatoire, puis chaque participant envoie un hachage du numéro sélectionné. Ensuite, les participants révèlent à tour de rôle les numéros choisis et effectuent une opération XOR sur les numéros révélés, et le résultat de cette opération devient le résultat du protocole.

L'étape de publication des hachages avant de révéler les numéros est nécessaire pour que l'attaquant ne puisse pas choisir son numéro après avoir vu les numéros des autres participants. Cela lui permettrait de déterminer pratiquement à lui seul le résultat du générateur de nombres aléatoires.

Au cours du protocole, les participants doivent parvenir à une décision commune (appelée consensus) à deux reprises : quand commencer à révéler les nombres sélectionnés, et donc arrêter d'accepter les hachages, et quand arrêter d'accepter les nombres sélectionnés et de calculer le résultat aléatoire. nombre. Prendre de telles décisions entre des participants qui ne se font pas confiance n'est pas une tâche facile en soi, et nous y reviendrons dans les prochains articles ; dans cet article nous supposerons qu'un tel algorithme de consensus est à notre disposition.

Parmi les propriétés décrites ci-dessus, lesquelles possèdent RANDAO ? Il est imprévisible, a la même vitalité que le protocole de consensus sous-jacent, mais il est biaisé. Plus précisément, un attaquant peut observer le réseau et, après que les autres participants ont révélé leurs numéros, il peut calculer leur XOR et décider de révéler ou non son numéro pour influencer le résultat. Même si cela empêche l'attaquant de déterminer à lui seul le résultat du générateur de nombres aléatoires, cela lui donne quand même 1 bit d'influence. Et si les attaquants contrôlent plusieurs participants, alors le nombre de bits qu'ils contrôlent sera égal au nombre de participants sous leur contrôle.

L’influence des attaquants peut être considérablement réduite en exigeant que les participants révèlent les numéros dans l’ordre. L'attaquant ne pourra alors influencer le résultat que s'il est ouvert en dernier. Bien que l’influence soit nettement moindre, l’algorithme reste biaisé.

RANDAO+VDF

Une façon de rendre RANDAO impartial est la suivante : une fois que tous les nombres sont révélés et que le XOR est calculé, son résultat est introduit dans l'entrée d'une fonction, ce qui prend très longtemps à calculer, mais vous permet de vérifier l'exactitude du calcul très rapidement.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Cette fonction est appelée Verifiable Delay Function, ou VDF. Si le calcul du résultat final prend plus de temps que l'étape de divulgation du numéro, alors l'attaquant ne sera pas en mesure de prédire l'effet de l'affichage ou du masquage de son numéro et perdra donc la possibilité d'influencer le résultat.

Développer de bons VDF est extrêmement difficile. Il y a eu plusieurs percées récemment, par ex. cette и celui-ci ce qui a rendu VDF plus pratique dans la pratique, et Ethereum 2.0 prévoit d'utiliser RANDAO avec VDF comme source de nombres aléatoires à long terme. Outre le fait que cette approche est imprévisible et impartiale, elle présente l'avantage supplémentaire d'être viable si au moins deux participants sont disponibles sur le réseau (en supposant que le protocole de consensus utilisé soit viable lorsqu'il s'agit d'un si petit nombre de participants).

Le plus grand défi de cette approche est de configurer le VDF de telle sorte que même un participant disposant d'un matériel spécialisé très coûteux ne sera pas en mesure de calculer le VDF avant la fin de la phase de découverte. Idéalement, l’algorithme devrait même avoir une marge de sécurité importante, disons 10x. La figure ci-dessous montre une attaque par un acteur disposant d'un ASIC spécialisé qui lui permet d'exécuter un VDF plus rapidement que le temps imparti pour révéler la confirmation RANDAO. Un tel participant peut toujours calculer le résultat final en utilisant ou non son numéro, puis, en fonction du calcul, choisir de l'afficher ou non.

Pour la famille VDF mentionnée ci-dessus, les performances d'un ASIC dédié peuvent être 100 fois supérieures à celles du matériel conventionnel. Ainsi, si la phase de déploiement dure 10 secondes, alors le VDF calculé sur un tel ASIC doit prendre plus de 100 secondes pour avoir une marge de sécurité de 10x, et donc le même VDF calculé sur du matériel standard doit prendre 100x 100 secondes = ~ 3 heures.

La Fondation Ethereum prévoit de résoudre ce problème en créant ses propres ASIC gratuits et accessibles au public. Une fois que cela se produira, tous les autres protocoles pourront également profiter de cette technologie, mais d’ici là, l’approche RANDAO+VDF ne sera pas aussi viable pour les protocoles qui ne peuvent pas investir dans le développement de leurs propres ASIC.

De nombreux articles, vidéos et autres informations sur VDF ont été collectés sur ce site.

Nous utilisons des codes d'effacement

Dans cette section, nous examinerons un protocole de génération de nombres aléatoires qui utilise effacer des codes. Il peut tolérer jusqu’à ⅓ des attaquants tout en restant viable, et permet à jusqu’à ⅔ des attaquants d’exister avant de pouvoir prédire ou influencer le résultat.

L'idée principale du protocole est la suivante. Pour simplifier, supposons qu'il y ait exactement 100 participants. Supposons également que tous les participants localement possèdent une clé privée et que les clés publiques de tous les participants sont connues de tous les participants :

1. Chaque participant propose localement une longue chaîne, la divise en 67 parties, crée des codes d'effacement pour obtenir 100 partages de telle sorte que 67 suffisent pour récupérer la chaîne, attribue chacun des 100 partages à l'un des participants et les crypte avec la clé publique du même participant. Tous les partages codés sont ensuite publiés.

2. Les participants utilisent une sorte de consensus pour parvenir à un accord sur des ensembles codés de 67 participants spécifiques.

3. Une fois le consensus atteint, chaque participant prend les partages codés dans chacun des 67 ensembles chiffrés avec sa clé publique, déchiffre tous ces partages et publie tous ces partages décryptés.

4. Une fois que 67 participants ont terminé l'étape (3), tous les ensembles convenus peuvent être complètement décodés et reconstruits grâce aux propriétés des codes d'effacement, et le nombre final peut être obtenu sous forme d'un XOR des lignes initiales avec lesquelles les participants ont commencé en (1) .

Ce protocole peut s’avérer impartial et imprévisible. Le nombre aléatoire résultant est déterminé une fois le consensus atteint, mais n'est connu de personne jusqu'à ce que les ⅔ des participants décodent les parties cryptées avec leur clé publique. Ainsi, le nombre aléatoire est déterminé avant que les informations suffisantes pour le reconstituer ne soient publiées.

Que se passe-t-il si, à l'étape (1), l'un des participants a envoyé aux autres participants des partages codés qui ne correspondent pas au code d'effacement correct pour une chaîne ? Sans modifications supplémentaires, différents participants ne pourront pas du tout récupérer la chaîne ou récupéreront des chaînes différentes, ce qui entraînera la réception par différents participants d'un nombre aléatoire différent. Pour éviter cela, vous pouvez procéder comme suit : chaque participant, en plus des partages codés, calcule également Arbre Merkla tous ces partages, et envoie à chaque participant à la fois le partage codé lui-même et la racine de l'arbre merkle, ainsi qu'une preuve de l'inclusion du partage dans l'arbre merkle. Dans le consensus de l'étape (2), les participants se mettent alors d'accord non seulement sur un ensemble d'ensembles, mais sur un ensemble de racines spécifiques de ces arbres (si un participant s'écartait du protocole et envoyait différentes racines d'arbres merkle à différents participants, et deux de ces racines sont affichées lors du consensus, la ligne n'est pas incluse dans l'ensemble de résultats). Suite au consensus, nous aurons 67 lignes codées et les racines correspondantes de l'arbre merkle de telle sorte qu'il y ait au moins 67 participants (pas nécessairement les mêmes qui ont proposé les lignes correspondantes), qui pour chacune des 67 lignes auront un message avec une part du code d'effacement, et une preuve de l'occurrence de leur part dans l'arbre correspondant effacé.

Lorsqu'à l'étape (4) le participant déchiffre 67 battements pour une certaine corde et essaie de reconstruire la corde originale à partir d'eux, l'une des options est possible :

1. La chaîne est restaurée, et si elle est ensuite à nouveau codée avec effacement et que l'arbre Merkle est calculé pour les parts calculées localement, la racine coïncide avec celle sur laquelle un consensus a été atteint.

2. La ligne est restaurée, mais la racine calculée localement ne correspond pas à celle à laquelle le consensus a été atteint.

3. La ligne n'est pas restaurée.

Il est facile de montrer que si l'option (1) s'est produite pour au moins un participant ci-dessus, alors l'option (1) s'est produite pour tous les participants, et vice versa, si l'option (2) ou (3) s'est produite pour au moins un participant, alors pour tous les participants, l'option (2) ou (3) se produira. Ainsi, pour chaque ligne de l’ensemble, soit tous les participants réussiront à la récupérer, soit tous les participants ne parviendront pas à la récupérer. Le nombre aléatoire résultant est alors un XOR des seules lignes que les participants ont pu récupérer.

Signatures de seuil

Une autre approche du caractère aléatoire consiste à utiliser ce que l’on appelle les signatures de seuil BLS. Un générateur de nombres aléatoires basé sur des signatures à seuil a exactement les mêmes garanties que l'algorithme basé sur un code d'effacement décrit ci-dessus, mais a un nombre asymptotique nettement inférieur de messages envoyés sur le réseau pour chaque nombre généré.

Les signatures BLS sont une conception qui permet à plusieurs participants de créer une signature commune pour un message. Ces signatures sont souvent utilisées pour économiser de l'espace et de la bande passante en ne nécessitant pas l'envoi de plusieurs signatures. 

Une application courante des signatures BLS dans les protocoles blockchain, en plus de générer des nombres aléatoires, est la signature de blocs dans les protocoles BFT. Disons que 100 participants créent des blocs, et qu'un bloc est considéré comme définitif si 67 d'entre eux le signent. Ils peuvent tous soumettre leurs parties de la signature BLS et utiliser un algorithme de consensus pour se mettre d’accord sur 67 d’entre elles, puis les fusionner en une seule signature BLS. 67 parties (ou plus) peuvent être utilisées pour créer la signature finale, qui dépendra des 67 signatures combinées et peut donc varier, même si les différents choix des 67 participants créeront une signature différente, une telle signature sera valide. signature du bloc. Les participants restants n'ont alors plus qu'à recevoir et vérifier une seule signature par bloc, au lieu de 67, sur le réseau, ce qui réduit considérablement la charge sur le réseau.

Il s'avère que si les clés privées utilisées par les participants sont générées d'une certaine manière, quelles que soient les 67 signatures (ou plus, mais pas moins) regroupées, la signature résultante sera la même. Cela peut être utilisé comme source d'aléatoire : les participants se mettent d'abord d'accord sur un message qu'ils signeront (cela pourrait être la sortie de RANDAO ou simplement le hachage du dernier bloc, cela n'a pas vraiment d'importance tant qu'il change à chaque fois). et est cohérent) et créez une signature BLS pour celui-ci. Le résultat de la génération sera imprévisible jusqu'à ce que 67 participants fournissent leurs pièces, et après cela, le résultat est déjà prédéterminé et ne peut dépendre des actions d'aucun participant.

Cette approche du caractère aléatoire est viable tant qu'au moins ⅔ des participants en ligne suivent le protocole, et est impartiale et imprévisible tant qu'au moins ⅓ des participants suivent le protocole. Il est important de noter qu’un attaquant qui contrôle plus d’un tiers mais moins d’un tiers des participants peut arrêter le protocole, mais ne peut pas prédire ni influencer son résultat.

Les signatures de seuil elles-mêmes constituent un sujet très intéressant. Dans la deuxième partie de l'article, nous analyserons en détail comment ils fonctionnent et comment il est exactement nécessaire de générer les clés des participants pour que les signatures de seuil puissent être utilisées comme générateur de nombres aléatoires.

En conclusion

Cet article est le premier d'une série d'articles de blog techniques NEAR. NEAR est un protocole et une plate-forme blockchain permettant de développer des applications décentralisées en mettant l'accent sur la facilité de développement et la facilité d'utilisation pour les utilisateurs finaux.

Le code du protocole est ouvert, notre implémentation est écrite en Rust, on peut la trouver ici.

Vous pouvez voir à quoi ressemble le développement de NEAR et expérimenter dans l'EDI en ligne. ici.

Vous pouvez suivre toute l'actualité en russe sur groupe de télégrammes et groupe sur VKontakte, et en anglais dans la version officielle twitter.

A très bientôt!

Source: habr.com