Les preuves à divulgation nulle de connaissance

22 min readJul 5, 2018

La sorcellerie cryptographique qui pourrait changer notre rapport à la confiance et à la transparence.

Dans l’article précédent, co-rédigé par Aurélien Calot, nous avons décrit des cas d’application pour les preuves à connaissance zéro sans toutefois en décrire le fonctionnement. L’objet de ce présent article n’est donc pas tant de présenter à nouveau les emplois de ces techniques que d’en démystifier le fonctionnement. L’explication du fonctionnement de ces preuves est généralement laissée de côté dans la plupart des articles sur le sujet, et il est attendu du lecteur qu’il admette les résultats qu’on lui présente sans poser de questions. L’idée est ici de rompre avec cette tradition et de vous inviter à découvrir ce qu’il se passe en coulisse.

N.B : Durant tout cet article nous allons décrire les zk-SNARKs dans le contexte d’une utilisation en Blockchain. Notez cependant que ces preuves peuvent être utilisées dans d’autres contextes.

Définition

De manière formelle, les preuves à divulgation nulle de connaissance permettent à un prover de démontrer à un verifier, qu’étant donnée une valeur de sortie x pour une fonction f, il connaît une valeur secrète w, telle que f(w)=x. Pour le dire plus simplement, ces preuves permettent à un prover de démontrer à un ou plusieurs verifier(s) qu’une assertion logique portant sur une valeur secrète est vraie, sans que le prover n’ait à divulguer d’information sur ce secret au(x) verifier(s).

Pour vous illustrer la chose, considérez par exemple un tirage de carte pour lequel Alice (prover) veut démontrer à Bob (verifier) qu’elle a tiré une carte rouge (carreau ou coeur) sans révéler à Bob quelle est sa carte exactement (dame de coeur par exemple). Comment Alice peut convaincre Bob que sa carte est rouge ?

Pour y parvenir, Alice pourrait montrer à Bob que le paquet contient toujours 26 cartes noires. De cette manière, elle lui prouverait irréfutablement que la carte qu’elle a tirée est rouge, sans toutefois lui révéler plus d’informations au sujet de la valeur de sa carte. En procédant ainsi Alice génère en fait une preuve à connaissance zéro puisqu’elle convainc Bob que la carte est rouge en délivrant un minimum d’information dans la manoeuvre.

Ainsi, pour qu’un procédé de preuve soit considéré “à connaissance zéro”, il doit admettre les trois propriétés suivantes :

aucun prover ne peut convaincre un verifier à propos d’une assertion fausse (soundness),
il existe un moyen pour le prover de démontrer au verifier la véracité de n’importe quelle vraie assertion (completeness),
et enfin, en produisant cette preuve le prover ne révèle rien d’autre au verifier que l’assertion qu’il cherche à prouver (zero-knowledge).

Zk-Snarks : pourquoi un nom aussi barbare ?

Le terme “preuve à divulgation nulle de connaissance” est en fait le terme générique que l’on utilise pour désigner cette catégorie de preuves cryptographiques. Dans ZCash et bientôt dans Ethereum, les preuves spécifiques utilisées sont les zk-SNARKS. Décomposons ensemble cet acronyme barbare :

S pour “succint” — signifie que la taille des preuves est faible en comparaison de la complexité des calculs effectués.
N pour “non-interactive” — signifie qu’il n’y a aucune, ou presque, interaction requise entre le prover et le verifier. Après la phase d’initialisation (cf. infra) un seul message est échangé entre le prover et le verifier. Ceci signifie que dans le cadre de la Blockchain, pour une adresse publique donnée, il suffit d’effectuer l’initialisation une seule fois pour pouvoir signer une infinité de transactions émanant de cette adresse (pas besoin de refaire l’initialisation à chaque nouvelle transaction).
AR pour “argument” — signifie que le verifier est assuré de l’intégrité de la preuve sous l’hypothèse que le prover a des ressources informatiques limitées (en cryptographie asymétrique, toute preuve est toujours basée sur ce genre d’hypothèse, nous expliquerons pourquoi dans la partie sur la théorie de la complexité).
K pour “of Knowledge” — signifie que le prover peut construire la preuve si et seulement si, il a connaissance d’une certaine donnée que l’on appelle witness (ex: sur un réseau Blockchain ce pourrait être l’adresse publique émettrice d’une transaction ou encore une signature de transaction valide).
Et enfin, le préfixe Zk pour Zero Knowledge, ce qui signifie que durant l’interaction le verifier n’apprend rien hormis le fait que la transaction est valide. On ne lui communique aucune information autre que la preuve.

Avant de rentrer dans le vif des explications, il nous faut cependant introduire brièvement “la théorie de la complexité”.

Théorie de la complexité:

En matière de cryptographie asymétrique, tout système de défense n’est valable que dans l’hypothèse d’assaillants pourvus de ressources informatiques limitées. De fait, la cryptographie asymétrique est intimement liée à ce qu’on appelle la théorie de la complexité. L’objet de la théorie de la complexité est de mesurer le nombre d’étapes de calcul élémentaires (ce qu’en informatique on appelle le “temps”) dont a besoin un programme pour obtenir un résultat, étant donné une entrée/input de longueur N (Peut-être avez-vous déjà croisé des notations du type O(log(N)) ou O(N^k)). Nous ne définirons pas ce qu’est “une étape de calcul élémentaire”, car ça n’a pas grand intérêt ici. Gardez simplement en tête que l’on a recours à la théorie de la complexité pour rendre compte de la puissance calculatoire requise par un programme, ce qu’on appelle le temps d’exécution (runtime).

La plupart des programmes que nous utilisons dans la vie courante sont en temps polynomial (noté O(n^k) avec k entier). Si l’on considère une entrée de longueur N, on peut dire qu’un programme P “est en temps polynomial” si le nombre d’étape de calcul nécessaire à son exécution est une fonction du type Q(N), où Q est un polynôme (ex: x³ + 2x + 1). En somme, un programme est executable en temps polynomial si l’évolution du nombre d’étapes de calcul en fonction de la taille de l’input (noté N et exprimée en bits) croit à un rythme polynomial ou à un rythme inférieur. La capacité calculatoire des hardware modernes les rend inutiles lorsque l’on se place dans le contexte d’un programme qui serait en temps exponentiel par exemple. Ces programmes en temps exponentiel ne sont executables que pour des input de très faible taille, parce que lorsque N augmente, le nombre d’étape de calcul augmente extrêmement rapidement. Les fonctions exponentielles ont une croissance “si rapide/forte”, qu’étant donné une input de grande taille, un programme en temps exponentiel, mettrait des années, voire des siècles, pour produire un résultat, même en étant exécuté sur un des plus gros ordinateurs du monde. C’est pour cela qu’en informatique nous utilisons majoritairement des programmes en temps polynomial.

P = NP ?

Ces considérations sur la théorie de la complexité sont essentielles à l’étude des Zk-Snarks, et sont centrales dans le domaine de la cryptographie asymétrique, car les méthodes de chiffrement asymétrique sont réputées inviolables d’un point de vue calculatoire. Elles ne sont pas “absolument inviolables”. Elles sont considérées inviolables car nous ne connaissons pas de programme en temps polynomial capable de les casser. Si par exemple vous parvenez à trouver un programme en temps polynomial pour la décomposition en facteur premier, vous seriez le maître du monde, car la sécurité de la plupart des méthodes de cryptographie modernes repose justement sur l’hypothèse qu’un tel programme n’existe pas.

Consacrer votre temps à la recherche d’un tel programme pourrait cependant vous valoir les railleries de nombreux mathématiciens car ce problème, ainsi que la classe de problème à laquelle il appartient, car pour la plupart d’entre eux ce problème est considéré comme insoluble. Le problème qui consiste à prouver qu’un tel programme de décomposition en facteur premiers ne peut pas exister, ou à prouver à l’inverse qu’il existe est encore un problème ouvert en mathématique. Ce problème mathématique admet une formulation plus générique: l’équivalence entre les classes de problème P et NP. Ce problème qui figure parmi la liste des problèmes du millénaire en mathématique peut s’expliquer ainsi :

En théorie de la complexité la classe des problèmes “P” désigne les problèmes pour lesquels il existe un programme qui fonctionne en O(n^k), i.e. en temps polynomial, et “NP” la classe des problèmes pour lesquels il n’existe pas de programme en temps polynomial. Le problème du millénaire mentionné ci-dessus propose donc de prouver que les deux classes sont équivalentes ou qu’elles ne le sont pas. Si ces deux classes sont équivalentes, cela signifie qu’il existe potentiellement des programmes permettant de casser toutes les techniques de cryptographie asymétrique, et sinon cela signifie que ces méthodes sont inviolables (elles sont aujourd’hui considérées comme telles parce que l’on part du principe que P n’est pas égal à NP, mais si l’on parvenait à démontrer cette inégalité, on pourrait dire que ces méthodes sont absolument inviolables).

Parmi les problèmes de la classe NP, on distingue certains problèmes dits “NP-complets”. Le terme complet désigne l’idée que ce problème décrit tous les problèmes contenus dans NP, c’est-à-dire que, considérant un problème NP-complet noté L, pour tout problème L’ dans NP, il existe une fonction de réduction “f” (en temps polynomial) telle que:

L(x) <=> L’(f(x)) (<=> : Lire “équivalent à”), où x représente l’input du problème.

Autrement dit, il existe une fonction de réduction telle que l’input à notre problème puisse être transformé en une input d’un problème NP-complet, de sorte que si x satisfait au problème L (i.e. L(x) = 1) alors f(x) satisfait nécessairement au problème NP.

Cette propriété de NP-complétude est particulièrement utile en computer science, en ce qu’elle permet de transformer un problème potentiellement difficile à résoudre en un problème connu et donc plus aisément soluble. Cette propriété de NP-complétude est importante pour effectuer des zk-SNARKS, car elle permet de traduire tout problème de génération de preuve à divulgation nulle de connaissance à un problème générique qui a été spécifiquement choisi pour être facilement réalisable par un ordinateur. Autrement dit, cette “astuce” apporte la propriété de “completness” puisqu’elle assure que quelque soit l’assertion qui doit être prouvée (c’est-à-dire quelque soit le NP-Problème qui nous préoccupe), il existe un moyen pour le prover d’en générer une preuve facilement vérifiable par un verifier.

C’en est fini pour les notions à introduire, on peut rentrer dans le vif du sujet.

En premier lieu nous allons montrer comment réduire le problème initial à un problème NP-Complet, pour ensuite décrire la phase d’initialisation (trusted setup) de la preuve. Cela nous conduira à présenter le problème spécifique auquel se réduit le système de génération de la preuve. Ensuite il s’agira de parler brièvement des courbes elliptiques et d’introduire les méthodes de chiffrement qui interviennent dans le procédé de preuve. Cette partie permettra au lecteur de découvrir les fondements mathématiques des techniques de chiffrement modernes comme le RSA et les systèmes clé publique/clé privée par association de points sur des courbes elliptiques. Enfin, nous présenterons les Zk-Snarks d’un bout à l’autre du processus de génération de preuve.

1. réduction

Rappelons que le but du système de Zk-Snarks est de générer une preuve attestant que f(w) = x ; où “w” est une valeur que l’on tient à garder secrète (witness) et où “f” est un programme connu (une fonction de hachage par exemple). Rappelons également, que f est dans NP, et que par conséquent, prouver que f(w) = x revient exactement à prouver que f’(g(w)) = x ; où f’ est un problème NP-complet et où g est une fonction de réduction exécutable en temps polynomial.

En pratique, la première étape consiste donc à transformer le problème initial en un problème NP-Complet. Pour parvenir à cela, l’idée est de transformer le problème initial en un “circuit logique à contrainte d’ordre 1” pour ensuite le transformer en un QAP (Quadratic Arithmetic Program — pas de panique nous allons expliquer ce que cela signifie). Ce processus de transformation s’appelle une réduction. Cette réduction est différente pour chaque programme, par conséquent il faudra la refaire pour chaque nouveau programme pour lequel on veut générer des preuves (ou pour l’exprimer à partir des notations plus haut : pour chaque fonction f, il faut calculer la fonction de réduction g qui lui est associée). C’est en revanche la seule partie du système de zk-SNARKS qui doit être adaptée, tout ce qui intervient par la suite demeure inchangé. En pratique il est cependant possible de créer un algorithme qui réalise la réduction automatiquement et d’envisager ainsi un programme de zk-SNARKS générique, adapté à n’importe quel problème de preuve, mais ce n’est pas l’objet de cette article que de décrire un tel programme.

Ainsi, une fois le QAP construit, on peut générer des preuves à volonté pour un programme donné, même lorsque le secret (le witness) change. C’est pour cela que dans ZCash n’importe quel nouvel utilisateur peut effectuer des transactions anonymes sans qu’il ai besoin pour cela de refaire ce travail de réduction à nouveau. Le système de zk-SNARKS qui intervient pour prouver qu’une transaction est bien valide est préconfiguré sur ZCash et peut-être réutilisé à l’envie.

La réduction du problème à un QAP est une tâche qui a peu d’intérêt pour notre explication et qui est longue à décrire, c’est pourquoi nous ne la détaillerons pas ici (explication à ce sujet “ici” par Vitalik Buterin pour les curieux). Gardez seulement en tête que nous allons travailler sur un problème spécifique, que l’on appelle QAP (cf. infra) et que c’est satisfaisant d’effectuer une telle réduction en vertu de la propriété de NP-complétude. Juste après cette phase de réduction, vient celle dite “d’initialisation”, et comme cette phase est extrêmement importante nous n’allons pas faire l’économie de son explication:

2. Trusted Setup

Cette phase d’initialisation, “trusted setup” en anglais, est très importante car c’est durant cette phase qu’apparaît la seule faille de sécurité des zk-SNARKs. Durant cette phase, le(s) verfier vont calculer les valeurs du “trusted setup”, les chiffrer et les publier dans un fichier public que l’on appelle le CRS (Common Reference String). Cette phase est critique puisque tout agent qui parviendrait à connaître les valeurs choisies par le verifier pour effectuer les calculs du “trusted setup” pourrait produire de fausses preuves. Pour pallier cette vulnérabilité, les fondateurs de ZCash ont défini toute une cérémonie sécurisée, au cours de laquelle ces valeurs critiques, que l’on appelle familièrement “toxic waste”, ont été générées. La fondation Ethereum devrait probablement opter pour un protocole de “trusted setup” décentralisé. L’idée est que tout noeud peut prendre part au protocole pour générer les “toxic waste”. Chaque noeud impliqué choisi une valeur au hasard, multiplie la valeur qu’il a reçu par sa valeur et la communique au voisin. De cette manière, il suffit qu’un seul noeud se soit débarrassé de son “toxic waste” pour qu’il devienne impossible de reconstituer la valeur finale. L’avantage de ce système est qu’il permet aux sceptiques de s’assurer directement que le trusted setup a été réalisé correctement, puisqu’il suffit pour cela qu’ils soient confiants dans le fait qu’ils ont bien détruit leur valeur personnelle. Même si les autres ne le faisaient pas, cela n’aurait pas d’incidence sur la sécurité du système de preuve.

Comme le CRS est un fichier public, on retrouve la propriété “non-interactive”, car en effet, prover et verifier se contentent de publier des valeurs dans ce fichier pour construire la preuve. Ils n’ont pas besoin d’échanger de messages. Nous reviendrons au CRS pour expliquer ce qu’il contient après avoir expliquer le problème QAP.

3. Quadratic Arithmetic Program

(le point représente ici le produit polynomial. Si la différence entre un produit polynomial et un produit d’entiers ne vous semble pas évidente, voici un petit rappel sur les polynômes).

Pour les Zk-snarks, le problème NP-Complet choisi s’appelle un Quadratic Arithmetic Program ou QAP. Un QAP est un ensemble de polynômes et le problème à résoudre est celui qui consiste à trouver une combinaison linéaire de ces polynômes, qui soit multiple d’un polynôme Z dit “polynôme cible” (i.e. une combinaison linéaire de deux polynômes A et B qui divise Z). Un QAP défini sur un corps fini F pour une entrée x de longueur n consiste en :

Deux ensembles de polynômes (V0,V1,…,Vm) ; (W0,W1,…,Wm) sur le champs vectoriel F.
Un polynôme cible Z sur F.
Une fonction injective h: {(i,j) |1≤i≤n, j ∈ {0,1}} → (1, 2, …, m)

Cette fonction injective f restreint les coefficients que l’on peut utiliser pour construire la combinaison linéaire des polynômes (V0,…,Vm) et (W0, …, Wm) en fonction de l’assertion qui doit être vérifiée. (L’assertion à vérifier est [f(w) = x ?], c’est donc x qui restreint h, et non pas w).

On dit que l’input x satisfait au QAP, si et seulement si, il existe a=(a1, a2, …, am) et b=(b1, b2, …, bm) dans F tels que :

ak, bk = 1 si k=h(i, x[i]) (x[i] représente le i-ème bit de x)
ak, bk = 0 si k=h(i, 1-x[i])
et le polynôme cible Z divise VaWb où Va = v0 + a1v1 + … + amvm et où Wb = w0 + b1w1 + … + bmwm

La fonction f définit donc quels coefficients seront nuls et lesquels seront non-nuls en fonction de l’input du problème. Très grossièrement, on peut dire que cette fonction réalise l’équivalence entre notre problème initial et un QAP spécifique.

Cette définition du problème QAP est assez formelle et peut s’avérer complexe à saisir, mais rassurez-vous, nous reviendrons dessus. Pour l’instant retenez simplement, que nous avons produit une réduction de notre problème initial pour le rendre équivalent à la résolution d’un QAP. Résolution, dont l’objet est de définir des coefficients linéaires, tels qu’une combinaison linéaire d’un ensemble de polynômes divise un autre polynôme, appelé polynôme cible. Et n’oubliez pas que le but initial de la réduction est de transformer le problème sur lequel on veut travailler. De fait, toute solution au problème QAP est une solution du problème initial pour peu que la réduction ait été réalisée correctement.

4. Fonction de chiffrement, courbe elliptique et pairing function

Pour produire notre système de preuve nous devons définir préalablement un “groupe d’ordre n” sur lequel nous allons travailler. Vous avez surement rencontré les groupes durant vos études en mathématiques. Le groupe des entiers N, ou des nombres rationnels R, par exemple. Sur chacun de ces groupes, les opérations algébriques que l’on peut réaliser sont définies telles que nous les connaissons habituellement (exemple 2 + 3 = 3 + 2 = 5). Sur les gorupes utilisés en cryptographie, c’est en revanche un peu différent. En cryptographie asymétrique, il peut être avantageux de pouvoir compter sur des outils/fonctions “qui fonctionnent bien dans un sens mais pas du tout dans l’autre”. En d’autres termes, on pourrait parler de “boîtes noires” : il est facile d’obtenir un résultat en appliquant l’outil, mais personne ne doit pouvoir retrouver l’antécédent à partir de la connaissance de la sortie de la “boîte noire”.

Lorsque l’on reste dans les groupes classiques, la plupart des fonctions admettent une bijection réciproque, c’est-à-dire une fonction “qui permet de faire le chemin inverse” (eg : si f(g(x)) = g(f(x)) alors g est la bijection réciproque de f et vice-versa). Si l’on se place dans un groupe bien choisit, de nombreuses fonctions simples n’admettent pas de bijections réciproques, et on arrive donc à quelque chose qui s’approche de notre concept de boîte noire.

En pratique pour les Zk-Snark, le groupe choisi est une courbe elliptique, à laquelle est associée une “pairing function”. C’est à partir de ce groupe d’ordre n que l’on définit la fonction de chiffrement suivante :

E(x) = g^x

(où g représente le générateur du groupe)

On dit que g est générateur du groupe G d’ordre n si et seulement si la liste g⁰, g¹, g², …, g^(n-1) décrit toutes les valeurs du groupe. Cette propriété d’ordre du groupe est très importante, car si l’on travaillait avec des nombres réels, il suffirait de calculer log(g^x) pour retrouver x, or le but ici est de créer des objets qui s’apparentent le plus possible à des boîtes noires : il faut qu’il soit facile de calculer E(x) pour tout x, mais impossible de retrouver x à partir de E(x). C’est exactement la propriété que nous offre ce type de groupe, puisque :

pour n≥ 3 (par exemple),

on a E(3) = E(n+3) = E(2n+3) = … = E(kn+3) quelque soit k

(preuve : E(3) = g³ = g^(n+3) …).

Et alors, la “pairing function” e() associée fonctionne de la manière suivante :

Pour tout (x,y) dans G, on a :

e(g^x, g^y)= e(g,g)^xy

Comme (x,y) sont dans G, il est impossible d’appliquer une transformation logarithmique pour retrouver les antécédents par la fonction de chiffrement. En fait, il n’existe aucune méthode connue pour retrouver ces antécédents, c’est justement l’idée que nous avons présenté sur le passage à propos de la théorie de la complexité. En pratique, l’ordre du groupe est cependant supérieur à 3 pour des raisons de sécurité évidentes.

5. Zk-Snarks en pratique (enfin !) :

Nous avons désormais tous les éléments pour comprendre en quoi consiste le trusted setup et pour comprendre comment le prover peut générer une preuve à connaissance zéro pour un problème. C’est parti !

Rappelons déjà, que nous avons les deux suites de polynômes (V0, V1, …, Vm) et (Wo, W1, …, Wm), ainsi qu’un polynôme cible Z de degré inférieur au égal à d.

En l’état, le problème QAP peut s’avérer long à résoudre car pour un ordinateur classique les produits polynomiaux peuvent être lourds en calcul pour de grands polynômes. Si effectuer des produits de polynômes peut-être intensif en calcul, ce n’est pas le cas d’opérations de même nature mais portant sur des nombres, c’est-à-dire sur des polynomes évalués en certains points. C’est pourquoi en pratique, il s’agira de choisir au hasard des éléments du groupe et de calculer la valeur des polynômes en ces points pour ensuite vérifier si la division tient. Réduire le problème du QAP à certaines valeurs permet de réduire drastiquement le temps de traitement, et dans la mesure où les points sont choisis au hasard, si l’égalité est vérifiée pour ces points, il est presque certain que cette même égalité tienne pour tout x. C’est cette astuce qui confère la propriété de “succintness” à ces preuves.

Ainsi, le verifier va choisir une valeur “s” dans G et un “⍺” réel, qui doivent absolument être détruits (toxic waste). Ensuite il publie dans le CRS :

E(s⁰), E(s¹), …, E(s^d) et E(⍺s⁰), E(⍺s¹), …, E(⍺s^d)

Puis il publie :

E(Z(s)), E(⍺Z(s))
E(V0(s)), …, E(Vm(s)) ; E(⍺V0(s)), …, E(⍺Vm(s))
E(W0(s)), …, E(Wm(s)) et E(⍺W0(s)), …, E(⍺Wm(s))

Enfin il choisit βv, βw, γ réels et publie :

E(γ), E(βv γ), E(βw γ),
E(βv v1(s)), …, E(βv Vm(s))
E(βw W1(s)), …, E(βw Wm(s))
E(βv Z(s)), E(βw Z(s))

Cette dernière série de valeurs va être utilisée pour vérifier que les polynômes évalués sont bien les polynômes (V0, …, Vm ; W0, …, Wm ; Z) et pas n’importe quels polynômes. Ces huits lignes de valeurs représentent alors le CRS entier.

Que reste-t-il à faire au prover ?

Il utilise la fonction de réduction “f” que nous avons défini dans la partie sur le QAP, afin d’obtenir (a1, …, am) et (b1, …, bm) ainsi que le polynôme H. Or, comme m est relativement grand (2 millions dans ZCash), pour une input donnée, il existe nécessairement des indices qui ne sont pas utilisés. Notons ces indices I-free et définissons V-free(x) = Σk akVk(x) où k décrit tous les indices dans I-free.

Enfin on définit W(x) = b1W1(x) + …. + bmWm(x), et la preuve a alors la forme suivante :

V-free = E(V-free(s)), W = E(W(s)), H = E(H(s)),
V’-free = E(α V-free(s)), W’ = E(α W(s)), H’ = E(α H(s)),
Y = E(βv V-free(s) + βw W(s)))

La première ligne correspond en fait à la valeur chiffrée des polynômes W et H au point s, auxquelles s’ajoute la valeur chiffrée de la combinaison linéaire des polynômes Vk au point “s” pout tout les indices qui ne sont pas décrits par la fonction de réduction f appliquée à notre input spécifique “x”. Ces indices ne sont donc jamais les mêmes d’une preuve à l’autre. La seconde ligne correspond aux valeurs des mêmes polynômes, mais évalués en “αs” cette fois. Et la troisième ligne sert à prouver que ce sont bien les “bons polynômes” qui sont évalués et pas n’importe quels polynômes. Bien entendu, le prover peut produire toutes ces valeurs uniquement à partir de ce que le verifier a mis dans le CRS.

Rappelons que l’input “x” est connue du verifier (c’est ce qui est à vérifier). De cela il vient que, le verifier peut calculer les valeurs de ak pour tous les indices k qui ne sont pas dans I-free, puisque la séparation entre les deux groupes d’indice est faite à partir de “x”. Ainsi, le verifier peut calculer la partie manquante de la somme, c’est-à-dire la combinaison linéaire pour tous les k qui ne sont pas dans I-free :

E(V-in(s)) = E(Σk akVk(s)) où k décrit tous les indices qui ne sont pas dans I-free.

A partir de cette dernière valeur et de la pairing function, le verifier vérifie les 3 séries d’égalité suivantes :

e(V’-free, g) = e(V-free, gα), e(W’, E(1)) = e(W, E(α)), e(H’, E(1)) = e(H, E(α))
e(E(γ), Y) = e(E(βv γ), V-free) e(E(βw γ), W)
e(E(V0(s)) E(V-in(s)) V-free, E(W0(s)) W) = e(H, E(Z(s)))

En (1), on vérifie trois fois la même chose, mais à chaque fois sur un polynôme différent, à savoir, que les valeurs produites par le prover correspondent bien à des constructions polynomiales faites à partir de ce qui a été publié dans le CRS.

Remarque: La valeur 1 apparaît à cet endroit car il faut pouvoir comparer W’ et αW qui sont cryptés, or comme W’ = E(αW(s)), que W = E(W(s)) et que E est homomorphique, il vient que : e(W’, E(1)) = g^(W’ x 1) = g^(W x α) = e(W, E(α)). Idem pour les deux autres relations. Cette relation ne tiendrait pas si ces polynômes n’étaient pas construits à partir des valeurs dans le CRS, pour la simple et bonne raison que la pairing function utilisée est choisie spécifiquement pour être compatible avec le groupe défini.

En (2), on s’assure en fait que ce sont bien les bons polynômes qui sont évalués et pas n’importe quels polynômes. Rappelez-vous, c’est pour ça qu’on avait ajouté E(γ), E(βv γ) et E(βw γ) au CRS. La partie gauche de l’égalité se développe ainsi :

e(E(γ), Y) = e(E(γ), E(βv vfree(s) + βw w(s))) = e(g, g)γ(βv vfree(s) + βw w(s))

Et la partie droite, nous donne ceci :

e(E(βv γ), V-free) e(E(βw γ), W) = e(E(βv γ), E(v-free(s))) e(E(βw γ), E(w(s))) = e(g, g)^((βv γ) v-free(s)). e(g, g)^((βw γ) w(s)) = e(g, g)^(γ(βv vfree(s) + βw w(s))).

Je vous accorde que ces développements sont parfaitement indigestes ! En fait ici, on a tout simplement développés les parties droite et gauches de (2) pour les exprimer comme une puissance de e(g,g) (où g est notre fameux générateur) afin de vérifier que l’égalité (2) est vraie. Ce qui, rappelons-le, atteste du fait que le prover a bien utilisé les mêmes polynômes que le verifier pour construire la preuve.

Enfin en (3) on vérifie tout simplement que l’égalité polynomiale du problème QAP est vraie, i.e. on vérifie que (V0(s) + a1V1(s) + … + amVm(s)) (W0(s) + b1W1(s) + … + bmWm(s)) = H(s) Z(s). Ici, la suite polynomiale est scindée en 2, car c’est ainsi que l’on s’assure que les coefficients (a1, …, am) et (b1, …, bm) ne sont pas choisis n’importe comment. Autrement dit, cette dichotomie des indices vient attester du fait que la fonction de réduction a été utilisée correctement par les deux parties (si ce n’est pas le cas, l’égalité est fausse).

Pour comprendre en quoi, le fait que l’égalité (3) soit vrai, atteste du fait que f(w) = x (formulation initiale du problème), il faut se rappeler, que notre problème initial a été converti en un QAP, dont les polynômes ont été construits à partir de valeurs chiffrées ; et que par conséquent, sans la connaissance de w, le prover n’aurait jamais pu créer une solution au problème QAP. La meilleure stratégie que peut adopter un agent extérieur pour produire une preuve sans connaitre w est tout simplement de choisir des combinaisons linéaires au hasard, or comme il en existe une infinité, on peut très raisonnablement décréter que puisque les égalités (1), (2) et (3) sont vraies, c’est que le prover connaît w tel que f(w) = x.

6. Zero-Knowledge ?

Si vous avez bien suivi notre explication vous ne devriez pas être satisfait par ce système pour l’instant ! En effet, il n’est pas à connaissance zéro ! Il faut remarquer que V-free et W sont une codification du witness “w”, or comme ils sont publiés avec la preuve, on peut imaginer qu’un agent malveillant puisse construire de fausses preuves en dérivant le witness de V-free et W.

Pour que le procédé que nous avons décrit jusqu’ici soit réellement à connaissance zéro, on effectue simplement les deux remplacements suivants :

V-free(s) est remplacé par V-free(s) + δ-free Z(s)
W(s) est remplacé par W(s) + δw Z(s).

En pratiquant ces substitution on s’assure que V-free(s) et W(s) deviennent impossible à différencier de nombres totalement aléatoires, ce qui nous ramène notre caractéristique “à connaissance zéro”. Et ces modifications, ne change rien à ce que nous avons décrit précédemment car les fonctions de pairing ne sont pas affectées par ce genre de transformation.

Voici la preuve pour les plus sceptiques :

On veut vérifier que :

(V0(s) + V-in(s) + V-free(s)) (W0(s) + W(s)) = H(s) Z(s) ,

ce qui revient désormais à vérifier que :

(V0(s) + V-in(s) + V-free(s) + δ-free Z(s)) (W0(s) + W(s) + δw Z(s))

En développant on remarque que, ce qui était H(s) dans la partie précédente, devient :

H(s) + δfree (W0(s) + W(s)) + δw (V0(s) + V-in(s) + V-free(s)) + (δ-free δw) Z(s)

Or, comme on a également affaire à un polynôme, cela signifie que la solution satisfait toujours au QAP, et désormais notre preuve a le bon goût d’être totalement à connaissance zéro !

NB: Par mesure de simplification nous avons présenté le sujet en travaillant sur des points unidimensionnels, mais il faut garder en tête que dans une application réelle des Zk-Snark, les éléments considérés seraient des vecteurs. Cette substitution ne change cependant rien à la logique fondamentale du système, et ne contrevient pas à la véracité des preuves que nous avons donné, mais elle introduit une lourdeur algébrique qui peut rendre le sujet encore plus indigeste.

NB2: A l’heure où j’écris ces lignes il est possible d’effectuer des Zk-Snark sur Ethereum (mainnet ou testnet ?), cependant le coût associé à l’utilisation de ces méthodes demeure assez élevé pour l’instant (1,600,000 gas par preuve). Ceci devrait changer dès la prochaine update Ethereum.

Conclusions et Remarques :

Félicitations pour votre persévérance et votre patience, le sujet que vous venez de découvrir est sûrement ce que vous rencontrerez de plus complexe durant vos recherches sur la Blockchain. Cette complexité n’est cependant pas accessoire, car vous conviendrez que ce que permettent de réaliser les Zk-Snarks est d’une très grande valeur, notamment dans le cadre des systèmes Blockchain. Gardez cependant en tête que ces techniques de preuves à connaissance zéro (dont les Zk-Snarks ne sont qu’une sous-catégorie) peuvent être utilisés sur d’autres données que celles contenues sur une Blockchain. Pour que le cas d’usage soit pertinent il faut cependant que la donnée sur laquelle porte le test soit “notariée”, c’est-à-dire qu’elle soit validée par une forme de consensus quelconque (même si elle est validée dans sa forme chiffrée). Ceci, car il serait stupide d’effectuer un test sur une donnée qu’un agent peut modifier unilatéralement. Pour reprendre l’exemple de la carte, cela revient à dire que notre test n’aurait pas de sens si la carte pouvait avoir été modifiée par son détenteur. Cela ne peut pas arriver avec un jeu de carte pour des raisons évidentes, mais c’est largement possible pour une donnée contenue dans une base de donnée privée.

Enfin, je vous prie de m’excuser si cette explication comporte des erreurs et des imprécisions, n’étant pas cryptographe de métier, je ne peux vous garantir la totale exactitude de ce qui précède. Au cas où vous n’auriez pas peur d’attaquer ce sujet en anglais, je vous invite largement à lire la série d’article rédigée par V. Buterin à ce sujet, ou encore celle produite par l’équipe ZCash, avec eux, il n’y a pas de risque de ce genre :)

Toute correction ou remarque de la part des lecteurs sera la bienvenue. N’oubliez pas de mettre vos claps si cette lecture vous a plu :)