Explication sur les SNARKs, partie IV : Comment faire une évaluation à l'aveugle de vérification des polynômes

Ariel Gabizon | Apr 11, 2017

<< Partie III

Dans cette partie, nous tirons partie des Parties II et III pour développer un protocole d'évaluation aveugle vérifiable des polynômes, ce que nous définirons rapidement. Dans la partie V nous commencerons à voir comment un tel protocole peut être utilisé pour construire les SNARKs, alors donnez-moi encore un peu de temps pour expliquer la connexion aux SNARKs.

Supposons, comme dans la Partie II, qu'Alice a un polynôme \(P\) de degré|d| et que Bob possède un point \(s\in\mathbb{F}_p\) qu'il a choisi aléatoirement. Nous voulons construire un protocole permettant à Bob d'apprendre \(E(P(s))\), i.e. le masquage de \(P\) évalué à \(s\), avec deux propriétés supplémentaires :

  1. Aveuglement : Alice n'apprendra pas \(s\) (et Bob n'apprendra pas) \(P\).
  2. Vérifiabilité : La probabilité qu'Alice envoie une valeur ne se trouvant pas sous la forme \(E(P(s))\) pour \(P\) de degré \(d\) qui lui est connue, mais que Bob accepte quand même - est négligeable.

C'est ce que nous appelons l'évaluation aveugle vérifiable d'un polynôme. Le protocole en Partie II nous a donné le premier élément mais pas le deuxième. Pour avoir la vérifiabilité nous avons besoin d'une version étendue de la Connaissance du Coefficient d'hypothèse (KCA) qui était présentée dans la Partie III.

Les propriétés de vérifiabilité et d'aveuglement sont utiles ensemble car elles permettent à Alice de décider quel polynôme \(P\) elle utilisera sans voir \(s\). [1] Ceci dans un sens, engage Alice dans une « réponse de polynôme » sans voir le « point de défi » \(s\). Cette intuition deviendra plus claire dans les prochaines parties de la série.

Un KCA étendu

Le KCA tel que défini dans la Partie III disait globalement quelque chose comme ceci : Si Bob donne à Alice des \(\alpha\)-pair \((a,b = \alpha\cdot a)\) et qu'ensuite Alice génère un autre \(\alpha\)-pair \((a',b')\), alors elle connaît \(c\) tel que \(a'=c\cdot a\). En d'autre mots, Alice connaît la relation entre \(a'\) et \(a\).

Maintenant, supposons qu'au lieu d'un seul, Bob envoie plusieurs \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (for the same \(\alpha\)) à Alice ; et qu'une fois de plus, après avoir reçu ces paires, Alice est mise au défi d'en générer d'autres \(\alpha\)-pair \((a',b')\). Souvenez-vous que le point principal est qu'Alice doit faire ceci bien qu'elle ne connaisse pas \(\alpha\).

Comme nous l'avons vu dans la Partie III, une manière naturelle qu'a Alice de générer un tel \(\alpha\)-pair, serait de prendre l'une des paires \((a_i,b_i)\) reçues de Bob, et de multiplier les deux éléments par du \(c\in\mathbb{F}^*_p\) ; si \((a_i,b_i)\) était un \(\alpha\)-pair, alors \((c\cdot a_i,c\cdot b_i)\) sera aussi en un seul élément. Mais Alice peut-elle générer des \(\alpha\)-pairs de davantage de manières maintenant qu'elle a reçu des \(\alpha\)-pairs multiples ? Peut-être en utilisant plusieurs des \(\alpha\)-pairs reçus simultanément pour en obtenir un nouveau ?

La réponse est oui : par exemple, Alice peut choisir deux valeurs \(c_1,c_2\in \mathbb{F}_p\) et calculer le couple \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\). Un simple calcul montre que, aussi long que \(a'\) est non-nul, c'est aussi un \(\alpha\)-pair :

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

De façon plus générale, Alice peut prendre n'importe quelle combinaison linéaire des paires données \(d\) - c'est-à-dire choisir n'importe quel \(c_1,\ldots,c_d\in\mathbb{F}_p\) et définir \((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\).

Notez que si Alice utilise cette stratégie afin de générer son \(\alpha\)-pair elle connaîtrait certaines relations linéaires entre \(a'\) et \(a_1,\ldots,a_d\) ; ce qui signifie, qu'elle connaît \(c_1,\ldots,c_d\) tel que \(a'=\sum_{i=1}^d c_i\cdot a_i\).

Le KCA étendu établit essentiellement que c'est la seule façon pour Alice de générer un \(\alpha\)-pair ; ce qui signifie que lorsqu'elle réussira, elle connaîtra une telle relation linéaire entre \(a'\) et \(a_1,\ldots,a_d\). De façon plus formelle, supposons que \(G\) soit un groupe de taille \(p\) avec un générateur \(g\) écrit en plus, tel que décrit dans la Partie III. La Connaissance du coefficient d'hypothèse puissance d (d-KCA) [2] dans \(G\) est tel que suit :

d-KCA: Supposons que Bob choisisse un \(\alpha\in\mathbb{F}_p^*\) aléatoire et \(s\in\mathbb{F}_p\), et envoie à Alice le \(\alpha\)-pairs \((g,\alpha\cdot g), (s\cdot g,\alpha s\cdot g),\ldots,(s^d\cdot g,\alpha s^d\cdot g)\). Imaginons qu'Alice sorte ensuite un autre \(\alpha\)-pair \((a',b')\). Ensuite, excepté dans des cas très peu probables, Alice connaît \(c_1,\ldots,c_d\in\mathbb{F}_p\) tel que \(\sum_{i=0}^d c_i s^i\cdot g = a'\).

Notez que dans le d-KCA Bob n'envoie pas un éventail arbitraire de \(\alpha\)-pairs, mais plutôt avec une certaine « structure polynomiale ». Ceci sera utile dans le protocole décrit plus bas.

Le protocole d'évaluation aveugle vérifiable

Supposons que notre HH est la modélisation \(E(x)=x\cdot g\) pour un générateur \(g\) de \(G\) tel que ci-dessus.

Pour plus de simplicité, nous présentons le protocole pour ce \(E\) particulier :

  1. Bob choisit un \(\alpha\in\mathbb{F}_p^*\) aléatoire, et envoie à Alice les masquages \(g,s\cdot g,\ldots,s^d\cdot g\) (de \(1,s,\ldots,s^d\)) ainsi que les masquages \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) (de \(\alpha,\alpha s,\ldots,\alpha s^d\)).
  2. Alice calcule \(a=P(s)\cdot g\) et \(b=\alpha P(s)\cdot g\) en utilisant les éléments envoyés dans la première étape, et les envoie tous les deux à Bob.
  3. Bob vérifie que \(b=\alpha \cdot a\), et accepte si, et seulement si cette égalité est vraie.

D'abord, notez qu'étant donné les coefficients de \(P\), \(P(s)\cdot g\) est une combinaison linéaire de \(g,s\cdot g,\ldots,s^d\cdot g\) ; et \(\alpha P(s)\cdot g\) est une combinaison linéaire de \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\). Par conséquent, de façon similaire au protocole de la Partie II, Alice peut en effet calculer ces valeurs des messages de Bob pour un polynôme \(P\) qu'elle connaît.

Deuxièmement, par le d-KCA si Alice envoie \(a\), \(b\) tel que \(b=\alpha \cdot a\) alors elle connaît de façon quasi certaine \(c_1,\ldots,c_d\in\mathbb{F}_p\) tel que \(a=\sum_{i=0}^d c_is^i\cdot g\). Dans ce cas, \(a=P(s)\cdot g\) pour le polynôme \(P(X)=\sum_{i=0}^d c_i\cdot X^i\) connu par Alice. En d'autres mots, la probabilité que Bob accepte à l'étape 3 pendant qu'Alice n'ait pas connaissance d'un tel|P| est négligeable.

Pour synthétiser, en utilisant le d-KCA nous avons développé un protocole pour l'évaluation aveugle vérifiable des polynômes. Dans les prochains posts, nous allons voir comment ce bloc de construction a une incidence dans les constructions SNARK.

[1]Dans la preuve totalement formelle, les choses sont quelque peu plus subtiles, puisque Alice voit des informations sur \(s\) avant de décider de son \(P\) - par exemple, les masquages de \(s,\ldots,s^d\).
[2]Le d-KCA a été introduit dans un «papier <http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf> »_ de Jens Groth.

cryptography, zkSNARKs, explainers | Afficher tous les mots-clés

Notice: Network Upgrade Overwinter will activate at block 347500, to be mined 2018-06-25 12:00 UTC-04:00 assuming 150 seconds/block