Initialement publié en anglais par StarkWare le 5 décembre, 2019

Au cours des derniers mois, un intérêt considérable a été porté à Optimistic Rollup (OR), un cadre de scalabilité basé sur les preuves de fraude (FP). Chez StarkWare, nous mettons en œuvre des Validity Proofs (VP) parce qu’ils sont plus sécurisés que FP. Cet article souligne quelques avantages supplémentaires que VP ont par rapport aux OR et corrige les idées fausses courantes sur VP, et sur StarkEx – le moteur de scalabilité VP basé sur STARK de StarkWare.

En particulier, comparer OR, VP est :

• Fondamentalement plus sûr

• 1000X plus économe en capital pour les retraits

• Plus scalable (on-chain)

• Au moins aussi efficace, en termes de calcul

Dans notre analyse précédente, nous avons comparé VP, où les transitions d’état ont lieu strictement entre les états valides, à OR, où toute transition d’état est permise (donc optimiste), et les participants peuvent présenter des preuves de fraude, c’est-à-dire de transitions d’état invalides. Il s’agissait essentiellement d’une analyse de sécurité, qui indiquait une attaque bien définie contre l‘OR, une attaque qui entraîne le vol de tous les fonds de l’OR (d’autres attaques possibles continuent d’être délibérées). Les solutions d’infrastructure proposées pour les blockchains doivent être suffisamment résilientes pour supporter toute la charge du monde financier, où les transactions sont effectuées quotidiennement. Comment VP et OR s’acquittent-ils de cette tâche? Étant donné que le coût du vol des fonds de l’OR n’est pas lié au montant de la prime, les agents rationnels sont obligés de briser le système une fois qu’on lui accorde une valeur substantielle. En revanche, VP ne peut pas être transféré dans un état invalide et les fonds ne peuvent pas être volés, peu importe le montant de la prime. Pour les systèmes financiers de grande valeur, VP est solide, OR est susceptible de se casser.

La sécurité peut également être analysée en fonction du rôle des données et des conséquences de leur absence. Avec OR, les données jouent un rôle beaucoup plus dangereux qu’en VP. En l’absence de données, les fonds de la OR peuvent être volés – c’est pourquoi les conceptions actuelles se concentrent sur la DA on-chain. Avec VP, les données on-chain (cad ZK-Rollup), les fonds sont aussi sûrs que sur L1 elle-même. Dans le cas de VP avec des données off-chain, les fonds peuvent simplement être gelés, pas volés.

Un problème douloureux avec la liquidité de crypto-monnaie est le retard associé au retrait des fonds. Avec OR, le délai de retrait standard est d’environ 1 semaine – la durée prévue pour soumettre les preuves de fraude (un paramètre de sécurité). Avec VP, la fenêtre de retrait standard est d’environ 10 min (et probablement beaucoup moins, avec des améliorations des logicielles et du matérielles supplémentaires) – la durée de production d’une preuve attestant de l’intégrité du dernier calcul. Le délai de retrait standard pour OR est donc 1000 fois plus long que pour VP (environ 1 semaine/10 minutes ~ 1000). Cette pénalité de 1000X doit être payée lors de l’utilisation d’OR, que cette pénalité soit exprimée en rendement du capital ou en durée.

Nous avons déjà décrit un mécanisme de retrait rapide trustless, dans lequel un utilisateur qui souhaite retirer des fonds rapidement, donne au fournisseur de liquidités un conditional payment – un IOU – pour les fonds off-chain, et reçoit à son tour – à la vitesse du réseau – le même montant on-chain, à partir du smart contract « cookie jar » du liquidity provider. Le liquidity provider peut réapprovisionner périodiquement son « cookie jar » avec les fonds accumulés dans son solde off-chain.

Le retrait rapide peut être utilisé à la fois pour VP et OR. Mais pour OR, le fournisseur de liquidité doit détenir 1000X plus de capital dans son « cookie jar », car il doit répondre aux demandes reçues pendant une fenêtre qui est 1000X plus longue. Ce ratio est indépendant de toute hypothèse que nous faisons dans l’algorithme de détermination de la liquidité requise dans le « cookie jar » : s’il est basé sur les retraits attendus, ou uniquement sur les retraits moins les dépôts; s’il est basé sur les besoins de liquidité de pointe ou seulement sur un scénario moyen/probable.

Malheureusement, les retraits rapides ne sont pas toujours une option viable. Lorsqu’il s’agit d’actifs non fongibles (ou simplement d’ensembles de fongibilité plus petits), ils sont impossibles (ou risquent d’être considérablement plus coûteux) :

• Non-Fungible Tokens (NFT) : Comme l’a d’abord décrit Vitalik, si un crypto-kitty de valeur, appelé Mitzi, est stocké off-chain, son propriétaire ne peut pas demander à le recevoir on-chain, car il n’y a qu’un Mitzi dans le monde.

• Transactions protégées : Un engagement du style Zerocash est également non fongible, d’une certaine manière. Pour activer un retrait rapide lors du retour d’un jeton protégé on-chain principale – où il doit rester protégé – l’utilisateur devrait faire preuve d’un engagement particulier vis-à-vis du liquidity provider.

Dans ces cas, lorsque les Retraits Rapides ne sont pas disponibles, les utilisateurs retournent à la fenêtre de retrait standard, qui est 1000 fois plus rapide pour VP que pour OR.

Dans cette section, afin de comparer les pommes aux pommes (comparable avec ce qui est comparable*), nous ne considérerons que les systèmes de rollup, pour lesquels, par définition, les données sont disponibles on-chain : OR vs STARK ZK-Rollup (StR). Toute solution qui stocke des données on-chain a la propriété indésirable d’une consommation de ressources on-chain qui croît linéairement avec le volume de transactions globales. Les données on-chain comprennent certains états (p.ex, les détails de la transaction) et un témoin (p.ex, les signatures numériques qui prouvent le consentement des parties à la transaction). La différence entre OR et StR est que le témoin OR est à l’échelle linéaire avec le nombre de transactions, alors que StR remplace tous ces témoins par une seule preuve qui est à l’échelle poly-logarithmique avec le nombre de transactions. Il est important de noter que, pour des lots suffisamment importants, l’empreinte de données on-chain de StR est significativement plus petite que celle de la OR.

Plus précisément : Dans StR, le témoin peut attester des vérifications effectuées par le rollup operator (p.ex. toutes les signatures numériques ont été vérifiées), et par conséquent un témoin (p.ex. un zk-proof) est requis par lot de calculs, ce qui évite d’ajouter un témoin à chaque transaction. Heureusement, dans les systèmes zkp modernes, la preuve est d’une taille pratiquement fixe (enfin, poly-logarithmique, comme nous l’avons dit plus haut). Par conséquent, à mesure que le lot s’agrandit, le coût amorti du témoin par transaction diminue.

Avec OR, un témoin est requis par transaction afin de permettre aux validateurs de s’assurer de l’exactitude, et il n’y a donc aucun avantage d’amortissement pour les lots plus importants. De plus, le témoin OR est considérablement plus grand que la transaction : par exemple, le témoin OR doit inclure toutes les signatures des utilisateurs¹, alors qu’en VP celles-ci peuvent être supprimées (la preuve attestant qu’elles ont été cochées off-chain). Dans les cas de paiements transparents, le témoin est 3X-5X plus grand que le paiement lui-même; dans les cas plus complexes (p.ex. transactions protégées), le témoin est souvent 10X plus grand que l’état, et parfois plus.

En résumé, la OR consomme beaucoup plus de ressources on-chain et atteindra donc un plafond de scalabilité bien avant StR.

Une comparaison souvent faite entre VP et OR concerne la charge de calcul : pour un calcul donné à effectuer off-chain, combien de travail supplémentaire est nécessaire dans chaque approche ? Nous nous concentrerons sur les capacités STARKs de StarkWare, car il s'agit du cadre VP que nous mettons actuellement en œuvre.

OR : Le nombre souvent cité pour OR est 100X, car le fait d'avoir 100 validateurs qui se surveillent les uns les autres devrait suffire à garantir que les calculs sont effectués correctement. Afin de valider, chacun de ces validateurs doit effectuer le calcul réel, donc 100X.

Notez que plus l'ensemble des validateurs est petit ou prédéterminé, plus il est facile pour eux de s'entendre ou pour des personnes extérieures de les corrompre ou de les attaquer.

STARK : Ici, une seule entité – le prouveur – doit effectuer un gros calcul, car la vérification est informatiquement triviale. C’est insignifiant à quel point ? On peut aujourd’hui vérifier des preuves pour d’énormes lots de calculs avec un simple smartphone, et donc ignorer les coûts de vérification. Le nombre souvent cité pour la surcharge du prouveur est 10.000X, car la génération de la preuve est un calcul exigeant. La réalité pour StR est que ce surcoût est en fait d’environ 100X, et donc dans la même fourchette que pour OR. Il n’est que 100X pour plusieurs raisons :

• Pour les opérations arithmétiques/algébriques, nous sommes déjà à un surcoût de calcul inférieur à 100X. La fonction de hachage Pedersen, que nous utilisons actuellement, n’est que 20X plus chère qu’un calcul natif : le test STARK d’un hachage Pedersen est 20X plus lent que le calcul direct d’un Pedersen.

• Pour des opérations telles que SHA-256 il y a certes des frais généraux considérables, mais nous avons l’intention de remplacer ces fonctions de hachage par des fonctions compatibles STARK. Nous avons été financés par la Fondation Ethereum pour le faire, et nous nous attendons à ce que le comité sélectionné d’experts universitaires en cryptanalyse émette sa recommandation au premier trimestre de 2020. Nous nous attendons à ce que la fonction de hachage STARK-friendly sélectionnée soit environ 100 fois plus lente à prouver qu’un calcul de hachage efficace (par exemple SHA-256).

Enfin, un argument souvent cité en faveur de OR est qu'il s'applique aux calculs généraux, et qu'il supportera le code EVM, alors que VP ne le fait pas. Nous sommes optimistes quant à l'utilisation de STARK pour le calcul général.

Avihu Levy & Uri Kolodny

Merci à Dan Robinson, John Adler et Vitalik Buterin pour leurs commentaires.

¹ BLS est souvent cité comme un mécanisme efficace d'agrégation de signatures. Nous pensons que BLS ne servira pas ce cas d'utilisation particulier, car il est mieux adapté à de nombreuses signatures sur un seul message. Dans le cas d'utilisation de la OR, de nombreux messages doivent être signés par leur expéditeur/récepteur respectif ; la vérification des signatures BLS prendrait ici environ 10 ms/signature (une seule opération d'appariement par message), ce qui pèserait à la fois sur les validateurs (off-chain) et on-chain principale en cas de litige pour fraude.

Traduction faite par @cleminso

Initialement publié en anglais par StarkWare le 5 décembre, 2019

Au cours des derniers mois, un intérêt considérable a été porté à Optimistic Rollup (OR), un cadre de scalabilité basé sur les preuves de fraude (FP). Chez StarkWare, nous mettons en œuvre des Validity Proofs (VP) parce qu’ils sont plus sécurisés que FP. Cet article souligne quelques avantages supplémentaires que VP ont par rapport aux OR et corrige les idées fausses courantes sur VP, et sur StarkEx – le moteur de scalabilité VP basé sur STARK de StarkWare.

En particulier, comparer OR, VP est :

• Fondamentalement plus sûr

• 1000X plus économe en capital pour les retraits

• Plus scalable (on-chain)

• Au moins aussi efficace, en termes de calcul

Dans notre analyse précédente, nous avons comparé VP, où les transitions d’état ont lieu strictement entre les états valides, à OR, où toute transition d’état est permise (donc optimiste), et les participants peuvent présenter des preuves de fraude, c’est-à-dire de transitions d’état invalides. Il s’agissait essentiellement d’une analyse de sécurité, qui indiquait une attaque bien définie contre l‘OR, une attaque qui entraîne le vol de tous les fonds de l’OR (d’autres attaques possibles continuent d’être délibérées). Les solutions d’infrastructure proposées pour les blockchains doivent être suffisamment résilientes pour supporter toute la charge du monde financier, où les transactions sont effectuées quotidiennement. Comment VP et OR s’acquittent-ils de cette tâche? Étant donné que le coût du vol des fonds de l’OR n’est pas lié au montant de la prime, les agents rationnels sont obligés de briser le système une fois qu’on lui accorde une valeur substantielle. En revanche, VP ne peut pas être transféré dans un état invalide et les fonds ne peuvent pas être volés, peu importe le montant de la prime. Pour les systèmes financiers de grande valeur, VP est solide, OR est susceptible de se casser.

La sécurité peut également être analysée en fonction du rôle des données et des conséquences de leur absence. Avec OR, les données jouent un rôle beaucoup plus dangereux qu’en VP. En l’absence de données, les fonds de la OR peuvent être volés – c’est pourquoi les conceptions actuelles se concentrent sur la DA on-chain. Avec VP, les données on-chain (cad ZK-Rollup), les fonds sont aussi sûrs que sur L1 elle-même. Dans le cas de VP avec des données off-chain, les fonds peuvent simplement être gelés, pas volés.

Un problème douloureux avec la liquidité de crypto-monnaie est le retard associé au retrait des fonds. Avec OR, le délai de retrait standard est d’environ 1 semaine – la durée prévue pour soumettre les preuves de fraude (un paramètre de sécurité). Avec VP, la fenêtre de retrait standard est d’environ 10 min (et probablement beaucoup moins, avec des améliorations des logicielles et du matérielles supplémentaires) – la durée de production d’une preuve attestant de l’intégrité du dernier calcul. Le délai de retrait standard pour OR est donc 1000 fois plus long que pour VP (environ 1 semaine/10 minutes ~ 1000). Cette pénalité de 1000X doit être payée lors de l’utilisation d’OR, que cette pénalité soit exprimée en rendement du capital ou en durée.

Nous avons déjà décrit un mécanisme de retrait rapide trustless, dans lequel un utilisateur qui souhaite retirer des fonds rapidement, donne au fournisseur de liquidités un conditional payment – un IOU – pour les fonds off-chain, et reçoit à son tour – à la vitesse du réseau – le même montant on-chain, à partir du smart contract « cookie jar » du liquidity provider. Le liquidity provider peut réapprovisionner périodiquement son « cookie jar » avec les fonds accumulés dans son solde off-chain.

Le retrait rapide peut être utilisé à la fois pour VP et OR. Mais pour OR, le fournisseur de liquidité doit détenir 1000X plus de capital dans son « cookie jar », car il doit répondre aux demandes reçues pendant une fenêtre qui est 1000X plus longue. Ce ratio est indépendant de toute hypothèse que nous faisons dans l’algorithme de détermination de la liquidité requise dans le « cookie jar » : s’il est basé sur les retraits attendus, ou uniquement sur les retraits moins les dépôts; s’il est basé sur les besoins de liquidité de pointe ou seulement sur un scénario moyen/probable.

Malheureusement, les retraits rapides ne sont pas toujours une option viable. Lorsqu’il s’agit d’actifs non fongibles (ou simplement d’ensembles de fongibilité plus petits), ils sont impossibles (ou risquent d’être considérablement plus coûteux) :

• Non-Fungible Tokens (NFT) : Comme l’a d’abord décrit Vitalik, si un crypto-kitty de valeur, appelé Mitzi, est stocké off-chain, son propriétaire ne peut pas demander à le recevoir on-chain, car il n’y a qu’un Mitzi dans le monde.

• Transactions protégées : Un engagement du style Zerocash est également non fongible, d’une certaine manière. Pour activer un retrait rapide lors du retour d’un jeton protégé on-chain principale – où il doit rester protégé – l’utilisateur devrait faire preuve d’un engagement particulier vis-à-vis du liquidity provider.

Dans ces cas, lorsque les Retraits Rapides ne sont pas disponibles, les utilisateurs retournent à la fenêtre de retrait standard, qui est 1000 fois plus rapide pour VP que pour OR.

Dans cette section, afin de comparer les pommes aux pommes (comparable avec ce qui est comparable*), nous ne considérerons que les systèmes de rollup, pour lesquels, par définition, les données sont disponibles on-chain : OR vs STARK ZK-Rollup (StR). Toute solution qui stocke des données on-chain a la propriété indésirable d’une consommation de ressources on-chain qui croît linéairement avec le volume de transactions globales. Les données on-chain comprennent certains états (p.ex, les détails de la transaction) et un témoin (p.ex, les signatures numériques qui prouvent le consentement des parties à la transaction). La différence entre OR et StR est que le témoin OR est à l’échelle linéaire avec le nombre de transactions, alors que StR remplace tous ces témoins par une seule preuve qui est à l’échelle poly-logarithmique avec le nombre de transactions. Il est important de noter que, pour des lots suffisamment importants, l’empreinte de données on-chain de StR est significativement plus petite que celle de la OR.

Plus précisément : Dans StR, le témoin peut attester des vérifications effectuées par le rollup operator (p.ex. toutes les signatures numériques ont été vérifiées), et par conséquent un témoin (p.ex. un zk-proof) est requis par lot de calculs, ce qui évite d’ajouter un témoin à chaque transaction. Heureusement, dans les systèmes zkp modernes, la preuve est d’une taille pratiquement fixe (enfin, poly-logarithmique, comme nous l’avons dit plus haut). Par conséquent, à mesure que le lot s’agrandit, le coût amorti du témoin par transaction diminue.

Avec OR, un témoin est requis par transaction afin de permettre aux validateurs de s’assurer de l’exactitude, et il n’y a donc aucun avantage d’amortissement pour les lots plus importants. De plus, le témoin OR est considérablement plus grand que la transaction : par exemple, le témoin OR doit inclure toutes les signatures des utilisateurs¹, alors qu’en VP celles-ci peuvent être supprimées (la preuve attestant qu’elles ont été cochées off-chain). Dans les cas de paiements transparents, le témoin est 3X-5X plus grand que le paiement lui-même; dans les cas plus complexes (p.ex. transactions protégées), le témoin est souvent 10X plus grand que l’état, et parfois plus.

En résumé, la OR consomme beaucoup plus de ressources on-chain et atteindra donc un plafond de scalabilité bien avant StR.

Une comparaison souvent faite entre VP et OR concerne la charge de calcul : pour un calcul donné à effectuer off-chain, combien de travail supplémentaire est nécessaire dans chaque approche ? Nous nous concentrerons sur les capacités STARKs de StarkWare, car il s'agit du cadre VP que nous mettons actuellement en œuvre.

OR : Le nombre souvent cité pour OR est 100X, car le fait d'avoir 100 validateurs qui se surveillent les uns les autres devrait suffire à garantir que les calculs sont effectués correctement. Afin de valider, chacun de ces validateurs doit effectuer le calcul réel, donc 100X.

Notez que plus l'ensemble des validateurs est petit ou prédéterminé, plus il est facile pour eux de s'entendre ou pour des personnes extérieures de les corrompre ou de les attaquer.

STARK : Ici, une seule entité – le prouveur – doit effectuer un gros calcul, car la vérification est informatiquement triviale. C’est insignifiant à quel point ? On peut aujourd’hui vérifier des preuves pour d’énormes lots de calculs avec un simple smartphone, et donc ignorer les coûts de vérification. Le nombre souvent cité pour la surcharge du prouveur est 10.000X, car la génération de la preuve est un calcul exigeant. La réalité pour StR est que ce surcoût est en fait d’environ 100X, et donc dans la même fourchette que pour OR. Il n’est que 100X pour plusieurs raisons :

• Pour les opérations arithmétiques/algébriques, nous sommes déjà à un surcoût de calcul inférieur à 100X. La fonction de hachage Pedersen, que nous utilisons actuellement, n’est que 20X plus chère qu’un calcul natif : le test STARK d’un hachage Pedersen est 20X plus lent que le calcul direct d’un Pedersen.

• Pour des opérations telles que SHA-256 il y a certes des frais généraux considérables, mais nous avons l’intention de remplacer ces fonctions de hachage par des fonctions compatibles STARK. Nous avons été financés par la Fondation Ethereum pour le faire, et nous nous attendons à ce que le comité sélectionné d’experts universitaires en cryptanalyse émette sa recommandation au premier trimestre de 2020. Nous nous attendons à ce que la fonction de hachage STARK-friendly sélectionnée soit environ 100 fois plus lente à prouver qu’un calcul de hachage efficace (par exemple SHA-256).

Enfin, un argument souvent cité en faveur de OR est qu'il s'applique aux calculs généraux, et qu'il supportera le code EVM, alors que VP ne le fait pas. Nous sommes optimistes quant à l'utilisation de STARK pour le calcul général.

Avihu Levy & Uri Kolodny

Merci à Dan Robinson, John Adler et Vitalik Buterin pour leurs commentaires.

¹ BLS est souvent cité comme un mécanisme efficace d'agrégation de signatures. Nous pensons que BLS ne servira pas ce cas d'utilisation particulier, car il est mieux adapté à de nombreuses signatures sur un seul message. Dans le cas d'utilisation de la OR, de nombreux messages doivent être signés par leur expéditeur/récepteur respectif ; la vérification des signatures BLS prendrait ici environ 10 ms/signature (une seule opération d'appariement par message), ce qui pèserait à la fois sur les validateurs (off-chain) et on-chain principale en cas de litige pour fraude.

Traduction faite par @cleminso