Initialement publié en anglais par StarkWare le 17 avril, 2019

Combiner les preuves probabilistes et les fonctions de hachage

C’est le cinquième et dernier article de notre série STARK Math.

Dans notre premier article, nous avons introduit la notion de responsabilité inclusive, et son importance pour les blockchains permissionless. Nous avons également expliqué pourquoi les propriétés de scalabilité des STARKs permettent d’atteindre cette notion. Nous recommandons au lecteur de lire ce premier article avant de poursuivre.

Dans nos deuxième, troisième et quatrième articles, nous nous sommes plongés dans la théorie mathématique derrière STARKs. Nous avons expliqué comment transformer les déclarations computationnelles en contraintes polynomiales. Nous avons expliqué comment réduire la vérification des contraintes polynomiales à la vérification des faibles degrés. Et nous avons décrit un test efficace pour les faibles degrés. Ci-dessous, nous n’assumons pas une certaine familiarité avec ces articles, à l’exception d’une section qui explique comment les protocoles décrits dans ces articles peuvent être considérés comme un certain type de preuve probabiliste (dont les détails n’ont pas d’importance dans cet article). (c’est la trad mais alors la phrase est bizarre)

Dans cet article, nous concluons la série en revisitant la notion d’un STARK puis en expliquant comment construire un STARK à partir de preuves probabilistes et de fonctions de hachage cryptographique.

Notre objectif : des arguments scalable et transparents

Nous souhaitons construire un STARK, qui est une preuve cryptographique (aka un «argument») à la fois scalable et transparent. Notre premier article décrit en détail cet objectif, que nous résumons maintenant.

Nous considérons les preuves cryptographiques pour les programmes d’intégrité computationnelle (IC). Cela signifie que, pour un programme donné A, input x, output y et T lié dans le temps, nous voulons produire une chaîne de démonstration π attestant l’instruction

«A(x) output y à l’intérieur des étapes de calcul T.»

Aucune procédure (efficace) ne devrait être en mesure de produire des preuves d’apparence valide pour les fausses déclarations (p.ex, revendiquer A(x) =1 alors qu’au lieu de A(x) =0). Des déclarations CI plus générales sont possibles, où A prend en outre une entrée auxiliaire privée, mais nous l’ignorons dans ce post.

Les STARK sont des preuves cryptographiques qui répondent aux propriétés suivantes.

• Scalabilité : le temps nécessaire pour produire π est T·polylog*(T), alors que le temps nécessaire pour valider π est seulement polylog(T); en particulier, la longueur de π est polylog(T)*. En d’autres termes, produire des preuves n’est pas beaucoup plus coûteux que simplement exécuter le calcul original, et la validation des preuves est exponentiellement plus rapide que d’exécuter le calcul original. Les preuves sont exponentiellement plus courtes que la taille du calcul original.
• Transparence : les paramètres globaux du système des preuves cryptographiques, utilisés pour produire et valider les preuves, n’ont pas de trappes. Cela contraste avec les systèmes de preuve qui s’appuient sur une partie de confiance pour échantillonner des paramètres publics basés sur des informations secrètes, ce qui peut servir de « piège » pour compromettre la sécurité du système de preuve.

À la fin de cet article, vous aurez une compréhension informelle de l’origine des propriétés de scalabilité et de transparence.

Nous notons brièvement ici que les STARK utilisent uniquement la cryptographie symétrique légère (fonctions de hachage cryptographique), ce qui les rend rapides et (probablement) sécurisés post-quantique. Cela contraste avec beaucoup d’autres preuves cryptographiques, dont la sécurité repose sur une cryptographie à clé publique qui est à la fois coûteuse et peu sûre contre les adversaires quantiques.

Feuille de route pour ce poste

Les constructions STARK connues combinent deux ingrédients :

1. de longues preuves qui peuvent être vérifiable facilement, local checks et peu coûteuses (long proofs that can be verified via random, and inexpensive, local checks; and)
2. une fonction de hachage cryptographique telle que SHA-256 ou Keccak.

De manière informelle, le premier composant donne à un STARK sa scalabilité, tandis que le second donne à un STARK sa transparence (sans entraver la scalabilité). Dans les sections qui suivent, nous développons le plan ci-dessus.

• Tout d’abord, nous décrivons la construction Micali, une méthode de construction de preuves cryptographiques qui suit le schéma ci-dessus. Les systèmes de preuve qui sous-tendent cette construction sont connus sous le nom de probabilistes vérifiables (PCP). Nous décrivons cette construction pour des raisons pédagogiques: il s’agit d’un cas particulier élégant de la construction que nous utilisons.
• Deuxièmement, nous expliquons pourquoi la construction Micali assure la transparence et la scaalbilité.
• Troisièmement, nous décrivons la notion de Proofs Interactifs Oracle (IOPs), qui généralise les PCPs et permet de concevoir des protocoles beaucoup plus efficaces. Nous expliquons également comment les protocoles d’arithmétique et de test de faible degré dans les messages précédents sont des IOPs.
• Enfin, nous mentionnons la construction BCS, une extension de la construction Micali qui utilise la notion plus générale de IOPs au lieu de PCPs. Des STARK efficaces, y compris ceux que nous utilisons, sont obtenus par la construction BCS.

Preuves cryptographiques des PCPs, via la construction Micali

Dans cette section, nous présentons les probabilistically-checkable proofs (PCP), un type de système de preuve qui implique une vérification locale aléatoire à une longue preuve. Nous expliquons ensuite comment un PCP peut être combiné avec une cryptographie légère pour obtenir un STARK. Cette construction provient d’un article de Silvio Micali (construit sur des travaux antérieurs de Joe Kilian).

Une probabilistically-checkable proof (PCP) est un protocole entre un prouveur PCP et un vérifieur PCP qui permet d’établir l’exactitude des déclarations d’intégrité computationnelle (CI) par une vérification locale aléatoire à une preuve longue. Dans le cas d’un énoncé CI (A*,x,y,T*), le prouveur PCP produit un enchainement de preuve ψ qui «encode» la trace de calcul du programme CI. Alors que la preuve ψ est plus longue que la trace de calcul de l’étape-T (la longueur de ψ est quasi linéaire en T), ψ a la particularité remarquable de pouvoir être validée par un test probabiliste qui ne lit qu’une petite partie de ψ. C’est-à-dire, étant donné la même instruction CI (A,x,y,T), le vérifieur PCP peut valider ψ en lisant aléatoirement un petit nombre d’emplacements de ψ puis en exécutant un «contrôle local» peu coûteux sur les valeurs lues. (Le nombre d’emplacements de lecture peut être une petite constante, comme 3, indépendante de T!) Si l’énoncé d’CI est vrai, le vérifieur accepte toujours. Si, au contraire, l’instruction CI est faux, alors le vérifieur rejette avec une forte probabilité, indépendamment de la façon dont la chaîne de preuve ψ a été choisie. Voir la figure 2 pour un diagramme.

Rappelons que notre but est de produire des preuves π courtes et rapides à valider. C’est très différent des PCP, qui impliquent plutôt des contrôles locaux peu coûteux à des preuves longues. Alors, comment allons-nous de ψ à π?

Naturellement l’idée qui peut venir à l’esprit est de demander au prouveur de pré-échantillonner une vue locale de ψ, au nom du vérifieur, puis d’envoyer cette vue locale comme preuve π. De manière plus détaillée, le prouveur simule un contrôle local aléatoire du vérifieur PCP sur la preuve longue ψ et inclut ensuite dans une preuve π seulement les emplacements de ψ lus via ce contrôle local; le prouveur inclut également dans π le caractère aléatoire ρ utilisé pour le vérificateur PCP. (Notez que π est court parce que le nombre d’emplacements de lecture de ψ est petit.) L’intuition du pré-échantillonnage est que, pour valider π, on pourrait exécuter le vérifieur PCP avec le même aléatoire ρ, ce qui entraînerait la lecture des mêmes emplacements de ψ, qui ont été inclus dans π. Cette idée attrayante, cependant, est imparfaite. Tout d’abord, un étalon trompeur peut inclure dans π un choix «aléatoire» ρ qui, en fait, n’est pas aléatoire. Deuxièmement, un test de fraude peut choisir des réponses aux requêtes du vérifieur PCP qui dépendent de ρ afin de passer la vérification locale du vérificateur PCP. Ceci est possible parce que la sécurité d’un PCP repose sur l’immuabilité d’un PCP, c’est-à-dire fixé avant le choix de la vérification locale aléatoire du vérifieur.

Les problèmes ci-dessus peuvent être résolus en utilisant n’importe quelle fonction de hachage cryptographique H telle que SHA-256 (modélisée comme un oracle aléatoire), pour réaliser un pré-échantillonnage sécurisé. Ici, «sécurisé» signifie que le prouveur sera en mesure de convaincre le vérifieur que l’information incluse dans la preuve courte π est un contrôle local aléatoire «honnête» qui a été exécuté sur une preuve longue ψ.

De manière informelle, comme le montre la Figure 3, l’étalon doit utiliser la fonction de hachage H pour valider la longueur de la preuve ψ via un arbre de Merkle, puis calculer l’aléatoire ρ en utilisant H pour hacher la racine de l’arbre de Merkle. Ceci garantit que l’aléatoire ρ est «aléatoire» (puisque ρ est un résultat de la fonction de hachage H) et garantit également que ρ est choisi après que le prouveur se soit engagé à ψ. Maintenant, le prouveur peut effectuer un pré-échantillonnage comme décrit ci-dessus, à savoir, il simule un contrôle local aléatoire du vérifieur PCP sur le caractère aléatoire ρ, pour déterminer quels emplacements de ψ doivent être inclus dans π. Enfin, le proveur «decommits» aux emplacements choisis, en incluant dans π un chemin d’authentification pour chaque emplacement choisi (le chemin d’authentification d’un emplacement se compose des frères et sœurs des nœuds sur le chemin de l’emplacement à la racine). Les chemins d’authentification montrent que les valeurs revendiquées de ψ sont cohérentes avec la racine de Merkle et, en particulier, n’ont pas été choisies par l’étalon après que l’aléatoire ρ a été dérivé de la racine. Dans l’ensemble, la preuve courte π ne comprendra que la racine revendiquée de l’arbre Merkle, les valeurs revendiquées de ψ pour les emplacements sélectionnés, et les chemins d’authentification pour chacune de ces valeurs (par rapport à la racine). On peut alors valider π en vérifiant tous les chemins d’authentification des valeurs revendiquées par rapport à la racine, en dérivant à nouveau l’aléatoire ρ de la racine, et en vérifiant que le vérifieur PCP accepte les valeurs revendiquées lorsqu’il est exécuté avec l’aléatoire 𝛒.¹

Pour résumer, nous avons utilisé la fonction de hachage H pour réaliser un «pré-échantillonnage sécurisé» qui permet d’inclure dans la preuve courte π un contrôle local aléatoire unique de la preuve longue ψ.

[1] : Cette «justification» pour expliquer pourquoi le pré-échantillonnage sécurisé fonctionne n’est qu’une intuition, et l’obtention d’une preuve formelle de sécurité nécessite un certain travail. Par exemple, un testeur malveillant pourrait essayer de s’engager sur de nombreuses preuves différentes ψ à la recherche d’un choix «favorable» d’aléatoire ρ, puis inclure ce choix favorable dans π. Une preuve de sécurité devrait établir que ces prouveurs, et en fait tout prouveur efficace, seront défaillants avec une forte probabilité.

La transparence vient de la cryptographie

Une fonctionnalité importante de la construction Micali est que la seule cryptographie est nécessaire pour produire ou valider une courte preuve π qui est une fonction de hachage cryptographique H (par exemple SHA-256 ou Keccak). Le choix de H est donc le seul «paramètre global» que tous les utilisateurs du système de preuve doivent connaître, et ce choix peut se faire par l’information du public. Cela signifie que les preuves cryptographiques obtenues par la construction Micali sont transparentes.

Ce qui précède contraste avec d’autres preuves cryptographiques où la production ou la validation des preuves nécessite l’utilisation de paramètres globaux qui sont produits à partir d’informations secrètes. Pour ceux qui connaissent bien les preuves cryptographiques basées sur des paires, un exemple typique de paramètres globaux est

(G, 𝛂·G, 𝛂²·G, 𝛂³·G,...)

où G est un élément de groupe et α est un scalaire secret. Ces paramètres globaux doivent être échantillonnés par une partie de confiance, ou lors d’une multi-party ceremony, car les utilisateurs ne devraient pas connaître la « trappe » α. En effet, connaître α permettrait de produire des preuves d’apparence valide pour les fausses déclarations.

L’évolutivité vient de la preuve probabiliste

Une autre fonctionnalité importante de la construction Micali est que le temps de production/validation d’une courte preuve π est proche du temps de production/validation de d’une longue preuve ψ. Cela s’explique simplement par le fait que les opérations cryptographiques nécessaires sont peu coûteuses en comparaison aux opérations du PCP. Nous apprenons donc que l’efficacité de la construction Micali est essentiellement déterminée par l’efficacité du PCP sous-jacent. En particulier, si le PCP est scalable (la production de δ prend du temps quasi linéaire en T alors que la validation de δ est exponentiellement plus rapide), alors la construction de Micali fournit une preuve cryptographique évolutive. La construction de PCP modulables est connue (voir le présent document).

Malheureusement, le coût des PCP reste très élevé, ce qui les rend impropres à une utilisation pratique. Pour cette raison, les implémentations des STARsK ne sont pas basées sur des PCP via la construction Micali. Au lieu de cela, ils sont basés sur un autre type de preuve probabiliste, pour laquelle on peut atteindre une scalabilité, avec de bons coûts concret et même avec zero knowledge. Nous en reparlerons plus tard.

IOPs : une nouvelle notion de preuve probabiliste

Efficient STARKs est basé sur un type de système de preuve probabiliste connu sous le nom  interactive oracle proofs (IOPs)(preuves d’oracles interactives), qui a été introduit en 2015. De manière informelle, un prouveur et un vérifieur s’engagent dans un protocole interactif où, à chaque tour, le vérifieur envoie un certain aléa 𝛔ᵢ ****au prouveur, et le prouveur répond par une longue preuve 𝚿ᵢ. A la fin de l’interaction, le vérifieur effectue un contrôle local aléatoire sur toutes les longues preuves (𝚿₁,𝚿₂,...) envoyées par le prouveur tout au long de l’interaction. Voir la figure 4 pour un diagramme. Notez qu’un PCP est simplement un « IOP non interactif » et qu’il s’agit donc d’un cas restreint.

Au cours des dernières années, les chercheurs ont développé de nombreux principes de conception pour construire des IOP à haut rendement: [BCGV16], [BCGRS16], [BB+16], [BBGR16], [BCFGRS16], [BBBHR17], [BBHR18], [BCRSVW18], [BKS19], [BGKS19]. Le protocole IOP que nous utilisons dans nos constructions STARK est le plus proche de [BBHR18].

Les postes précédents décrivent un IOP efficace

Nous expliquons maintenant comment nos articles précédents sur l’arithmétique et les tests de faible degré décrivaient réellement un IOP efficace. La figure 5 présente un diagramme de cette IOP. La première phase du protocole est l’arithmétique, qui transforme l’instruction donnée de CI (A*,x,y,T*) en un problème qui implique l’établissement des limites de degré sur certains polynômes. La deuxième phase consiste en des essais à faible degré, qui résolvent ce dernier problème. Nous résumons le workflow du protocole.

Arithmétique (zone bleue de la figure 5). Le prouveur et le vérifieur transforment le programme A en un ensemble de contraintes polynomiales, comme décrit dans notre article Arithmetisation I. De plus, le prouveur exécute le calcul décrit par (A*,x,y,T*), obtenant une trace de calcul par T-step

Ensuite, comme décrit dans notre article Arithmetisation II, le prouveur encode cette trace pour obtenir une trace encodée Φ, qui est envoyée au vérifieur. (Dans ce cas, le prouveur n’a pas besoin de recevoir un caractère aléatoire de la part du vérifieur avant d’envoyer Φ.) Après cela, le vérifieur envoie l’aléatoire 𝛔₀ qui permet au prouveur et au vérifieur de «grouper» toutes les contraintes polynomiales en une seule contrainte polynomiale, en prenant leur combinaison linéaire aléatoire. Le prouveur combine cette dernière avec la trace encodée Φ afin d’obtenir un polynôme composé 𝚵 qui est envoyé au vérifieur. Le vérifieur s’assure, par un contrôle de cohérence local, que Φ et 𝚵 sont convenablement liés. A ce stade, si la vérification de cohérence locale réussit avec une probabilité élevée, l’instruction CI est vraie si et seulement si Φ et 𝚵 ont un faible degré .

Low-degree testing (zone grise de la figure 5). le prouveur utilise le protocole FRI (décrit dans notre article low-degree testing) pour convaincre le vérifieur que Φ et 𝚵 sont des évaluations de polynômes de faible degré. Ceci implique de s’engager dans un protocole où, à chaque tour, le vérifieur envoie une partie aléatoire 𝛔ᵢ et le prouveur répond avec une preuve auxiliaire 𝚿ᵢ, et à la fin du protocole, le vérifieur effectue un contrôle local aléatoire sur Φ,𝚵 et 𝚿ᵢ. Si le vérifieur du protocole FRI accepte avec une probabilité élevée, alors Φ et 𝚵 ont les degrés souhaités. Dans l’affirmative, le vérificateur conclut que l’énoncé d’CI (A*,x,y,T*) est un énoncé vrai.

Preuves cryptographiques via la construction BCS

Des STARKs efficaces sont obtenus par la construction BCS, une méthode qui combine un IOP avec une fonction de hachage cryptographique H afin d’obtenir une preuve cryptographique. Cette méthode est une extension de la construction Micali, et elle conserve ses caractéristiques (transparence et scalabilité) dont nous avons parlé plus haut. Dans cet article, nous ne décrivons pas la construction du BCS, mais nous remarquons seulement qu’elle peut être considérée comme une application de la construction Micali à chaque round d’un OIP et comme une chaîne de hachage des engagements de chaque ronde (qui maintient l’ordre des rounds).

Conclusion

Dans cet article, nous avons expliqué que des constructions STARK efficaces sont obtenues en combinant des IOPs efficaces (une sorte de preuve probabiliste) et des fonctions de hachage cryptographique. L’IOP confère au STARK sa scalabilité, tandis que la fonction de hachage confère au STARK sa transparence. Différentes constructions STARK diffèrent dans les IOPs sous-jacents, et nous avons expliqué comment nos articles précédents décrivaient les composants du protocole IOP utilisés dans notre construction STARK.

Ceci conclut notre série STARK Math. Nous espérons qu’il a été d’une grande valeur pour vous !

Alessandro Chiesa et Gideon Kaempfer

Traduction faite par @cleminso