Langue

Explication des SNARKs, partie 6 : le protocole Pinocchio

Ariel Gabizon | May 10, 2017

<< Part V

Dans la partie V, nous avons vu comment une déclaration qu'Alice souhaitait prouver à Bob pouvait être convertie en une forme équivalente dans le « langage des polynômes » appelé Programme d'arithmétique quadratique (QAP).

Dans cette partie, nous allons expliquer comment Alice peut envoyer une preuve très simple à Bob pour indiquer qu'elle possède une affectation satisfaisant un QAP. Nous utiliserons le protocole Pinocchio de Parno, Howell, Gentry et Raykova. Commençons par rappeler la définition d'un QAP que nous avons établie lors de la dernière partie :

Un programme d’arithmétique quadratique * |Q| *de degré \(d\) et de taille \(m\) est constitué de polynômes * |L1..m|, |R1..m|, |O1..m| *et un polynôme cible \(T\) de degré \(d\).

Une affectation \((c_1,\ldots,c_m)\) satisfait \(Q\) si, en définissant \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) et \(P:=L\cdot R -O\), on obtient que \(T\) divise \(P\).

Comme nous l'avons vu dans la Partie 5, Alice cherche généralement à prouver qu'elle possède une affectation satisfaisante avec plusieurs restrictions supplémentaires, par exemple \(c_m=7\). Cependant, nous choisissons d'ignorer cet aspect ici par souci de simplicité et de démontrer comment prouver uniquement les connaissances d'une affectation satisfaisante quelconque.

Si Alice dispose d'une affectation satisfaisante, cela signifie, en définissant \(L,R,O,P\) comme ci-dessus, qu'il existe un polynôme \(H\) tel que \(P=H\cdot T\). Plus spécifiquement, pour tout \(s\in\mathbb{F}_p\), nous avons \(P(s)=H(s)\cdot T(s)\).

Supposons maintenant qu'Alice ne dispose pas d'une affectation satisfaisante, mais qu'elle conçoit tout de même \(L,R,O,P\) tel qu'énoncé ci-dessus à partir d'une affectation non satisfaisante quelconque \((c_1,\ldots,c_m)\). Nous sommes alors certains que \(T\) ne divise pas \(P\). Cela signifie que, pour tout polynôme \(H\) de degré maximal \(d\), \(P\) et \(H\cdot T\) sont des polynômes distincts. Notez qu'ici, le degré maximal de \(P\) et de \(H\cdot T\) est \(2d\).

Nous pouvons à présent utiliser le fameux lemme de Schwartz-Zippel, qui précise que deux polynômes distincts d'un degré maximal \(2d\) sont égaux sur un maximum de \(2d\) points \(s\in\mathbb{F}_p\). Ainsi, si \(p\) est bien plus grand que \(2d\), la probabilité que \(P(s)=H(s)\cdot T(s)\) pour un \(s\in\mathbb{F}_p\) aléatoire est très faible.

Nous en déduisons le schéma de protocole suivant, visant à vérifier si Alice dispose d'une affectation satisfaisante :

  1. Alice choisit les polynômes \(L,R,O,H\) de degré maximal \(d\).
  2. Bob choisit un point \(s\in\mathbb{F}_p\) aléatoire et calcule \(E(T(s))\).
  3. Alice envoie à Bob les masquages de tous ces polynômes évalués à \(s\), à savoir \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\).
  4. Bob vérifie si l'équation souhaitée est vérifiée à \(s\). En d'autres termes, il vérifie si \(E(L(s)\cdot R(s)-O(s))=E(T(s)\cdot H(s))\).

Rappelons l'objectif : si Alice ne dispose pas d'une affectation satisfaisante, elle finira pas utiliser des polynômes pour lesquels l'équation ne se vérifie pas de façon identique, et donc ne se vérifie pas pour la plupart des choix de \(s\). Ainsi, Bob sera plus susceptible de rejeter le polynôme avec son choix de \(s\).

Nous cherchons à savoir si nous disposons des outils nécessaires pour appliquer ce schéma. Il est crucial qu'Alice choisisse les polynômes qu'elle utilisera sans connaître \(s\). Néanmoins, cela correspond parfaitement au problème que nous avons résolu dans le protocole d'évaluation aveugle vérifiable que nous avons développé dans les parties 2 à 4.

Grâce à cela, nous savons que nous devons vérifier quatre aspects afin de transformer ce schéma en un zk-SNARK. Nous aborderons deux de ces aspects dans cette partie, puis les deux autres dans la partie suivante.

Vérification que la sélection des polynômes d'Alice est conforme une affectation

Ce premier élément est des plus importants : le fait qu'Alice ne dispose pas d'une affectation satisfaisante ne signifie pas qu'elle ne peut pas trouver le moindre polynôme \(L,R,O,H\) de degré maximal \(d\) avec \(L\cdot R-O=T\cdot H\). Cela signifie uniquement qu'elle ne peut pas trouver de tels polynômes où \(L,R\) et \(O\) ont été « générés à partir d'une affectation », c'est-à-dire que \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) pour le même ensemble \((c_1,\ldots,c_m)\).

Le protocole de la partie 4 confirme uniquement qu'elle utilise des polynômes \(L,R,O\) quelconques du bon degré, mais pas que ceux-ci ont été générés à partir d'une affectation. C'est ici que la preuve formelle devient un peu plus subtile : nous effectuons ici un schéma imprécis de la solution.

Combinons les polynômes \(L,R,O\) en un unique polynôme \(F\) comme suit :

\(F=L+X^{d+1}\cdot R+X^{2(d+1)}\cdot O\)

En multipliant \(R\) par \(X^{d+1}\) et \(O\) par \(X^{2(d+1)}\), les coefficients de \(L,R,O\) « ne se mélangent pas » dans \(F\). Ainsi, les coefficients de \(1,X,\ldots,X^d\) dans \(F\) correspondent exactement aux coefficients de \(L\), les \(d+1\) prochains coefficients de \(X^{d+1},\ldots,X^{2d+1}\) correspondent exactement aux coefficients de \(R\) et les \(d+1\) derniers coefficients correspondent à ceux de \(O\).

Combinons maintenant de la même façon les polynômes dans la définition du QAP, en définissant pour chaque \(i\in \{1,\ldots,m\}\) un polynôme \(F_i\) dont les \(d+1\) premiers coefficients correspondent aux coefficients de \(L_i\), puis de \(R_i\) et enfin de \(O_i\). Cela signifie que pour chaque \(i\in \{1,\ldots,m\}\), nous définissons le polynôme

\(F_i=L_i+X^{d+1}\cdot R_i+X^{2(d+1)}\cdot O_i\)

Notez que lorsque nous additionnons deux des \(F_i\), \(L_i\), \(R_i\) et \(O_i\) « s'additionnent séparément ». Par exemple, \(F_1+F_2 = (L_1+L_2)+X^{d+1}\cdot (R_1+R_2)+X^{2(d+1)}\cdot(O_1+O_2)\).

Supposons, plus généralement, que nous avons \(F=\sum_{i=1}^mc_i\cdot F_i\) pour des coefficients \((c_1,\ldots,c_m)\) quelconques. Nous aurions également \(L=\sum_{i=1}^m c_i\cdot L_i, R=\sum_{i=1}^m c_i\cdot R_i, O=\sum_{i=1}^m c_i\cdot O_i\) pour les mêmes coefficients \((c_1,\ldots,c_m)\). En d'autres termes, si \(F\) est une combinaison linéaire des \(F_i\), alors \(L,R,O\) ont bien été générés à partir d'une affectation.

Ainsi, Bob demandera à Alice de lui prouver que \(F\) est une combinaison linéaire de \(F_i\). Pour ce faire, il convient de suivre une approche similaire au protocole d'évaluation vérifiable :

Bob choisit un \(\beta\in\mathbb{F}^*_p\) aléatoire puis envoie à Alice les masquages \(E(\beta\cdot F_1(s)),\ldots,E(\beta\cdot F_m(s))\). Il demande ensuite à Alice de lui envoyer l'élément \(E(\beta\cdot F(s))\). Si elle y parvient, une version étendue de la Connaissance du coefficient d'hypothèse insinue qu'elle sait comment rédiger \(F\) sous la forme d'une combinaison linéaire des \(F_i\).

Ajout de l'élément de connaissance zéro et dissimulation de l'affectation

Alice souhaite dissimuler toutes les informations sur son affectation dans un zk-SNARK. Cependant, les masquages \(E(L(s)),E(R(s)),E(O(s)),E(H(s))\) fournissent certaines informations sur l'affectation.

Par exemple, pour une autre affectation satisfaisante quelconque \((c'_1,\ldots,c'_m)\), Bob peut calculer les masquages \(E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))\) et les \(L',R',O',H'\) correspondants. Si le résultat du calcul à partir des masquages d'Alice diffère, il peut en déduire que \((c'_1,\ldots,c'_m)\) n'est pas l'affectation d'Alice.

Pour éviter toute perte d'informations concernant son affectation, Alice dissimulera son affectation en ajoutant un « décalage \(T\) aléatoire » à chaque polynôme. En d'autres termes, elle choisit des valeurs \(\delta_1,\delta_2,\delta_3\in\mathbb{F}^*_p\) aléatoires et définit \(L_z:=L+\delta_1\cdot T,R_z:=R+\delta_2\cdot T,O_z:=O+\delta_3\cdot T\).

Partons du principe que \(L,R,O\) ont été générés à partir d'une affectation satisfaisante. Ainsi, \(L\cdot R-O = T\cdot H\) pour un quelconque polynôme \(H\). Puisque nous venons d'ajouter un multiple de \(T\) à tous les éléments, \(T\) divise également \(L_z\cdot R_z-O_z\). Effectuons les calculs pour vérifier cela :

\(L_z\cdot R_z-O_z = (L+\delta_1\cdot T)(R+\delta_2\cdot T) - O-\delta_3\cdot T\) \(= (L\cdot R-O) + L\cdot \delta_2\cdot T + \delta_1\cdot T\cdot R + \delta_1\delta_2\cdot T^2 - \delta_3\cdot T\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) \(=T\cdot (H+L\cdot \delta_2 + \delta_1\cdot R + \delta_1 \delta_2\cdot T)\)

Par conséquent, en définissant \(H'=H+L\cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2\cdot T\), nous obtenons \(L_z\cdot R_z-O_z=T\cdot H_z\). En utilisant les polynômes \(L_z,R_z,O_z,H_z\) au lieu de \(L,R,O,H\), Bob acceptera toujours les polynômes d'Alice.

D'autre part, ces polynômes évalués à \(s\in\mathbb{F}_p\) avec \(T(s)\neq 0\) (qui correspond à tous les polynômes à l'exception des \(d\) \(s\)') ne dévoilent aucune information sur l'affectation. Par exemple, puisque \(T(s)\) n'est pas nul et \(\delta_1\) est aléatoire, \(\delta_1\cdot T(s)\) correspond à une valeur aléatoire, ainsi, \(L_z(s)=L(s)+\delta_1\cdot T(s)\) ne dévoile aucune information sur \(L(s)\) puisqu'il est dissimulé par cette valeur aléatoire.

Que nous reste-t-il pour la prochaine partie ?

Nous avons présenté un schéma du protocole Pinocchio pour lequel Alice peut convaincre Bob qu'elle possède une affectation satisfaisante pour un QAP, sans avoir à révéler d'informations sur l'affectation. Nous devons néanmoins résoudre deux derniers problèmes avant d'obtenir un zk-SNARK :

  • Dans le schéma, Bob a besoin d'un HH qui « prend en charge la multiplication ». Par exemple, il doit calculer \(E(H(s)\cdot T(s))\) à partir de \(E(H(s))\) et \(E(T(s))\). Néanmoins, nous n'avons pour l'instant pas trouvé d'exemple de HH pour lequel une telle opération est possible. Nous avons uniquement identifié un HH qui prend en charge les additions et les combinaisons linéaires.
  • Au cours de ces différentes parties, nous avons parlé de protocoles interactifs entre Alice et Bob. Nous cherchons cependant à ce qu'Alice puisse envoyer des preuves non interactives à message unique qui soient publiquement vérifiables. Cela signifie que toute personne qui consulte cette preuve à message unique sera convaincue de sa validité, et non simplement Bob (qui a déjà communiqué avec Alice).

Ces deux problèmes peuvent être résolus en associant des courbes elliptiques. Nous développerons cela dans notre prochaine et dernière partie.

cryptographie, zkSNARK, explications | Afficher tous les mots-clés