Explication des SNARKs Partie VII : Couplages de Courbes Elliptiques

Ariel Gabizon | Jun 07, 2017

<< Partie VI

Dans la partie VI, nous avons vu un aperçu de zk-SNARK Pinocchio. Il nous manquait deux choses : un HH qui supporte à la fois l'addition et la multiplication nécessaires aux vérifications du vérificateur, et une transition d'un protocole interactif à un système de preuve non interactive.

Dans cette publication, nous verrons qu'en utilisant des courbes elliptiques, nous pouvons obtenir une forme de HH limitée, mais suffisante pour nos besoins, qui supporte la multiplication. Nous montrerons ensuite que cette HH limitée suffit également à convertir notre protocole en système non interactif souhaité.

Nous commencerons par introduire les courbes elliptiques et par expliquer comment elles nous donnent la HH nécessaire.

Courbes elliptiques et leurs couplages

Supposons que \(p\) soit un nombre premier supérieur à \(3\), et prenons \(u,v\in\mathbb{F}_p\) tel que \(4u^3+27v^2\neq 0\). Regardons l'équation

\(Y^2=X^3 +u\cdot X +v\)

Une courbe elliptique \({\mathcal C}\) est l'ensemble des points \((x,y)\) [1] qui satisfont une telle équation. Ces courbes nous donnent un moyen intéressant de construire des groupes. Les éléments du groupe seront les points \((x,y)\in \mathbb{F}^2_p\) qui sont sur la courbe, c'est-à-dire qui satisfont l'équation, avec un point spécial \({\mathcal O}\), qui, pour des raisons techniques, est parfois appelé  « point à l'infini », et qui sert d'élément d'identité, c'est-à-dire le zéro du groupe.

La question est maintenant de savoir comment ajouter deux points \(P=(x_1,y_1),Q=(x_2,y_2)\) pour en obtenir un troisième. La règle de l’addition provient de quelque chose d’un peu abstrait appelé le groupe des classes de diviseurs de la courbe. Pour nos besoins, tout ce que vous devez savoir sur ce groupe des classes de diviseurs est qu'il impose la contrainte suivante à la définition de l'addition : La somme des points sur n'importe quelle ligne doit être nulle, c'est-à-dire \({\mathcal O}\).

Voyons comment la règle d'addition est dérivée de cette contrainte. Regardez une ligne verticale, définie par une équation de la forme \(X=c\). Supposons que cette ligne coupe la courbe à un point \(P=(x_1,y_1)\). Étant donné que l'équation de la courbe est de la forme \(Y^2=f(X)\), si \((x_1,y_1)\) est sur la courbe, c’est également le cas du point \(Q:=(x_1,-y_1)\). En outre, étant donné qu'il s'agit d'une ligne verticale et que l'équation de la courbe est de degré deux dans \(Y\), nous pouvons être sûrs que ce sont les seuls points où la ligne et la courbe se croisent.

Test |P+Q=O --> P=-Q|

Ainsi, nous devons avoir \(P+Q={\mathcal O}\), ce qui signifie que \(P=-Q\) ; c'est-à-dire que \(Q\) est l'inverse de \(P\) dans le groupe.

Regardons maintenant les points \(P\) et \(Q\) qui ont une première coordonnée différente - à savoir \(x_1\neq x_2\), et voyons comment les additionner. Nous faisons passer une ligne par \(P\) et \(Q\).

Test |P+Q+R=0|

Puisque la courbe est définie par un polynôme de degré trois en \(X\) et coupe déjà cette ligne (non verticale) en deux points, elle est assurée de couper la ligne en un troisième point, que nous désignons par \(R=(x,y)\), et aucun autre point.

Nous devons donc avoir \(P+Q+R={\mathcal O}\), ce qui signifie que \(P+Q=-R\); et nous savons maintenant que \(-R\) est obtenu à partir de \(R\) en faisant basculer la deuxième coordonnée de \(y\) à \(-y\).

Ainsi, nous avons dérivé la règle d'addition pour notre groupe : Points donnés \(P\) et \(Q\), faire passer une ligne par eux, puis prendre le point « miroir » du troisième point d'intersection de la ligne en tant que résultat de l'addition. [2]

Ce groupe est généralement appelé \({\mathcal C}(\mathbb{F}_p)\) - car il se compose de points sur la courbe \({\mathcal C}\) avec des coordonnées dans \(\mathbb{F}_p\); mais désignons-le par \(G_1\) à partir de maintenant. Supposons pour simplifier que le nombre d'éléments dans \(G_1\) est un nombre premier \(r\) , et qu’il est différent de \(p\). C'est souvent le cas, par exemple dans la courbe que Zcash utilise actuellement. Dans ce cas, tout élément \(g\in G_1\) différent de \({\mathcal O}\) génère \(G_1\).

Le plus petit entier \(k\) tel que \(r\) divise \(p^k-1\) s'appelle le degré d'intégration de la courbe. Nous émettons l’hypothèse que lorsque \(k\) n'est pas trop petit, disons, au moins \(6\), alors le problème de logarithme discret dans \(G_1\), c'est-à-dire trouver \(\alpha\) à partir de \(g\) et \(\alpha \cdot g\), est très difficile. (Dans les courbes BN [3] actuellement utilisées par Zcash \(k=12\)).

Le groupe multiplicatif de \(\mathbb{F}_{p^k}\) contient un sous-groupe d’ordre \(r\) que nous désignons \(G_T\). Nous pouvons regarder les points de la courbe avec des coordonnées dans \(\mathbb{F}_{p^k}\) et pas seulement dans \(\mathbb{F}_p\). Avec la même règle d'addition, ces points forment également un groupe avec \({\mathcal O}\) appelé \({\mathcal C}(\mathbb{F}_{p^k})\). Notez que \({\mathcal C}(\mathbb{F}_{p^k})\) contient clairement \(G_1\). Outre \(G_1\), \({\mathcal C}(\mathbb{F}_{p^k})\) contiendra un sous-groupe supplémentaire \(G_2\) d’ordre \(r\) (en fait, \(r-1\) sous-groupes supplémentaires d’ordre \(r\)).

Fixer les générateurs \(g\in G_1,h\in G_2\). Il s'avère qu'il existe une carte efficace, appelée Couplage Réduit de Tate, mettant un couple d'éléments de \(G_1\) et \(G_1\) dans un élément de \(G_T\),

tel que

  1. \(\mathrm{Tate}(g,h)=\mathbf{g}\) pour un générateur \(\mathbf{g}\) de \(G_T\), et
  2. étant donné un couple d'éléments \(a,b \in \mathbb{F}_r\), nous avons \(\mathrm{Tate}(a\cdot g,b\cdot h)=\mathbf{g}^{ab}\).

Définir Tate dépasse le cadre de cette série d’articles, et s'appuie sur des concepts de  géométrie algébrique, en particulier celui des diviseurs. Voici un croquis de la définition de \(\mathrm{Tate}\) : [4]

Pour \(a\in\mathbb{F}_p\), le polynôme \((X-a)^r\) a un zéro de multiplicité \(r\) au point \(a\), et aucun autre zéro. Pour un point \(P\in G_1\), les diviseurs nous permettent de prouver qu'il existe une fonction \(f_P\) de la courbe à \(\mathbb{F}_p\) qui a également, dans un sens précis, un zéro de multiplicité \(r\) à \(P\) et aucun autre zéro. \(\mathrm{Tate}(P,Q)\) est alors défini comme \(f_P(Q)^{(p^k-1)/r}\).

Il n’est pas forcément évident de comprendre ce que cette définition a à voir avec les propriétés indiquées, et en effet, la preuve que \(\mathrm{Tate}\) possède ces propriétés est assez complexe. En définissant \(E_1(x) := x\cdot g, E_2(x):=x\cdot h, E(x):=x\cdot \mathbf{g}\), on obtient une version faible d'une HH qui supporte à la fois l'addition et la multiplication : \(E_1,E_2,E\) sont des HH qui supportent l'addition et connaissant les valeurs cachées \(E_1(x)\), \(E_2(y)\) nous pouvons calculer \(E(xy)\). En d'autres termes, si nous avons les « bonnes » valeurs cachées de \(x\) et \(y\), nous pouvons obtenir une valeur cachée (différente) de \(xy\). Mais, par exemple, si nous avions des valeurs cachées de \(x,y,z\) nous ne pourrions pas obtenir de valeur cachée de \(xyz\).

Passons maintenant aux systèmes de preuve non interactive. Commençons par expliquer exactement ce que nous entendons par « non interactive ».

Preuves non-interactives dans le modèle de chaîne de référence commune

La notion la plus forte et la plus intuitive d'une preuve non interactive est probablement la suivante. Afin de prouver une certaine affirmation, un prouveur diffuse un message unique à toutes les parties, sans communication préalable de quelque sorte que ce soit ; et toute personne lisant ce message serait convaincue de l’affirmation du prouveur. Cela peut sembler impossible dans la plupart des cas. [5]

Une notion légèrement plus souple de la preuve non interactive est de permettre une chaîne de référence commune (En anglais, Common Reference String : CRS). Dans le modèle CRS, avant que des preuves ne soient construites, il y a une phase de préparation dans laquelle une chaîne est construite selon un certain processus aléatoire et diffusée à toutes les parties. Cette chaîne est appelée CRS et est ensuite utilisée pour aider à construire et à vérifier les preuves. L'hypothèse est que le caractère aléatoire utilisé dans la création de la CRS n'est connu d'aucune partie, car la connaissance de ce caractère aléatoire pourrait permettre de construire des preuves de fausses affirmations.

Nous allons expliquer comment, dans le modèle CRS, nous pouvons convertir le protocole d'évaluation aveugle vérifiable de la Partie IV en un système de preuve non interactive. Étant donné que le protocole de la Partie VI consistait en quelques sous-protocoles de ce type, il peut être transformé en un système de preuve non interactive d'une manière similaire.

Protocole d'évaluation non-interactive

La version non interactive du protocole d'évaluation consiste essentiellement à publier le premier message de Bob en tant que CRS. Rappelons que le but du protocole est d'obtenir la valeur cachée \(E(P(s))\) du polynôme \(P\) d'Alice à un \(s\in\mathbb{F}_r\) choisi au hasard.

Configuration: \(\alpha\in \mathbb{F}_r^*,s\in\mathbb{F}_r\) sont choisis au hasard et la CRS :

\((E_1(1),E_1(s),\ldots,E_1(s^d),\) \(E_2(\alpha),E_2(\alpha s),\ldots,E_2(\alpha s^d))\)
est publiée.

Preuve : Alice calcule \(a=E_1(P(s))\) et \(b=E_2(\alpha P(S))\) en utilisant les éléments de la CRS et le fait que \(E_1\) et \(E_2\) supportent des combinaisons linéaires.

Verification: Fix the \(x,y\in \mathbb{F}_r\) tel que \(a=E_1(x)\) and \(b=E_2(y)\). Bob computes \(E(\alpha x)=\mathrm{Tate}(E_1(x),E_2(\alpha))\) and \(E(y)=\mathrm{Tate}(E_1(1),E_2(y))\), and checks that they are equal. (If they are equal it implies \(\alpha x =y\).)

Comme expliqué dans la partie IV, Alice peut seulement construire \(a,b\) qui passe le contrôle de vérification si \(a\) est la valeur cachée de \(P(s)\) pour un polynôme \(P\) de degré \(d\) connu d’elle. La principale différence ici est que Bob n'a pas besoin de connaître \(\alpha\) pour la vérification, car il peut utiliser la fonction de couplage pour calculer \(E(\alpha x)\) uniquement à partir de \(E_1(x)\) et \(E_2(\alpha)\). Ainsi, il n'a pas besoin de construire et d'envoyer le premier message lui-même, et ce message peut simplement être corrigé dans la CRS.

[1]Vous vous demandez peut-être  « L'ensemble des points d'où ?». Nous voulons dire par là l'ensemble des points avec des coordonnées dans la clôture algébrique de \(\mathbb{F}_p\). En outre, la courbe a une version affine et une version projective. Lorsque nous parlons de la version projective, nous incluons également le « point à l'infini » \({\mathcal O}\) comme élément de la courbe.
[2]Nous n'avons pas abordé le cas de l'ajout de \(P\) à lui-même. Cela se fait en utilisant la ligne qui est tangente à la courbe à \(P\) et en prenant \(R\) comme deuxième point d'intersection de cette ligne avec la courbe.
[3]https://eprint.iacr.org/2005/133.pdf
[4]Le couplage utilisé par Zcash est le couplage optimal Ate, basé sur le couplage réduit de Tate, et peut être calculé plus efficacement que \(\mathrm{Tate}\).
[5]En termes de théorie de la complexité, on peut montrer que seules les langages en BPP ont des preuves à divulgation nulle de connaissance non interactives dans ce sens. Le type d’affirmations que nous devons prouver dans les transactions Zcash, par ex. « Je connais une préimage du hachage de cette chaîne », correspond à la classe de complexité NP qui est censée être beaucoup plus grande que BPP.
[6]Les images utilisées ont été tirées de cet article et sont utilisées dans le cadre de la licence Creative Commons.

cryptographie, zkSNARKs, explicatifs | Afficher tous les mots-clés

Notice: Network Upgrade Overwinter will activate at block 347500, to be mined 2018-06-25 12:00 UTC-04:00 assuming 150 seconds/block