Présentation

function getAbsolutelyRandomNumer() { return 4; // returns absolutely random number! } 

Comme dans le cas du concept de chiffrement cryptographique absolument sécurisé, les vrais protocoles de balises aléatoires publiquement vérifiables (ci-après PVRB) essaient seulement de se rapprocher le plus possible du schéma idéal. dans les réseaux réels sous sa forme pure, il n'est pas applicable: il faut se mettre strictement d'accord sur un bit, il doit y avoir beaucoup de tours, et tous les messages doivent être parfaitement rapides et toujours délivrés. Bien sûr, dans les réseaux réels, ce n'est pas le cas. Par conséquent, lors de la conception de PVRB pour des tâches spécifiques dans les chaînes de blocs modernes, en plus de l'impossibilité de contrôler le caractère aléatoire et la force cryptographique qui en résultent, de nombreux problèmes purement architecturaux et techniques se posent.

La blockchain elle-même est pour PVRB essentiellement un support de communication dans lequel messages = transactions. Cela vous permet d'ignorer partiellement les problèmes de réseau, la remise des messages, les problèmes de middleware - tous ces risques sont supportés par un réseau décentralisé, et sa principale valeur pour PVRB est l'incapacité de retirer ou de ruiner une transaction déjà envoyée - cela ne permet pas aux participants de refuser de participer au protocole, à moins qu'ils aient eu une attaque par consensus réussie. Ce niveau de sécurité est acceptable, donc PVRB devrait être résistant à la collusion entre les participants exactement de la même manière que la chaîne de blockchain principale. En outre, cela laisse entendre que PVRB devrait faire partie du consensus, si le réseau était d'accord sur la chaîne de blocs principale, laissez-le s'entendre en même temps sur le seul résultat aléatoire honnête. Ou, PVRB est juste un protocole autonome implémenté par un contrat intelligent qui fonctionne de manière asynchrone en ce qui concerne la blockchain et les blocs. Les deux méthodes ont leurs avantages et leurs inconvénients, et le choix entre elles est extrêmement simple.

Deux façons de mettre en œuvre PVRB

Décrivons plus en détail deux options pour implémenter PVRB: la version autonome, qui fonctionne à l'aide d'un contrat intelligent indépendant de la blockchain, et intégrée par consensus, qui est intégrée dans le protocole selon laquelle le réseau s'accorde sur une chaîne de blocs et des transactions incluses. Dans tous les cas, je garderai à l'esprit les moteurs de blockchain populaires: Ethereum, EOS, et tous similaires à eux dans la manière de placer et de traiter des contrats intelligents.

Contrat autonome

Dans ce mode de réalisation, PVRB est un contrat intelligent qui accepte les transactions de producteurs aléatoires (ci-après RP), les traite, combine les résultats et, par conséquent, donne une valeur que tout utilisateur de ce contrat peut obtenir. Cette valeur ne peut pas être stockée directement dans le contrat, mais être représentée uniquement par des données à partir desquelles une et une seule valeur du caractère aléatoire résultant peut être obtenue de manière déterministe. Dans ce schéma, les RP sont des utilisateurs de blockchain, et n'importe qui peut participer au processus de génération.

L'option de contrat autonome est bonne:

• portabilité (les contrats peuvent être glissés de la blockchain vers la blockchain)
• simplicité de mise en œuvre et de test (les contrats sont faciles à écrire et à tester)
• commodité dans la mise en œuvre de schémas économiques (il est facile de créer votre propre jeton, dont la logique sert les objectifs du PVRB)
• la possibilité d'exécuter dans les blockchains existantes

Il présente également des inconvénients:

• fortes limitations des ressources dans les calculs, le volume des transactions et le stockage (en d'autres termes, cpu / mem / io)
• restrictions sur les opérations au sein du contrat (toutes les instructions ne sont pas disponibles, il est difficile de connecter des bibliothèques externes)
• l'incapacité à organiser la messagerie plus rapidement que les transactions ne sont incluses dans la blockchain

Cette option convient à l'implémentation de PVRB, qui doit être exécuté sur un réseau existant qui ne contient pas de cryptographie complexe et ne nécessite pas un grand nombre d'interactions.

Intégré au consensus

Dans ce mode de réalisation, PVRB est implémenté dans le code de nœud de chaîne de blocs, est intégré ou fonctionne en parallèle avec l'échange de messages entre les nœuds de chaîne de blocs. Les résultats du protocole sont écrits directement dans les blocs produits et les messages de protocole sont envoyés sur le réseau p2p entre les nœuds. Étant donné que le protocole entraîne l'écriture des nombres en blocs, le réseau doit parvenir à un consensus à leur sujet. Cela signifie que les messages PVRB, ainsi que les transactions, doivent être validés par les nœuds et inclus dans des blocs afin que tout participant au réseau puisse vérifier la conformité avec le protocole PVRB. Cela nous conduit automatiquement à la décision évidente: si le réseau négocie un consensus sur le bloc et les transactions, le PVRB devrait faire partie du consensus, pas un protocole autonome. Sinon, une situation est possible où le bloc est valide du point de vue du consensus, mais le protocole PVRB n'est pas respecté et du point de vue du PVRB le bloc ne peut pas être accepté. Donc, si l'option «consensus intégré» est choisie, le PVRB devient un élément important du consensus.

Décrivant la mise en œuvre du PVRB au niveau du consensus sur le réseau, vous ne pouvez en aucun cas contourner les questions de finalité. La finalité est un mécanisme utilisé dans le consensus déterministe, un bloc de verrouillage (et une chaîne qui y mène) qui est final et ne sera jamais jeté même si une fourche parallèle apparaît. Par exemple, il n'y a pas un tel mécanisme dans Bitcoin - si vous publiez une chaîne de plus grande complexité, il en remplacera une moins complexe, quelle que soit la longueur de la chaîne. Et dans EOS, par exemple, les derniers sont les soi-disant derniers blocs irréversibles, qui apparaissent en moyenne tous les 432 blocs (12 * 21 + 12 * 15, pré-vote + pré-validation). Ce processus attend essentiellement 2/3 des signatures des producteurs de blocs (ci-après BP). Lorsque des fourches plus anciennes que la dernière LIB apparaissent, elles sont simplement jetées. Ce mécanisme vous permet de garantir que la transaction est incluse dans la blockchain et ne sera jamais pompée, quelles que soient les ressources de l'attaquant. En outre, les blocs finaux sont des blocs signés par 2/3 BP dans Hyperledger, Tendermint et d'autres consensus basés sur pBFT. En outre, un protocole pour garantir la finalité est logique de faire un complément sur le consensus, car il peut fonctionner de manière asynchrone avec la production et la publication de blocs. Voici un bon article sur la finalisation d'Ethereum.

La finalité est extrêmement importante pour les utilisateurs qui, sans elle, pourraient être victimes de l'attaque «double dépense» lorsque BP «détient» les blocs et les publie après que le réseau a «vu» une bonne transaction. S'il n'y a pas de finalité, alors la fourchette publiée remplace le bloc par la «bonne» transaction par une autre, de la «mauvaise» fourchette, dans laquelle les mêmes fonds sont transférés à l'adresse de l'attaquant. Dans le cas du PVRB, les exigences de finalité sont encore resserrées, car la construction de fourches pour PVRB signifie qu'un attaquant peut préparer plusieurs options pour une maison au hasard afin de publier la plus rentable pour lui, et limiter le temps d'une éventuelle attaque est une bonne solution.

Par conséquent, la meilleure option est de combiner PVRB et finalité dans un protocole - puis le bloc finalisé = finalisé au hasard, et c'est exactement ce que vous deviez obtenir. Désormais, les joueurs recevront un caractère aléatoire garanti en N secondes, et ils peuvent être sûrs qu'il est impossible de revenir en arrière ou de le rejouer.

L'option intégrée au consensus est bonne:

• la possibilité d'une implémentation asynchrone en ce qui concerne la production de blocs - les blocs sont produits comme d'habitude, mais en parallèle, le protocole PVRB peut fonctionner, ce qui ne rend pas chaque bloc aléatoire
• la possibilité de mettre en œuvre une cryptographie même lourde, sans les restrictions imposées aux contrats intelligents
• la possibilité d'organiser la messagerie plus rapidement que les transactions ne sont incluses dans la blockchain, par exemple, une partie du protocole peut fonctionner entre les nœuds sans diffuser de messages sur le réseau

Il présente également des inconvénients:

• difficultés de test et de développement - vous devez émuler des erreurs réseau, des nœuds manquants, des fourches dures réseau
• les erreurs d'implémentation nécessitent un réseau hard fork

Les deux méthodes de mise en œuvre de PVRB ont droit à la vie, mais la mise en œuvre de contrats intelligents dans les chaînes de blocs modernes est encore assez limitée dans les ressources informatiques, et toute transition vers une cryptographie sérieuse est souvent tout simplement impossible. Nous aurons besoin d'une cryptographie sérieuse, comme cela sera démontré plus tard. Bien que ce problème soit clairement temporaire, une cryptographie sérieuse dans les contrats est nécessaire pour résoudre de nombreux problèmes, et il apparaît progressivement (par exemple, les contrats système pour les zkSNARK dans Ethereum)

La blockchain, qui fournit un canal de messagerie de protocole transparent et fiable, le fait pour une raison. Tout protocole décentralisé doit tenir compte de la possibilité d'une attaque Sybil, toute action peut être effectuée par les forces coordonnées de nombreux comptes.Par conséquent, lors de la conception, il est nécessaire de prendre en compte les capacités des attaquants à créer un nombre arbitraire de participants au protocole agissant en collusion.

PVRB et variables de bloc.

Je n'ai pas menti quand j'ai dit que jusqu'à présent, personne n'avait implémenté un bon PVRB, vérifié par de nombreuses applications de jeu, dans les blockchains. D'où viennent donc tant d'applications de jeu dans Ethereum et EOS? Cela me surprend autant que vous, eh bien, d'où avez-vous tiré autant de nombres aléatoires «persistants» dans un environnement complètement déterministe?

La façon préférée d'obtenir au hasard dans la blockchain est de prendre une sorte d'informations «imprévisibles» dans le bloc, et en fonction de cela pour faire au hasard - il suffit de mettre en cache une ou plusieurs valeurs. Un bon article sur les problèmes de tels régimes ici . Vous pouvez prendre certaines des valeurs «imprévisibles» du bloc, par exemple, le hachage du bloc, le nombre de transactions, la complexité du réseau et d'autres valeurs inconnues à l'avance. Ensuite, mettez-les en cache, un ou plusieurs, et, en théorie, vous devriez obtenir un vrai hasard. Vous pouvez même ajouter à wihitepaper que votre schéma est «sécurisé post-quantique» (car il existe des fonctions de hachage à l'épreuve des quantiques :)).

Mais même les hachages sécurisés post-quantiques ne suffisent pas, hélas. Le secret réside dans les exigences pour PVRB, je les rappelle d'un article précédent:

1. Le résultat doit avoir une distribution uniformément prouvée, c'est-à-dire basée sur une cryptographie suffisamment solide.
2. 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.
3. 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
4. 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).

Dans ce cas, seule la condition 1 est remplie, et 2. n'est pas remplie. En hachant les valeurs imprévisibles du bloc, nous obtenons une distribution uniforme et un bon caractère aléatoire. Mais BP a au moins la capacité de «publier un bloc ou non». Ainsi, BP peut au moins choisir parmi DEUX options d'aléatoire: «la nôtre» et une qui se révélera si quelqu'un d'autre fait le blocage. BP peut «espionner» à l'avance ce qui se passe si elle publie un bloc, et décide simplement de le faire ou non. Ainsi, en jouant par exemple «impair-pair» ou «rouge / noir» à la roulette, il ne peut publier un bloc que s'il voit une victoire. Il fait également une stratégie inopérante pour utiliser, par exemple, un hachage d'un bloc du futur. Dans ce cas, ils disent que «un aléatoire sera utilisé, qui est obtenu en hachant les données actuelles et le hachage du futur bloc avec une hauteur, par exemple, N + 42, où N est la hauteur actuelle du bloc. Cela renforce un peu le schéma, mais il permet toujours à BP, bien qu'à l'avenir, de choisir, de maintenir le bloc ou de publier.

BP souple dans ce cas est compliqué, mais pas beaucoup. C'est juste que lors de la validation et de l'inclusion d'une transaction dans le bloc, une vérification rapide est effectuée pour voir s'il y aura un gain et, éventuellement, la sélection d'un paramètre de transaction afin d'obtenir une forte probabilité de gagner. Dans le même temps, attraper un BP intelligent, pour de telles manipulations est presque impossible, chaque fois que vous pouvez utiliser de nouvelles adresses, et gagner un peu, sans provoquer de soupçons.

Les méthodes utilisant les informations du bloc ne conviennent donc pas au rôle d'implémentation universelle du PVRB. Dans une version limitée, avec des restrictions sur la taille des paris, des restrictions sur le nombre de joueurs et / ou l'inscription KYC (pour empêcher un joueur d'utiliser plusieurs adresses), ces schémas peuvent fonctionner pour les petits jeux, mais rien de plus.

PVRB et validation-révélation.

D'accord, grâce au hachage et au moins à l'imprévisibilité relative du hachage de bloc et d'autres variables. Si vous résolvez le problème des mineurs de premier plan, vous devriez obtenir quelque chose de plus approprié. Ajoutons des utilisateurs à ce schéma - bien qu'ils affectent également le caractère aléatoire: toute personne du support technique vous dira que la chose la plus aléatoire dans les systèmes informatiques est les actions des utilisateurs :)

Le schéma naïf, lorsque les utilisateurs envoient simplement des nombres aléatoires et que le résultat est calculé comme, par exemple, un hachage de leur somme, ne convient pas. Dans ce cas, le dernier joueur peut choisir son propre contrôle aléatoire de ce que sera le résultat. Par conséquent, le modèle de validation-révélation très largement utilisé est utilisé. Les participants envoient d'abord des hachages à partir de leur (validation) aléatoire, puis ouvrent le (s) aléatoire (s) eux-mêmes. La phase de «révélation» ne commence qu'après la collecte de la validation nécessaire, afin que les participants puissent envoyer exactement l'aléatoire à partir duquel ils ont envoyé un hachage plus tôt. Maintenant, nous aveuglons tout cela avec les paramètres du bloc, et c'est mieux que celui pris du futur (vous ne pouvez découvrir l'aléatoire que dans l'un des futurs blocs), et le tour est joué - le hasard est prêt! Maintenant, n'importe quel joueur influence le caractère aléatoire résultant, et peut "vaincre" le BP malveillant en le bloquant avec son propre, auparavant inconnu, aléatoire ... Vous pouvez également ajouter une protection contre le sabotage du protocole en ne l'ouvrant pas au stade de la révélation - nécessitant simplement d'appliquer un certain montant à la transaction - caution d'assurance, qui sera restituée uniquement lors de la procédure de révélation. Dans ce cas, commettre et ne pas révéler sera désavantageux.

C'était une bonne tentative, et de tels schémas sont également dans les DApps de jeu, mais hélas, ce n'est pas encore suffisant. Maintenant, non seulement le mineur, mais tout participant au protocole peut influencer le résultat. Il est toujours possible de contrôler la valeur elle-même, avec un degré de variabilité moindre et pour de l'argent, mais, comme dans le cas du mineur, si les résultats du tirage sont plus précieux que les frais de participation au protocole PVRB, le producteur aléatoire (RP) peut décider de révéler ou non et peut toujours choisir parmi au moins deux options aléatoires.
Mais il y avait une possibilité de punir ceux qui commettent et ne révèlent pas, et ce schéma est toujours utile. Sa simplicité est un avantage majeur - des protocoles plus sérieux nécessitent un calcul beaucoup plus puissant.

PVRB et signatures déterministes.

Il existe un autre moyen d'obtenir qu'un RP fournisse un nombre pseudo-aléatoire qu'il ne peut pas affecter s'il est fourni avec un «prototype» - c'est une signature déterministe. Une telle signature est, par exemple, RSA et n'est pas ECS. Si RP a une paire de clés: RSA et ECC, et qu'il signe une certaine valeur avec sa clé privée, dans le cas de RSA, il obtiendra UNE ET UNE SEULE signature, et dans le cas d'ECS, il peut générer un nombre illimité de signatures valides différentes. Cela est dû au fait que lors de la création d'une signature ECS, un nombre aléatoire est utilisé, choisi par les signataires, et il peut être choisi comme souhaité, donnant au signataire la possibilité de choisir l'une des signatures. Dans le cas de RSA: «une valeur d'entrée» + «une paire de clés» = «une signature». Il est impossible de prédire quelle sera la signature d'un autre RP, donc le PVRB avec des signatures déterministes peut être organisé en combinant les signatures RSA de plusieurs participants qui ont signé la même valeur. Par exemple - le précédent aléatoire. Dans ce schéma, beaucoup de ressources sont enregistrées, car les signatures sont à la fois une confirmation de l'exactitude du comportement du protocole et une source de hasard.

Cependant, même avec des signatures déterministes, le schéma est toujours vulnérable au problème du «dernier acteur». Le dernier participant peut toujours décider de publier ou non sa signature, contrôlant ainsi le résultat. Vous pouvez affiner le schéma, y ​​ajouter des hachages de blocs, effectuer des arrondis afin que le résultat ne puisse pas être prédit à l'avance, mais toutes ces méthodes, même en tenant compte de nombreuses améliorations, laissent toujours sans solution le problème de l'influence d'un participant sur le résultat collectif dans un environnement non fiable et ne peuvent que fonctionner dans des conditions de contraintes économiques et temporelles. De plus, la taille des clés RSA (1024 et 2048 bits) est assez grande, et la taille des transactions blockchain est un paramètre extrêmement important. Apparemment, d'une manière simple, cela ne fonctionnera pas, nous allons plus loin.

PVRB et schémas de partage secret

En cryptographie, il existe des schémas qui peuvent permettre au réseau de se mettre d'accord sur une et une seule valeur de PVRB, tandis que ces schémas résistent à toute action malveillante d'une partie des participants. Un protocole utile à connaître est le schéma de partage secret de Shamir. Il sert à diviser un secret (par exemple une clé secrète) en plusieurs parties, et à distribuer ces parties à N participants. Le secret est distribué de telle manière que M parties de N sont suffisantes pour sa restauration, alors qu'il peut s'agir de n'importe quelle partie M. Si sur les doigts, puis ayant un graphique d'une fonction inconnue, les participants échangent des points sur le graphique, et après avoir reçu M points, la fonction entière peut être restaurée.
Une bonne explication est donnée dans le wiki et jouer avec lui pratiquement pour perdre le protocole dans votre tête est utile sur la page de démonstration .

Si le régime FSSS (Fiat-Shamir Secret Sharing) était applicable sous sa forme pure, il s'agirait d'un PVRB irrécupérable. Dans la version la plus simple, le protocole peut ressembler à ceci:

• Chaque participant génère son propre hasard et en distribue des parts aux autres participants
• M shares, , ,
• random- PVRB

, , threshold- . , RP , , “last actor”.

, PVRB secret sharing - , , . , , , . - EOS — share : . , proof- , . , verify , block-producer , , verify . , (0.5 ).

— - . proof-, — off-chain , — PVRB.

PVRB threshold signatures

secret sharing, , “threshold”. M N, N, “threshold” . “last actor”, , , . , .

threshold- PVRB — threshold-. threshold-, longread Dash.

BLS (BLS Boneh-Lynn-Shacham, ), — , , BLS , , . . , BLS , , M N , , publicly verifiable, , M- .

threshold BLS signatures BLS - ( ), threshold- . BLS , threshold- “last-actor”, , , , .

, PVRB , BLS threshold signatures, . , DFinity ( , , verifiable secret sharing), Keep.network ( random beacon yellowpaper , -, ).

PVRB

, , PVRB , . , , . PVRB , : CPU, memory, storage, I/O. PVRB — , , . , RP, , proof- , .

, PVRB:

• . PVRB unbiasable, . ,
• “last actor” . PVRB , , RP .
• . PVRB , , RP , ,
• . RP “ , ”. p2p , ,
• . PVRB on-chain , . -,
• liveness . PVRB , RP
• trusted setup . PVRB setup , . . - — ,
• . , , , ..

threshold BLS — , , , threshold. , , , , , , , realtime, , , threshold . , threshold-, , (slashing) , . , BLS , , EOS Ethereum — . — WebAssembly EVM, . (), . , 1024 2048 bit RSA, 4-8 , Bitcoin Ethereum.

— , . , Go geth, Rust Parity, C++ EOS. JavaScript , JavaScript , WebAssembly, -.

Conclusion

, , , , , . , , setup- , whitepaper- , - “ , ”.

, PVRB Haya , threshold BLS signatures, PVRB , - . , : secret sharing random_seed, threshold BLS , . , , , , , , — , , . — , , governance .

PVRB, , , , , , , , , , - . , , .

, , , , :)