Wiki du cours

Rédacteur: Léo Morino

A traiter [edit]

Le but de ce sujet est d'expliquer la préparation d'un zk-SNARK.

• Hypothèses pour la sécurité du zk-SNARK. (Assumption 1 of Appendix 4 of [1]: expliquer informellement, knowledge of exponent, cf. [2]: expliquer informellement également.)
• Idée de base: Comment prouver qu'un point d'une courbe elliptique est une combinaison linéaire de points donnés [2].
• Clé d'évaluation publique et clé de vérification publique ("trusted setup"), toxic waste [2].

Introduction [edit]

Prenons une personne que nous appellerons client par la suite qui souhaite réaliser des calculs compliqués et celle-ci n'arrive pas à les réaliser seule. Pour palier à ce problème, le client va demander à une autre personne (plus compétente) de réaliser les calculs à sa place. On la nommera le travailleur. Le travailleur va ensuite de son coté réaliser les opérations. Ainsi, le résultat obtenu est donné au client. Cependant, le client et d'autres personnes aimeraient avoir un moyen de vérifier la véracité du résultat pour se protéger des travailleurs malhonnêtes ou malintentionnés. Cette vérification permet aussi aux travailleur de se dégager de toutes responsabilités. Il faut donc trouver un moyen pour que toutes personnes ait la possibilité de vérifier l'exactitude du résultat. Pour cela, le travailleur va, en plus du résultat, envoyer une preuve de l'exactitude de la solution.

Hypothèses pour la sécurité du zk-SNARK [edit]

Pour permettre une mise en œuvre du système zk-SNARK en toute sécurité, nous allons définir des hypothèses de dureté :

1. L'hypothèse de la q-puissance de Diffie-Hellman.
2. L'hypothèse de la q-force de Diffie-Hellman.
3. L'hypothèse de la connaissance de l'exposant.

Plaçons nous dans sur une courbe elliptique pour comprendre ces hypothèses.

Soit \(E\) une courbe elliptique sur un corps \(K\) donné.

La première hypothèse (q-PDH) nous dit que si nous connaissons un certain nombre de multiple d'un point donné alors il est difficile de connaître le prochain multiple.

Pour la deuxième (qui est moins intuitive), je vous laisse vous référer à la définition donner dans Craig Gentry, Jon Howell, Bryan Parno, Mariana Raykova, Pinocchio, nearly practical verfiable computations Appendice A

La troisième nous dit que si nous prenons \( P,Q \in E \) tel que \(Q= kP \) et \(S\) un autre point de notre courbe alors il est difficile de trouver un point \(R\) vérifiant \(kS=R\) à moins de poser \(S=jP\) et \(R=jQ\). Bien entendu dans cette définition, \(k\) n'est pas connue sinon cela rendrait le problème trivial.

Étant donnés plusieurs couples \((P_i,Q_i)\) vérifiant \(kP_i=Q_i\) pour tout \(i \in [ 1,n ] \), nous pouvons créer une combinaison linéaire de tous ces points pour obtenir un nouveau couple. En effet, malgré tous ces points et le fait que k n'est pas connu, la connaissance de l'exposant nous dit que la seule manière de créer un tel couple est de prendre \(S\) comme combinaison linéaire des \(P_i\). Par exemple, prenons \(S=\sum_{i=1}^n c_iP_i\). Ensuite, il suffit de prendre les même coefficient et poser \(R=\sum_{i=1}^n c_iQ_i\). Ainsi, nous venons de créer le couple \((S,R)\) qui vérifie \(kS=R\) tout ça sans connaître l'entier \(k\).

De plus, si nous avons un couple \((S,R)\), alors il est facile de vérifier si \(kS=R\) sans connaître \(k\). En effet, avec le couplage de Weil, il suffit de vérifier que \(e(P,R)=e(Q,S)\). En effet, si \(Q= kP \) et \(kS=R\) alors

1. \(e(P,R)=e(P,kS)=e(P,S)^k\)
2. \(e(Q,S)=e(kP,S)=e(P,S)^k\)

Il est important de remarquer que si nous avons seulement un ensemble de points \(P_i\) alors il sera difficile de créer les \(Q_i\) associés sans connaître le \(k\). En effet, si nous connaissons ce fameux k alors il nous suffira de prendre des points \(S\) et calculer \(kS=R\) sans se soucier de la des points donnés plus haut. Ainsi, on pourra créer un grand nombre de couples \((S,R)\) sans difficulté. Cependant, il nous faut créer ces points pour notre protocole. Ainsi, la création de ce protocole implique de faire confiance aux créateurs de ce dernier sur le fait qu'il aient détruits les "déchets toxiques" (ici \(k\) est un "dechet toxique")

Donc, il nous faut choisir une personne de confiance. En effet, après que cette personne ait construit les couples \((P_i,Q_i)\) nécessaires à notre problème, il faut impérativement que cette personne détruise le \(k\) pour éviter que des personnes l'utilisent. C'est ce qu'on appelle le "principe de confiance".(trusted setup).

Clé évaluation et clé de vérification [edit]

Dans ce sujet et le suivant, nous allons énoncer et détailler un protocole (zk-snark) qui permet de fournir des preuves à divulgation nulle de connaissance pour n'importe quel problème formulable sous la forme d'un programme arithmétique quadratique.

Un système de calcul public vérifiable (VC) permet à un client de sous traiter à un travailleur via une clé d'évaluation. De plus, le client peut vérifier l'exactitude de la solution via une clé de vérification. Plus formellement, un VC est définit par:

Définition: (Vérification de Calcul Public) Un système de calcul public vérifiable se compose de 3 algorithmes à temps polynomial (Gen_clé, calcul, Vérification) définis comme suit

1. Gen_clé: (cle_eval,cle_verif) \(\leftarrow\) Gen_cle\((F, 1 ^\lambda) \) où avec l'algorithme Gen_cle qui prend une fonction \(F\) et un paramètre de sécurité \(\lambda\) comme argument, le client génère aléatoirement 2 clés publics: une clé d'évaluation (cle_eval)et une clé de vérification (cle_verif).
2. \((y, \pi_y ) \leftarrow\) Calcul(cle_eval, \(u\)): Le travailleur calcule la solution et ressort \(y \leftarrow F(u)\) et \(\pi_y\) qui est une preuve de l'exactitude de sa solution.
3. \({0, 1} \leftarrow\) Vérification(cle_verif,\( u, y, \pi_y\)): Étant donnée notre clé de vérification (cle_verif), cet algorithme de vérification nous renvois 1 si \(F(u) = y\) et 0 sinon.

Ici, nous allons détailler les données nécessaires à la clé d'évaluation, la clé de vérification et le fonctionnement des "déchets toxiques" qui doivent être détruits après la création du protocole.

Pour mieux illustrer nos propos, nous allons appliquer notre protocole zk_NARKs aux programmes arithmétiques quadratiques.

Pour rappel dans le sujet précédent, nous voulions trouver des x qui vérifiaient la relation suivante.

1. \(A(x) B(x) - C(x)= H(x) Z(x)\)

où \(A\), \(B\) et \(C\) sont respectivement des combinaisons linéaire de l'ensemble de polynômes \({A_1,A_2,...,A_n}, {B_1,B_2,...,B_n} \ et \ {C_1,C_2,...,C_n}\) construit préalablement et public. l'ensemble de polynômes et le polynôme \(Z(t)\) sont des données du problème et donc accessible à tous.

Protocole

Tout d'abord, il nous faut une personne de confiance qui va produire les données nécessaires à la cle_eval et la cle_verif définis plus haut. Pour cela, il va choisir aléatoirement un point de notre courbe, notons le \(G\). Ensuite, il va choisir \(k_a, k_b, k_c, d\) et \(t_0\) des entiers avec \(k_a \ne k_b \ne k_c \) . Ces nombres sont appelés "déchets toxiques" et il devra les détruire après avoir effectué les calculs suivant(leur destruction permet une protection contre les fausses preuves):

1. \(Z(t_0)G\)
2. \(k_aG\)
3. \(k_bG\)
4. \(k_cG\)
5. \(A_1(t_0)G, A_2(t_0)G,..., B_1(t_0)G, B_2(t_0)G,..., C_1(t_0)G, C_2(t_0)G,...\)
6. \(A_1(t_0)k_aG, A_2(t_0)k_aG,..., B_1(t_0)k_bG, B_2k_b(t_0)G,..., C_1(t_0)k_cG, C_2(t_0)k_cG,...\)
7. \((A_i(t_0) + B_i(t_0) + C_i(t_0))dG\) pour chaque \(i\)
8. \(dG\)
9. \(G, t_0G, t_0^2G,.... \) (le nombre dépend du protocole)

Toutes ces données sont nécessaires pour la suite du schéma mais une fois fait, il n'y a plus besoin de le refaire. Les clients et travailleurs utiliseront le même protocole pour le même problème.

Maintenant, nous allons affecter chaque données à l'étape associée. Dans le sujet suivant, nous verrons comment le travailleur et le client les utilisent

Clé_eval:

Dans cette partie, le travailleur va créer sa preuve. Pour cela, il a besoin de:

1. \(A_1(t_0)G, A_2(t_0)G,..., B_1(t_0)G, B_2(t_0)G,..., C_1(t_0)G, C_2(t_0)G,...\)
2. \(A_1(t_0)k_aG, A_2(t_0)k_aG,..., B_1(t_0)k_bG, B_2k_b(t_0)G,..., C_1(t_0)k_bG, C_2(t_0)k_bG,...\)
3. \((A_i(t_0) + B_i(t_0) + C_i(t_0))dG\) pour chaque \(i\)
4. \(G, t_0G, t_0^2G,...., t_0^{2n}G\)

Clé_verif

Ici, le vérificateur va pouvoir tester la véracité d'une preuve. Pour cela, il a besoin des données suivantes

1. \((A_i(t_0) + B_i(t_0) + C_i(t_0))dG\) pour chaque \(i\)
2. \(k_aG\)
3. \(k_bG\)
4. \(k_cG\)
5. \(dG\)
6. \(\pi_z = Z(t_0)G\)

Ainsi que des données que le prouveur lui fournira. Ces dernières seront explicités dans le sujet suivant.

Déchets toxiques

Une fois que son protocole est crée, cette personne devra détruire les données suivantes:

1. \(k_a\)
2. \(k_b\)
3. \(k_c\)
4. \(d\)

Il faut les détruire pour se protéger contre les fausses preuves.

Dans le prochain sujet, nous verrons comment les différents protagonistes utilisent ces données. Grâce à ce type de protocole, le prouveur fournit une preuve à divulgation nulle de connaissance.

Références [edit]

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