Une analyse approfondie de la sécurité complète de STARK

Suivant : Sain et sauf — Une plongée en profondeur dans la sécurité STARK
Traduction et relecture : "Communauté chinoise Starknet"
Faits en bref
STARK non interactif est dérivé de preuves Oracle interactives (IOP), compilées en preuves non interactives dans le modèle Oracle stochastique.
Cet article explique les dernières mises à jour de la documentation ethSTARK et fournit une analyse complète et détaillée de la sécurité du protocole ethSTARK dans le modèle Oracle aléatoire.
Explication détaillée de la sécurité STARK
Le système de preuve STARK, ou argument de connaissance transparent et évolutif, est un outil puissant pour l'intégrité informatique : il permet une vérification sans confiance de l'exactitude des calculs effectués sur des données publiques. Dans cet article, nous allons plonger dans la sécurité fournie par les preuves STARK, les définir et explorer les techniques pour prouver la sécurité des schémas.
(Lisez la section 6 de la documentation ethSTARK (version 1.2) pour plus de détails, ainsi que le travail indépendant important et complet sur ce sujet réalisé par Block et al.)
Qu’essayons-nous de réaliser avec l’analyse de sécurité ? Nous voulons empêcher les « attaques réussies » contre le système STARK causées par une fausse déclaration et la preuve STARK acceptée par le validateur STARK en réponse à cette (fausse) déclaration. Parce que les fausses déclarations sont dangereuses et qu’elles peuvent prendre toutes les tailles et toutes les formes, nous voulons être en sécurité contre elles toutes. Toute fausse déclaration, même aussi triviale que 1+1=3, lorsqu'elle est combinée avec une preuve STARK acceptée par un validateur STARK, est considérée comme une attaque réussie contre le système. (Ceux qui ont une formation en cryptographie seront peut-être intéressés de savoir que STARK peut également satisfaire des concepts de sécurité plus forts tels que la fiabilité des connaissances, mais par souci de simplicité, cet article se concentrera sur le cas simple de la fiabilité).
Comment définit-on formellement la sécurité d’un système STARK ? Nous déterminons cela en analysant « l’erreur de fiabilité ». L'« erreur de fiabilité » mesure approximativement le « coût » attendu qu'il faudrait à un attaquant pour lancer une attaque réussie (c'est-à-dire trouver une preuve STARK pour une fausse déclaration acceptée par un validateur STARK). Mathématiquement parlant, l'erreur de fiabilité est une fonction (t) dont l'entrée est le paramètre de temps t, représentant le temps de calcul que l'attaquant est prêt à consacrer pour lancer une attaque, et la sortie est la probabilité que l'attaque de l'attaquant réussisse (trouvée pour fausses déclarations (preuve convaincante). Plus le « coût » t que l'attaquant est prêt à dépenser est élevé, plus sa probabilité de succès est élevée.
Jusqu’à présent, nous avons défini la sécurité de STARK comme une fonction (t), ce qui est différent de la façon dont la sécurité est discutée quotidiennement sur Twitter crypto. Sur Twitter, vous entendrez peut-être : « Cette solution comporte 96 bits de sécurité. » Comment cela se traduit-il dans notre définition de la sécurité ? Il n’y a pas de réponse unique à cette question, car les gens comprennent « x éléments de sécurité » de manière légèrement différente :
Interprété strictement, cela signifie que pour tout t compris entre 1 et 2⁹⁶, l'erreur de fiabilité est (t) 2⁹⁶ . Un attaquant qui court pour 2⁹⁶ ou moins a une très faible probabilité de succès, inférieure à 2⁹⁶, soit moins de 1 sur un milliard fois 1 sur un milliard.
Une interprétation plus vague, et peut-être plus courante, est que la sécurité 96 bits signifie que pour tout t, il existe un cas où t/(t) 2⁹⁶. Cela signifie que la probabilité de succès est (inversement) linéaire avec le temps d’exécution. Si l'attaquant a un temps d'exécution de 2⁸⁶, alors sa probabilité de succès est d'au plus 2¹⁰.
Dans cet article, nous aborderons la deuxième option.
De l'IOP à STARK avec une sécurité 96 bits
Alors, comment prouver qu’une solution possède 96 bits de sécurité ? Afin de répondre à cette question, nous devons comprendre la structure de haut niveau sur laquelle STARK est construit. STARK se compose de trois parties principales : IOP (Interactive Oracle Proof), l'arbre Merkle et le hachage Fiat-Shamir. Notre objectif principal est l'IOP ; Une fois ces composants spécifiés, nous pouvons les compiler pour produire un STARK. Nous aborderons ces composants en détail, y compris ce qu'ils sont et comment ils s'assemblent.
Le premier composant que nous examinerons est l'IOP : l'IOP est similaire à une preuve interactive standard, dans laquelle le prouveur et le validateur interagissent pendant plusieurs tours (nous sommes limités aux protocoles de pièces publics, où le validateur envoie uniquement des défis aléatoires au prouveur). Dans un IOP, le vérificateur ne lit pas entièrement le message du prouveur, mais échantillonne plutôt une petite partie des bits du message de chaque prouveur. C'est pourquoi STARK, compilé plus tard, atteint sa simplicité.
Compte tenu de l'IOP, comment puis-je construire un STARK à partir de celui-ci ? Les messages du prouveur peuvent être très longs (en fait, ils sont plus longs que le calcul lui-même). Pour compresser ces informations, nous utilisons des arbres Merkle. Un arbre Merkle est un arbre de hachage binaire dans lequel chaque nœud feuille représente une requête ou une réponse dans l'IOP. Les racines sont la promesse de tout le message. Lorsqu'un validateur souhaite lire un emplacement spécifique dans un message, le prouveur fournit la valeur de cet emplacement et le chemin de vérification. Le validateur peut ensuite utiliser ce chemin pour vérifier que la valeur est correcte. Le validateur IOP ne lit qu'une petite quantité d'informations de localisation à partir des informations du prouveur. Par conséquent, des protocoles concis (protocoles avec un faible volume de communication) peuvent être implémentés à l’aide d’arbres Merkle.
Tours compressés
Nous pouvons choisir un STARK interactif, mais pour simplifier le processus de génération de STARK, nous choisissons généralement un STARK non interactif afin que le validateur n'ait pas besoin d'attendre des informations externes lors de la construction de STARK. En fait, c'est ainsi que tous les systèmes STARK sont actuellement déployés et comment le protocole ethSTARK est construit. Les STARK non interactifs sont également un cas particulier de SNARK transparents (transparents signifie qu'aucune configuration fiable n'est requise pour les instancier ; "Arthur Merlin Protocol" ou "Public Coin IOP"). Pour ce faire, la dernière étape consiste à appliquer l’algorithme de Fiat-Shamir pour compresser plusieurs séries d’interactions en un seul message, que nous appelons une preuve STARK. La transformation Fiat-Shamir est une méthode de conversion d'un protocole interactif en un protocole non interactif. Le prouveur simule un protocole interactif tout en parlant à la fonction de hachage. Pour dériver le défi aléatoire du tour i, le prouveur hache l'enregistrement partiel du tour i et interprète le résultat comme le défi suivant.
Cela garantit que le prouveur ne peut pas modifier sa réponse une fois le défi généré. Cependant, les prouveurs de triche disposent de nouvelles pistes politiques qui ne sont pas disponibles dans les IOP interactives. Le prouveur peut régénérer le défi du validateur en modifiant les dernières informations du prouveur, afin qu'il obtienne un nouvel enregistrement et donc un nouveau défi. Il s'avère que les concepts de fiabilité standard de l'IOP ne suffisent pas à démontrer la sécurité de la conversion Fiat-Shamir.
Par exemple, ayez une IOP de 96 tours et ajoutez le hack suivant au validateur : Si le premier bit du caractère aléatoire du validateur est 0 à chacun des 96 tours, alors le validateur l'acceptera (sans voir aucune preuve). Nous pouvons voir que l'ajout de ce hack au validateur ne fait qu'ajouter un terme de 2⁹⁶ à l'erreur de fiabilité de l'IOP. Cependant, après la transformation Fiat-Shamir, un attaquant peut facilement modifier les informations du prouveur pour garantir que chaque valeur de hachage commence par 0, compromettant ainsi le système en très peu de temps. Rassurez-vous, ce scénario désastreux n’est qu’un exemple théorique et ne s’applique pas aux STARK déployés. Voyons donc pourquoi notre STARK est finalement sûr. En bref, nous montrerons que, pour un attaquant effectuant au plus t étapes, la probabilité de réussite de l'attaque est d'au plus (t) t 2⁹⁶.
IOP et fiabilité tour par tour
La sécurité de STARK dépend de ses IOP sous-jacentes. Mais qu’est-ce que cela signifie pour un IOP d’avoir 96 bits de sécurité ? Par définition standard, IOP a une erreur de fiabilité de 2⁹⁶ : cela signifie que la probabilité qu'un attaquant (quel que soit le temps d'exécution) puisse tromper un validateur est au maximum de 2 à 96. Cependant, comme nous l'avons vu, la fiabilité de l'IOP n'est qu'un des trois composants, ce qui n'est pas suffisant pour obtenir 96 bits de sécurité de STARK compilés à partir des trois étapes. En revanche, la sécurité de STARK compilé est prouvée en supposant que STARK présente une erreur de fiabilité tour par tour de 96 bits (une définition similaire appelée fiabilité de récupération d'état est parfois utilisée).
Intuitivement, la « solidité tour par tour » signifie que chaque tour possède 96 bits de sécurité, et pas seulement l'intégralité du protocole. Pour être plus précis, la fiabilité tour par tour fait référence à l'existence d'un prédicat qui peut obtenir une partie de l'enregistrement du protocole et nous dire si cet enregistrement est « trompeur » : « enregistrement vide » n'est pas « trompeur », et quand Et l'enregistrement complet n'est "trompeur" que s'il est accepté par le validateur. Enfin, pour tout enregistrement partiel qui n'usurpe pas le validateur, la probabilité que l'enregistrement devienne une « usurpation » au tour suivant est d'au plus 2⁹⁶. S'il existe un prédicat avec ces propriétés, on dit que le protocole a 96 bits de fiabilité tour par tour (ce prédicat ne nécessite pas de calcul efficace).
Dans de nombreux cas, les gens analysent uniquement la fiabilité de la PIO et non sa fiabilité globale. Certes, il est difficile de penser à un exemple (à l'exception des exemples fabriqués) d'IOP offrant une fiabilité standard mais pas une fiabilité totale. Cependant, lors du calcul de limites de sécurité spécifiques, des différences entre les deux peuvent apparaître et chaque élément compte. Par conséquent, pour dériver des limites étroites et spécifiques, une analyse rigoureuse de la fiabilité tour par tour de la PIO est nécessaire. C’est exactement ce que nous faisons avec le protocole FRI et l’ethSTARK IOP sur lequel est basé STARK IOP. L’analyse elle-même est loin d’être anodine et dépasse le cadre de cet article. Grâce à la nouvelle analyse, nous pouvons définir des paramètres précis pour notre preuve.
La fiabilité, tour après tour, nous donne réellement l’assurance dont nous avons besoin. Le prouveur peut régénérer le défi plusieurs fois, mais nous savons qu'à chaque tour, la probabilité de générer un enregistrement frauduleux est de 2⁹⁶. Par conséquent, si le prouveur a t fois (mesuré en nombre d'appels de hachage), alors il peut essayer. la plupart du temps t pour obtenir un enregistrement trompeur, ce qui limite sa probabilité de succès à (t) t 2⁹⁶.
Ajouter toutes les erreurs
Enfin, pour que tout cela soit vrai, nous devons nous assurer que le prouveur ne peut pas falsifier l’arbre de Merkle. Nous pouvons montrer que tant que le prouveur ne trouve aucune collision dans la fonction de hachage, il ne peut pas tricher dans l'arbre de Merkle. La probabilité qu'un attaquant trouve une collision à l'aide d'appels t (fonction de hachage aléatoire) est d'au plus t2/2, qui est la longueur de sortie de la fonction de hachage (causée par le « paradoxe de l'anniversaire »). fonction de hachage La longueur est le double de la sécurité requise. Donc, si nous avons une fonction de hachage avec une longueur de sortie de 192 et un IOP avec une fiabilité tour par tour de 96 bits, nous obtenons un STARK compilé qui est une erreur sexuelle fiable. (t)=t2-⁹⁶ + t2 2¹⁹⁶. Puisque t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, ce schéma a 95 bits de sécurité.
Résumer
Dans l’ensemble, STARK fournit une méthode puissante pour vérifier en toute confiance l’exactitude des calculs effectués sur les données publiques. La sécurité de STARK est généralement mesurée par « l'erreur de fiabilité », qui représente la probabilité qu'un attaquant réussisse à fournir une fausse déclaration et à convaincre le validateur avec une preuve. Afin d'atteindre un niveau de sécurité requis, tel que 96 bits, l'IOP sous-jacente doit être fiable tour par tour, garantissant qu'un niveau de sécurité élevé est maintenu à chaque tour. Nous avons analysé la fiabilité tour par tour des IOP sur lesquelles notre STARK est basé pour en déduire des limites de sécurité spécifiques.