Bienvenue ! Vous découvrez Zcash ?
Le réseau Zcash est récent, mais il évolue rapidement ! Inscrivez-vous et nous vous communiquerons plus d’informations pour faire vos premiers pas avec Zcash !

Langue

Explication sur les SNARK, partie 5 : Des calculs aux polynômes

Ariel Gabizon | Apr 25, 2017

<< Partie 4

Dans les trois parties précédentes, nous avons développé un certain mécanisme pour gérer les polynômes. Dans celle-ci, nous allons démontrer comment convertir des déclarations que nous souhaiterions prouver et vérifier dans le langage des polynômes. Cette utilisation des polynômes découle des travaux révolutionnaires de Lund, Fortnow, Karloff et Nisan.

En 2013, une autre étude innovante réalisée par Gennaro, Gentry, Parno et Raykova présentait le Quadratic Arythmetics Program (Programme d’arithmétique quadratique ou QAP), un programme extrêmement utile de conversion des calculs en polynômes. Les QAP sont depuis devenus la base des constructions zk-SNARK modernes, notamment celles utilisées par Zcash.

Pour expliquer la conversion en QAP, nous allons partir d’un exemple. Cependant, même en procédant ainsi, la tâche reste ardue. Préparez-vous donc à faire travailler vos méninges !

Supposons qu’Alice souhaite prouver à Bob qu’elle sait que \(c_1,c_2,c_3 \in \mathbb{F}_p\) tel que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\). La première étape consiste à présenter l’expression calculée à partir de \(c_1,c_2,c_3\) sous la forme d’un circuit arithmétique.

Circuits arithmétiques

Un circuit arithmétique est composé de portes qui calculent les opérations arithmétiques telles que les additions et les multiplications. Des câbles relient les portes entre elles. Pour notre exemple, le circuit correspond au schéma suivant :

An example of an arithmetic circuit

Les câbles inférieurs correspondent aux câbles d’entrée, tandis que le câble supérieur correspond au câble de sortie. Ce dernier transmet le résultat du calcul du circuit sur les entrées.

Comme illustré, nous étiquetons les câbles et les portes du circuit d’une façon bien particulière, nécessaire pour l’étape suivante du processus de conversion du circuit en QAP :

– Lorsqu’un câble sortant relie plusieurs portes, comme \(\mathsf{w_1}\) dans notre exemple, nous le considérons toujours comme un câble unique. – Nous estimons que les portes de multiplication possèdent exactement deux câbles d’entrée, à savoir le câble de gauche et le câble de droite. – Nous n’étiquetons pas les câbles reliant une porte d’addition à une porte de multiplication, ni la porte d’addition. Nous considérons que les entrées de la porte d’addition accèdent directement à la porte de multiplication. Ainsi, dans notre exemple, \(\mathsf{w_1}\) et \(\mathsf{w_3}\) sont toutes deux considérées comme des entrées de droite de \(\mathsf{g_2}\).

Pour le circuit, une affectation légale désigne l’affectation de valeurs aux câbles étiquetés par laquelle la valeur de sortie de chaque porte de multiplication correspond au produit des entrées correspondantes.

Ainsi, pour notre circuit, une affectation légale prend la forme suivante : \((c_1,\ldots,c_5)\)\(c_4=c_1\cdot c_2\) et \(c_5=c_4\cdot (c_1+c_3)\).

Avec cette terminologie, Alice tente de prouver qu’elle sait qu’il existe une affectation légale \((c_1,\ldots,c_5)\), telle que \(c_5=7\). L’étape suivante consiste à convertir cela en une déclaration associée à des polynômes, à l’aide des QAP.

Réduction à un QAP

Nous associons chaque porte de multiplication à un élément de champ : \(\mathsf{g_1}\) sera associée à \(1\in\mathbb{F}_p\) et \(\mathsf{g_2}\) à \(2\in\mathbb{F}_p\). Nous désignons les points \(\{1,2\}\) par le terme points cibles. Nous devons maintenant définir un ensemble de « polynômes de câble gauche » \(L_1,\ldots,L_5\), de « polynômes de câble droit » \(R_1,\ldots,R_5\) et de « polynômes de câble de sortie » \(O_1,\ldots,O_5\).

La définition repose sur le principe suivant : les polynômes auront généralement une valeur nulle aux points cibles, à l’exception des polynômes impliqués au niveau de la porte de multiplication correspondant au point cible.

Concrètement, puisque \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) sont respectivement des câbles de gauche, de droite et de sortie de \(\mathsf{g_1}\), nous définissons \(L_1=R_2=O_4=2-X\), car le polynôme \(2-X\) a pour valeur un sur le point cible \(1\) correspondant à \(\mathsf{g_1}\) et zéro sur le point cible \(2\) correspondant à \(\mathsf{g_2}\).

Notez que les câbles \(\mathsf{w_1}\) et \(\mathsf{w_3}\) sont tous les deux des câbles de droite de \(\mathsf{g_2}\). De ce fait, nous définissons de la même manière \(L_4=R_1=R_3=O_5=X-1\), puisque \(X-1\) a pour valeur un sur le point cible \(2\) correspondant à \(\mathsf{g_2}\) et zéro sur l’autre point cible.

Nous établissons que les autres polynômes sont des polynômes nuls.

Étant donnée la nature des valeurs fixes \((c_1,\ldots,c_5)\), nous les utilisons comme coefficients pour définir des polynômes de « somme » de gauche, de droite et de sortie. Ainsi, nous définissons :

\(L:=\sum_{i=1}^5 c_i\cdot L_i, R:=\sum_{i=1}^5 c_i\cdot R_i, O:=\sum_{i=1}^5 c_i\cdot O_i\),

puis nous définissons le polynôme \(P:=L\cdot R -O\).

Désormais, après toutes ces définitions, le point central correspond à : \((c_1,\ldots,c_5)\). Il s’agit d’une affectation légale au circuit si et seulement si * |P| *disparaît sur tous les points cibles.

Examinons cela à l’aide de notre exemple. Supposons que nous avons défini \(L,R,O,P\) comme ci-dessus, avec des points donnés quelconques \(c_1,\ldots,c_5\). Évaluons tous ces polynômes au point cible \(1\) :

De tous les \(L_i\), seul \(L_1\) n’a pas de valeur nulle en \(1\). Nous avons donc \(L(1)=c_1\cdot L_1(1)=c_1\). De la même façon, nous obtenons \(R(1)=c_2\) et \(O(1)=c_4\).

Par conséquent, \(P(1)=c_1\cdot c_2-c_4\). Un calcul similaire démontre que \(P(2)= c_4\cdot (c_1+c_3) - c_5\).

En d’autres termes, \(P\) disparaît aux points cibles si et seulement si \((c_1,\ldots,c_5)\) est une affectation légale.

Nous utilisons à présent le fait algébrique suivant : pour un polynôme \(P\) et un point \(a\in\mathbb{F}_p\), nous avons \(P(a)=0\) si et seulement si le polynôme \(X-a\) divise \(P\), c’est-à-dire \(P=(X-a)\cdot H\) pour un quelconque polynôme \(H\).

En définissant le polynôme cible \(T(X):=(X-1)\cdot (X-2)\), nous déterminons ainsi que \(T\) divise \(P\) si et seulement si \((c_1,\ldots,c_5)\) est une affectation légale.

À l’issue de cette discussion, nous définissons un QAP comme suit :

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 d’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\), nous déterminons que \(T\) divise \(P\).

À l’aide de cette terminologie, Alice souhaite prouver qu’elle connaît une affectation \((c_1,\ldots,c_5)\) qui satisfait le QAP décrit ci-dessus avec \(c_5=7\).

En somme, nous avons vu comment une déclaration comme « Je connais des câbles \(c_1,c_2,c_3\) tels que \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\) » peut être convertie à l’aide des QAP en une déclaration équivalente reposant sur des polynômes. Dans la prochaine partie, nous examinerons un protocole efficace pour prouver les connaissances d’une affectation satisfaisant un QAP.

[1]Dans cet article, nous avons essayé de prendre un exemple concis de réduction à un QAP. Nous recommandons également l’excellent article de Vitalik Buterin pour en savoir plus sur la conversion d’un programme en un QAP.

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