Le tri cryptographique dans les blockchains: l'importance des VRF

Quand la crypto peut être le joueur système

À mesure que je lis et que je comprends de plus en plus les technologies de chaîne de blocs dans le cadre de mon travail de chercheur chez Witnet, je commence à comprendre l’importance que les protocoles et les schémas cryptographiques ont dans leur conception. Il est étonnant de voir comment une petite décision de conception peut influencer la manière dont les utilisateurs interagissent avec le système et, potentiellement, en tirer parti.

Dans ce billet, j'aimerais partager quelques recherches internes que nous avons menées chez Witnet et expliquer comment nous nous sommes rendus compte que nos hypothèses cryptographiques n'étaient pas assez solides pour nos objectifs initiaux.

PoE dans le cadre des protocoles Blockchain

La preuve d'éligibilité (PoE) devient de plus en plus populaire dans la technologie Blockchain. En fait, les PoE nous donnent l’opportunité de décider qui est responsable de la réalisation d’une action. Lorsque l’éligibilité est découverte individuellement par chaque pair, nous l’appelons généralement un système de tri cryptographique, c’est-à-dire la possibilité de découvrir par vous-même si vous êtes le gagnant d’une «loterie».

Un tri cryptographique doit remplir plusieurs propriétés. Premièrement, les nœuds individuellement devraient pouvoir déterminer s'ils sont éligibles pour effectuer une action donnée. Deuxièmement, l'éligibilité devrait être vérifiable par cryptographie par d'autres pairs. Troisièmement, une triition cryptographique est associée à une identité unique, c'est-à-dire que les pairs doivent être sûrs que la preuve a été générée par le pair qui la réclame. De plus, on souhaiterait également que la preuve ne soit pas distinguable du hasard.

Nous avons observé plusieurs schémas de tri cryptographiques proposés dans le cadre d'une conception en chaîne de blocs, allant de la célèbre Preuve de travail en Bitcoin à de nouvelles propositions telles que, par exemple, Algorand, Filecoin ou Witnet. Dans cet article, je vais nous concentrer sur le tri cryptographique décrit dans Witnet et ses améliorations possibles. J'espère que les informations affichées ici sont utiles pour d'autres blockchains ayant le même objectif.

Tri cryptographique basé sur des signatures numériques

Les systèmes de tri cryptographiques basent généralement leur éligibilité sur la chance d'obtenir un nombre aléatoire inférieur à une valeur cible donnée. La difficulté dépend évidemment de la valeur cible; plus la valeur est élevée, plus les pairs ont de chances de devenir éligibles. La valeur cible peut en effet varier selon les pairs, peut-être en fonction de leur comportement lors des tâches précédentes. C'est précisément l'approche décrite par Witnet. Le tri cryptographique dans Witnet est défini comme suit:

Tri cryptographique dans Witnet

Où <> désigne la signature sur la clé M, et I désigne l’influence du pair i au temps t. L’influence fait référence à la réputation du nœud, c’est-à-dire à la manière dont il s’est comporté dans les tâches précédentes. Essentiellement, si le hachage de la signature de la tâche qu'un homologue souhaite effectuer tombe en dessous de la valeur cible, il devient alors éligible pour exécuter la tâche. Nous observons comment chaque pair peut déterminer individuellement sa triure sans interagir avec aucun autre pair du réseau. La valeur aléatoire est commune à tous les pairs (pourrait bien être le hash du bloc précédent).

Afin de vérifier l'éligibilité d'un nœud, le reste des nœuds vérifie d'abord que la signature a été générée avec les paramètres appropriés (valeur aléatoire associée à l'époque et à la tâche en cours pour lesquelles le nœud opte). Ensuite, ils hachent la signature pour voir si elle tombe en dessous de la valeur cible. Si tel est le cas, l'éligibilité du pair pour la tâche est vérifiée.

Les triages cryptographiques basés sur des signatures numériques (c'est-à-dire la signature d'un message donné) remplissent les instructions définies ci-dessus: ils sont générés par un pair donné, ils sont vérifiables via la clé publique et leur sortie semble aléatoire sans la clé publique.

Mais les schémas de tri cryptographiques basés sur les signatures numériques ont tendance à remplir (comme dans Witnet) une autre condition que je n'ai pas mentionnée: chaque pair doit avoir un seul coup d'éligibilité pour un message d'entrée. Sinon, les pairs pourraient simplement jouer à la loterie autant de fois qu'ils le voudraient jusqu'à ce qu'ils deviennent éligibles. La question que nous nous sommes posée dans Witnet était la suivante: les signatures numériques remplissent-elles cette propriété?

Le problème: une sortie non unique pour ECDSA

Avant de répondre à la question précédente, laissez-moi vous présenter brièvement le fonctionnement de la cryptographie à courbes elliptiques.

En résumé, la cryptographie à courbe elliptique (ECC) est un cryptosystème à clé publique dans lequel chaque homologue détient une paire de clés privée-publique. La clé privée n'est connue que du propriétaire, tandis que la clé publique est connue de tous les pairs. Les pairs en communication doivent d’abord s’entendre sur la courbe ECC qu’ils
vont utiliser. Une courbe est simplement l'ensemble des points définis par une équation,
par exemple, y ^ 2 = x ^ 3 + ax + b. La courbe est définie, entre autres paramètres, par un point générateur permettant d’atteindre tout autre point de la courbe. Pour construire un tel système, ECC construit l'arithmétique suivante:

  • si P est un point de la courbe, -P est sa réflexion sur l'axe des x
  • si deux points P et Q sont distincts, le résultat de l'ajout de P et Q est
    calculé en traçant une ligne traversant P et Q, qui se croiseront dans une
    troisième point -R dans la courbe. R est calculé en prenant le reflet de −R
    par rapport à l'axe des x.
  • P + P est calculé en traçant une ligne tangente à la courbe en P, qui
    recoupera à nouveau un troisième point de la courbe -2P. 2P est juste le
    réflexion sur l'axe des x
Exemple d'addition de courbes elliptiques

Notez qu'avec cette arithmétique, nous pouvons déjà ajouter des points et par conséquent, multiplier des points avec des escaliers (5P est juste 2P + 2P + P). La paire de clés privée-publique est construite en choisissant d'abord un entier aléatoire qui nous servira de clé privée. La clé publique est simplement la multiplication de l'entier avec le point générateur. La sécurité du schéma repose sur la difficulté ou la récupération de l'entier à l'origine du point clé public. Ceci est, étant donné la clé publique Q, le problème pour trouver l'entier k qui multiplie le générateur pour atteindre Q est équivalent au problème du logarithme discret.

Avec un tel système, on peut déjà effectuer plusieurs approches cryptographiques. L'un d'eux est la capacité de générer des signatures numériques. L'image globale de la génération de siganture ECDSA peut être vue dans l'image suivante

Génération de signature ECDSA

Essentiellement, le message d'entrée m est d'abord haché. Ensuite, un nombre aléatoire u est choisi de telle sorte que, multiplié par le point générateur G, mappe sur un point de la courbe dont la coordonnée x est 0. Si cette condition n'est pas remplie, la valeur u est à nouveau choisie. Si c'est le cas, alors l'inverse de u est multiplié par (e + dr) jusqu'à ce que la valeur soit différente de zéro. La signature est le tuple (r, s).

En fait, nous n’avons pas besoin de comprendre complètement l’algorithme pour comprendre que la signature (r, s) dépend fortement de la valeur aléatoire u sélectionnée à la ligne 5. En d’autres termes, la valeur de la signature dépendra d’une valeur aléatoire et, par conséquent, un message donné peut mapper sur plusieurs signatures différentes.

Ceci est déjà en conflit avec ce que nous décrivions idéalement pour un tri cryptographique. Si l'éligibilité d'un pair dépendra du hachage d'une signature pouvant prendre différentes valeurs en fonction de la valeur aléatoire u choisie, on peut s'attendre à ce que les pairs calculent en permanence les signatures jusqu'à ce qu'elles en trouvent une pour laquelle le hachage est suffisamment faible. devenir éligible. Fait intéressant, le schéma de cryptographie utilisé donne aux pairs la possibilité de jouer au système.

La solution: les VRF en tant que tri cryptographique

Malgré le problème mentionné, nous ne voudrions pas renoncer à tous les avantages que les signatures numériques offrent à notre système. Par conséquent, nous devons ajouter la propriété unicité à notre triade cryptographique, comme s'il s'agissait d'une «version à clé publique d'un HMAC à clé». Les fonctions aléatoires vérifiables (VRF) semblent faire l'affaire (et en fait, elles sont utilisées dans Algorand). Les VRF ont été introduits pour la première fois par Silvio Micali dans [1]. Les VRF génèrent deux sorties: une "signature unique" β et une preuve π. En plus d'être un système cryptographique à clé publique, ils ont les propriétés suivantes:

  • La résistance à la collision, c’est-à-dire qu’il est difficile de trouver deux entrées mappées sur la même sortie.
  • Pseudo-aléatoire, c’est-à-dire que la sortie est indiscernable du hasard si quiconque ne connaît pas la clé secrète.
  • Unicité approuvée, qui nécessite que, dans le cas d’une clé publique, une entrée VRF m corresponde à une sortie unique β.

La dernière déclaration est assez importante. Cela signifie que β sera toujours unique pour un message d'entrée donné et une clé publique, alors que la preuve peut être aléatoire. Ainsi, les pairs ne peuvent pas générer plusieurs signatures avant d’avoir atteint une valeur suffisamment basse, car ils obtiendront toujours la même valeur pour une même entrée. En d’autres termes, ils n’exécutent la loterie qu’une fois par message d’entrée.

Exemple VRF

La question est bien sûr de savoir comment construire ces schémas. Nous suivons le schéma proposé dans [2], qui décrit les constructions de VRF pour RSA et ECC. Par souci de brièveté, nous omettons la description de construction RSA. En effet, ECC offre aux schémas cryptographiques des avantages en termes de taille de clé et de signature par rapport à RSA pour atteindre le même niveau de sécurité.

L'algorithme de vérification de signature ECC-VRF est visible ci-dessous. ECVRF_hash_to_curve est une fonction qui hache un entier en un point de la courbe. Au contraire, ECVRF_hash_points est une fonction qui hache plusieurs points de la courbe en un entier. Avec ces deux fonctions auxiliaires, nous pouvons construire le schéma de génération de signature suivant:

Génération de preuve ECC-VRF

La sortie β est ensuite hachée pour vérifier si le résumé est inférieur à la valeur cible, tandis que la preuve π est utilisée par le vérificateur pour vérifier que la sortie a bien été calculée avec la clé publique associée et pour le message donné de la manière suivante:

Vérification de preuve ECC-VRF

Si nous examinons l’algorithme, si et seulement si c ’est égal à c, la preuve est vérifiée. En comparant l’étape 15 de la vérification et l’étape 4 de la génération de signature, nous pouvons voir que l’égalité tiendra tant que u = Gt et v = Ht. Le vérificateur peut-il valider cela sans connaître la clé secrète k? Dans ce qui suit, nous démontrons l'exactitude de l'égalité:

  • La valeur u = Qc + Gs = Qc + G (t-kc) = Qc + Gt-Gkc = Qc + Gt -Qc = Gt
  • La valeur v = βc + Hs = βc + H (t-kc) = βc + Ht-Hkc = βc + Ht-βc = Ht

On peut vérifier que l’égalité est vraie sans avoir à connaître la valeur secrète k.

Conclusions

Dans cet article, je partageais les raisons pour lesquelles les schémas de tri cryptographiques basés sur les signatures numériques pouvaient constituer une incitation importante pour les pairs à jouer au système, en particulier lorsque l'éligibilité d'une tâche dépend d'eux. Dans le cas de Witnet, les tâches d’extraction de données et de demande de données dépendent toutes les deux du résultat de la triition. Par conséquent, nous ne pouvons pas créer une telle incitation pour les pairs. Nous pouvons parvenir à une situation où la récompense d'une demande de données est suffisamment élevée pour inciter les pairs à générer de manière persistante des signatures pour celle-ci jusqu'à ce que le hachage soit suffisamment faible, ce qui permet d'effectuer une sorte de preuve de travail sous-estimée pour les demandes de données. En fait, si les nœuds mettent toutes les ressources dans une requête de données généreuse, le reste sera oublié et les performances du système seront sérieusement affectées.

Les fonctions aléatoires vérifiables semblent résoudre le problème décrit ci-dessus. En effet, ils conservent tous les avantages des signatures numériques, avec un fait supplémentaire: la «signature» est unique pour une clé publique et un message donnés. De plus, les VRF génèrent la preuve grâce à laquelle le vérificateur peut vérifier la validité de la transaction. Ainsi, les VRF semblent la bonne approche pour des systèmes comme Witnet.

Références

  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/Verifiable_Random_Functions.pdf
  • https://filecoin.io/filecoin.pdf
  • https://witnet.io/static/witnet-whitepaper.pdf
  • https://eprint.iacr.org/2017/099.pdf
  • https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03