Il y a quelque temps, je traduisais un livre sur la technologie à preuve de connaissance nulle. Le contenu de base a été traduit à la fin du mois dernier. La traduction a pris beaucoup plus de temps que prévu. Nous discutons actuellement de certaines erreurs matérielles dans le livre avec l'auteur et préparons la version finale.
Quoi qu'il en soit, j'ai enfin le temps de regarder quelque chose de nouveau. Commençons par l'algorithme Nova~
Informations relatives à l'algorithme Nova
Trois informations peuvent aider à comprendre l’algorithme Nova :
Papier Nova :
Nouvelles attaques potentielles et corrections correspondantes :
Résumé de la compréhension des attaques potentielles de Nova :
Cet article est une compréhension et un résumé des informations ci-dessus. **Certaines des images de cet article proviennent des informations ci-dessus et ne seront pas étiquetées une par une dans cet article. **
Commencez avec IVC
L'algorithme Nova est un nouvel algorithme de preuve de connaissance nulle pour IVC (Incrementally Verifiable Computation). IVC, c'est-à-dire que la même fonction calcule de manière itérative la sortie précédente comme entrée suivante. Le processus de calcul itératif de la fonction F est le suivant :
z0 est l'entrée initiale et le résultat généré par le calcul de la fonction F est utilisé comme entrée de la fonction F suivante.
Détendez-vous R1CS et Slack Commitment R1CS
Comme nous le savons tous, R1CS est une représentation des contraintes de circuit dans une technologie de preuve à connaissance nulle. Le R1CS détendu peut être considéré comme une forme étendue de R1CS. Sur la base de R1CS, un scalaire u et un vecteur d'erreur E sont ajoutés. Une instance de R1CS détendu est représentée par (E, u, x).
L'engagement détendu R1CS engage les vecteurs E et W sur la base du R1CS détendu. Une instance d'un engagement de relâchement R1CS est représentée par (\bar{E}, u, \bar{W}, x), où x et u sont des variables publiques.
Extension du R1CS au R1CS détendu pour le schéma de pliage. Notez que du point de vue du R1CS détendu, R1CS en est un cas particulier. En d’autres termes, le R1CS est aussi un R1CS slack « spécial ».
Schéma de pliage
Intuitivement parlant, un schéma de repliement pour une relation R consiste à « réduire » deux instances conformes à la relation R en une nouvelle instance de la relation composite R. Slack R1CS/Relax Commitment R1CS peut effectuer des plis similaires. Le processus de pliage est similaire pour les deux. Le schéma de pliage de Slack Commitment R1CS est le suivant :
L'ensemble du schéma de pliage se compose de 4 étapes. Dans la première étape, le prouveur P envoie un engagement \bar{T} de l’élément croisé T au vérificateur. Dans la deuxième étape, le vérificateur envoie un défi aléatoire r au prouveur. La troisième étape est la définition de l'engagement que le prouveur et le vérificateur doivent respecter. Dans la quatrième étape, le prouveur effectue seul et replie les vecteurs E et W des deux instances.
Fonction augmentée F' (Fonction Argumentée)
Schéma de réduction, l'instance R1CS réduite est assouplie. Alors, quels sont les calculs prouvés par ces exemples R1CS assouplis ? Ces calculs incluent évidemment des calculs de pliage. Ces calculs ne sont pas seulement la fonction F dans les calculs IVC, ils sont également appelés fonctions augmentées F'. Le calcul de la fonction augmentée F' se compose principalement de deux parties :
Fonction 1/F en IVC
2/ Calcul de pliage de l'instance R1CS
Look idéal
Avec la compréhension ci-dessus, vous pouvez imaginer le processus de pliage :
Parmi eux, circuit est le circuit correspondant à la fonction augmentée F'. acc{1,2,3,4,5,6} est une instance R1CS à engagement lâche. Le circuit a deux calculs : 1/Détendez le repliement de l'instance d'engagement R1CS, comme acc1+acc2->acc3. 2/Calculez la fonction F, en changeant l'état de l'état 1 à l'état 2, puis de l'état 2 à l'état 3, etc.
A noter que le circuit correspondant à la fonction augmentée F' est lui-même une instance R1CS, qui peut être exprimée comme une instance R1CS relâchée. C'est acc4 et acc6 sur la photo. "résumer" consiste à convertir une instance Slack R1CS en une instance Slack R1CS validée.
En regardant attentivement l'entrée du deuxième circuit, acc3 est l'instance R1CS à engagement détendu après le pliage, et acc4 est l'instance R1CS à engagement détendu qui prouve que acc3 est le résultat de pliage correct. Ces deux instances entreront dans le prochain repliement et généreront acc5. Vous pouvez imaginer que si acc3 et acc4 sont des instances R1CS d'engagement slack satisfiables, cela signifie que acc3 est plié à partir de deux instances R1CS d'engagement slack satisfiables. En d'autres termes, acc1 et acc2 sont des engagements slack satisfiables. Ce type de fiabilité peut être déduit « en avant » étape par étape, prouvant ainsi que le calcul de la fonction F dans chaque circuit est correct. En général, grâce à la satisfiabilité de deux instances R1CS d’engagement de relâchement correspondant à un certain circuit, tous les calculs IVC précédents peuvent s’avérer corrects.
Regard réel
Les amis qui connaissent les preuves sans connaissance savent que les courbes elliptiques sont souvent utilisées dans les schémas d'engagement polynomiaux. L'engagement polynomial correspondant sur le domaine scalaire est représenté par le domaine de base de la courbe elliptique. Les circuits R1CS sont généralement représentés par le domaine scalaire. Regardez attentivement, le « résumé » dans l'image ci-dessus implique une conversion de domaine. Autrement dit, si vous souhaitez replier l'instance R1CS d'engagement slack correspondant à un circuit, vous devez la "plier" dans un autre circuit. À ce stade, un cycle de courbe elliptique doit être introduit. Entre deux ou plusieurs courbes elliptiques, le domaine scalaire d'une courbe est le même que le domaine de base de l'autre courbe. Par coïncidence, le domaine scalaire de cette courbe est le même que le domaine de base de la courbe précédente. En utilisant une telle boucle de courbe elliptique, le « look idéal » peut être réalisé :
L'ensemble du processus de pliage est divisé en deux circuits de pliage. La partie supérieure peut être appelée le pli du Circuit 1, et la partie inférieure peut être appelée le pli du Circuit 2. Une représentation formelle de la relation entre les deux circuits se trouve à la page 8 du document « Attaques potentielles contre Nova et corrections correspondantes ». U représente l'instance pliée et u représente l'instance détendue correspondant à une instance R1CS. Notez que le circuit 1 réduit l'instance R1CS d'engagement slack correspondant au circuit 2, tandis que le circuit 2 réduit l'instance R1CS d'engagement slack correspondant au circuit 1. L'objectif principal du circuit 2 est de réduire l'instance R1CS d'engagement de marge correspondant au circuit 1, et le calcul de la fonction dans son circuit n'a aucun sens. Au lieu de cela, la fonction F est implémentée dans le circuit 1. Combiné avec "l'apparence idéale", nous pouvons approximativement deviner la satisfiabilité de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 est une partie importante de la preuve.
Parce que le "circuit" est coupé en deux parties, et le circuit respectif est replié dans l'autre circuit. Il existe plusieurs problèmes de liaison entre les instances : la liaison entre les instances u et U et la liaison des instances u passant entre deux circuits. Afin de résoudre ces problèmes de liaison, des variables publiques x_0/x_1 sont introduites dans le circuit, où x_1 spécifie l'instance U de sortie du circuit liée à l'instance u et la sortie de la fonction F actuelle (afin de simplifier la structure du circuit, ce qui n'est pas reflété dans la figure). Vous pensez que si le résultat H_1 de l'instance U est introduit dans le circuit, si l'instance u est satisfiable, x_0/x_1 est à la fois réel et fiable, c'est-à-dire qu'il est "lié" à U. x_0 établit la relation de liaison entre l'entrée u et U, et x_1 établit la relation de liaison entre la sortie u et U.
Par exemple, lorsque u{i+1}^1 est utilisé comme entrée de la seconde moitié du circuit, il passe par le circuit 2 et sa sortie u{i+1}^2.x0 = u{i+1 }^1.x1, donc, lors de l'entrée dans la partie supérieure du circuit, si u{i+1}^2 peut être satisfait, alors son x_0 doit être égal au résultat de H1 de U_{i +1}^2. Ceci est vérifié dans le circuit 1. De cette façon, il est garanti que la bonne instance est transmise entre les deux circuits.
Preuve d'IVC
Afin de prouver qu'IVC est calculé correctement dans une certaine itération, les informations suivantes doivent être prouvées logiquement :
En plus de prouver que quatre instances peuvent être satisfaites, il est également nécessaire de prouver la relation de liaison entre deux x1, comme le montre la figure suivante :
La question de savoir si ces informations sont correctes nécessite la mise en œuvre d'un circuit de preuve supplémentaire. Autrement dit, la preuve du calcul IVC est une preuve du circuit. Il est concevable que s'il s'agit d'un calcul avec de nombreuses itérations, ces itérations doivent à l'origine être effectuées dans le circuit une par une, mais maintenant seules quatre instances de circuit doivent être vérifiées pour la satisfiabilité et les relations de liaison. L’amélioration des performances est énorme.
Correction des attaques et des algorithmes
En voyant l'image ci-dessus, j'ai une intuition : je sens que les instances des circuits supérieur et inférieur sont "séparées" et n'ont aucune liaison. En fait, c’est ainsi que l’attaque est structurée.
Les U_i^1 et U{i+1}^2 forgés, bien qu'ils soient forgés, sont des instances satisfiables. Forgez u{i+1}^1, modifiez x_0 et x_1 pour correspondre à l'instance U forgée. Évidemment, l'instance u{i+1}^1 n'est pas satisfaite. Bien qu'il ne soit pas satisfait, le circuit du circuit 2 peut toujours être satisfait, mais l'instance de sortie U{i+1}^1 n'est pas satisfaite. Si u{i+1}^2 est construit avec succès, le circuit 1 peut construire u{i+2}^1 et U_{i+2}^2 satisfaisants, et satisfaire la relation de liaison de x1. De cette façon, la moitié de la preuve finale de contrefaçon est construite en premier. Grâce à la symétrie, l'instance de sortie de la moitié inférieure peut être construite. En « épissant » les résultats des deux constructions, la preuve du calcul IVC peut être falsifiée.
La logique de contrôle révisée est la suivante :
Le chapitre 6 du document « Attaques potentielles sur Nova et correctifs correspondants » fournit une analyse détaillée de la sécurité. Les amis intéressés peuvent vérifier eux-mêmes le papier original.
L'idée de base de Nova est de replier les instances de circuits via un schéma de repliement. La logique est plutôt alambiquée et nécessite une réflexion approfondie sur le processus de repliement du circuit et les relations de liaison dans le circuit.
Un mot pour le décrire : Absolu~
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
Progrès révolutionnaire dans la technologie de preuve à connaissance nulle : une exploration approfondie de l'algorithme Nova
Il y a quelque temps, je traduisais un livre sur la technologie à preuve de connaissance nulle. Le contenu de base a été traduit à la fin du mois dernier. La traduction a pris beaucoup plus de temps que prévu. Nous discutons actuellement de certaines erreurs matérielles dans le livre avec l'auteur et préparons la version finale.
Quoi qu'il en soit, j'ai enfin le temps de regarder quelque chose de nouveau. Commençons par l'algorithme Nova~
Informations relatives à l'algorithme Nova
Trois informations peuvent aider à comprendre l’algorithme Nova :
Cet article est une compréhension et un résumé des informations ci-dessus. **Certaines des images de cet article proviennent des informations ci-dessus et ne seront pas étiquetées une par une dans cet article. **
Commencez avec IVC
L'algorithme Nova est un nouvel algorithme de preuve de connaissance nulle pour IVC (Incrementally Verifiable Computation). IVC, c'est-à-dire que la même fonction calcule de manière itérative la sortie précédente comme entrée suivante. Le processus de calcul itératif de la fonction F est le suivant :
z0 est l'entrée initiale et le résultat généré par le calcul de la fonction F est utilisé comme entrée de la fonction F suivante.
Détendez-vous R1CS et Slack Commitment R1CS
Comme nous le savons tous, R1CS est une représentation des contraintes de circuit dans une technologie de preuve à connaissance nulle. Le R1CS détendu peut être considéré comme une forme étendue de R1CS. Sur la base de R1CS, un scalaire u et un vecteur d'erreur E sont ajoutés. Une instance de R1CS détendu est représentée par (E, u, x).
L'engagement détendu R1CS engage les vecteurs E et W sur la base du R1CS détendu. Une instance d'un engagement de relâchement R1CS est représentée par (\bar{E}, u, \bar{W}, x), où x et u sont des variables publiques.
Extension du R1CS au R1CS détendu pour le schéma de pliage. Notez que du point de vue du R1CS détendu, R1CS en est un cas particulier. En d’autres termes, le R1CS est aussi un R1CS slack « spécial ».
Schéma de pliage
Intuitivement parlant, un schéma de repliement pour une relation R consiste à « réduire » deux instances conformes à la relation R en une nouvelle instance de la relation composite R. Slack R1CS/Relax Commitment R1CS peut effectuer des plis similaires. Le processus de pliage est similaire pour les deux. Le schéma de pliage de Slack Commitment R1CS est le suivant :
L'ensemble du schéma de pliage se compose de 4 étapes. Dans la première étape, le prouveur P envoie un engagement \bar{T} de l’élément croisé T au vérificateur. Dans la deuxième étape, le vérificateur envoie un défi aléatoire r au prouveur. La troisième étape est la définition de l'engagement que le prouveur et le vérificateur doivent respecter. Dans la quatrième étape, le prouveur effectue seul et replie les vecteurs E et W des deux instances.
Fonction augmentée F' (Fonction Argumentée)
Schéma de réduction, l'instance R1CS réduite est assouplie. Alors, quels sont les calculs prouvés par ces exemples R1CS assouplis ? Ces calculs incluent évidemment des calculs de pliage. Ces calculs ne sont pas seulement la fonction F dans les calculs IVC, ils sont également appelés fonctions augmentées F'. Le calcul de la fonction augmentée F' se compose principalement de deux parties :
Fonction 1/F en IVC
2/ Calcul de pliage de l'instance R1CS
Look idéal
Avec la compréhension ci-dessus, vous pouvez imaginer le processus de pliage :
Parmi eux, circuit est le circuit correspondant à la fonction augmentée F'. acc{1,2,3,4,5,6} est une instance R1CS à engagement lâche. Le circuit a deux calculs : 1/Détendez le repliement de l'instance d'engagement R1CS, comme acc1+acc2->acc3. 2/Calculez la fonction F, en changeant l'état de l'état 1 à l'état 2, puis de l'état 2 à l'état 3, etc.
A noter que le circuit correspondant à la fonction augmentée F' est lui-même une instance R1CS, qui peut être exprimée comme une instance R1CS relâchée. C'est acc4 et acc6 sur la photo. "résumer" consiste à convertir une instance Slack R1CS en une instance Slack R1CS validée.
En regardant attentivement l'entrée du deuxième circuit, acc3 est l'instance R1CS à engagement détendu après le pliage, et acc4 est l'instance R1CS à engagement détendu qui prouve que acc3 est le résultat de pliage correct. Ces deux instances entreront dans le prochain repliement et généreront acc5. Vous pouvez imaginer que si acc3 et acc4 sont des instances R1CS d'engagement slack satisfiables, cela signifie que acc3 est plié à partir de deux instances R1CS d'engagement slack satisfiables. En d'autres termes, acc1 et acc2 sont des engagements slack satisfiables. Ce type de fiabilité peut être déduit « en avant » étape par étape, prouvant ainsi que le calcul de la fonction F dans chaque circuit est correct. En général, grâce à la satisfiabilité de deux instances R1CS d’engagement de relâchement correspondant à un certain circuit, tous les calculs IVC précédents peuvent s’avérer corrects.
Regard réel
Les amis qui connaissent les preuves sans connaissance savent que les courbes elliptiques sont souvent utilisées dans les schémas d'engagement polynomiaux. L'engagement polynomial correspondant sur le domaine scalaire est représenté par le domaine de base de la courbe elliptique. Les circuits R1CS sont généralement représentés par le domaine scalaire. Regardez attentivement, le « résumé » dans l'image ci-dessus implique une conversion de domaine. Autrement dit, si vous souhaitez replier l'instance R1CS d'engagement slack correspondant à un circuit, vous devez la "plier" dans un autre circuit. À ce stade, un cycle de courbe elliptique doit être introduit. Entre deux ou plusieurs courbes elliptiques, le domaine scalaire d'une courbe est le même que le domaine de base de l'autre courbe. Par coïncidence, le domaine scalaire de cette courbe est le même que le domaine de base de la courbe précédente. En utilisant une telle boucle de courbe elliptique, le « look idéal » peut être réalisé :
L'ensemble du processus de pliage est divisé en deux circuits de pliage. La partie supérieure peut être appelée le pli du Circuit 1, et la partie inférieure peut être appelée le pli du Circuit 2. Une représentation formelle de la relation entre les deux circuits se trouve à la page 8 du document « Attaques potentielles contre Nova et corrections correspondantes ». U représente l'instance pliée et u représente l'instance détendue correspondant à une instance R1CS. Notez que le circuit 1 réduit l'instance R1CS d'engagement slack correspondant au circuit 2, tandis que le circuit 2 réduit l'instance R1CS d'engagement slack correspondant au circuit 1. L'objectif principal du circuit 2 est de réduire l'instance R1CS d'engagement de marge correspondant au circuit 1, et le calcul de la fonction dans son circuit n'a aucun sens. Au lieu de cela, la fonction F est implémentée dans le circuit 1. Combiné avec "l'apparence idéale", nous pouvons approximativement deviner la satisfiabilité de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 est une partie importante de la preuve.
Parce que le "circuit" est coupé en deux parties, et le circuit respectif est replié dans l'autre circuit. Il existe plusieurs problèmes de liaison entre les instances : la liaison entre les instances u et U et la liaison des instances u passant entre deux circuits. Afin de résoudre ces problèmes de liaison, des variables publiques x_0/x_1 sont introduites dans le circuit, où x_1 spécifie l'instance U de sortie du circuit liée à l'instance u et la sortie de la fonction F actuelle (afin de simplifier la structure du circuit, ce qui n'est pas reflété dans la figure). Vous pensez que si le résultat H_1 de l'instance U est introduit dans le circuit, si l'instance u est satisfiable, x_0/x_1 est à la fois réel et fiable, c'est-à-dire qu'il est "lié" à U. x_0 établit la relation de liaison entre l'entrée u et U, et x_1 établit la relation de liaison entre la sortie u et U.
Par exemple, lorsque u{i+1}^1 est utilisé comme entrée de la seconde moitié du circuit, il passe par le circuit 2 et sa sortie u{i+1}^2.x0 = u{i+1 }^1.x1, donc, lors de l'entrée dans la partie supérieure du circuit, si u{i+1}^2 peut être satisfait, alors son x_0 doit être égal au résultat de H1 de U_{i +1}^2. Ceci est vérifié dans le circuit 1. De cette façon, il est garanti que la bonne instance est transmise entre les deux circuits.
Preuve d'IVC
Afin de prouver qu'IVC est calculé correctement dans une certaine itération, les informations suivantes doivent être prouvées logiquement :
En plus de prouver que quatre instances peuvent être satisfaites, il est également nécessaire de prouver la relation de liaison entre deux x1, comme le montre la figure suivante :
La question de savoir si ces informations sont correctes nécessite la mise en œuvre d'un circuit de preuve supplémentaire. Autrement dit, la preuve du calcul IVC est une preuve du circuit. Il est concevable que s'il s'agit d'un calcul avec de nombreuses itérations, ces itérations doivent à l'origine être effectuées dans le circuit une par une, mais maintenant seules quatre instances de circuit doivent être vérifiées pour la satisfiabilité et les relations de liaison. L’amélioration des performances est énorme.
Correction des attaques et des algorithmes
En voyant l'image ci-dessus, j'ai une intuition : je sens que les instances des circuits supérieur et inférieur sont "séparées" et n'ont aucune liaison. En fait, c’est ainsi que l’attaque est structurée.
Les U_i^1 et U{i+1}^2 forgés, bien qu'ils soient forgés, sont des instances satisfiables. Forgez u{i+1}^1, modifiez x_0 et x_1 pour correspondre à l'instance U forgée. Évidemment, l'instance u{i+1}^1 n'est pas satisfaite. Bien qu'il ne soit pas satisfait, le circuit du circuit 2 peut toujours être satisfait, mais l'instance de sortie U{i+1}^1 n'est pas satisfaite. Si u{i+1}^2 est construit avec succès, le circuit 1 peut construire u{i+2}^1 et U_{i+2}^2 satisfaisants, et satisfaire la relation de liaison de x1. De cette façon, la moitié de la preuve finale de contrefaçon est construite en premier. Grâce à la symétrie, l'instance de sortie de la moitié inférieure peut être construite. En « épissant » les résultats des deux constructions, la preuve du calcul IVC peut être falsifiée.
La logique de contrôle révisée est la suivante :
Le chapitre 6 du document « Attaques potentielles sur Nova et correctifs correspondants » fournit une analyse détaillée de la sécurité. Les amis intéressés peuvent vérifier eux-mêmes le papier original.
L'idée de base de Nova est de replier les instances de circuits via un schéma de repliement. La logique est plutôt alambiquée et nécessite une réflexion approfondie sur le processus de repliement du circuit et les relations de liaison dans le circuit.
Un mot pour le décrire : Absolu~