Initialement publié en anglais par StarkWare le 05 Octobre 2023.

Découvrez l'analyse complète de la sécurité des STARKs.

TLDR

• Les STARKs non interactifs commencent comme des Preuves Oracle Interactives (IOPs) qui sont ensuite compilées en versions non interactives dans le modèle d'oracle aléatoire.

• Cet article explique la récente mise à jour de la documentation ethSTARK, qui fournit une analyse complète et concrète de la sécurité du protocole ethSTARK dans le modèle d'oracle aléatoire.

Explication de la sécurité des STARK

Un système de preuve STARK (Scalable Transparent Argument of Knowledge) est un outil puissant pour garantir l'intégrité des calculs effectués sur des données publiques sans nécessiter de confiance. Dans cet article, nous explorons la sécurité offerte par les preuves STARK en définissant le concept et en explorant les techniques pour prouver la sécurité du schéma.

(Pour tous les détails, veuillez consulter la section 6 de la documentation ethSTARK (version 1.2) ainsi que le travail indépendant et complet de Block et al. sur le sujet.)

Quel est notre objectif avec cette analyse de sécurité ? Nous cherchons à prévenir une "attaque réussie" sur le système STARK, qui se produit lorsque nous avons une fausse déclaration et une preuve STARK acceptée par le vérificateur STARK pour cette (fausse) déclaration. Étant donné que les fausses déclarations peuvent prendre différentes formes et tailles, nous voulons être protégés contre toutes les fausses déclarations. Toute fausse déclaration, aussi simple que 1+1=3, combinée à une preuve STARK acceptée par un vérificateur STARK pour cette déclaration, est considérée comme une attaque réussie sur le système. (Les personnes ayant des connaissances cryptographiques seront intéressées de savoir que les STARKs satisfont également des notions de sécurité plus fortes, telles que la propriété de knowledge soundness, mais pour simplifier, cet article se concentre sur le cas plus simple de la justesse.)

Comment définissons-nous formellement la sécurité d'un système STARK ? Nous le faisons en analysant “soundness error”, qui mesure approximativement le "coût" attendu qu'un attaquant devrait dépenser pour construire une attaque réussie (c'est-à-dire trouver une preuve STARK pour une fausse déclaration qui est néanmoins acceptée par le vérificateur STARK). Mathématiquement, soundness error est une fonction (t) qui prend en entrée un paramètre de temps "t", représentant la quantité de temps de calcul qu'un attaquant est prêt à dépenser pour monter l'attaque, et retourne la probabilité de succès de l'attaquant pour réussir l'attaque (trouver une preuve convaincante d'une fausse déclaration). À mesure que le "coût" (t) que l'attaquant est prêt à dépenser augmente, sa probabilité de succès augmente également.

Jusqu'à présent, nous avons défini la sécurité des STARKs comme une fonction (t), ce qui n'est pas la manière dont vous discutez naturellement de la sécurité, disons, sur le Twitter crypto. Là-bas, vous avez probablement entendu des déclarations du type "Le schéma a 96 bits de sécurité". Comment cette déclaration se traduit-elle dans notre définition de sécurité ? Il n'y a pas de réponse unique car les gens ont des interprétations légèrement différentes de "x bits de sécurité" :

• Une traduction très stricte signifierait que pour tout (t) entre 1 et 2⁹⁶, l'erreur de justesse est (t)2⁹⁶. Cela signifie que tout temps d'exécution d'attaque inférieur ou égal à 2⁹⁶ a une probabilité de succès extrêmement faible, inférieure à 2⁹⁶, ce qui est inférieur à une chance sur un milliard de milliards de milliards.

• Une traduction plus souple, et peut-être plus courante, est que 96 bits de sécurité signifient que pour tout (t), il est valable que t/(t) 2⁹⁶. Cela signifie que la probabilité de succès décroît de manière inversement linéaire par rapport au temps d'exécution. Par exemple, si un attaquant a un temps d'exécution de 2⁸⁶, sa probabilité de succès est au plus 2¹⁰.

Dans cet article, nous nous référerons à la deuxième option.

Des IOP aux STARK avec une Sécurité de 96 Bits

Comment prouvons-nous qu'un schéma a une sécurité de 96 bits ? Pour répondre à cela, nous devons comprendre la structure globale de la construction des STARKs.

STARK est composé de trois éléments principaux : un IOP (une preuve oracle interactive), un arbre de Merkle et un hachage Fiat-Shamir. Le composant principal sur lequel nous nous concentrerons est l'IOP. Une fois ces éléments spécifiés, ils peuvent être compilés pour obtenir STARK. Nous allons expliquer ces éléments plus en détail, ce qu'ils sont et comment les assembler.

Le premier élément que nous examinerons est l'IOP : Il ressemble à une preuve interactive classique, où un prover et un verifier interagissent pendant plusieurs tours (nous nous limitons aux protocoles à public coin, où le verifier envoie uniquement des défis aléatoires au prover). Dans un IOP, le verifier ne lit pas entièrement les messages du prover, mais échantillonne plutôt un petit nombre de bits de chaque message du prover. C'est ce qui permet la concision du STARK compilé par la suite.

Maintenant que nous avons un IOP, comment construire STARK à partir de celui-ci ? Les messages du prover pourraient être longs (en réalité, ils sont plus longs que le calcul lui-même). Pour compresser les messages, nous utilisons des arbres de Merkle. Un arbre de Merkle est un arbre de hachage binaire où chaque nœud feuille représente une requête ou une réponse dans l'IOP. La racine de l'arbre est un engagement envers l'ensemble du message. Lorsque le vérificateur souhaite lire un emplacement spécifique dans un message, le prover fournit la valeur à cet emplacement ainsi qu'un chemin d'authentification. Le vérificateur peut ensuite utiliser le chemin pour vérifier que la valeur est correcte. Le vérificateur IOP ne lit qu'un petit nombre d'emplacements des messages du prover. Ainsi, l'utilisation d'un arbre de Merkle permet d'obtenir un protocole succinct (avec une petite communication).

Compression des tours

On peut choisir d'utiliser des STARKs interactifs, ce qui signifie qu'il est souvent pratique de les rendre non interactifs afin de simplifier le processus de génération, de sorte que le prover n'ait pas besoin d'attendre des messages externes lors de leur construction. En effet, c'est ainsi que tous les systèmes STARK sont actuellement déployés, y compris le protocole ethSTARK. Les STARKs non interactifs sont également un cas particulier des SNARKs transparents (la transparence signifie qu'aucune configuration de confiance n'est nécessaire pour les instancier ; cela est également connu sous le nom de "protocole Arthur Merlin" ou de "IOP à public coin"). Dans cette optique, une étape finale consiste à appliquer Fiat-Shamir pour compresser les tours en un seul message, que nous appellerons la Preuve STARK. La transformation Fiat-Shamir convertit un protocole interactif en un protocole non interactif. Le prover simule le protocole interactif tout en "parlant à une fonction de hachage". Pour dériver le défi aléatoire pour le tour i, le prover hache le transcript partiel jusqu'au tour i, et interprète la sortie comme le prochain défi.

Cela garantit que le prover ne peut pas modifier ses réponses après que le défi ait été généré. Cependant, le prover tricheur dispose de nouvelles stratégies qu'il n'avait pas avec l'IOP interactif. Le prover peut régénérer le défi du vérificateur en modifiant le dernier message du prouveur, ce qui donnerait un nouveau transcript, et donc un nouveau défi également. Il s'avère que la notion de justesse standard des IOPs ne suffit pas à prouver la sécurité de la transformation Fiat-Shamir.

Par exemple, considérons un IOP avec 96 tours avec le "hack" suivant pour le verifier : si le premier bit de l'aléa du verifier est 0 lors de chacun des 96 tours, alors le vérificateur accepte (sans regarder la preuve du tout). On peut voir qu'ajouter ce hack au vérificateur n'ajoute qu'un terme de 2⁹⁶ à l'erreur de justesse de l'IOP. Cependant, après la transformation Fiat-Shamir, un attaquant peut facilement modifier les messages du prover pour s'assurer que chaque hachage commence par un zéro, brisant essentiellement le système en très peu de temps. Soyez rassuré, ce scénario effrayant est simplement un exemple théorique, et ne s'applique pas aux STARKs déployés. Alors, voyons pourquoi nos STARKs sont finalement sécurisés ? En un mot, nous montrerons qu'un attaquant exécutant au plus t étapes réussira à attaquer avec une probabilité au plus ((t) t 2⁹⁶. Les détails suivent.

Par exemple, considérez un IOP avec 96 rounds et la "faille" suivante pour le verifier : si le premier bit de la séquence aléatoire du verifier est 0 dans chacun des 96 rounds, alors le verifier accepte (sans même examiner la preuve). On peut constater que l'ajout de cette faille au verifier n'ajoute qu'un terme de 2⁹⁶ à soundness error de l'IOP. Cependant, après la transformation Fiat-Shamir, un attaquant peut facilement modifier les messages du prover pour s'assurer que chaque hachage commence par un zéro, ce qui revient essentiellement à compromettre le système en très peu de temps. Soyez rassuré, ce scénario effrayant n'est qu'un exemple théorique, il ne s'applique pas aux STARKs déployés. Alors, voyons pourquoi nos STARKs sont sécurisés malgré tout ? En résumé, nous montrerons qu'un attaquant qui effectue au plus t étapes réussira à attaquer avec une probabilité d'au plus (t) t 2⁹⁶. Les détails suivent.

IOPs et justesse Tour par Tour

La sécurité d'un STARK dépend de la sécurité de son IOP sous-jacent. Mais que signifie-t-il pour un IOP d'avoir une sécurité de 96 bits ? Selon la définition standard, cela signifie que l'IOP a une soundness error de 2⁹⁶ : cela signifie que la probabilité pour n'importe quel attaquant (indépendamment du temps d'exécution) de tromper le verifier est au plus de 2–96. Cependant, comme nous l'avons discuté précédemment, la justesse de l'IOP n'est qu'un des trois composants nécessaires pour obtenir une sécurité de 96 bits pour le STARK compilé à partir de ces trois étapes. Au lieu de cela, la sécurité du STARK compilé est prouvée en supposant que le STARK a une soundness error tour par tour de 96 bits (parfois appelée state-restoration soundness).

Intuitivement, la justesse tour par tour signifie que chaque tour a une sécurité de 96 bits, et pas seulement le protocole global. Plus précisément, la justesse tour par tour indique qu'il existe un prédicat qui prend en entrée un transcrit partiel du protocole et nous indique si ce transcrit est "trompeur" : le transcrit vide n'est pas "trompeur", un transcrit complet est "trompeur" si et seulement si le vérificateur l'accepte. Enfin, pour tout transcrit partiel qui n'est pas un transcrit trompeur pour le vérificateur, la probabilité qu'au tour suivant le transcrit devienne "trompeur" est au plus de 2⁹⁶. Si un tel prédicat existe avec ces propriétés, nous disons que le protocole a une justesse tour par tour de 96 bits (le prédicat n'est pas nécessairement calculable efficacement).

Dans de nombreux cas, seule soundness d'un IOP est analysée et non la soundness tour par tour. Il est difficile de penser à des exemples où un IOP a une soundness standard et non une soundness tour par tour (sauf dans des exemples artificiels). Cependant, les différences entre les deux pourraient apparaître lors de la dérivation de limites de sécurité concrètes où chaque bit compte. Ainsi, pour obtenir des limites précises et concrètes, il est nécessaire de donner une analyse précise d’une soundness tour par tour de l'IOP. C'est précisément ce que nous faisons pour le protocole FRI, puis pour l'IOP ethSTARK qui sous-tend l'IOP de nos STARKs. L'analyse elle-même est complexe et dépasse le cadre de cet article. Grâce à cette nouvelle analyse, nous pouvons définir des paramètres précis pour nos preuves.

Soundness tour par tour nous donne la garantie souhaitée. Le prover peut régénérer le défi plusieurs fois, mais nous savons que pour n'importe quel tour, la probabilité de générer un transcrit "trompeur" est de 2⁹⁶. Ainsi, si le prover prend un temps t, mesuré en nombre d'invocations de hachage, alors il peut essayer au plus t fois d'obtenir un transcrit trompeur, ce qui limite sa probabilité de succès à (t) t 2⁹.

Ajout de tous les Termes d'erreur

Enfin, pour que tout cela soit valable, nous devons nous assurer que le prover ne peut pas altérer l'arbre de Merkle. On peut montrer que tant que le prover ne trouve pas de collision dans la fonction de hachage, il ne peut pas tricher dans l'arbre de Merkle. La probabilité qu'un attaquant trouve une collision en utilisant t invocations (à une fonction de hachage aléatoire) est au plus de t2/2, où est la longueur de sortie de la fonction de hachage (ceci est dû au "paradoxe des anniversaires"). C'est pourquoi nous devons définir la fonction de hachage pour avoir une longueur qui est le double de la sécurité désirée. Ainsi, si nous avons une fonction de hachage avec une longueur de sortie de 192 et un IOP avec une justesse tour par tour de 96 bits, nous obtenons un STARK compilé avec une soundness error (t)=t2-⁹⁶ + t2 2¹⁹. En particulier, un tel schéma a 95 bits de sécurité puisque t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵.

Résumé

En conclusion, les STARKs offrent une méthode puissante pour vérifier la justesse des calculs effectués sur des données publiques de manière sans confiance. La sécurité des STARKs est généralement mesurée en termes “soundness error”, qui représente la probabilité qu'un attaquant fournisse avec succès une fausse déclaration et convainque le vérificateur avec une preuve. Pour atteindre un niveau de sécurité souhaité, tel que 96 bits, l'IOP sous-jacent doit satisfaire à la soundness tour par tour, garantissant que chaque tour maintient un niveau de sécurité élevé. Nous avons analysé soundness tour par tour de l'IOP sous-jacent à nos STARKs, ce qui nous a permis de dériver des limites de sécurité concrètes.