Prouver votre âge sans montrer votre naissance
Un circuit arithmétique écrit un énoncé sur un secret sous forme de petites sommes et de petits produits qui doivent tous tenir. Un SNARK est une preuve courte : vous connaissez des valeurs qui les font tous tenir.
C’est ainsi qu’un système peut vérifier que vous avez plus de 18 ans, ou que vous êtes sur une liste, sans voir les données privées.
À la fin de cette leçon
Remarque
Je peux écrire un énoncé sur un secret sous forme de contraintes et contrôler un témoin face à elles.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Corps | les entiers modulo un nombre premier, avec addition et multiplication | modulo 97 |
| Porte | une somme ou un produit, avec sa sortie | |
| Témoin | une valeur pour chaque fil, secret compris | |
| Contrainte | une équation que le témoin doit vérifier | |
| SNARK | une preuve courte qu’un témoin existe, rapide à vérifier |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un énoncé devient une liste de portes
Prenez l’énoncé « je connais x tel que x fois x plus 2 fois x égale 48 ». Découpez-le en étapes qui font une seule chose : x2 = x fois x, two_x = x plus x, out = x2 plus two_x. Chaque étape est une porte.
Le prouveur remplit chaque fil : c’est le témoin. La partie publique est out = 48. Chaque valeur vit dans un corps, ici modulo 97.
Contrôler un témoin face aux portes
docker exec jupyter python3 steps/constraints.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Lire ce que le labo a affiché
Le labo écrit en anglais : « first bad gate » veut dire première porte fausse. Pour x = 6, le témoin vaut x2 = 36, two_x = 12 et out = 48, et la première porte fausse est -1, c’est-à-dire aucune. Toutes les portes tiennent.
Un prouveur avec x = 5 qui annonce out = 48 échoue à la porte 2, la dernière addition, car 25 plus 10 font 35. Un faux témoin ne peut pas satisfaire toutes les portes.
À vous : les portes d’un cube
F = 97 # chaque somme et chaque produit se calcule modulo 97
# Énoncé : « je connais x tel que x * x * x + 2 * x = 33 », et 33 est public.
portes = [
["mul", "x", "x", "x2"],
["mul", "x2", "x", "x3"],
["add", "x", "x", "deux_x"],
["add", "x3", "deux_x", "sortie"],
]
x = 3
w = {"x": x, "x2": x * x % F, "x3": x * x * x % F, "deux_x": 2 * x % F, "sortie": 33}
for porte in portes:
a = w[porte[1]]
b = w[porte[2]]
if porte[0] == "mul":
valeur = a * b % F
else:
valeur = (a + b) % F
print(porte[0], porte[1], porte[2], "->", porte[3], "tient :", valeur == w[porte[3]])
# Remplacez x = 3 par x = 4 (sortie reste 33) et relancez. Quelle porte échoue ?
Un contrôle d’intervalle est fait de bits
Pour prouver qu’un secret x est entre 0 et 15 sans le montrer, le prouveur donne quatre bits. Deux sortes de contraintes les contrôlent. Chaque bit b doit vérifier b fois b égale b, ce que seuls 0 et 1 font. Et les bits, pondérés par 1, 2, 4 et 8, doivent avoir x pour somme.
Le labo a contrôlé 11 écrit 1, 1, 0, 1 : vrai. Un bit à 2 a cassé la première règle : faux.
Exemple travaillé : des portes en contraintes
| Porte | Contrainte, gauche fois droite égale sortie | Avec x = 6 |
|---|---|---|
| x2 = x fois x | x fois x = x2 | 6 fois 6 = 36 |
| two_x = x plus x | (x + x) fois 1 = two_x | 12 fois 1 = 12 |
| out = x2 plus two_x | (x2 + two_x) fois 1 = out | 48 fois 1 = 48 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Où intervient un SNARK
Jusqu’ici, le vérificateur a contrôlé le témoin en le voyant, ce qui montre le secret. Un SNARK permet au prouveur de convaincre le vérificateur qu’un tel témoin existe. La preuve fait quelques centaines d’octets et se vérifie vite, quelle que soit la taille du circuit.
Des langages comme Noir et Circom transforment un énoncé en contraintes de ce genre. Ce labo ne les fait pas tourner : il n’a pas de prouveur, donc le circuit reste en Python.
Lister les fonctions de circuit.py
docker exec jupyter grep -n def circuit.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
On croit souvent qu’un SNARK prouve que l’énoncé a du sens. Il prouve seulement que les contraintes tiennent. S’il manque une contrainte, comme la règle des bits, un prouveur peut satisfaire le reste avec des valeurs que l’auteur n’a jamais voulues.