Fonctions aléatoires vérifiables dans le consensus

Les protocoles de consensus ont besoin d'aléa pour l'élection du chef, la sélection des comités et l'attribution des fragments. Cet aléa doit satisfaire trois propriétés : l'imprévisibilité (personne ne peut prédire le résultat avant sa révélation), l'impossibilité de le biaiser (aucun participant ne peut manipuler le résultat à son avantage) et la vérifiabilité publique (chacun peut vérifier que le résultat est correct sans faire confiance au générateur). Les approches naïves échouent : le nombre aléatoire d'un seul nœud peut être manipulé, et les protocoles d'engagement-révélation permettent au dernier révélateur d'introduire un biais. Les fonctions aléatoires vérifiables (VRF) répondent aux trois exigences.

Une fonction aléatoire vérifiable (VRF), introduite par Micali, Rabin et Vadhan en 1999, est une fonction pseudo-aléatoire qui fournit une preuve de correction. Une VRF comporte trois algorithmes : KeyGen génère une paire de clés (SK, PK) ; Prove(SK, alpha) produit (beta, pi), où beta est le résultat et pi une preuve ; et Verify(PK, alpha, beta, pi) renvoie valide ou invalide. Le résultat beta est indiscernable d'une valeur aléatoire pour quiconque ne connaît pas SK (pseudo-aléa d'une VRF), et la preuve pi est infalsifiable (unicité d'une VRF). La taille de la preuve est de O(1), c'est-à-dire constante quelle que soit l'entrée.

La construction de VRF la plus largement déployée est ECVRF (IETF RFC 9381), fondée sur la difficulté du logarithme discret sur courbe elliptique. Étant donné une clé privée x et l'entrée alpha, le prouveur calcule H = hash-to-curve(PK, alpha) (ce qui associe alpha à un point de la courbe), puis gamma = x * H (multiplication scalaire). Le résultat de la VRF est beta = keccak(gamma). La preuve pi utilise un argument de connaissance nulle de type Schnorr : le prouveur s'engage sur un k aléatoire, calcule le défi c = hash(H, gamma, k*G, k*H), la réponse s = k - c*x, puis produit pi = (gamma, c, s). La vérification contrôle les équations de Schnorr et recalcule beta.

Algorand (Silvio Micali et al., 2017) a été pionnier dans l’utilisation des VRF pour le consensus sur chaîne de blocs. À chaque tour, chaque validateur évalue en privé VRF(SK, round || seed) afin d’obtenir une sortie aléatoire. La sortie est comparée à un seuil : si VRF_output < stake_fraction * threshold, le validateur est sélectionné comme membre du comité ou proposant de bloc. Seul le validateur connaît sa sélection jusqu’à ce qu’il diffuse son bloc ou son vote accompagné de la preuve VRF. Cette auto-sélection cryptographique élimine le besoin d’une élection publique du dirigeant, ce qui rend Algorand résistant aux attaques ciblées par déni de service contre les futurs dirigeants connus.

Ouroboros Praos de Cardano (la version actuellement déployée) utilise des VRF pour l’élection des dirigeants de créneau. À chaque époque, une nouvelle graine aléatoire est dérivée de la chaîne de blocs. Chaque opérateur de pool de mise (SPO) évalue VRF(SK, slot || epoch_seed) pour chaque créneau de l’époque. Si la sortie est inférieure à un seuil proportionnel à sa mise, il devient le dirigeant du créneau et peut produire un bloc. La preuve VRF est incluse dans l’en-tête du bloc, ce qui permet à chacun de vérifier que le SPO a été élu légitimement. Cardano bénéficie ainsi d’une sécurité démontrable contre les adversaires adaptatifs qui découvrent le calendrier des dirigeants au cours de l’époque.

Ethereum utilise RANDAO (des signatures BLS accumulées) plutôt que des VRF pour sa balise d’aléa. RANDAO est plus simple — aucune primitive cryptographique supplémentaire au-delà de BLS — mais il est vulnérable au biais du dernier révélateur : un proposant de bloc qui peut prévoir que sa contribution à RANDAO produira un résultat défavorable peut retenir son bloc, au prix de sa récompense de bloc. L’élection fondée sur les VRF dissimule l’identité de l’élu jusqu’à ce qu’il se révèle, ce qui élimine complètement cette possibilité d’attaque. Le compromis est le suivant : VRF ajoute une complexité cryptographique (hachage vers la courbe, génération de preuves), tandis que RANDAO réutilise l’infrastructure BLS existante.

Chainlink VRF fournit de l’aléa vérifiable sous forme de service pour les contrats intelligents. Un contrat client demande une valeur aléatoire en payant des jetons LINK. Un nœud oracle Chainlink détient une paire de clés VRF. Le nœud évalue ECVRF(SK, seed), où la graine est dérivée du hachage du bloc et d’une valeur nonce fournie par l’utilisateur, puis soumet (beta, pi) sur la chaîne. Le contrat coordinateur de VRF vérifie la preuve avant de transmettre la sortie aléatoire au client. Les contrats intelligents peuvent ainsi accéder à un aléa résistant aux manipulations sans que la chaîne doive implémenter une balise VRF native — ce qui est utile pour la création de NFT, les loteries et les jeux.

Le protocole Signal utilise VXEdDSA (EdDSA vérifiable sur X25519), une construction de VRF sur Curve25519. Lorsqu’un expéditeur génère la signature d’une clé préalable à usage unique, le VRF sert à produire une valeur déterministe mais imprévisible à partir du message et de la clé de l’expéditeur. Cela empêche la réutilisation de cette valeur, qui compromettrait la sécurité d’EdDSA, tout en conservant la vérifiabilité des signatures. La preuve VRF permet au destinataire de vérifier que la valeur a été dérivée correctement, empêchant l’expéditeur de choisir une valeur malveillante susceptible de permettre des attaques visant à retrouver la clé. VXEdDSA montre que les VRF constituent un outil cryptographique général qui dépasse le cadre du consensus.

Les fonctions de délai vérifiables (VDF) sont parfois confondues avec les VRF. Une VDF exige un calcul séquentiel pendant au moins T étapes (propriété de verrouillage temporel) et produit une sortie accompagnée d’une preuve courte de correction. Les VDF servent à atténuer le biais du dernier révélateur dans RANDAO : la couche VDF prévue pour Ethereum obligerait toute tentative de manipulation à exécuter une VDF à l’avance, ce qui prendrait plus de temps que la fenêtre d’attaque. Les VRF fournissent une évaluation privée instantanée ; les VDF fournissent une évaluation publique et lente. Elles sont complémentaires : les VDF empêchent le biais du dernier révélateur, tandis que les VRF empêchent la prédiction du dirigeant.

La sélection par VRF améliore nettement la sécurité contre les adversaires adaptatifs. Dans PBFT et Tendermint, l’identité du dirigeant est connue à l’avance (calendrier à tour de rôle), ce qui permet à un adversaire de lancer une attaque par déni de service distribué contre le prochain dirigeant avant qu’il ne propose son bloc. La sélection fondée sur les VRF garde l’identité du dirigeant secrète jusqu’à la diffusion du bloc — à ce moment-là, le bloc a déjà été proposé et une attaque par déni de service arrive trop tard. On parle de sécurité adaptative ou d’élection imprévisible du dirigeant. La propriété cryptographique qui permet cela est que la sortie du VRF est pseudo-aléatoire pour quiconque ne possède pas la clé privée.

Une implémentation correcte des VRF exige de porter une attention particulière à plusieurs points. Le hachage vers la courbe doit utiliser un algorithme uniforme à temps constant (la RFC 9380 de l’IETF définit des méthodes normalisées pour prévenir les fuites temporelles). La valeur k du VRF dans la preuve doit être dérivée de manière déterministe de (SK, alpha) au moyen de la RFC 6979 — réutiliser k ou utiliser une valeur k aléatoire faible divulgue la clé secrète, comme dans le cas d’une réutilisation de la valeur nonce d’ECDSA. La taille de la preuve pour ECVRF-P256-SHA256-TAI est de 80 octets ; pour ECVRF-ED25519-SHA512-ELL2, elle est également de 80 octets — les deux conviennent à une inclusion sur la chaîne. La propriété d’unicité du VRF garantit qu’il n’existe pas deux preuves valides pour une même paire (SK, alpha).

Pourquoi l’élection du dirigeant fondée sur les VRF offre-t-elle une sécurité supérieure à la désignation des dirigeants à tour de rôle ?

Les VRF produisent des sorties pseudo-aléatoires accompagnées de preuves cryptographiques de correction, ce qui garantit l’imprévisibilité, l’absence de biais et la vérifiabilité publique. ECVRF (RFC 9381) est la construction normalisée sur les courbes elliptiques. Algorand utilise l’auto-sélection cryptographique par VRF pour résister aux adversaires adaptatifs. Ouroboros Praos de Cardano utilise les VRF pour l’élection du dirigeant de chaque créneau. Chainlink VRF fournit de l’aléa vérifiable aux contrats intelligents. Les VRF complètent les VDF, qui traitent le biais du dernier révélateur, et se distinguent de RANDAO, qui utilise des signatures BLS accumulées et présente une faiblesse connue liée au dernier révélateur.