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

Qu’est-ce qu’une preuve à divulgation nulle ?

Après cette leçon: Je peux expliquer la complétude, la correction et la divulgation nulle à l’aide d’une preuve interactive.

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

Prouver qu’on connaît un secret sans le dire

Une preuve à divulgation nulle de connaissance permet de convaincre quelqu’un que vous connaissez un secret, sans montrer ce secret. Elle sert à se connecter sans envoyer de mot de passe et à prouver des faits sur des données privées.

Aujourd’hui, vous jouez à un jeu qui montre l’idée, puis vous mesurez pourquoi il fonctionne.

À la fin de cette leçon

Remarque

Je peux expliquer la complétude, la correction et la divulgation nulle à l’aide d’une preuve interactive.

Mots-clés

MotCe que ça veut dire
Prouveurcelui qui affirme connaître un secret
Vérificateurcelui qui contrôle l’affirmation
Défiune question tirée au hasard par le vérificateur
Complétudeun prouveur honnête réussit toujours
Correctionun prouveur qui triche échoue presque toujours
Divulgation nullele vérificateur n’apprend rien, sauf que l’affirmation est vraie

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

La caverne, une preuve interactive

Une caverne a deux chemins, A et B, reliés au fond par une porte fermée à clé. Le prouveur dit qu’il connaît le mot qui ouvre la porte.

Le prouveur entre par un chemin pendant que le vérificateur attend dehors. Puis le vérificateur crie un chemin au hasard, A ou B. Le prouveur doit sortir par ce chemin. Avec le mot, il y arrive toujours. Sans le mot, il ne réussit que s’il a deviné juste, une fois sur deux.

Jouer de nombreuses fois à la caverne

Commande
docker exec jupyter python3 steps/cave.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 : « rounds » veut dire tours et « cheaters » tricheurs. Le prouveur qui connaît le mot a réussi 20 tours sur 20. C’est la complétude.

Ensuite, 1000 tricheurs ont joué. Après le tour 1, il en restait 493, après le tour 2 seulement 243, et après le tour 10 aucun. Chaque tour les divise à peu près par deux. Vingt tours laissent à un tricheur une chance sur 1048576. C’est la correction.

Exemple travaillé : la chance d’un tricheur

ToursChance de tous les réussir en trichantEn nombre décimal
11 sur 20,5
21 sur 40,25
31 sur 80,125
101 sur 1024environ 0,001
201 sur 1048576environ 0,000001

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

À vous : un tricheur dans la caverne

Code: python
import random

rng = random.Random(3)

def un_tour(connait_le_mot):
    entre_par = rng.choice("AB")
    demande = rng.choice("AB")
    if connait_le_mot:
        return True
    return entre_par == demande

reussis = 0
for n in range(10):
    if un_tour(False):
        reussis = reussis + 1
    else:
        print("pris au tour", n + 1)
        break
print("tours réussis :", reussis)
# Remplacez False par True, pour que le prouveur connaisse le mot, et relancez.

Pourquoi le vérificateur n’apprend rien

Si vous regardez de dehors, vous voyez le prouveur sortir par le chemin demandé. Vous n’entendez jamais le mot.

Pire pour un espion : un film du jeu ne prouve rien. Les deux personnes ont pu convenir des chemins à l’avance et couper le film. Si un faux enregistrement ressemble en tout à un vrai, le vrai ne dévoile rien. C’est l’idée de la divulgation nulle.

Erreur fréquente

Attention

On croit souvent que divulgation nulle veut dire que le vérificateur n’apprend rien du tout. Il apprend une chose : que l’affirmation est vraie. Ce qu’il n’apprend pas, c’est le secret, ni rien qui l’aide à le trouver.

Lister les scripts du labo

Commande
docker exec jupyter ls steps

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

À 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.