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

Présentation

«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 bref - comment et pourquoi le hasard est utilisé dans les blockchains, et un peu comment distinguer le «bon» du aléatoire du «mauvais». La génération d'un nombre vraiment aléatoire est un problème extrêmement difficile, même sur un ordinateur séparé, et a longtemps été étudié par les cryptographes. Eh bien, dans les réseaux décentralisés, la génération de nombres aléatoires est encore plus complexe et importante.

C'est dans les réseaux où les participants ne se font pas confiance que la capacité de générer un nombre aléatoire indéniable peut résoudre efficacement de nombreux problèmes importants et améliorer considérablement les schémas existants. De plus, les jeux de hasard et les loteries ne sont pas du tout l'objectif numéro un, comme un lecteur inexpérimenté peut sembler au premier abord.

Génération de nombres aléatoires

Les ordinateurs ne savent pas comment produire eux-mêmes des nombres aléatoires, pour cela ils ont besoin d'une aide extérieure. 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 elles-mêmes ne sont pas entièrement aléatoires, car elles se situent dans une certaine plage ou ont une nature prévisible de changements. Pour transformer ces nombres en un nombre vraiment aléatoire dans une plage donnée, des transformations cryptographiques leur sont appliquées afin d'obtenir des valeurs pseudo-aléatoires uniformément réparties à partir des valeurs inégalement réparties de la source d'entropie. Les valeurs obtenues sont appelées pseudo-aléatoires, car elles ne sont pas vraiment aléatoires, mais sont dérivées de manière déterministe de l'entropie. Tout bon algorithme cryptographique, chiffrant les données, produit des textes chiffrés qui ne devraient pas être statistiquement indiscernables d'une séquence aléatoire, donc pour la production d'aléatoire, vous pouvez prendre une source d'entropie qui ne fournit qu'une bonne répétabilité et l'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 reprise par l'algorithme de chiffrement.

Pour terminer le court programme éducatif, j'ajouterai 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 numéros pseudo-aléatoires générés sont utilisés pour établir des connexions sécurisées dans différents réseaux, pour générer des clés cryptographiques, pour équilibrer la charge, pour contrôler l'intégrité, et pour bien d'autres utilisations. La sécurité de nombreux protocoles dépend de la capacité à générer des données aléatoires fiables et imprévisibles de l'extérieur, à les enregistrer et à ne pas les ouvrir avant la prochaine étape du protocole, sinon la sécurité sera compromise. Une attaque sur un générateur de valeur pseudo-aléatoire est extrêmement dangereuse et menace tous les logiciels qui utilisent la génération aléatoire à la fois.

Vous devez savoir tout cela si vous avez suivi un cours de base de cryptographie, alors continuons avec les réseaux décentralisés.

Blockchain Random

Tout d'abord, je vais parler des blockchains avec support pour les contrats intelligents, ce sont elles qui peuvent pleinement profiter des opportunités offertes par une qualité aléatoire indéniable. De plus, par souci de concision, j'appellerai cette technologie « balises aléatoires publiquement vérifiables » ou PVRB. Étant donné que les chaînes de blocs sont des réseaux dans lesquels tout participant peut vérifier des informations, l'élément clé du nom est «publiquement vérifiable», c'est-à-dire quiconque à l'aide de calculs peut obtenir la preuve que le nombre résultant, placé sur la blockchain, a les propriétés suivantes:

• Le résultat doit avoir une distribution uniformément prouvée, c'est-à-dire basée sur une cryptographie suffisamment solide.
• Il n'est possible de contrôler aucun des bits du résultat. Par conséquent, le résultat ne peut pas être prévu à l'avance.
• Vous ne pouvez pas saboter le protocole de génération en ne participant pas au protocole ou en surchargeant le réseau avec des messages d'attaque
• Tout ce qui précède devrait être résistant à la collusion du nombre autorisé de participants malhonnêtes dans le protocole (par exemple, 1/3 des participants).

Toute possibilité pour un petit groupe de participants conspirant de produire un hasard pair / impair contrôlé est un trou de sécurité. Toute opportunité pour le groupe de cesser d'émettre une maison au hasard est un trou de sécurité. En général, les problèmes sont nombreux et cette tâche n'est pas aisée ...

Il semble que l'application la plus importante pour PVRB soit divers jeux, loteries et généralement tout type de jeu sur la blockchain. En effet, c'est une direction importante, mais la maison aléatoire dans les blockchains a des applications et plus importantes. Considérez-les.

Algorithmes de consensus

PVRB est crucial pour le consensus de réseautage. Les transactions dans les chaînes de blocs sont protégées par une signature électronique, par conséquent, «l'attaque d'une transaction» est toujours l'inclusion / exclusion d'une transaction dans un bloc (ou dans plusieurs blocs). Et la tâche principale de l'algorithme de consensus est de s'entendre sur l'ordre de ces transactions et sur l'ordre des blocs qui incluent ces transactions. En outre, une propriété nécessaire pour de vraies chaînes de blocs est la finalité - la capacité du réseau à accepter que la chaîne vers le bloc finalisé est définitive et ne sera jamais exclue en raison de l'apparition d'une nouvelle fourche. Habituellement, pour convenir qu'un bloc est valide et, surtout, définitif, vous devez collecter les signatures de la plupart des producteurs de blocs (ci-après BP - producteurs de blocs), ce qui nécessite au moins de fournir une chaîne de blocs à tous les BP et de distribuer des signatures entre tous les BP. . À mesure que le nombre de BP augmente, le nombre de messages requis sur le réseau augmente de façon exponentielle; par conséquent, les algorithmes de consensus qui nécessitent une finalité, tels que ceux utilisés dans le consensus pBFT d'Hyperledger, ne fonctionnent pas à la bonne vitesse, à partir de plusieurs dizaines de BP, nécessitant un grand nombre de connexions.

Si le réseau a un PVRB indéniable et honnête, alors, même dans l'approximation la plus simple, il est possible de sélectionner l'un des producteurs de blocs sur la base de celui-ci et de le nommer «leader» pour un tour du protocole. Si nous avons N producteurs de blocs, dont M: M > 1/2 N sont honnêtes, ne censurons pas les transactions et ne construisons pas de chaînes de fourches afin de mener une attaque de "double dépense", alors l'utilisation d'un PVRB incontestable uniformément distribué vous permettra de choisir un leader honnête avec probabilité M / N (M / N > 1/2) . Si chaque leader se voit attribuer son propre intervalle de temps pendant lequel il peut produire un bloc et valider la chaîne, et ces intervalles sont égaux dans le temps, alors la chaîne de blocs honnêtes de BP sera plus longue que la chaîne formée par le BP malveillant, et l'algorithme de consensus s'appuyant sur la longueur de la chaîne, jetez simplement le «mauvais». Ce principe d'allocation de tranches de temps égales à chaque BP a été appliqué pour la première fois dans Graphene (le prédécesseur d'EOS), et permet de fermer la plupart des blocs avec une seule signature, ce qui réduit considérablement la charge du réseau et permet à ce consensus de fonctionner extrêmement rapidement et régulièrement. Cependant, les réseaux EOS doivent désormais utiliser des blocs spéciaux (Last Irreversible Block), qui sont confirmés par 2/3 des signatures BP. Ces blocs sont utilisés pour assurer la finalité (l'impossibilité d'une chaîne de fourches commençant plus tôt que le dernier dernier bloc irréversible).

De plus, dans les implémentations réelles, le schéma de protocole est plus compliqué - le vote pour les blocs proposés est effectué en plusieurs étapes afin de maintenir le réseau en cas de saut de bloc et de problèmes de réseau, mais même dans cet esprit, les algorithmes de consensus PVRB nécessitent beaucoup moins de messages entre les BP, ce qui vous permet de les rendre plus rapides que le PBFT traditionnel, ou ses différentes modifications.

Le représentant le plus frappant de tels algorithmes: Ouroboros de l'équipe Cardano, qui, comme annoncé, a une résistance mathématiquement prouvable à la collusion entre BP.

À Ouroboros, PVRB est utilisé pour définir le soi-disant «calendrier BP» - un calendrier selon lequel chaque BP se voit attribuer son propre créneau horaire pour la publication d'un bloc. Le gros avantage de l'utilisation du PVRB est la totale «égalité des droits» de BP (selon la taille de leurs soldes). L'honnêteté PVRB garantit que les BP malveillants ne peuvent pas contrôler le calendrier des créneaux horaires, et ne peuvent donc pas manipuler la chaîne en préparant et en analysant les fourches de la chaîne à l'avance, et pour sélectionner une fourche, vous pouvez simplement vous fier à la longueur de la chaîne sans utiliser de méthodes délicates pour calculer l'utilité du BP et «Poids» de ses blocs.

En général, dans tous les cas où un participant au hasard doit être sélectionné dans un réseau décentralisé, PVRB est presque toujours le meilleur choix, plutôt qu'une option déterministe basée, par exemple, sur un hachage de bloc. Sans PVRB, la capacité d'influencer le choix du participant conduit à l'apparition d'attaques dans lesquelles l'attaquant peut, en choisissant parmi plusieurs options pour l'avenir, choisir le prochain participant corrompu ou plusieurs à la fois, afin de fournir une part plus importante dans la décision. L'utilisation de PVRB discrédite ces types d'attaques.

Mise à l'échelle et équilibrage de charge

Le PVRB peut également être très utile dans les tâches visant à réduire la charge de travail et à augmenter les paiements. Pour commencer, il est logique de lire l’ article de Rivest «Les billets de loterie électroniques en tant que micropaiements». L'essence générale est qu'au lieu d'effectuer 100 paiements de 1c du payeur au destinataire, vous pouvez jouer à une loterie honnête avec un prix de 1 $ = 100c, où le payeur transfère l'un de ses 100 «billets de loterie» à la banque pour chaque paiement en 1c. L'un de ces tickets gagne la banque 1 $, et c'est ce ticket que le destinataire peut fixer sur la blockchain. Plus important encore, les 99 billets restants sont transférés entre le destinataire et le payeur sans aucune participation externe, via 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 trouvée ici .

Ce schéma présente plusieurs problèmes, par exemple, le destinataire peut cesser de servir le payeur immédiatement après avoir reçu un billet gagnant, mais pour de nombreuses applications spéciales, telles que la facturation à la minute ou les abonnements électroniques aux services, ils peuvent être négligés. L'exigence principale, bien sûr, est l'honnêteté de la loterie, et le PVRB est absolument nécessaire pour sa tenue.

Le choix d'un participant aléatoire est également extrêmement important pour les protocoles de partage, dont le but est de mettre à l'échelle horizontalement la chaîne de blocs, permettant aux différents partenaires métier de traiter uniquement leur portée de transactions. Il s'agit d'une tâche extrêmement difficile, notamment en matière de sécurité lors de la fusion de fragments. Le choix honnête d'un BP aléatoire afin de l'attribuer aux responsables d'un fragment particulier, comme dans les algorithmes de consensus, est également une tâche PVRB. Dans les systèmes centralisés, les fragments sont attribués par l'équilibreur, il calcule simplement le hachage à partir de la demande et l'envoie à l'exécuteur nécessaire. Sur les blockchains, la capacité d'influencer cette mission peut conduire à une attaque de consensus. Par exemple, le contenu des transactions peut être contrôlé par l'attaquant, il peut contrôler quelles transactions entrent dans le fragment qu'il contrôle et manipuler la chaîne de blocs qu'il contient. Une discussion sur le problème de l'utilisation de nombres aléatoires pour les problèmes de partage dans Ethereum peut être trouvée ici.
Sharding est l'une des tâches les plus ambitieuses et les plus sérieuses dans le domaine de la blockchain, sa solution vous permettra de construire des réseaux décentralisés de performances et de volume fantastiques. PVRB n'est qu'un des blocs importants pour le résoudre.

Jeux, protocoles économiques, arbitrage

Le rôle des nombres aléatoires dans l'industrie du jeu est difficile à surestimer. L'utilisation explicite dans les casinos en ligne, et implicite dans le calcul des effets de l'action d'un joueur, sont tous des problèmes extrêmement difficiles pour les réseaux décentralisés, où il n'y a aucun moyen de s'appuyer sur une source centrale de hasard. Mais, un choix aléatoire peut résoudre de nombreux problèmes économiques et aider à construire des protocoles plus simples et plus efficaces. Supposons que dans notre protocole, il existe des différends concernant le paiement de certains services peu coûteux, et ces différends sont assez rares. Dans ce cas, s'il existe un PVRB indéniable, les clients et les vendeurs peuvent s'entendre sur une résolution aléatoire des litiges, mais avec une probabilité donnée. Par exemple, avec une probabilité de 60%, le client gagne et avec une probabilité de 40%, le vendeur gagne. Une telle approche absurde, du premier point de vue, permet de résoudre automatiquement les différends avec une part précisément prévisible de victoires / défaites, ce qui convient aux deux parties sans implication de tiers et perte de temps inutile. De plus, le rapport de probabilité peut être dynamique et dépendre de certaines variables globales. Par exemple, si une entreprise se porte bien, il y a un faible nombre de litiges et une rentabilité élevée, l'entreprise peut automatiquement déplacer la probabilité de résolution d'un litige vers une approche orientée client, par exemple 70/30 ou 80/20, et vice versa, si les litiges prennent beaucoup d'argent et sont frauduleux ou inadéquats, vous pouvez déplacer la probabilité dans l'autre sens.

Un grand nombre de protocoles décentralisés intéressants, tels que les registres à jeton, les marchés de prédiction, les courbes de liaison et bien d'autres sont des jeux économiques qui récompensent les bons comportements et les mauvais mauvais. Ils rencontrent souvent des problèmes de sécurité dont la protection se contredit. Ce qui est protégé contre une attaque par des «baleines» avec des milliards de jetons («gros enjeu») est vulnérable aux attaques de milliers de comptes avec de petits soldes («enjeu sybil»), et les mesures prises contre une attaque, telles que les commissions non linéaires créées pour pour rendre un gros steak désavantageux, ils sont généralement discrédités par une autre attaque. Puisqu'il s'agit d'un jeu économique, les pondérations statistiques correspondantes peuvent être calculées à l'avance et remplacer simplement les commissions par des commissions aléatoires avec la distribution appropriée. De telles commissions probabilistes sont mises en œuvre extrêmement simplement si la blockchain a une source fiable d'aléatoire et ne nécessite aucun calcul complexe, ce qui rend la vie difficile aux baleines et à la sybille.
Il est nécessaire de continuer à se rappeler que le contrôle d'un seul bit dans cette randomisation vous permet de tricher, de réduire et de doubler les probabilités, donc le PVRB honnête est le composant le plus important de ces protocoles.

Où trouver le bon aléatoire?

En théorie, des choix aléatoires honnêtes dans les réseaux décentralisés offrent la sécurité prouvée de presque tous les protocoles contre la collusion. La justification est assez simple - si le réseau est d'accord sur un bit 0 ou 1, et parmi les participants moins de la moitié sont malhonnêtes, alors, avec un nombre suffisant d'itérations, le réseau est assuré de parvenir à un consensus sur ce bit avec une probabilité fixe. Tout simplement parce qu'un hasard honnête choisira 51 participants sur 100 dans 51% des cas. Mais c'est en théorie, car dans les réseaux réels, pour assurer un tel niveau de sécurité que dans les articles, il nécessite beaucoup de messages entre hôtes, une cryptographie multi-passes complexe, et toute complication du protocole ajoute immédiatement de nouveaux vecteurs d'attaque.
C'est pourquoi nous ne voyons pas encore dans les blockchains un PVRB éprouvé qui aurait été utilisé suffisamment de temps pour être testé par de vraies applications, de multiples audits, des charges et bien sûr, de vraies attaques, sans lesquelles il est difficile d'appeler le produit vraiment sûr.

Néanmoins, il existe plusieurs approches prometteuses à la fois, elles diffèrent dans de nombreux détails et certaines d'entre elles résoudront certainement le problème. Avec des ressources informatiques modernes, la théorie cryptographique est capable de se transformer assez habilement en applications pratiques. À l'avenir, nous serons heureux de parler de la mise en œuvre du PVRB: il y en a plusieurs maintenant, chacun a son propre ensemble de propriétés et de fonctionnalités importantes dans la mise en œuvre, et chacun a une bonne idée. Il n'y a pas beaucoup d'équipes impliquées dans le hasard, et l'expérience de chacune d'entre elles est extrêmement importante pour tout le monde. Nous espérons que nos informations permettront aux autres équipes d'avancer plus rapidement, en tenant compte de l'expérience de leurs prédécesseurs.