Initialement publié en anglais par StarkWare le 5 février, 2019.

Part 1

La mission de StarkWare est d’appliquer la technologie de preuve cryptographique STARK dans le monde réel. Ceci est le premier article de la série expliquant la théorie mathématique derrière la technologie STARK et notre mise en œuvre de celle-ci. Nous commençons par un article facilement compréhensible et nous augmenterons la difficulté mathématique dans les articles suivants.

La mission de StarkWare est d’appliquer la technologie de preuve cryptographique STARK dans le monde réel. Ceci est le premier article de la série expliquant la théorie mathématique derrière la technologie STARK et notre mise en œuvre de celle-ci. Nous commençons par un article facilement compréhensible et nous augmenterons la difficulté mathématique dans les articles suivants.

I. Introduction

L’intégrité computationnelle est une propriété fondamentale sous-jacente au commerce. Dit plus simplement, cela signifie que le résultat d’un certain calcul est correct. C’est ce qui nous permet de faire confiance au solde de notre compte bancaire ou à la facture dans un magasin. A travers cet article nous expliquerons la façon dont les blockchains permissionless traditionelles arrivent à l’intégrité computationnelle sans nécessiter de confiance. Nous monterons cependant en quoi cela leur porte défault au niveau de leur scalabilité et de leur confidentialité et comment la technologie STARKs peut améliorer ça.

II. Confiance vs Vérification

Le « vieux monde » : Confiance ou responsabilité déléguée

Les systèmes financiers (banques, courtiers, bourses, etc.) doivent fonctionner avec intégrité pour remplir leurs fonctions sociétales. Mais quels sont les mécanismes qui les incitent à le faire ? «Le vieux monde » suppose la confiance comme substitut de l’intégrité. Nous faisons confiance aux banques, aux fonds de pension etc… d’oeuvrer honnêtement. Plongeons ensemble plus profondément et examinons les fondements de cette confiance, en ignorant le « théâtre de l’intégrité », les grands bâtiments et les costumes de fantaisie mis pour nous impressionner. D’un point de vue purement rationnel et utilitaire, ce qui empêche le système financier de saisir tous nos fonds, c’est la menace de la honte sociale et de la justice (prison, amendes…). Il y a aussi une incitation : la réputation, qui attire de futurs clients qui permettent de générer davantages de profits. En signant les rapports de gestion avec leur nom, les gens du « vieux monde » mettent en jeu leur liberté personnelle et leur capital existant et futur comme garantie d’intégrité, et nous, le public, fondons notre confiance sur cela. La vérification de cette intégrité est déléguée à des experts comme les comptables, les auditeurs et les organismes de réglementation. Ce n’est pas un mauvais système : il sert d’ailleurs fidèlement les économies modernes depuis longtemps.

Une nouvelle variante de l’approche du « vieux monde » est l’Environnement d'exécution de confiance (le TEE) . Un fabricant informatique de confiance (comme Intel) produit une machine physique (comme la puce SGX) qui ne peut pas s’écarter du calcul spécifié et signe les états corrects en utilisant une clé secrète connue uniquement de cette machine physique. L’intégrité est maintenant basée sur la confiance dans le matériel et son fabricant et sur l’hypothèse qu’il est impossible d’extraire les clés secrètes de ces dispositifs physiques.

Le « nouveau monde » : Vérification ou responsabilisation inclusive

Les blockchains offrent un moyen plus direct d’atteindre l’intégrité, grâce à la devise « Ne faites pas confiance, vérifiez ». Ce « nouveau monde » n’a pas besoin d’un théâtre d’intégrité, il ne dépend pas de comptables, et les développeurs et mainteneurs du réseau ne mettent pas en jeu leur liberté personnelle pour gagner la confiance du public. L’intégrité est garantie par la responsabilité inclusive : un nœud avec du matériel informatique standard (un ordinateur portable connecté à internet) devrait être en mesure de vérifier l’intégrité de toutes les transactions du système.

La méthode courante pour vérifier l’intégrité calculatoire dans les blockchains permissionless est la relecture naïve : tous les nœuds sont invités à ré-exécuter (rejouer) les calculs qui vérifient chaque transaction. La responsabilité inclusive, sous cette forme naïve, provoque deux problématiques immédiates :

La confidentialité : Si tout le monde peut inspecter toutes les transactions, la confidentialité peut être compromise. L’absence de protection de la vie privée dissuade les entreprises car elle signifie que les informations sensibles ne peuvent rester personnelles. Elle décourage aussi les individus, car elle érode la dignité humaine.

La scalabilité : Exiger que le système soit vérifiable par un simple ordinateur portable standard signifie qu’on ne peut pas faire grandir le réseau en utilisant de plus gros ordinateurs et une plus grande bande passante. Cela conduit inévitablement à une limitation sévère du débit du système.

Les systèmes de preuves (dont nous allons parler) sont une excellente solution à ces deux difficultés. Les systèmes de preuves à divulgation nulle de connaissances (Zero Knowledge proof) sont déjà un outil établi pour répondre à la problématique de la vie privée des blockchains ce qui est expliqué avec brillaut dans plusieurs articles de Zcash [1, 2, 3]. Bien que les ZK-STARKs ne dévoilent aucune connaissance (Zero Knowledge), nous n’aborderons pas le sujet dans cet article où nous nous concentrerons sur la scalabilité et la transparence (le S et le T dans STARK).

III. Les systèmes de preuves

Les systèmes de preuves ont commencé avec le système de preuve interactive (IP) introduit par Goldwasser, Micali et Rackoff en 1985. Les systèmes de preuves interactives sont des protocoles qui impliquent deux types d’entités : un prouveur et un vérifieur , qui interagissent sur un certain nombre de tours en envoyant des messages. Le prouveur et le vérifieur ont des objectifs opposés : le prouveur veut convaincre le vérifieur de l’intégrité d’un certain calcul, et le vérifieur est un contrôleur méfiant chargé par le public de distinguer le vrai du faux. Le prouveur et le vérifieur communiquent de façon interactive, en s’envoyant des messages à tour de rôle. Ces messages dépendent de l’affirmation prouvée, des messages antérieurs, et peuvent également utiliser un certain caractère aléatoire. Du côté du prouveur, le caractère aléatoire est utilisé pour atteindre la divulgation nulle de connaissance et du côté du vérifieur, le caractère aléatoire est nécessaire pour générer des requêtes au prouveur. À la fin du processus interactif, le vérifieur prend une décision, soit d’accepter le nouvel état, soit de le rejeter.

Une bonne analogie est la mise en examen pratiqué dans un tribunal lorsqu’une partie présente une affirmation et que sa contrepartie remet en question sa validité. Pour que l’affirmation soit considérée comme vraie, les réponses fournies par le plaignant (prouveur) aux questions de l’examinateur (vérifieur) doivent être cohérentes et valides. On s’attend à ce que la mise en examen révèle toutes les incompatibilités entre l’affirmation et la réalité, et donc qu’elle soit considérée comme fausse.

Nous disons qu’un système de preuve répond à l’intégrité calculatoire si lors de l’actualisation du système de l’état A à l’état B, les propriétés suivantes sont maintenues :

Completness : Si le prouveur sait en effet changer l’état de A à B de manière valide, alors le prouveur réussira à convaincre le vérifieur d’accepter le changement.

Soundness: Si le prouveur ne sait pas comment changer l’état de A à B, alors le vérifieur remarquera une incohérence dans l’interaction et rejettera la transition d’état suggérée. Il reste une faible probabilité de faux positifs, c’est-à-dire une probabilité que le vérifieur accepte une preuve invalide. Cette probabilité est un paramètre de sécurité système qui peut être réglé à un niveau acceptable comme 1/(2^128), similaire aux chances de gagner à l’Euromillion quatre fois de suite.

Ces deux propriétés ont une importance cruciale sur le principe de la responsabilité inclusive que nous avons évoqué plus tôt. Le vérifieur peut accepter le changement d’état suggérée par le prouveur sans faire de suppositions sur l’intégrité du prouveur. En fait, le prouveur peut fonctionner sur du matériel défectueux, il peut être une source fermée exécuté sur un ordinateur contrôlé par une entité malveillante. La seule chose qui importe¹ est que les messages envoyés par le prouveur amènent le vérifieur à accepter l’affirmation. Si tel est le cas, nous savons que l’intégrité calculatoire existe.

IV. STARK

À l’heure actuelle, il y a quelques constructions théoriques de systèmes de preuve, avec des implémentations. Certains sont déployés dans des cryptomonnaies, comme les SNARKs utilisés par Zerocash/Zcash, et Bulletproofs (BP) déployé dans Monero. (Pour des informations générales sur les systèmes de preuve aller ici.) Ce qui distingue STARKs est la combinaison des trois propriétés suivantes : la scalabilité (le S dans STARK), la transparence (le T dans STARK), et la légèreté de la cryptographie.

Scalabilité L’accélération exponentielle de la vérification

La scalabilité signifie que deux propriétés d’efficacité tiennent simultanément :

• La scalabilité du prouveur : Le temps nécessaire au prouveur est « presque linéaire » dans le temps qu’il faudrait à un ordinateur de confiance pour vérifier l’intégrité calculatoire en ré-exécutant simplement le calcul par lui-même et en vérifiant que le résultat correspond à ce que quelqu’un prétend. Le ratio du temps nécessaire pour produire une preuve sur le temps nécessaire pour simplement exécuter le calcul demeure raisonnablement faible.
• La scalabilité du vérifieur : Le temps d’exécution du vérifieur est polynômial dans le logarithme du temps de relecture naïf. En d’autres termes, le temps d’exécution du vérifieur est exponentiellement plus petit que simplement rejouer le calcul (rappelons que la « ré-exécution » est la méthode utilisée dans les blockchains actuelles pour atteindre la responsabilité inclusive).

Appliquer cette notion de scalabilité à une blockchain. Au lieu du mode actuel de vérification par lecture naïve, imaginez à quoi les choses vont ressembler quand une blockchain passera à la vérification en utilisant des systèmes de preuve. Au lieu de simplement envoyer les transactions pour les ajouter à la blockchain, un nœud de prouveur devra générer une preuve, mais grâce à la scalabilité du prouveur son temps d’exécution est presque linéaire au temps d’exécution de la solution par relecture naïve. Et la scalabilité du vérifieur permettra une diminution exponentielle de son temps de vérification. De plus, à mesure que le débit de la blockchain augmente, la majeure partie de l’effet sera supportée par les noeuds du prouveur (qui pourraient fonctionner sur du matériel dédié, comme les mineurs), tandis que les vérifieur , qui constitueraient la plupart des noeuds du réseau, ne seraient guère affectés.

Prenons un exemple hypothétique concret, en supposant que le temps du vérifieur (en millisecondes) évolue comme le carré du logarithme du nombre de transactions (tx). Supposons que nous commencions avec 10,000 tx/bloc. Le temps de fonctionnement du vérifieur est :

VTime *= (*log₂ 10,000)² ~ (13.2)² ~ 177 ms

Augmentez maintenant la taille du bloc par 100 (à 1,000,000 tx/bloc). Le nouveau temps de fonctionnement du vérifieur est :

VTime *= (*log₂ 1,000,000)² ~ 20² ~ 400 ms

En d’autres termes, une augmentation de 100x du débit de transaction n’a entraîné qu’une augmentation de 2,25x du temps d’exécution du vérifieur !

Dans certains cas, le vérifieur devra tout de même télécharger et vérifier la disponibilité des données, ce qui est un processus de temps linéaire, mais le téléchargement des données est généralement beaucoup moins coûteux et plus rapide que la vérification de sa validité.

Transparence : confiance envers personne, intégrité pour tous

La transparence² signifie qu’il n’y a pas besoin de configuration de confiance, il n’y a pas d’utilisation de secrets dans la mise en place du système. La transparence offre de nombreux avantages. Il élimine la procédure de génération de configuration des paramètres qui constitue une faille. L’absence d’une configuration de confiance permet même aux entités puissantes, les grandes sociétés, les monopoles et les gouvernements, qui contrôlent le système financier « de l’ancien monde » de prouver l’intégrité calculatoire et d’obtenir l’acceptation publique de leurs revendications parce qu’il n’y a aucun moyen connu de faire des preuves STARK de faussetés, même par les entités les plus puissantes. D’un point de vue plus tactique, il est beaucoup plus facile de déployer de nouveaux outils et de nouvelles infrastructures et de changer les outils existants sans avoir besoin de cérémonies élaborées de génération de paramètres. Plus important encore, la transparence s’harmonise bien avec le « nouveau monde » qui exige une responsabilité inclusive sans présomption de confiance. Pour paraphraser Abraham Lincoln, les systèmes transparents permettent d’opérer avec une confiance envers personne, mais une intégrité pour tous.

Cryptographie allégée : Sécurisé et rapide

La technologie STARK a des hypothèses cryptographiques minimales³ qui sous-tendent sa sécurité : l’existence de fonctions cryptographiques sécurisées et de hachage résistant aux collisions. Beaucoup de ces primitives existent aujourd’hui comme instructions matérielles, et la cryptographie allégée permet deux autres avantages :

• La sécurité post-quantique : les STARK sont vraisemblablement sécurisés contre les ordinateurs quantiques efficaces.
• Une efficacité concrète : Pour un calcul donné, le prouveur STARK est au moins 10x plus rapide que le prouveur SNARK et Bulletproofs. Le vérifieur STARK est au moins 2x plus rapide que le vérifieur SNARK et plus de 10x plus rapide que le vérifieur Bulletproof. Etant donnée que StarkWare continue d’optimiser les STARKs, ces ratios s’amélioreront probablement davantage. Cependant, la longueur d’une preuve STARK est ~100x plus grande que celle d’une SNARK et ~20x plus grande que celle d’une BulletProofs.

V. Résumé

Nous avons commencé par expliquer le « nouveau monde » des blockchains permissionless, où la devise est « Ne faites pas confiance, vérifiez ». Le principe de la responsabilité inclusive exige que l’intégrité du système financier soit facilement vérifiable par quiconque, par opposition à la responsabilité déléguée du « vieux monde ». Pour permettre aux blockchains d’exister à grande échelle, nous avons besoin de méthodes qui permettent de vérifier l’intégrité calculatoire plus rapidement que la relecture naïve utilisée dans les blockchains actuelles.

Les STARKs sont un type particulier de système de preuve qui permettent la scalabilité et la transparence, et sont basés sur de la cryptographie allégée. Leur scalabilité et leur transparence permet une vérification peu coûteuse et sans confiance de l’intégrité computationelle. C’est la promesse des STARKs et la mission de StarkWare.

Notre prochain article va aller un peu plus loin dans les mathématiques de la construction des STARKs. Merci à Vitalik Buterin et Arthur Breitman pour avoir relu le brouillon de ce post.

Michael Riabzev & Eli Ben-Sasson StarkWare Industries

. . .

¹La préservation de la confidentialité (ZK) impose des exigences au code du prouveur, afin de garantir que les messages du prouveur ne divulguent pas d'informations sur le témoin via des canaux secondaires. Mais la solidité ne nécessite aucune hypothèse de confiance.

²Formellement, un système de preuve transparent est un système dans lequel tous les messages du vérifieur sont des chaînes aléatoires publiques. De tels systèmes sont également connus sous le nom de protocoles Arthur-Merlin.

³Cette minimisation des hypothèses cryptographiques est valable pour les STARKs interactifs (iSTARKs). Les STARK non interactifs (nSTARK) requièrent l'heuristique de Fiat-Shamir, qui est différente.

Traduction faite par @Henri