Peut-on générer des nombres aléatoires si nous ne nous faisons pas confiance ? Partie 1

Salut, Habr !

Dans cet article, je vais parler 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, réaliser un générateur « presque » bon est assez simple, mais en créer un très bon est difficile.

Pourquoi générer des nombres aléatoires pour des participants qui ne se font pas confiance ? L'un des domaines d'application est celui des applications décentralisées. Par exemple, une application qui accepte une mise d'un participant et double le montant avec une probabilité de 49 %, ou le prend avec une probabilité de 51 %, ne fonctionnera que si elle peut obtenir un nombre aléatoire de manière impartiale. Si un attaquant peut influencer le résultat du générateur de nombres aléatoires et même légèrement augmenter ses chances de recevoir un paiement dans l'application, il pourra facilement la vider.

Lorsque nous développons un protocole distribué de génération de nombres aléatoires, nous voulons qu'il possède trois propriétés :

1. Il doit être impartial. En d'autres termes, aucun participant ne doit avoir d'influence sur le résultat du générateur de nombres aléatoires.

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

3. Le protocole doit être viable, c'est-à-dire résistant à ce qu'un certain pourcentage de participants se déconnecte du réseau ou tente intentionnellement d'arrêter le protocole.

Dans cet article, nous examinerons deux approches : RANDAO + VDF et une approche basée sur des codes de correction d'effacement. Dans la prochaine partie, nous détaillerons l'approche basée sur des signatures seuil.

Mais d'abord, examinons un algorithme simple et souvent utilisé qui est viable, imprévisible mais biaisé.

RANDAO

RANDAO est une approche très simple et donc assez fréquemment utilisée pour obtenir de l'aléa. Tous les participants du réseau choisissent d'abord un nombre pseudo-aléatoire localement, puis chaque participant envoie le hachage du nombre choisi. Ensuite, les participants révèlent à tour de rôle leurs nombres choisis, et effectuent une opération XOR sur les nombres révélés, le résultat de cette opération devenant le résultat du protocole.

Un pas de publication des hachages avant de révéler les nombres est nécessaire pour que l'attaquant ne puisse pas choisir son nombre après avoir vu les nombres des autres participants. Cela lui permettrait en fait de déterminer seul la sortie du générateur de nombres aléatoires.

Tout au long du protocole, les participants doivent parvenir à un consensus à deux reprises : d'abord sur le moment de révéler les nombres choisis, puis de cesser d'accepter les hachages, et ensuite sur le moment de cesser d'accepter les nombres choisis et de calculer le résultat. Prendre de telles décisions entre des participants qui ne se font pas confiance est en soi une tâche difficile, et nous y reviendrons dans de futurs articles. Dans cet article, nous supposerons qu'un tel algorithme de consensus est à notre disposition.

Quelles sont les propriétés décrites ci-dessus qui s'appliquent à RANDAO ? Il est imprévisible, possède la même viabilité que le protocole de consensus qui le sous-tend, mais il est biaisé. En particulier, un attaquant peut observer le réseau, et une fois que d'autres participants ont révélé leurs nombres, il peut calculer leur XOR et décider de révéler ou non son nombre pour influencer le résultat. Bien que cela ne permette pas à l'attaquant de déterminer seul la sortie du générateur de nombres aléatoires, cela lui donne tout de même 1 bit d'influence. Et si les attaquants contrôlent plusieurs participants, le nombre de bits qu'ils contrôlent sera égal au nombre de participants sous leur contrôle.

L'influence des attaquants peut être fortement réduite en exigeant que les participants révèlent leurs nombres dans l'ordre. Dans ce cas, l'attaquant ne pourra influencer le résultat que s'il est le dernier à se révéler. Bien que l'influence soit considérablement réduite, l'algorithme reste biaisé.

RANDAO + VDF

Une des options pour rendre RANDAO impartial est la suivante : après que tous les nombres ont été révélés et que le XOR a été calculé, le résultat est introduit dans une fonction qui prend beaucoup de temps à calculer, mais permet de vérifier la précision du calcul très rapidement.

(vdf_output, vdf_proof) = VDF_compute(input) // c'est très lent
correct = VDF_verify(input, vdf_output, vdf_proof) // c'est très rapide

Cette fonction s'appelle Verifiable Delay Function, ou VDF. Si le calcul du résultat final prend plus de temps que la phase de divulgation des nombres, un attaquant ne pourra pas prédire l'effet de la démonstration ou de la dissimulation de son nombre, et par conséquent il perdra la capacité d'influencer le résultat.

Le développement de bons VDF est extrêmement difficile. Récemment, plusieurs avancées ont été réalisées, par exemple celui-ci et celle-ci, qui ont rendu les VDF plus applicables en pratique, et Ethereum 2.0 prévoit à long terme d'utiliser RANDAO avec VDF comme source de nombres aléatoires. En plus du fait que cette approche est imprévisible et impartiale, elle a l'avantage supplémentaire d'être viable tant qu'au moins deux participants sont disponibles sur le réseau (à condition que le protocole de consensus utilisé soit viable en tenant compte d'un si petit nombre de participants).

La plus grande difficulté de cette approche réside dans la configuration d'un VDF de manière à ce qu'un participant disposant de matériel spécialisé très coûteux ne puisse pas calculer le VDF avant la fin de la phase de divulgation. Idéalement, l'algorithme devrait avoir même une marge de sécurité significative, disons 10x. La figure ci-dessous montre l'attaque d'un participant ayant un ASIC spécialisé, ce qui lui permet d'exécuter le VDF plus rapidement que le temps alloué pour la divulgation de la confirmation RANDAO. Un tel participant pourrait toujours calculer le résultat final en utilisant ou non son nombre, puis, en se basant sur les calculs, choisir de le montrer ou non.

Pour la famille de VDF mentionnée ci-dessus, la performance d'un ASIC spécialisé peut être plus de 100 fois supérieure à celle d'un équipement ordinaire. Ainsi, si la phase de divulgation dure 10 secondes, un VDF calculé sur un tel ASIC doit prendre plus de 100 secondes pour avoir une marge de sécurité de 10 fois, et donc le même VDF, calculé sur un équipement ordinaire, doit prendre 100 x 100 secondes = ~ 3 heures.

La Fondation Ethereum prévoit de résoudre ce problème en créant ses propres ASIC publics et gratuits. Dès que cela se produira, tous les autres protocoles pourront également profiter de cette technologie, mais jusqu'à ce moment-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 le VDF ont été rassemblés sur ce site.

Utilisation des codes d'effacement

Dans cette section, nous examinerons le protocole de génération de nombres aléatoires qui utilise des codes d'effacement. Il peut supporter jusqu'à ⅓ d'agresseurs tout en restant viable, et permet l'existence de jusqu'à ⅔ d'agresseurs avant qu'ils ne puissent prédire ou influencer le résultat.

L'idée principale du protocole est la suivante. Pour simplifier, supposons qu'il ait exactement 100 participants. Supposons aussi que tous les participants aient localement une certaine clé privée, et que les clés publiques de tous les participants soient connues de tous :

1. Chaque participant invente localement une longue chaîne, la divise en 67 parties, crée des codes d'effacement pour obtenir 100 parts, dont 67 suffisent pour reconstruire la chaîne, attribue chacune des 100 parts à un participant et les chiffre avec la clé publique du même participant. Ensuite, toutes les parts codées sont publiées.

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

3. Une fois le consensus atteint, chaque participant prend les parts codées dans chacun des 67 ensembles, chiffrées avec leur clé publique, déchiffre toutes ces parts et publie toutes ces parts déchiffrées.

4. Une fois que 67 participants ont exécuté 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 comme XOR des chaînes initiales dont les participants ont commencé en (1).

Il est possible de montrer que ce protocole est impartial et imprévisible. Le nombre aléatoire résultant est déterminé après l'atteinte du consensus, mais il est inconnu pour tous tant que ⅔ des participants n'ont pas décrypté les parties chiffrées avec leur clé publique. Ainsi, le nombre aléatoire est défini avant que l'information nécessaire à sa récupération ne soit publiée.

Que se passe-t-il si, à l'étape (1), l'un des participants envoie aux autres participants des parts codées qui ne constituent pas un code d'effacement correct pour une certaine chaîne ? Sans modifications supplémentaires, des participants différents ne pourront soit pas récupérer la chaîne du tout, soit récupérer des chaînes différentes, ce qui entraînera des nombres aléatoires différents pour chaque participant. Pour éviter cela, il est possible de faire ce qui suit : chaque participant, en plus des parts codées, calcule également un arbre de Merkle , toutes ces parts, et envoie à chaque participant à la fois sa part codée et la racine de l'arbre de Merkle, ainsi que la preuve de l'inclusion de la part dans l'arbre de Merkle. Au consensus à l'étape (2), les participants ne se mettent alors pas seulement d'accord sur plusieurs ensembles, mais sur plusieurs racines spécifiques de ces arbres (si un participant s'écarte du protocole et envoie différentes racines d'arbre de Merkle à différents participants, et que deux de ces racines sont montrées durant le consensus, sa chaîne n'est pas incluse dans l'ensemble résultant). À la fin du consensus, nous aurons 67 chaînes codées et leurs racines d'arbre de Merkle correspondantes, de sorte qu'il y a au moins 67 participants (pas nécessairement les mêmes qui ont proposé les chaînes correspondantes), ayant pour chacune des 67 chaînes un message avec une part de code d'effacement, et une preuve de l'inclusion de leur part dans l'arbre de Merkle correspondant.

Lorsque, à l'étape (4), un participant déchiffre 67 parts pour une certaine chaîne, et tente de reconstruire la chaîne originale à partir de celles-ci, l'une des options possibles est :

1. La chaîne est reconstruite, et si elle est ensuite codée à nouveau avec des codes d'effacement, et que l'arbre de Merkle est calculé pour les parts calculées localement, la racine correspond à celle sur laquelle le consensus a été atteint.

2. La chaîne est reconstruite, mais la racine calculée localement ne correspond pas à celle sur laquelle le consensus a été atteint.

3. La chaîne n'est pas reconstruite.

Il est facile de montrer que si au moins un participant a rencontré l'option (1), alors tous les participants rencontreront l'option (1), et inversement, si au moins un participant a rencontré l'option (2) ou (3), alors tous les participants rencontreront l'option (2) ou (3). Ainsi, pour chaque ligne dans l'ensemble, soit tous les participants parviennent à la restaurer, soit aucun participant ne peut la restaurer. Ensuite, le nombre aléatoire résultant est le XOR uniquement des lignes que les participants ont réussi à restaurer.

Signatures de seuil

Une autre approche à la randomisation consiste à utiliser ce que l'on appelle des signatures de seuil BLS. Un générateur de nombres aléatoires basé sur des signatures de seuil possède exactement les mêmes garanties que l'algorithme décrit ci-dessus basé sur des codes effaçables, mais a une asymptotique du nombre de messages échangés sur le réseau pour chaque nombre généré beaucoup plus faible.

Les signatures BLS sont une construction qui permet à plusieurs participants de créer une signature commune pour un message. De telles signatures sont souvent utilisées pour économiser de l'espace et de la bande passante, car elles ne nécessitent pas l'envoi de plusieurs signatures. 

Une application fréquente des signatures BLS dans les protocoles blockchain, en plus de la génération de nombres aléatoires, est la signature de blocs dans les protocoles BFT. Par exemple, 100 participants créent des blocs, et un bloc est considéré comme final si 67 d'entre eux le signent. Tous peuvent présenter leurs parties de la signature BLS et utiliser un certain algorithme de consensus pour convenir de 67 d'entre eux, puis les combiner en une seule signature BLS. N'importe quelles 67 (ou plus) parties peuvent être utilisées pour créer la signature finale, qui dépend des 67 signatures spécifiques qui ont été combinées et peut donc varier, mais malgré le fait qu'un choix différent de 67 participants produira une signature différente, toute signature de ce type sera une signature valide pour le bloc. Les autres participants n'ont alors qu'à recevoir et vérifier uniquement une signature par bloc, et non pas 67, 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, peu importe quelles 67 signatures (ou plus, mais pas moins) sont agrégées, la signature résultante sera identique. Cela peut être utilisé comme source d'aléa : les participants conviennent d'abord d'un certain message qu'ils signeront (cela peut être le résultat de RANDAO ou simplement le hachage du dernier bloc, en fait cela n'a pas d'importance tant que cela change à chaque fois et est consensuel), et créent une signature BLS pour celui-ci. Le résultat de la génération sera imprévisible tant que 67 participants n'auront pas fourni leurs parts, et après cela, les résultats sont déjà prédéfinis et ne peuvent pas dépendre des actions d'un participant.

Cette approche de l'aléa est viable tant qu'au moins ⅔ des participants sont en ligne et suivent le protocole, et elle est impartiale et imprévisible tant qu'au moins ⅓ des participants respectent le protocole. Il est important de noter qu'un attaquant qui contrôle plus d'un tiers mais moins des deux tiers des participants peut arrêter le protocole, mais ne peut pas prévoir ou influencer son résultat.

Les signatures de seuil en elles-mêmes sont un sujet très intéressant. Dans la deuxième partie de cet article, nous examinerons en détail comment elles fonctionnent et comment il est 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 techniques sur le blog NEAR. NEAR est un protocole blockchain et une plateforme pour le développement d'applications décentralisées mettant l'accent sur la simplicité 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, et elle peut être trouvée ici.

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

Pour suivre toutes les nouvelles en russe, vous pouvez visiter le groupe sur Telegram et dans groupe sur VKontakte., et en anglais sur le site officiel Twitter.

À bientôt !

Source : habr.com