Nombres aléatoires et réseaux décentralisés : application pratique

Introduction

«La génération de nombres aléatoires est trop importante pour être laissée au hasard»
Robert Cavyu, 1970

Cet article est consacré à l'application pratique de solutions utilisant la génération collective de nombres aléatoires dans un environnement non fiable. En résumé, il s'agit de la façon dont et pourquoi le hasard est utilisé dans les blockchains, et un peu sur la manière de distinguer un « bon » hasard d'un « mauvais ». Générer un nombre véritablement aléatoire est un problème extrêmement complexe, même sur un seul ordinateur, et a été étudié depuis longtemps par des cryptographes. Dans les réseaux décentralisés, la génération de nombres aléatoires devient encore plus difficile et cruciale.

C'est précisément dans les réseaux où les participants ne se font pas confiance que la capacité de générer un nombre aléatoire indiscutable permet de résoudre efficacement de nombreuses tâches essentielles et d'améliorer considérablement les schémas déjà existants. De plus, les jeux d'argent et les loteries ne constituent pas du tout la priorité numéro un, contrairement à ce que pourrait penser un lecteur non averti.

Génération de nombres aléatoires

Les ordinateurs ne peuvent pas générer de nombres aléatoires par eux-mêmes, ils ont besoin d'une aide externe. Un ordinateur peut obtenir une valeur aléatoire en utilisant, par exemple, les mouvements de la souris, la quantité de mémoire utilisée, les courants parasites sur les contacts du processeur et de nombreuses autres sources, appelées sources d'entropie. Ces valeurs ne sont pas complètement aléatoires, car elles se situent dans une certaine plage ou présentent un caractère prévisible de variation. Pour transformer ces chiffres en un véritable nombre aléatoire dans une plage donnée, on applique des cryptotransformations afin d'obtenir des valeurs pseudo-aléatoires uniformément distribuées à partir de valeurs d'entropie non uniformément réparties. Les valeurs obtenues sont appelées pseudo-aléatoires, car elles ne sont pas véritablement aléatoires, mais déterministiquement produites à partir de l'entropie. Tout bon algorithme cryptographique, en chiffrant des données, produit des textes chiffrés qui doivent être statistiquement indiscernables d'une séquence aléatoire, donc pour produire du hasard, on peut prendre une source d'entropie qui assure seulement une bonne unicité et imprévisibilité des valeurs même dans de petites plages ; le reste du travail de dispersion et de mélange des bits dans la valeur résultante sera pris en charge par l'algorithme de chiffrement.

Pour conclure cette brève introduction, il convient d'ajouter que la génération de nombres aléatoires même sur un seul appareil est l'un des piliers de la sécurité de nos données ; les nombres pseudo-aléatoires générés sont utilisés lors de l'établissement de connexions sécurisées dans différents réseaux, pour générer des clés cryptographiques, pour équilibrer la charge, pour le contrôle d'intégrité, et pour encore de nombreuses applications. La sécurité de nombreux protocoles dépend de la capacité à générer un hasard fiable et imprévisible provenant de l'extérieur, à le conserver et à ne pas le révéler jusqu'à l'étape suivante du protocole, sinon la sécurité sera compromise. Une attaque sur le générateur de valeurs pseudo-aléatoires est extrêmement dangereuse et met en péril tous les logiciels utilisant la génération de hasards.

Tout cela, vous devez le savoir si vous avez suivi un cours de base en cryptographie, donc continuons sur les réseaux décentralisés.

Aléatoire dans les blockchains

Tout d'abord, je vais parler des blockchains avec support des contrats intelligents, car c'est elles qui peuvent pleinement exploiter les possibilités offertes par un aléatoire de qualité irréfutable. Ensuite, pour plus de simplicité, je vais appeler cette technologie “Publicly Verifiable Random Beacons” ou PVRB. Étant donné que les blockchains sont des réseaux où les informations peuvent être vérifiées par chaque participant, une partie essentielle du nom est “Publicly Verifiable”, c'est-à-dire que quiconque peut obtenir une preuve par calcul que le nombre obtenu, stocké dans la blockchain, possède les propriétés suivantes :

• Le résultat doit avoir une distribution prouvée équitable, c'est-à-dire reposant sur une cryptographie résistante à la preuve.
• Il est impossible de contrôler l'un des bits du résultat. Par conséquent, le résultat ne peut pas être prédit à l'avance.
• Il est impossible de saboter le protocole de génération en ne participant pas au protocole ou en surchargeant le réseau avec des messages attaquants.
• Tout ce qui précède doit être résistant aux collusions d'un nombre admissible de participants malhonnêtes au protocole (par exemple 1/3 des participants).

Toute possibilité pour un groupe minoritaire collusionnaire de générer un aléatoire pair/impair contrôlé est une faille de sécurité. Toute possibilité pour un groupe de stopper la génération d'aléatoire est une faille de sécurité. En général, il y a de nombreux problèmes, et cette tâche n'est pas facile…

Il semble que l'application la plus importante pour le PVRB soit les jeux divers, les loteries, et en général tous les types de jeux d'argent sur la blockchain. En effet, c'est un domaine important, mais l'aléatoire dans les blockchains a des applications encore plus significatives. Examinons-les.

Algorithmes de consensus

Le PVRB pour l'organisation du consensus réseau joue un rôle immense. Les transactions dans les blockchains sont sécurisées par une signature électronique, donc une "attaque sur une transaction" consiste toujours à inclure ou à exclure une transaction dans un bloc (ou dans plusieurs blocs). La principale tâche de l'algorithme de consensus est de convenir de l'ordre de ces transactions et de l'ordre des blocs qui incluent ces transactions. De plus, une caractéristique nécessaire pour les blockchains réelles est la finalité — la possibilité pour le réseau de convenir que la chaîne jusqu'au bloc finalisé est définitive, et ne sera jamais exclue en raison de l'apparition d'un nouveau fork. En général, pour convenir qu'un bloc est valide et, surtout, final, il est nécessaire de recueillir des signatures de la plupart des producteurs de blocs (ci-après BP — block-producers), ce qui nécessite au minimum de transmettre la chaîne de blocs à tous les BP, et de propager les signatures entre tous les BP. Avec l'augmentation du nombre de BP, le nombre de messages nécessaires dans le réseau augmente de manière exponentielle, par conséquent, les algorithmes de consensus nécessitant la finalité, comme ceux utilisés par exemple dans le consensus pBFT de Hyperledger, ne fonctionnent pas à la vitesse requise, même avec quelques dizaines de BP, nécessitant un nombre énorme de connexions.

S'il existe un PVRB incontestable et honnête dans le réseau, même dans l'approximation la plus simple, il est possible de choisir l'un des producteurs de bloc comme "leader" durant un tour du protocole. Si nous avons N des producteurs de blocs, dont M : M > 1/2 N sont honnêtes, ne censurent pas les transactions et ne construisent pas de forks de la chaîne dans le but de mener une attaque de "double dépense", alors l'utilisation d'un PVRB incontestable uniformément distribué permettra de choisir un leader honnête avec une probabilité de M / N (M / N > 1/2)Si chaque leader se voit assigner un intervalle de temps propre pendant lequel il peut produire un bloc et valider la chaîne, et si ces intervalles sont égaux, alors la chaîne de blocs des BP honnêtes sera plus longue que celle formée par les BP malveillants. L'algorithme de consensus, qui s'appuie sur la longueur de la chaîne, rejettera simplement la "mauvaise". Ce principe d'attribution d'égales quantités de temps à chaque BP a été appliqué pour la première fois dans Graphene (prédécesseur d'EOS) et permet à la plupart des blocs d'être fermés par une seule signature, réduisant ainsi considérablement la charge réseau et permettant à ce consensus de fonctionner extrêmement rapidement et de manière stable. Cependant, les réseaux EOS doivent actuellement utiliser des blocs spéciaux (Last Irreversible Block), qui sont validés par les signatures de 2/3 des BP. Ces blocs servent à garantir la finalité (l'impossibilité d'un fork de la chaîne commençant avant le dernier Last Irreversible Block).

De plus, dans les mises en œuvre réelles, le schéma du protocole est plus complexe : les votes sur les blocs proposés se déroulent par étapes pour maintenir le fonctionnement du réseau en cas de blocage ou de problèmes réseau. Même en prenant cela en compte, les algorithmes de consensus utilisant PVRB nécessitent considérablement moins de messages entre les BP, ce qui les rend plus rapides que le PВFT traditionnel ou ses diverses modifications.

Le représentant le plus marquant de tels algorithmes est : Ouroboros de l'équipe de Cardano, qui, comme annoncé, possède une résistance mathématiquement prouvée à la collusion parmi les BP.

Dans Ouroboros, le PVRB est utilisé pour déterminer le soi-disant "BP schedule" — un calendrier selon lequel chaque BP se voit attribuer un créneau horaire pour publier un bloc. Un grand avantage de l'utilisation de PVRB est l'égalité totale des BP (selon la taille de leurs soldes). L'honnêteté du PVRB garantit que les BP malveillants ne peuvent pas contrôler le calendrier des créneaux horaires et, par conséquent, ne peuvent pas manipuler la chaîne en préparant et en analysant à l'avance les forks de la chaîne. Pour choisir un fork, il suffit de se fier à la longueur de la chaîne, sans recourir à des méthodes rusées de calcul de "l'utilité" des BP et du "poids" de leurs blocs.

Dans tous les cas où il est nécessaire de sélectionner un participant aléatoire dans un réseau décentralisé, le PVRB est presque toujours le meilleur choix, par rapport à une option déterministe basée, par exemple, sur le hachage d'un bloc. Sans PVRB, la possibilité d'influencer le choix d'un participant conduit à des attaques où l'attaquant peut, en choisissant parmi plusieurs options futures, sélectionner le prochain participant corrompu ou plusieurs d'entre eux, afin d'obtenir une part plus significative dans la prise de décision. L'utilisation du PVRB discrédite ces types d'attaques.

Mise à l'échelle et répartition de la charge

Le PVRB peut également apporter des avantages considérables dans les tâches de réduction de charge et de mise à l'échelle des paiements. Il est judicieux de commencer par examiner le document article de Rivestra « Billets de loterie électroniques en tant que micropaiements ». L'idée générale est que, au lieu de faire 100 paiements de 1 centime du payeur au bénéficiaire, on peut jouer à une loterie équitable avec un prix de 1 $ = 100 centimes, où le payeur, pour chaque paiement de 1 centime, transmet à la banque l'un de ses 100 « billets de loterie ». Un de ces billets rapporte 1 $ à la banque, et c'est ce billet que le bénéficiaire peut enregistrer sur la blockchain. L'aspect le plus important est que les 99 autres billets sont transférés entre le bénéficiaire et le payeur sans aucune intervention externe, par un canal privé et à la vitesse souhaitée. Une bonne description du protocole basé sur ce schéma dans le réseau Emercoin peut être lue ici.

Ce schéma présente plusieurs problèmes, par exemple, le bénéficiaire peut cesser de servir le payeur immédiatement après avoir reçu le billet gagnant, mais pour de nombreuses applications particulières, telles que la facturation à la minute ou les abonnements électroniques à des services, ces problèmes peuvent être ignorés. La principale exigence est bien sûr l'honnêteté de la loterie, et pour cela, le PVRB est absolument nécessaire.

Le choix d'un participant aléatoire est également crucial pour les protocoles de sharding, dont l'objectif est l'évolutivité horizontale de la chaîne de blocs, permettant à différents BP de traiter uniquement leur champ de transactions. C'est une tâche extrêmement complexe, notamment en ce qui concerne la sécurité lors de la fusion des shards. Le choix honnête d'un BP aléatoire pour désigner le responsable d'un shard spécifique, tout comme dans les algorithmes de consensus, constitue également un défi pour le PVRB. Dans les systèmes centralisés, les shards sont attribués par un équilibreur, qui calcule simplement le hash de la demande et l'envoie au destinataire approprié. Dans les blockchains, la possibilité d'influencer cette attribution peut conduire à une attaque contre le consensus. Par exemple, le contenu des transactions peut être contrôlé par un attaquant, qui peut décider quelles transactions sont intégrées dans le shard qu'il contrôle et manipuler la chaîne de blocs à l'intérieur. Vous pouvez lire la discussion sur le problème de l'utilisation des nombres aléatoires pour les tâches de sharding dans Ethereum. ici
Le sharding est l'une des tâches les plus ambitieuses et sérieuses dans le domaine de la blockchain, et sa résolution permettra de construire des réseaux décentralisés d'une performance et d'une capacité fantastiques. Le PVRB n'est qu'un des blocs importants pour sa résolution.

Jeux, protocoles économiques, arbitrage

Le rôle des nombres aléatoires dans l'industrie du jeu est difficile à surestimer. Leur utilisation explicite dans les casinos en ligne, ainsi que leur utilisation implicite lors du calcul des effets des actions des joueurs, pose des problèmes complexes pour les réseaux décentralisés, où il n'est pas possible de se fier à une source centrale de hasard. Cependant, le choix aléatoire peut également résoudre de nombreux problèmes économiques et aider à construire des protocoles plus simples et plus efficaces. Supposons que notre protocole soit confronté à des litiges concernant le paiement de certains services peu coûteux, et que ces litiges surviennent relativement rarement. Dans ce cas, s'il existe un PVRB incontestable, les clients et les vendeurs peuvent convenir de résoudre aléatoirement les litiges avec une probabilité donnée. Par exemple, avec une probabilité de 60 %, le client l'emporte et avec une probabilité de 40 %, le vendeur. Cette approche, qui peut sembler absurde au premier abord, permet de résoudre automatiquement les litiges avec des taux de victoire/perte précisés, satisfaisant les deux parties sans avoir besoin d'un tiers et en économisant du temps. De plus, le rapport des probabilités peut être dynamique et dépendre de certaines variables globales. Par exemple, si l'entreprise se porte bien, observant un faible nombre de litiges et une haute rentabilité, elle peut automatiquement ajuster la probabilité de résolution des litiges en faveur des clients, par exemple à 70/30 ou 80/20, et inversement, si les litiges coûtent cher et sont frauduleux ou inappropriés, elle peut déplacer la probabilité dans l'autre sens.

De nombreux protocoles décentralisés intéressants, tels que les registres de jetons organisés par des utilisateurs, les marchés prédictifs, les courbes de bonification et bien d'autres, constituent des jeux économiques où un bon comportement est récompensé et un mauvais est puni. Ces systèmes rencontrent souvent des problèmes de sécurité, dont la protection s'oppose les uns aux autres. Ce qui est protégé contre l'attaque des "baleines" possédant des milliards de jetons ("big stake") est vulnérable aux attaques menées par des milliers de comptes avec de petits soldes ("sybil stake"), et les mesures prises contre une attaque, telles que les frais non linéaires conçus pour rendre le travail d'un grand stake non rentable, sont généralement discréditées par une autre attaque. Étant donné qu'il s'agit d'un jeu économique, les poids statistiques correspondants peuvent être calculés à l'avance et il suffit de remplacer les frais par des frais randomisés avec une distribution adéquate. De tels frais probabilistes sont réalisés extrêmement simplement, si la blockchain dispose d'une source de randomisation fiable et ne nécessitent aucun calcul complexe, compliquant la vie tant pour les baleines que pour les sybils.
Il est également important de se rappeler que le contrôle d'un seul bit dans cette randomisation permet de manipuler, en augmentant ou diminuant les probabilités de moitié, si un PVRB honnête est une composante essentielle de tels protocoles.

Où trouver un bon aléa ?

En théorie, un tirage au sort équitable dans des réseaux décentralisés peut garantir une sécurité démontrable presque pour n'importe quel protocole contre les collusions. La justification est assez simple : si le réseau s'accorde sur un bit de 0 ou 1, et que moins de la moitié des participants sont malhonnêtes, alors, avec un nombre suffisant d'itérations, le réseau arrivera à un consensus sur ce bit avec une probabilité fixe. Tout simplement parce qu'un aléa honnête choisira 51 des 100 participants dans 51 % des cas. Mais c'est dans la théorie, car dans les réseaux réels, pour garantir un tel niveau de sécurité, comme dans les articles, un grand nombre de messages entre les hôtes est nécessaire, une cryptographie complexe à plusieurs niveaux, et toute complication du protocole ajoute immédiatement de nouveaux vecteurs d'attaque.
C'est pourquoi nous ne voyons pas encore de PVRB durable dans les blockchains, qui ait été utilisé suffisamment longtemps pour passer les tests d'applications réelles, d'audits multiples, de charges de travail, et bien sûr, d'attaques réelles, sans lesquelles il est difficile de qualifier le produit de véritablement sécurisé.

Cependant, il existe plusieurs approches prometteuses, qui se distinguent par de nombreux détails, et l'une d'entre elles résoudra certainement le problème. Avec les ressources informatiques modernes, la théorie cryptographique peut être habilement transformée en applications pratiques. Plus tard, nous serons ravis de parler des implementations de PVRB : il en existe actuellement plusieurs, chacune ayant son propre ensemble de propriétés et de caractéristiques de mise en œuvre, et chacune reposant sur une bonne idée. Peu d'équipes travaillent sur les générateurs de nombres aléatoires, et l'expérience de chacune d'elles est extrêmement précieuse pour toutes les autres. Nous espérons que nos informations permettront aux autres équipes d'avancer plus rapidement, en tenant compte de l'expérience des prédécesseurs.

Source : habr.com