Initialement publié en anglais par StarkWare le 23 Juin, 2020

Un service VDF basé sur STARK

Nous sommes heureux d’annoncer que VeeDo – notre service VDF (Vérifiable Delay Function) basé sur STARK est désormais disponible sur Mainnet. Cet article est conçu comme une introduction sur VeeDo. Il commence par décrire les éléments constitutifs de VeeDo. Nous décrivons ensuite notre première application pour VeeDo, un PoC pour une balise aléatoire, et comparons notre solution aux solutions aléatoires existantes. Enfin, nous discutons de certaines applications futures et des business models que nous envisageons pour VeeDo.

Verifiable Delay Functions (FDV) en français “les fonctions de retard vérifiables” ont d’abord été suggérées dans les travaux de Boneh et al. Comme leur nom l’indique, les VDFs sont des fonctions qui utilisent le calcul pour fournir un délai, un décalage temporel.

il peut être très difficile et/ou couteux pour quiconque de réduire le temps de retard par plus d'un facteur constant, bien que maitrisé.

Le VDF utilisé par VeeDo est une fonction f qui est :

1. Lent à calculer

2. Rapide à inverser (càd. le calcul f^(-1) est rapide)

3. On peut fournir une preuve π de l’intégrité computationnelle de f, d’une manière qui contourne la nécessité de rejouer le calcul lent de la fonction f.

Pour obtenir les propriétés ci-dessus d’un VDF, VeeDo combine la fonction delay f avec une autre primitive cryptographique, le protocole STARK.

La fonction delay f obtient comme entrée une paire : un élément de champ s donnée d’entrée, et un certain nombre d’itérations n. Il lance une seule boucle pour n itérations, à partir de cette donnée d’entrée. (Le nombre d’itérations, n, bien supérieur à un million, est un paramètre qui peut être ajusté pour obtenir le délai souhaité.) Chaque itération de la boucle est aussi simple : trouvez la racine d’un modulo polynôme de faible degré (cubique) un premier p qui est «large», dans le PoC de VeeDo, un premier de 126 bits. L’étape de recherche de racines est approximativement 42x plus difficile que la direction inverse de l’évaluation d’un polynôme cubique.

La propriété vérifiable du VDF, c'est-à-dire sa complexité de vérification poly-logarithmique, est obtenue par le protocole STARK. Une fois le calcul de f(s,n) effectué, trois éléments <*s, n*, *f*(s,n)> sont envoyés au prouveur STARK. Le proveur prouve alors que le calcul est valide. Le calcul de f sur s et la génération de la preuve sont effectués off-chain. <*s, n*, f(s,n)>, ainsi que la preuve, sont ensuite envoyés au vérifieur, un smart-contract fonctionnant on-chain. Le vérifieur STARK efficace s'exécute en un temps qui est poly-logarithmique en n (la longueur du calcul de f).

Notez que pour les petits délais, la méthode de vérification naïve consistant à calculer n itérations de f^(-1) peut-être suffisante. Le rôle joué par la preuve STARK ici est de compresser exponentiellement le processus de vérification naïf (de n à poly-log(n)) lorsque de grands délais sont nécessaires.

Notre analyse pointe vers une autre propriété importante du VDF de VeeDo : le hardware-resistance. Dans le calcul du VDF, les GPU et les FPGAs n’ont pas d’avantage sur un CPU 64 bits standard en termes de latence. De plus, nous avons une compréhension détaillée de la limite d’amélioration que l’on pourrait attendre de l’ASIC personnalisé pour ce calcul. Une analyse détaillée de ces aspects sera incluse dans un livre blanc que nous publierons sur VeeDo.

La première application que nous avons l’intention de traiter avec VeeDo est aléatoire trustless et sans parti pris sur Ethereum. Actuellement, Ethereum la source la plus largement utilisée de l’aléatoire est le hachage de bloc. Il y a plus de 3500 contrats intelligents qui l’utilisent. Le hachage aléatoire des blocs est facile à utiliser, accessible (généré à chaque bloc), et peu coûteux. Ces mêmes propriétés facilitent également la manipulation de l’aléatoire des hachages de blocs, et les chercheurs l’ont bien évidemment démontré (voir par exemple Bunz et al.). Deux autres sources d’aléatoire sont le service d’aléatoire basé sur l’oracle de Chainlink et la balise aléatoire de Keep Network (basée sur un relais de seuil BLS). Pour rester impartiales, ces solutions requièrent soit une majorité honnête, soit supposent la non-collusion de l’opérateur et du fournisseur de l’oracle. Ainsi, leur confiance nécessite des mécanismes crypto-économiques et des hypothèses de confiance non triviales.

L’utilisation d’un VDF comme balise d’aléatoire a été initialement proposée par Justin Drake, et est la principale proposition pour l’aléatoire de la chaîne de relais de l’Eth 2.0. L’idée de base est d’utiliser une source d’entropie élevée comme graine s au VDF (par exemple le hachage du bloc), puis d’exécuter le VDF pour n itérations et d’utiliser sa sortie f (s,n) comme aléatoire non biaisé. En supposant que personne ne sait prédire f(s,n) à partir de s en moins de t secondes, nous pouvons demander aux joueurs de faire toutes sortes de mouvements et d’enchères avant que t secondes ne se produisent, et utiliser le résultat f(s,n) comme aléatoire pour les événements qui se sont produits avant que t secondes ne se soient écoulées. En d’autres termes, l’impartialité de l’aléatoire d’un VDF n’est pas fondée sur des hypothèses crypto-économiques ou de confiance; elle repose plutôt sur des hypothèses concernant la vitesse maximale des calculs séquentiels.

Le PoC comprend une composante off-chain et des smart contracts on-chain. La composante off-chain comprend les éléments de calcul lourds du VDF, à savoir le calcul de la fonction de temporisation et la génération de la preuve. On-chain il y a deux smart contracts : un smart contract Verifieur qui vérifie la preuve, et un smart contract relais où nous enregistrons l’aléatoire calculé (pour les preuves validées).

Les caractéristiques de l’écoulement sont les suivantes :

1. Choisir un bloc tous les 820 blocs (environ une fois toutes les 3 heures)

2. Calculer les données d’entrée s à partir du hachage du bloc

3. Calculer la sortie VDF f(s,n) – exécuter la delay function f sur s pour n itérations

4. Générer une preuve attestant la validité du calcul

5. Envoyer la preuve au Verifier smart contract

6. Envoyer le nouveau caractère aléatoire au smart contract relais

Dans le PoC, le nombre d’itérations est de 10*2**25-1, ce qui correspond à un délai d’environ 3,5 minutes (sur un processeur puissant de dernière génération, chaque itération prend ~634 ns). On s’attend à ce que le nouveau caractère aléatoire ainsi que la preuve soient acceptés on-chain environ 20 minutes après l’extraction du bloc choisi. Ce délai peut être amélioré, mais cela n’entre pas dans le champ d’application du présent PC. Pour une description plus détaillée des aspects techniques, consultez le dépôt github.

Un avertissement important : en tant que PoC, il n’y a aucune garantie sur la disponibilité, ni sur la longévité du service. Il s’agit d’une démarche d’exploration visant à solliciter les commentaires et les idées de la communauté.

Il y a plusieurs autres applications que nous examinons, au-delà du hasard. Nous aborderons brièvement deux d’entre eux : les timelocks et un mécanisme de PoW de nouvelle génération. Nous sommes confiants que de nombreuses autres applications verront le jour, alors que l’écosystème commence à explorer VeeDo sérieusement.

Timelocks : les Timelocks sont un élément important de la cryptographie. Ils permettent de sceller l’information pendant une période prédéterminée, puis de la rendre publique. Habituellement, les Timelocks sont mis en œuvre à l’aide d’un commitment scheme. Le principal inconvénient de ces stratagèmes est que l’auteur de l’infraction est toujours tenu d’être en ligne ultérieurement pour révéler l’information engagée. Implicitement, cela signifie aussi que la partie contractante a la possibilité de ne pas révéler son engagement. Cela équivaut à une option gratuite, et si cette option n’est pas correctement fixée, l’efficacité du marché est diminuée. Deux cas d’utilisation intéressants dans les blockchains permissionless sont le vote décentralisé et les sealed-bid auctions. VeeDo peut vous aider : comme nous l’avons mentionné ci-dessus, une propriété intéressante de la fonction delay de VeeDo est que l’inverse (f^(-1)) est beaucoup plus court à calculer. Un utilisateur désireux de synchroniser un b secret (par exemple, une enchère ou un vote) peut rapidement calculer et publier s=f^(-1) (b,n). Le public peut maintenant apprendre b en calculant f(s,n), ce qui a pour résultat que b est révélé avec le délai souhaité.

NextGen PoW : un algorithme PoW robuste reste un problème difficile dans l’espace blockchain. Le problème est amplifié lorsque l’on tente de relancer une blockchain et son économie symbolique. Les solutions existantes sont déficientes : les airdrop sont sujets aux attaques de Sybil. Les ICO sont limitées aux investisseurs accrédités. Enfin, la vision originale de «One CPU = One Vote/Token» s’est avérée assez insaisissable, car invariablement du matériel personnalisé est construit pour accélérer n’importe quel algorithme PoW donné. Il en résulte un degré moindre de décentralisation pour le réseau exploité. VeeDo présente une alternative, qui uniformise les règles du jeu : les propriétaires de matériel coûteux et personnalisé ont très peu d’avantages (et un avantage limité) sur toutes les femmes (et tous les hommes) disposant d’un CPU.

VeeDo n’est pas seulement une expérimentation technologique, c’est aussi une expérimentation commerciale. Le DeFi se développe rapidement, et l’écosystème commence à peine à comprendre ce qu’il est possible de faire avec les nombreux Legos développés ces jours-ci. On pourrait les classer en fonction de la couche sur laquelle ils opèrent :

• Layer-1 (L-1) : Comme Uniswap et d’autres nous le montrent, il y a beaucoup à construire avec ces Legos directement sur L-1.

• Layer-2 (L-2) : De notre vision très centrée sur l’univers blockchain, on pourrait dire que l’univers fintech (PayPal, Coinbase, etc.) est entièrement L-2.

• L-1/L-2 Interface : Money Legos pourrait être rendu plus puissant si nous parvenons à combler efficacement le fossé L-1/L-2, et à exploiter les ressources disponibles en L-2 (informatique et stockage dans le cloud/mobile) pour alimenter les interactions sur L-1.

VeeDo est notre première tentative d’exploration de cette interface. Le «frontend» de VeeDo est un smart contract sur Ethereum (L-1); son «backend» calcule les preuves STARK dans le cloud (L-2).

La première série de défis a trait à la disponibilité des services : comment garantir une disponibilité suffisante ? Comment faire en sorte que le service dans son ensemble soit suffisamment décentralisé ? Ici, il y a plusieurs pistes à explorer, y compris l’open-sourcing, l’octroi de licences et la facturation d’un smart contract.

La monétisation par le biais d’une commission par un smart contract peut présenter des défis de «free-riding», particulièrement lorsqu’il s’agit de biens publics, une source si robuste d’aléatoire. Là aussi, nous avons quelques idées dans en tête que nous allons explorer prochainement

VeeDo est le VDF basé sur STARK de StarkWare, et son PoC est désormais disponible sur Mainnet. Nous voyons une route passionnante qui nous attend avec de nombreuses applications. La première application utilise VeeDo pour générer un aléatoire robuste. Tout ceci est expérimental, donc nous sommes impatients d’entendre vos commentaires, de discuter des demandes d’intérêt, etc. Veuillez nous envoyer un courriel à veedo@starkware.co

Kineret Segal, Tom Brand

Traduction faite par @cleminso

Initialement publié en anglais par StarkWare le 23 Juin, 2020

Un service VDF basé sur STARK

Nous sommes heureux d’annoncer que VeeDo – notre service VDF (Vérifiable Delay Function) basé sur STARK est désormais disponible sur Mainnet. Cet article est conçu comme une introduction sur VeeDo. Il commence par décrire les éléments constitutifs de VeeDo. Nous décrivons ensuite notre première application pour VeeDo, un PoC pour une balise aléatoire, et comparons notre solution aux solutions aléatoires existantes. Enfin, nous discutons de certaines applications futures et des business models que nous envisageons pour VeeDo.

Verifiable Delay Functions (FDV) en français “les fonctions de retard vérifiables” ont d’abord été suggérées dans les travaux de Boneh et al. Comme leur nom l’indique, les VDFs sont des fonctions qui utilisent le calcul pour fournir un délai, un décalage temporel.

il peut être très difficile et/ou couteux pour quiconque de réduire le temps de retard par plus d'un facteur constant, bien que maitrisé.

Le VDF utilisé par VeeDo est une fonction f qui est :

1. Lent à calculer

2. Rapide à inverser (càd. le calcul f^(-1) est rapide)

3. On peut fournir une preuve π de l’intégrité computationnelle de f, d’une manière qui contourne la nécessité de rejouer le calcul lent de la fonction f.

Pour obtenir les propriétés ci-dessus d’un VDF, VeeDo combine la fonction delay f avec une autre primitive cryptographique, le protocole STARK.

La fonction delay f obtient comme entrée une paire : un élément de champ s donnée d’entrée, et un certain nombre d’itérations n. Il lance une seule boucle pour n itérations, à partir de cette donnée d’entrée. (Le nombre d’itérations, n, bien supérieur à un million, est un paramètre qui peut être ajusté pour obtenir le délai souhaité.) Chaque itération de la boucle est aussi simple : trouvez la racine d’un modulo polynôme de faible degré (cubique) un premier p qui est «large», dans le PoC de VeeDo, un premier de 126 bits. L’étape de recherche de racines est approximativement 42x plus difficile que la direction inverse de l’évaluation d’un polynôme cubique.

La propriété vérifiable du VDF, c'est-à-dire sa complexité de vérification poly-logarithmique, est obtenue par le protocole STARK. Une fois le calcul de f(s,n) effectué, trois éléments <*s, n*, *f*(s,n)> sont envoyés au prouveur STARK. Le proveur prouve alors que le calcul est valide. Le calcul de f sur s et la génération de la preuve sont effectués off-chain. <*s, n*, f(s,n)>, ainsi que la preuve, sont ensuite envoyés au vérifieur, un smart-contract fonctionnant on-chain. Le vérifieur STARK efficace s'exécute en un temps qui est poly-logarithmique en n (la longueur du calcul de f).

Notez que pour les petits délais, la méthode de vérification naïve consistant à calculer n itérations de f^(-1) peut-être suffisante. Le rôle joué par la preuve STARK ici est de compresser exponentiellement le processus de vérification naïf (de n à poly-log(n)) lorsque de grands délais sont nécessaires.

Notre analyse pointe vers une autre propriété importante du VDF de VeeDo : le hardware-resistance. Dans le calcul du VDF, les GPU et les FPGAs n’ont pas d’avantage sur un CPU 64 bits standard en termes de latence. De plus, nous avons une compréhension détaillée de la limite d’amélioration que l’on pourrait attendre de l’ASIC personnalisé pour ce calcul. Une analyse détaillée de ces aspects sera incluse dans un livre blanc que nous publierons sur VeeDo.

La première application que nous avons l’intention de traiter avec VeeDo est aléatoire trustless et sans parti pris sur Ethereum. Actuellement, Ethereum la source la plus largement utilisée de l’aléatoire est le hachage de bloc. Il y a plus de 3500 contrats intelligents qui l’utilisent. Le hachage aléatoire des blocs est facile à utiliser, accessible (généré à chaque bloc), et peu coûteux. Ces mêmes propriétés facilitent également la manipulation de l’aléatoire des hachages de blocs, et les chercheurs l’ont bien évidemment démontré (voir par exemple Bunz et al.). Deux autres sources d’aléatoire sont le service d’aléatoire basé sur l’oracle de Chainlink et la balise aléatoire de Keep Network (basée sur un relais de seuil BLS). Pour rester impartiales, ces solutions requièrent soit une majorité honnête, soit supposent la non-collusion de l’opérateur et du fournisseur de l’oracle. Ainsi, leur confiance nécessite des mécanismes crypto-économiques et des hypothèses de confiance non triviales.

L’utilisation d’un VDF comme balise d’aléatoire a été initialement proposée par Justin Drake, et est la principale proposition pour l’aléatoire de la chaîne de relais de l’Eth 2.0. L’idée de base est d’utiliser une source d’entropie élevée comme graine s au VDF (par exemple le hachage du bloc), puis d’exécuter le VDF pour n itérations et d’utiliser sa sortie f (s,n) comme aléatoire non biaisé. En supposant que personne ne sait prédire f(s,n) à partir de s en moins de t secondes, nous pouvons demander aux joueurs de faire toutes sortes de mouvements et d’enchères avant que t secondes ne se produisent, et utiliser le résultat f(s,n) comme aléatoire pour les événements qui se sont produits avant que t secondes ne se soient écoulées. En d’autres termes, l’impartialité de l’aléatoire d’un VDF n’est pas fondée sur des hypothèses crypto-économiques ou de confiance; elle repose plutôt sur des hypothèses concernant la vitesse maximale des calculs séquentiels.

Le PoC comprend une composante off-chain et des smart contracts on-chain. La composante off-chain comprend les éléments de calcul lourds du VDF, à savoir le calcul de la fonction de temporisation et la génération de la preuve. On-chain il y a deux smart contracts : un smart contract Verifieur qui vérifie la preuve, et un smart contract relais où nous enregistrons l’aléatoire calculé (pour les preuves validées).

Les caractéristiques de l’écoulement sont les suivantes :

1. Choisir un bloc tous les 820 blocs (environ une fois toutes les 3 heures)

2. Calculer les données d’entrée s à partir du hachage du bloc

3. Calculer la sortie VDF f(s,n) – exécuter la delay function f sur s pour n itérations

4. Générer une preuve attestant la validité du calcul

5. Envoyer la preuve au Verifier smart contract

6. Envoyer le nouveau caractère aléatoire au smart contract relais

Dans le PoC, le nombre d’itérations est de 10*2**25-1, ce qui correspond à un délai d’environ 3,5 minutes (sur un processeur puissant de dernière génération, chaque itération prend ~634 ns). On s’attend à ce que le nouveau caractère aléatoire ainsi que la preuve soient acceptés on-chain environ 20 minutes après l’extraction du bloc choisi. Ce délai peut être amélioré, mais cela n’entre pas dans le champ d’application du présent PC. Pour une description plus détaillée des aspects techniques, consultez le dépôt github.

Un avertissement important : en tant que PoC, il n’y a aucune garantie sur la disponibilité, ni sur la longévité du service. Il s’agit d’une démarche d’exploration visant à solliciter les commentaires et les idées de la communauté.

Il y a plusieurs autres applications que nous examinons, au-delà du hasard. Nous aborderons brièvement deux d’entre eux : les timelocks et un mécanisme de PoW de nouvelle génération. Nous sommes confiants que de nombreuses autres applications verront le jour, alors que l’écosystème commence à explorer VeeDo sérieusement.

Timelocks : les Timelocks sont un élément important de la cryptographie. Ils permettent de sceller l’information pendant une période prédéterminée, puis de la rendre publique. Habituellement, les Timelocks sont mis en œuvre à l’aide d’un commitment scheme. Le principal inconvénient de ces stratagèmes est que l’auteur de l’infraction est toujours tenu d’être en ligne ultérieurement pour révéler l’information engagée. Implicitement, cela signifie aussi que la partie contractante a la possibilité de ne pas révéler son engagement. Cela équivaut à une option gratuite, et si cette option n’est pas correctement fixée, l’efficacité du marché est diminuée. Deux cas d’utilisation intéressants dans les blockchains permissionless sont le vote décentralisé et les sealed-bid auctions. VeeDo peut vous aider : comme nous l’avons mentionné ci-dessus, une propriété intéressante de la fonction delay de VeeDo est que l’inverse (f^(-1)) est beaucoup plus court à calculer. Un utilisateur désireux de synchroniser un b secret (par exemple, une enchère ou un vote) peut rapidement calculer et publier s=f^(-1) (b,n). Le public peut maintenant apprendre b en calculant f(s,n), ce qui a pour résultat que b est révélé avec le délai souhaité.

NextGen PoW : un algorithme PoW robuste reste un problème difficile dans l’espace blockchain. Le problème est amplifié lorsque l’on tente de relancer une blockchain et son économie symbolique. Les solutions existantes sont déficientes : les airdrop sont sujets aux attaques de Sybil. Les ICO sont limitées aux investisseurs accrédités. Enfin, la vision originale de «One CPU = One Vote/Token» s’est avérée assez insaisissable, car invariablement du matériel personnalisé est construit pour accélérer n’importe quel algorithme PoW donné. Il en résulte un degré moindre de décentralisation pour le réseau exploité. VeeDo présente une alternative, qui uniformise les règles du jeu : les propriétaires de matériel coûteux et personnalisé ont très peu d’avantages (et un avantage limité) sur toutes les femmes (et tous les hommes) disposant d’un CPU.

VeeDo n’est pas seulement une expérimentation technologique, c’est aussi une expérimentation commerciale. Le DeFi se développe rapidement, et l’écosystème commence à peine à comprendre ce qu’il est possible de faire avec les nombreux Legos développés ces jours-ci. On pourrait les classer en fonction de la couche sur laquelle ils opèrent :

• Layer-1 (L-1) : Comme Uniswap et d’autres nous le montrent, il y a beaucoup à construire avec ces Legos directement sur L-1.

• Layer-2 (L-2) : De notre vision très centrée sur l’univers blockchain, on pourrait dire que l’univers fintech (PayPal, Coinbase, etc.) est entièrement L-2.

• L-1/L-2 Interface : Money Legos pourrait être rendu plus puissant si nous parvenons à combler efficacement le fossé L-1/L-2, et à exploiter les ressources disponibles en L-2 (informatique et stockage dans le cloud/mobile) pour alimenter les interactions sur L-1.

VeeDo est notre première tentative d’exploration de cette interface. Le «frontend» de VeeDo est un smart contract sur Ethereum (L-1); son «backend» calcule les preuves STARK dans le cloud (L-2).

La première série de défis a trait à la disponibilité des services : comment garantir une disponibilité suffisante ? Comment faire en sorte que le service dans son ensemble soit suffisamment décentralisé ? Ici, il y a plusieurs pistes à explorer, y compris l’open-sourcing, l’octroi de licences et la facturation d’un smart contract.

La monétisation par le biais d’une commission par un smart contract peut présenter des défis de «free-riding», particulièrement lorsqu’il s’agit de biens publics, une source si robuste d’aléatoire. Là aussi, nous avons quelques idées dans en tête que nous allons explorer prochainement

VeeDo est le VDF basé sur STARK de StarkWare, et son PoC est désormais disponible sur Mainnet. Nous voyons une route passionnante qui nous attend avec de nombreuses applications. La première application utilise VeeDo pour générer un aléatoire robuste. Tout ceci est expérimental, donc nous sommes impatients d’entendre vos commentaires, de discuter des demandes d’intérêt, etc. Veuillez nous envoyer un courriel à veedo@starkware.co

Kineret Segal, Tom Brand

Traduction faite par @cleminso