Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Circuits, contraintes et place des SNARK

Après cette leçon: Je peux écrire un énoncé sur un secret sous forme de contraintes et contrôler un témoin face à elles.

Leçon de 70 min2 commandesLab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

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

MotCe que ça veut direExemple
Corpsles entiers modulo un nombre premier, avec addition et multiplicationmodulo 97
Porteune somme ou un produit, avec sa sortie
Témoinune valeur pour chaque fil, secret compris
Contrainteune équation que le témoin doit vérifier
SNARKune 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

Commande
docker exec jupyter python3 steps/constraints.py

Affiché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

Code: python
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

PorteContrainte, gauche fois droite égale sortieAvec x = 6
x2 = x fois xx fois x = x26 fois 6 = 36
two_x = x plus x(x + x) fois 1 = two_x12 fois 1 = 12
out = x2 plus two_x(x2 + two_x) fois 1 = out48 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

Commande
docker exec jupyter grep -n def circuit.py

Affiché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.

À propos de ce labo et de sa source: Lab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.