Nombres aléatoires et réseaux décentralisés : applications pratiques

introduction

« La génération de nombres aléatoires est trop importante pour être laissée au hasard. »
Robert Cavé, 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 sur la façon de distinguer le « bon » hasard du « mauvais ». Générer un nombre véritablement aléatoire est un problème extrêmement difficile, même sur un seul ordinateur, 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 indiscutable nous permet de résoudre efficacement de nombreux problèmes critiques et d'améliorer considérablement les systèmes existants. De plus, les jeux de hasard et les loteries ne sont pas ici l’objectif numéro un, comme cela peut paraître au premier abord au lecteur inexpérimenté.

Génération de nombres aléatoires

Les ordinateurs ne peuvent pas générer eux-mêmes des nombres aléatoires ; ils ont besoin d’une aide extérieure pour ce faire. L'ordinateur peut obtenir des valeurs aléatoires, par exemple à partir des mouvements de la souris, de la quantité de mémoire utilisée, des courants vagabonds sur les broches du processeur et de nombreuses autres sources appelées sources d'entropie. Ces valeurs elles-mêmes ne sont pas complètement aléatoires, car elles se situent dans une certaine plage ou présentent un modèle de changement prévisible. Pour transformer de tels nombres en un nombre véritablement aléatoire dans une plage donnée, des cryptotransformations leur sont appliquées pour produire des valeurs pseudo-aléatoires uniformément distribuées à partir des valeurs inégalement distribuées de la source d'entropie. Les valeurs résultantes 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, lors du chiffrement de données, produit des textes chiffrés qui devraient être statistiquement impossibles à distinguer d'une séquence aléatoire. Ainsi, pour produire du caractère aléatoire, vous pouvez prendre une source d'entropie, qui ne fournit qu'une bonne répétabilité et une imprévisibilité des valeurs, même dans de petites plages, le le reste du travail consiste à disperser et à mélanger les bits. La valeur résultante sera reprise par l'algorithme de cryptage.

Pour compléter un bref programme éducatif, j'ajouterai que la génération de nombres aléatoires même sur un seul appareil est l'un des piliers pour assurer 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 divers réseaux, pour générer clés cryptographiques, pour l'équilibrage de charge, la surveillance de l'intégrité et pour bien d'autres applications. La sécurité de nombreux protocoles dépend de la capacité à générer un aléatoire fiable et imprévisible de l’extérieur, à le stocker et à ne le révéler qu’à l’étape suivante du protocole, sinon la sécurité sera compromise. Une attaque contre un générateur de valeurs pseudo-aléatoires est extrêmement dangereuse et menace immédiatement tous les logiciels utilisant la génération aléatoire.

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

Aléatoire dans les blockchains

Tout d’abord, je parlerai des blockchains prenant en charge les contrats intelligents : ce sont elles qui peuvent pleinement profiter des opportunités offertes par un hasard indéniable et de haute qualité. De plus, par souci de concision, j'appellerai cette technologie «Balises aléatoires publiquement vérifiables» ou PVRB. Puisque les blockchains sont des réseaux dans lesquels les informations peuvent être vérifiées par n'importe quel participant, la partie clé du nom est « Publicly Verifiable », c'est-à-dire N'importe qui peut utiliser des calculs pour obtenir la preuve que le nombre résultant affiché sur la blockchain possède les propriétés suivantes :

• Le résultat doit avoir une distribution dont il est prouvé qu'elle est uniforme, c'est-à-dire être basé sur une cryptographie dont la solidité est prouvée.
• Il n'est possible de contrôler aucun des bits du résultat. En conséquence, l’issue ne peut être prédite à 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 doit résister à la collusion d'un nombre autorisé de participants malhonnêtes au protocole (par exemple, 1/3 des participants).

Toute possibilité de collusion entre un groupe mineur de participants pour produire même un hasard pair/impair contrôlé est une faille de sécurité. Toute capacité du groupe à arrêter l’émission de données aléatoires constitue une faille de sécurité. En général, les problèmes sont nombreux et cette tâche n'est pas facile...

Il semble que l’application la plus importante du PVRB concerne divers jeux, loteries et généralement tout type de jeu sur la blockchain. Il s’agit en effet d’une direction importante, mais le caractère aléatoire des blockchains a des applications encore plus importantes. Regardons-les.

Algorithmes de consensus

PVRB joue un rôle énorme dans l’organisation du consensus du réseau. Les transactions dans les blockchains sont protégées par une signature électronique, donc une « attaque sur une transaction » est toujours l'inclusion/exclusion d'une transaction dans un bloc (ou plusieurs blocs). Et la tâche principale de l'algorithme de consensus est de se mettre d'accord sur l'ordre de ces transactions et sur l'ordre des blocs qui incluent ces transactions. En outre, une propriété nécessaire pour les véritables blockchains est la finalité - la capacité du réseau à 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. Habituellement, pour convenir qu'un bloc est valide et, surtout, définitif, il est nécessaire de recueillir les signatures de la majorité des producteurs de blocs (ci-après dénommés BP - producteurs de blocs), ce qui nécessite au moins de livrer la chaîne de blocs. à tous les BP, et distribuer les signatures entre tous les BP. À mesure que le nombre de BP augmente, le nombre de messages nécessaires dans le réseau augmente de façon exponentielle. Par conséquent, les algorithmes de consensus exigeant une finalité, utilisés par exemple dans le consensus Hyperledger pBFT, ne fonctionnent pas à la vitesse requise, à partir de plusieurs dizaines de BP, nécessitant un grand nombre de connexions.

S'il existe un PVRB indéniable et honnête dans le réseau, alors, même dans l'approximation la plus simple, on peut choisir sur cette base l'un des producteurs de blocs et le nommer « leader » au cours d'un tour du protocole. Si nous avons N producteurs de blocs, dont M: M > 1/2 N sont honnêtes, ne censurent pas les transactions et ne bifurquent pas la chaîne pour mener une attaque de « double dépense », alors l'utilisation d'un PVRB uniformément distribué et incontesté 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 que ces intervalles sont égaux dans le temps, alors la chaîne de blocs des BP honnêtes sera plus longue que la chaîne formée par les BP malveillants, et le consensus L’algorithme s’appuie sur la longueur de la chaîne et éliminera simplement la « mauvaise ». Ce principe d'attribution 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, le réseau EOS doit désormais utiliser des blocs spéciaux (Last Irreversible Block), confirmés par les signatures des 2/3 BP. Ces blocs servent à assurer la finalité (impossibilité d'une fourche de chaîne démarrant avant le 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 s'effectue en plusieurs étapes pour maintenir le réseau en cas de blocs manquants et de problèmes avec le réseau, mais même en tenant compte de cela, les algorithmes de consensus utilisant PVRB nécessitent beaucoup moins de messages entre BP, ce qui permet de les rendre plus rapides que le PVFT traditionnel, ou ses diverses modifications.

Le représentant le plus éminent de ces algorithmes : Ouroboros de l’équipe Cardano, qui serait mathématiquement prouvable contre la collusion de BP.

Dans Ouroboros, PVRB est utilisé pour définir ce que l'on appelle le « planning BP » - un planning 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 l’« égalité » complète des BP (selon la taille de leurs bilans). L'intégrité du PVRB garantit que les BP malveillants ne peuvent pas contrôler la planification des plages 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 fourchette, il suffit simplement de se fier à la longueur de la chaîne. chaîne, sans recourir à des méthodes astucieuses pour calculer « l’utilité » de BP et le « poids » de ses blocs.

En général, dans tous les cas où un participant aléatoire doit être choisi dans un réseau décentralisé, le 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 d'un participant conduit à des attaques dans lesquelles l'attaquant peut choisir parmi plusieurs futurs pour choisir le prochain participant corrompu ou plusieurs à la fois pour s'assurer d'une plus grande part dans la décision. L’utilisation du PVRB discrédite ce type d’attaques.

Mise à l'échelle et équilibrage de charge

Le PVRB peut également s’avérer très utile dans des tâches telles que la réduction de la charge et la mise à l’échelle des paiements. Pour commencer, il est logique de se familiariser avec article Rivesta « Billets de loterie électroniques comme micropaiements ». L'idée générale est qu'au lieu d'effectuer des paiements de 100 1c du payeur au destinataire, vous pouvez jouer à une loterie honnête avec un prix de 1$ = 100c, où le payeur donne à la banque un de 1 de ses « billets de loterie » pour chacun. Paiement 100c. L’un de ces tickets remporte un pot de 1$, et c’est ce ticket que le destinataire peut enregistrer dans la blockchain. Le plus important est que les 99 tickets restants soient transférés entre le destinataire et le payeur sans aucune participation extérieure, via un canal privé et à la vitesse souhaitée. Une bonne description du protocole basé sur ce schéma sur le réseau Emercoin peut être lue ici.

Ce système présente quelques problèmes, par exemple le destinataire peut cesser de servir le payeur immédiatement après avoir reçu un ticket gagnant, mais pour de nombreuses applications spéciales, telles que la facturation à la minute ou les abonnements électroniques à des services, celles-ci peuvent être négligées. La principale exigence, bien entendu, est l’équité de la loterie, et pour sa mise en œuvre, un PVRB est absolument nécessaire.

Le choix d'un participant aléatoire est également extrêmement important pour les protocoles de sharding, dont le but est de faire évoluer horizontalement la chaîne de blocs, permettant aux différents BP de traiter uniquement leur périmètre de transactions. Il s'agit d'une tâche extrêmement difficile, notamment en termes de sécurité lors de la fusion de fragments. La sélection équitable d'un BP aléatoire dans le but d'affecter les responsables d'un fragment spécifique, comme dans les algorithmes de consensus, est également la tâche du PVRB. Dans les systèmes centralisés, les fragments sont attribués par un équilibreur ; il calcule simplement le hachage de la requête et l'envoie à l'exécuteur requis. Dans les blockchains, la capacité d’influencer cette mission peut conduire à une attaque contre le consensus. Par exemple, le contenu des transactions peut être contrôlé par un attaquant, il peut contrôler quelles transactions vont vers le fragment qu'il contrôle et manipuler la chaîne de blocs qu'il contient. Vous pouvez lire une discussion sur le problème de l'utilisation de nombres aléatoires pour les tâches de partitionnement dans Ethereum. ici
Le Sharding est l’un des problèmes les plus ambitieux et les plus sérieux dans le domaine de la blockchain ; sa solution permettra de construire des réseaux décentralisés d’une performance et d’un volume fantastiques. Le PVRB n’est que l’un des blocs importants pour le résoudre.

Jeux, protocoles économiques, arbitrage

Le rôle des nombres aléatoires dans l’industrie du jeu ne peut guère être surestimé. L’utilisation explicite dans les casinos en ligne et l’utilisation implicite lors du calcul des effets de l’action d’un joueur sont autant de problèmes extrêmement difficiles pour les réseaux décentralisés, où il n’existe aucun moyen de s’appuyer sur une source centrale de hasard. Mais la sélection aléatoire peut également résoudre de nombreux problèmes économiques et contribuer à l’élaboration de protocoles plus simples et plus efficaces. Supposons que dans notre protocole il y ait des litiges concernant le paiement de certains services peu coûteux, et que ces litiges se produisent assez rarement. Dans ce cas, s'il existe un PVRB incontesté, les clients et les vendeurs peuvent convenir de résoudre les litiges de manière aléatoire, 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. Cette approche, absurde du premier point de vue, permet de résoudre automatiquement les litiges avec une part de gains/pertes précisément prévisible, qui convient aux deux parties, sans aucune participation d'un tiers et sans 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, 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 orientation client, par exemple 70/30 ou 80/20, et vice versa, si les litiges coûtent beaucoup d’argent et sont frauduleux ou inadéquats, vous pouvez faire basculer la probabilité dans l’autre sens.

Un grand nombre de protocoles décentralisés intéressants, tels que les registres de jetons, les marchés de prédiction, les courbes de liaison et bien d'autres, sont des jeux économiques dans lesquels les bons comportements sont récompensés et les mauvais comportements sont pénalisés. Ils contiennent souvent des problèmes de sécurité pour lesquels les protections entrent en conflit les unes avec les autres. Ce qui est protégé contre une attaque par des « baleines » avec des milliards de tokens (« big Stake ») est vulnérable aux attaques de milliers de comptes avec de petits soldes (« sybil Stake ») et aux mesures prises contre une seule attaque, comme la non-attaque. Les frais linéaires créés pour rendre non rentable le travail avec un enjeu important sont généralement discrédités par une autre attaque. Puisqu'il s'agit d'un jeu économique, les poids statistiques correspondants peuvent être calculés à l'avance, et simplement remplacer les commissions par des commissions aléatoires avec la répartition appropriée. De telles commissions probabilistes sont mises en œuvre de manière extrêmement simple si la blockchain dispose d'une source fiable d'aléatoire et ne nécessite aucun calcul complexe, rendant la vie difficile tant aux baleines qu'aux sybils.
Dans le même temps, il est nécessaire de continuer à se rappeler que le contrôle d'un seul bit dans ce caractère aléatoire vous permet de tricher, en réduisant et en augmentant les probabilités de moitié, donc un PVRB honnête est l'élément le plus important de tels protocoles.

Où trouver le bon aléatoire ?

En théorie, une sélection aléatoire équitable dans les réseaux décentralisés garantit que presque tous les protocoles sont protégés contre la collusion. La logique est assez simple : si le réseau s'accorde sur un seul bit 0 ou 1 et que moins de la moitié des participants sont malhonnêtes, alors, avec suffisamment d'itérations, le réseau est assuré d'atteindre un consensus sur ce bit avec une probabilité fixe. Tout simplement parce qu’un tirage au sort honnête sélectionnera 51 participants sur 100 dans 51 % des cas. Mais c'est en théorie, parce que... dans les réseaux réels, pour assurer un tel niveau de sécurité que dans les articles, de nombreux messages entre hôtes, une cryptographie multi-passes complexe sont nécessaires, et toute complication du protocole ajoute immédiatement de nouveaux vecteurs d'attaque.
C'est pourquoi nous ne voyons pas encore de PVRB résistant et éprouvé dans les blockchains, qui aurait été utilisé pendant suffisamment de temps pour être testé par des applications réelles, de multiples audits, des charges et, bien sûr, de véritables attaques, sans lesquelles il est difficile d'appeler un PVRB. produit vraiment sûr.

Cependant, il existe plusieurs approches prometteuses, elles diffèrent sur 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 intelligemment traduite en applications pratiques. À l'avenir, nous serons heureux de parler des implémentations de PVRB : il y en a maintenant plusieurs, chacune a son propre ensemble de propriétés importantes et de fonctionnalités d'implémentation, et derrière chacune se cache une bonne idée. Il n'y a pas beaucoup d'équipes impliquées dans la randomisation et l'expérience de chacune d'entre elles est extrêmement importante pour tous les autres. Nous espérons que nos informations permettront à d'autres équipes d'avancer plus rapidement, en tenant compte de l'expérience de leurs prédécesseurs.

Source: habr.com