Prouver qu’un nom figure sur une longue liste
Un arbre de Merkle résume toute une liste en un seul hachage court, la racine. Une preuve d’appartenance montre ensuite qu’un élément est dans la liste avec quelques hachages seulement, et non la liste entière.
Les systèmes à divulgation nulle s’en servent pour prouver qu’on appartient à un groupe, et les blockchains pour prouver qu’un paiement est dans un bloc.
À la fin de cette leçon
Remarque
Je peux vérifier une preuve d’appartenance de Merkle face à une racine.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Feuille | le hachage d’un élément de la liste |
| Nœud | le hachage de deux hachages mis bout à bout |
| Racine | le hachage unique en haut de l’arbre |
| Voisin | l’autre hachage d’une paire |
| Preuve d’appartenance | les voisins sur le chemin d’une feuille à la racine |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un arbre, ce sont des hachages de hachages
Hachez chaque élément pour obtenir les feuilles. Groupez les feuilles par paires et hachez chaque paire pour obtenir le niveau suivant. Recommencez jusqu’à ce qu’il reste un seul hachage : la racine.
Changez un élément, et sa feuille change, puis son parent, et ainsi de suite jusqu’à la racine. La racine représente donc toute la liste. Le module 37 (blockchain) reliait des blocs en ligne par des hachages ; un arbre les relie par paires.
À vous : un arbre de quatre salles
import hashlib
def feuille(element):
return hashlib.sha256(("leaf:" + element).encode()).hexdigest()
def noeud(gauche, droite):
return hashlib.sha256(("node:" + gauche + droite).encode()).hexdigest()
# Quatre salles réservées dans un bâtiment partagé.
a = feuille("salle-1")
b = feuille("salle-2")
c = feuille("salle-3")
d = feuille("salle-4")
gauche = noeud(a, b)
droite = noeud(c, d)
racine = noeud(gauche, droite)
print("racine :", racine[:16])
# Une preuve que salle-3 est réservée : d, puis gauche.
controle = noeud(gauche, noeud(feuille("salle-3"), d))
print("la preuve de salle-3 donne la racine :", controle == racine)
# Échangez gauche et le noeud intérieur dans l’appel extérieur, et relancez.
Une preuve, ce sont les voisins en montant
Pour montrer qu’un élément est dans la liste, donnez ses voisins. C’est le hachage à côté de lui, puis celui à côté de son parent, et ainsi de suite. Celui qui vérifie hache l’élément, ajoute chaque voisin du bon côté, et compare le résultat à la racine.
Une liste de 8 demande 3 voisins, et une liste d’environ un million seulement 20.
Vérifier que dev est dans la liste
docker exec jupyter python3 steps/membership.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. Huit noms ont donné une racine qui commence par fb53457810bd44ae. La preuve pour dev, le quatrième nom, compte 3 hachages, chacun marqué L ou R selon son côté, gauche ou droite. En hachant dev le long du chemin, on retrouve la racine : la réponse est True.
Le nom dan avec la même preuve donne False. Personne ne sait fabriquer un chemin qui mène un autre nom à cette racine.
Exemple travaillé : la longueur d’une preuve
| Éléments dans la liste | Niveaux au-dessus des feuilles | Hachages dans une preuve |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 3 | 3 |
| 1024 | 10 | 10 |
| 1048576 | 20 | 20 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
On croit souvent que les voisins se joignent dans n’importe quel ordre. C’est faux : noeud(a, b) et noeud(b, a) sont deux hachages différents. La position de l’élément donne le côté. À une position paire, le voisin va à droite.
Lister les fonctions de merkle.py
docker exec jupyter grep -n def merkle.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.