Wiki du cours

Rédacteur: [Laurane Marco]

A traiter [Modifier]

Le but de ce sujet est d'expliquer la procédure de vérification d'un zk-SNARK. (Il faut probablement se baser sur [2], décrire le formalisme de [1] en détail risque d'être indigeste...)

• Contenu de l'argument de connaissance.
• Vérification du fait que les polynômes de l'argument sont des combinaison linéaires des polynômes élémentaires.
• Vérification du fait que les polynômes de l'argument ont les mêmes coefficients.
• Vérification de la divisibilité QAP.
• Comment masquer la solution (divulgation nulle de connaissance, voir la référence [3], partie VI).

Références [Modifier]

[1] Craig Gentry, Jon Howell, Bryan Parno, Mariana Raykova, Pinocchio, nearly practical verfiable computations, Section 2.3 (3.1)
[2] Vitalik Buterin, Zk-SNARKs: Under the hood
[3] Ariel Gabizon, Explaining zk-SNARKs

Introduction [Modifier]

On a la solution d'un QAP donné par un ensemble de polynômes \((A,B,C)\) vérifiant \(A(x)\cdot B(x)-C(x) = H(x)\cdot Z(x)\).
Afin de construire l'argument de connaissance, on part d'un ensemble de données publiques construit au préalable appelé trusted setup.

Trusted setup

Il contient les données suivantes:

• les polynômes \(A_1\), ... , \(A_m\), \(B_1\),..., \(B_m\), \(C_1\),..., \(C_m\) définis par la donnée du problème
• le polynôme \( Z \)
• des points \((G\cdot A_i(t), G\cdot A_i(t)\cdot k_a)\), \((G\cdot B_i(t), G\cdot B_i(t)\cdot k_b)\), \((G\cdot C_i(t), G\cdot C_i(t)\cdot k_c)\) pour \(i=1,...,m\) où \(G\) est un point sur une courbe elliptique qui est spécifié par le protocole
• \(G\cdot Z(t) \)
• les points \(G,G\cdot t,G\cdot t^2, G\cdot t^3,...\), le nombre exact de termes dépendant du setup, par exemple, pour Zcash on a besoin d'en calculer environ 2 millions.
• les points \(G\cdot (A_i(t)+B_i(t)+C_i(t))\cdot b\) pour \(i=1,...,m\)

Par ailleurs, dans le processus de création de ces données on a utilisé les valeurs \(k_a, k_b, k_c, t ,b\) qui sont appelées toxic waste et doivent absolument être supprimées sous peine de voir n'importe qui être capable de créer une fausse preuve.

Contenu de l'argument de connaissance [Modifier]

Le prouveur veut montrer qu'il connait \((A,B,C)\) solution du QAP qui est une combinaison linéaire spécifique des \(A_i\), \(B_i\) et \(C_i\),\(i=1,...,m\). Dans des cas réels \(A\),\(B\) et \(C\) sont très grands et au lieu d'expliciter la combinaison linéaire, on va prouver que c'est bien une combinaison linéaire qui vérifie la propriété souhaitée (i.e. \(A(x)\cdot B(x)-C(x) = H(x)\cdot Z(x)\)) sans révéler plus d'information.
La construction de l'argument de connaissance se déroule de la façon suivante.

Etape 1 : A l'aide des \((G\cdot A_i(t), G\cdot A_i(t)\cdot k_a)\), \((G\cdot B_i(t), G\cdot B_i(t)\cdot k_b)\), \((G\cdot C_i(t), G\cdot C_i(t)\cdot k_c)\), \(i=1,...,m\) , il calcule :

• \(π_a= G\cdot A(t)\) et \(π'_a= G\cdot A(t)\cdot k_a\)
• \(π_b= G\cdot B(t)\) et \(π'_b= G\cdot B(t)\cdot k_b\)
• \(π_c= G\cdot C(t)\) et \(π'_c= G\cdot C(t)\cdot k_c\)

Etape 2 : A l'aide des \(G\cdot A_i(t), G\cdot B_i(t), G\cdot C_i(t) \), \(i=1,...,m\) il calcule la combinaison linéaire \(G\cdot(A(t)+B(t)+C(t))\) et \(G\cdot(A(t)+B(t)+C(t))\cdot b\).

Etape 3 : A l'aide des \(G,G\cdot t, G\cdot t^2, G\cdot t^3,...\) il calcule \(π_h=G\cdot H(t) \) pour la solution du QAP.

Etape 4: Il transmet \(π_a,π_b,π_c, G\cdot (A(t)+B(t)+C(t)), G\cdot (A(t)+B(t)+C(t))\cdot b, π_h\) au vérificateur.

Vérification de l'argument de connaissance [Modifier]

Il s'agit ici de vérifier trois points : Les polynômes \(A\),\(B\) et \(C\) sont bien des combinaisons linéaires des polynômes élémentaires, ils ont bien les mêmes coefficients et ils vérifient la divisibilité QAP i.e. \(A(x)\cdot B(x)-C(x) = H(x)\cdot Z(x)\).

Pour cela on va utiliser l'hypothèse knowledge of exponent et une propriété du couplage :

• Hypothèse: Pour un adversaire \(\mathcal{A}\) qui prend pour argument \(q, G, a\cdot G\), où \(q\) est la caractéristique du corps et retourne \((C,Y)\) tel que \(Y=a\cdot C\), il existe un extracteur \(\overline{\mathcal{A}}\) qui étant donné le même argument que \(\mathcal{A}\) retourne \(c\) tel que \(c\cdot G=C\) (voir Sujet 31)
• Etant donné P,Q,R,S tel que \(P=k\cdot Q\), on peut vérifier que \(R=k\cdot S\) en vérifiant que \(e(R,Q)=e(P,S)\).

Etape 1 : Pour vérifier que \(A\) est une combinaison linéaire des\(A_i\), on vérifie que \(e(π_a, G\cdot k_a )=e(G, π'_a)\). On fait de même pour \(B\) et \(C\).

Etape 2 : Pour vérifier que les polynômes de l'argument ont les mêmes coefficients, on fait également une vérification grâce au couplage, on vérifie que \(e(A(t)+B(t)+C(t),G\cdot b )=e(G\cdot (A_i(t)+B_i(t)+C_i/t))\cdot b, G)\)

Etape 3 : On veut vérifier que \(A(x)\cdot B(x)-C(x)=H(x)\cdot Z(x)\). La encore, on utilise le couplage: on vérifie que \(e(π_a,π_b)/(e(π_c,G)=e(π_h,G\cdot Z(t))\), si c'est le cas on a bien la divisibilité est vérifiée

Si les 3 points sont tous vérifiés et uniquement dans ce cas le vérificateur accepte la preuve.

Comment masquer la solution ? [Modifier]

On ne veut pas que notre preuve donne d'information sur les polynômes \(A\),\(B\) et \(C\), on va donc ajouter un décalage aléatoire proportionnel à Z à chaque polynôme. C'est-à-dire on choisit \(∂_a, ∂_b, ∂_c\) entiers et on définit \(\tilde{A}=A+∂_a\cdot Z, \tilde{B}=B+∂_b\cdot Z, \tilde{C}=C+∂_c \cdot Z\).
Etant donné que \(A\),\(B\) et \(C\) étaient solution de notre QAP, i.e. \(A\cdot B - C=Z\cdot H\) on a que \(\tilde{A}, \tilde{B}, \tilde{C}\) le sont aussi :
\( \tilde{A}\cdot \tilde{B}-\tilde{C}=(A+∂_a\cdot Z)(B+∂_b\cdot Z)-(C+∂_c \cdot Z)\)
\(= A\cdot B-C +A\cdot ∂_b\cdot Z +∂_a\cdot Z\cdot B +∂_a\cdot ∂_b\cdot Z^2- ∂_c \cdot Z\)
\(= Z\cdot(H+A\cdot ∂_b +∂_a\cdot B +∂_a\cdot ∂_b\cdot Z- ∂_c)\) 
\(= Z\cdot \tilde{H}\)
avec \(\tilde{H}=H+A\cdot ∂_b +∂_a\cdot B + ∂_a\cdot ∂_b\cdot Z- ∂_c\).

Donc si on utilise tout le long de la prevue les polynômes modifiés, le vérificateur acceptera la preuve. Cependant, ces polynômes modifiés évalués en un \(t\) tel que \(Z(t)≠0\) ne révèlent aucune information sur les polynômes originaux \(A\),\(B\) et \(C\). Etant donné que \(∂_i, i=a,b,c\) est aléatoire et \(Z(t)≠0\), on a que \(∂_i\cdot Z(t)\) est aléatoire aussi et donc \(A(t)+∂_a\cdot Z(t)\), resp. \(B(t)+∂_b\cdot Z(t), C(t)+∂_c\cdot Z(t)\) ne donne pas d'informations sur \(A\), resp. \(B\) et \(C\). Ils sont masqués par cette valeur aléatoire.