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

Arbres de Merkle et preuves d’appartenance

Après cette leçon: Je peux vérifier une preuve d’appartenance de Merkle face à une racine.

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

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

MotCe que ça veut dire
Feuillele hachage d’un élément de la liste
Nœudle hachage de deux hachages mis bout à bout
Racinele hachage unique en haut de l’arbre
Voisinl’autre hachage d’une paire
Preuve d’appartenanceles 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

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

Commande
docker exec jupyter python3 steps/membership.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. 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 listeNiveaux au-dessus des feuillesHachages dans une preuve
422
833
10241010
10485762020

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

Commande
docker exec jupyter grep -n def merkle.py

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.