Wiki du cours

Rédacteur: [A remplir]

A traiter [Modifier]

Le but de ce sujet est d'expliquer ce que sont les programmes arithmétiques quadratiques en utilisant un exemple. Il s'agit de transformer une fonction impliquant les quatre opérations arithmétiques usuelles (addition, soustraction, multiplication, division) en un programme arithmétique quadratique sur le modèle de [1] (voir aussi [3]). Utilisez un exemple simple mais différent de ceux dans ces références.

• Expression de la fonction en terme de portes arithmétiques.
• Transformation en un système contraint de rang 1 (R1CS)
• Transformation du système contraint en un programme arithmétique quadratique.
• Définition des programmes arithmétiques quadratiques.

Introduction: [Modifier]

Considérons que Alice voudrait prouver à Bob qu'elle connaît la solution de l’équation \( x^2-1=0\) sans révéler cette solution. pour ce but on suivre les étapes suivants :

1-Expression de la fonction en terme de portes arithmétiques: [Modifier]

Le but est de convertir le code original \(x^2-1\), qui peut contenir des instructions et expressions arbitrairement complexes, en une séquence d'instructions de deux formes:
\(x=y\) où y peut être un nombre et un variable.
\( x=y (op ) z \) t.q \(op\) \(\in\) \(\left\lbrace -,+,*,/\right\rbrace \).
Le code flattening correspondant de notre équation est:
\( out_1 = x * x \) (premire porte)
\(y = out_1 - 1\) (deuxème porte)

2-Transformation en un système contraint de rang 1 (R1CS): [Modifier]

Considérons trois vecteurs \(\vec{a},\vec{b},\vec{c}\), on définie la solution de R1CS comme un vecteur \(\vec{s}\) qui sataisfait l'équation \((\vec{s}.\vec{a})*(\vec{s}.\vec{b})-(\vec{s}.\vec{c})=0 \) où le point "." est le produit scalaire , ce vector containt les variables du programme .par exemple dans notre programme \(\vec{s}\) est: \( (\begin{matrix}{} s_1,
s_2,
s_3 ,
s_4 \end{matrix} )= (\begin{matrix}{} 1,
x,
out_1,
y \end{matrix})\) .
Remarque : on commence toujours par 1.
Maintenant ,on donne des valeurs de \(\vec{a},\vec{b},\vec{c}\)pour les deux portes.

• Pour la première porte \(out_1 = x * x :\)On pose \(a\) et \(b\) ayant des zéros partout excepté à l'entrée correspondant à \(x \)et on pose \(c\) ayant des zéros partout excepté à l'entrée correspondant à \(out_1 \) , alors on obtient
  \( \vec{a_1}=\left[0,1,0,0\right] \),
  \( \vec{b_1}=\left[0,1,0,0\right] \),
  \( \vec{c_1}=\left[0,0,1,0\right] \) .
• Pour la deuxième porte \(y = out_1 - 1 \) : pareillement on trouve que
  \(\vec{a_2}=\left[-1,0,1,0\right] \) ,
  \(\vec{b_2}=\left[1,0,0,0\right] \),
  \( \vec{c_2}=\left[0,0,0,1\right] \).
  Remarque: vérifions de la condition (s.a)*(s.b)-(s.c)=0 pour les deux portes :
  \((a_{1,1}s_{1}+a_{1,2}s_{2}+a_{1,3}s_{3}+a_{1,4}s_{4})*(b_{1,1}s_{1}+b_{1,2}s_2+b_{1,3}s_3+b_{1,4}s_4)-(c_{1,1}s_1+c_{1,2}s_2+c_{1,3}s_3+c_{1,4}s_4)=s_2*s_2-s_3=x*x-out_1=0 \)(vrai).
  \((a_{2,1}s_1+a_{2,2}s_2+a_{2,3}s_3+a_{2,4}s_4)*(b_{2,1}s_1+b_{2,2}s_2+b_{2,3}s_3+b_{1,4}s_4) -(c_{2,1}s_1+c_{2,2}s_2+c_{2,3}s_3+c_{2,4}s_4)=-1+out_1-y=0 \)(vrai).

3-Transformation de R1CS en un programme arithmétique quadratique QAP: [Modifier]

Dans cet étape on passe des vectors aux polynômes en utilisant "l'interpolation de Lagrange". D'abord ,définissons les polynômes \(A_i , B_i, C_i \) tel que \(i\in {1,..,N}\) où N est le long des vactors \(\vec{a_1},\vec{b_1},\vec{c_1}\) . Dans notre exemple N=4, tels que \(A_i(n)=a_{n,i}\) , \(B_i(n)=b_{n,i}\) ,\(C_i(n)=c_{n,i}\) , où \(n\) est le nombre de la porte. Pour notre programme on a \(n=1,2\) et : \(A_1(1)=0 , A_1(2)=-1 , i.e. A_1 \)est un polynôme passe par (1,0) , (2,-1).
\(A_2(1)=1, A_2(2)=0 , i.e. A_2 \)est un polynôme passe par (1,1) , (2,0) .
\(A_3(1)=0 , A_3(2)=1 , i.e. A_3 \)est un polynôme passe par (1,0) , (2,1) .
\(A_4(1)=0 , A_4(2)=0 , i.e. A_4 \)est un polynôme passe par (1,0) , (2,0) .
Ensuit,en utilisant lagrange interpolation on trouve \(A_1(x)=1-x\) . Pareillement ,on trouve \(A_2,A_3,A_4, B_1 ,B_2 ,B_3 ,B_4 ,C_1,C_2,C_3,C_4\). Définissons \(\vec{A(x)}=(A_1(x),A_2(x),A_3(x),A_4(x))\) , \(\vec{B(x)}=(B_1(x),B_2(x),B_3(x),B_4(x))\) , \(\vec{C(x)}=(C_1(x),C_2(x),C_3(x),C_4(x))\) . on pose \(a(x)=\vec{A}.\vec{S}\) , \(b(x)=\vec{B}.\vec{S}\) et \(c(x)=\vec{C}.\vec{S}\). Avec ces définitions on peux exprimer R1CS par une équation \(a(x) * b(x)-c(x)=H(x).Z(x)\) , pour tout x. telle que Z(x),H(x) déterminées comme suivant : on a \(A(1)=\vec{a_1}\) , \(A(2)=\vec{a_2}\) , \(B(1)=\vec{b_1}\) , \(B(2)=\vec{b_2}\) et \(C(1)=\vec{c_1}\) , \(C(2)=\vec{c_2}\) , alors \(a(1)*b(1)-c(1) =0\) et \(a(2)*b(2)-c(2) =0\) donc \(a(x) * b(x)-c(x)=0 \)pour \(x=1,2\) alors \(z(x)=(x-1)*(x-2)\) divise \(a(x) * b(x)-c(x)\) , donc il existe \(H(x)\) t.q \(a(x) * b(x)-c(x)=H(x).(x-1)(x-2)\) .
ET ALORS!! Un programme arithmétique quadratique de degré n et de taille N se compose de polynômes \(A_i , B_i , C_i\) t.q i=1,...,N et \(Z\) qui est un polynôme de degré n, ces sont les donnés . Alice entre le valeur de \(\vec{S}\) ,si le valeur est correspondant à vrai solution alors \(a(x) * b(x)-c(x)\) divisible par \(Z\) , sinon alors Alice ne connaît pas la solution .

Références [Modifier]

[1] Vitalik Buterin, Quadratic Arithmetic Programs: from Zero to Hero
[2] Craig Gentry, Jon Howell, Bryan Parno, Mariana Raykova, Pinocchio, nearly practical verfiable computations, Section 2.2.1
[3] Ariel Gabizon, Explaining zk-SNARKs, Part V