Lässt es sich mit cremefarbenem Papier, einer Tönung, mehr Kontrast oder größerer Schrift besser lesen? Wählen Sie Ihre Farben und Ihre Schrift, einmalig für alle Seiten.

Kostenlose Lektion

Merkle-Bäume und Mitgliedschaftsbeweise

Nach dieser Lektion: Ich kann einen Merkle-Mitgliedschaftsbeweis gegen eine Wurzel prüfen.

Lektion, 65 Min.2 BefehleZero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

Ein Name auf einer langen Liste

Ein Merkle-Baum macht aus einer ganzen Liste einen einzigen kurzen Hash, die Wurzel. Ein Mitgliedschaftsbeweis zeigt dann mit wenigen Hashes, dass ein Element auf der Liste steht. Die ganze Liste braucht man dafür nicht.

Zero-Knowledge-Systeme beweisen damit, dass man zu einer Gruppe gehört. Blockchains beweisen damit, dass eine Zahlung in einem Block steht.

Am Ende dieser Lektion

Notiz

Ich kann einen Merkle-Mitgliedschaftsbeweis gegen eine Wurzel prüfen.

Schlüsselwörter

BegriffWas er bedeutet
Blattder Hash eines Elements der Liste
Knotender Hash aus zwei verbundenen Hashes
Wurzelder einzige Hash an der Spitze des Baums
Geschwisterder andere Hash in einem Paar
Mitgliedschaftsbeweisdie Geschwister auf dem Pfad von einem Blatt zur Wurzel

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Ein Baum besteht aus Hashes von Hashes

Hashen Sie jedes Element, das ergibt die Blätter. Verbinden Sie die Blätter paarweise und hashen Sie jedes Paar, das ergibt die nächste Ebene. Wiederholen Sie das, bis ein einziger Hash bleibt: die Wurzel.

Ändert sich ein Element, ändert sich sein Blatt, dann der Knoten darüber und so weiter bis zur Wurzel. Die Wurzel steht also für die ganze Liste. Modul 37 (Blockchain) hat Blöcke in einer Reihe mit Hashes verkettet; ein Baum verkettet sie paarweise.

Probieren Sie es: ein Baum aus vier Räumen

Code: python
import hashlib

def blatt(element):
    return hashlib.sha256(("leaf:" + element).encode()).hexdigest()

def knoten(links, rechts):
    return hashlib.sha256(("node:" + links + rechts).encode()).hexdigest()

# Vier gebuchte Räume in einem gemeinsamen Gebäude.
a = blatt("raum-1")
b = blatt("raum-2")
c = blatt("raum-3")
d = blatt("raum-4")
links = knoten(a, b)
rechts = knoten(c, d)
wurzel = knoten(links, rechts)
print("Wurzel:", wurzel[:16])

# Ein Beweis, dass raum-3 gebucht ist: erst d, dann links.
probe = knoten(links, knoten(blatt("raum-3"), d))
print("Beweis für raum-3 ergibt die Wurzel:", probe == wurzel)
# Tauschen Sie im äußeren Aufruf links und den inneren Knoten und starten Sie erneut.

Ein Beweis sind die Geschwister nach oben

Um zu zeigen, dass ein Element auf der Liste steht, gibt man seine Geschwister an. Zuerst den Hash daneben, dann den Hash neben dem Knoten darüber und so weiter. Wer prüft, hasht das Element, verbindet jedes Geschwister auf der richtigen Seite und vergleicht das Ergebnis mit der Wurzel.

Eine Liste mit 8 Elementen braucht 3 Geschwister, eine Liste mit etwa einer Million nur 20.

Prüfen, ob dev auf der Liste steht

Befehl
docker exec jupyter python3 steps/membership.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Lesen Sie, was das Lab gedruckt hat

Acht Namen ergaben eine Wurzel, die mit fb53457810bd44ae beginnt. Der Beweis für dev, den vierten Namen, hat 3 Hashes. Jeder trägt L oder R für die Seite, auf der er steht. dev den Pfad hinauf gehasht ergab die Wurzel, die Antwort war also True.

Der Name dan mit demselben Beweis ergab False. Niemand kann einen Pfad bauen, der einen anderen Namen zu dieser Wurzel macht.

Beispiel: wie lang ein Beweis ist

Elemente auf der ListeEbenen über den BlätternHashes im Beweis
422
833
10241010
10485762020

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Ein häufiger Fehler

Warnung

Viele glauben, die Geschwister ließen sich in beliebiger Reihenfolge verbinden. Das stimmt nicht: knoten(a, b) und knoten(b, a) sind verschiedene Hashes. Die Position des Elements nennt die Seite. Bei einer geraden Position auf einer Ebene kommt das Geschwister nach rechts.

Die Funktionen in merkle.py auflisten

Befehl
docker exec jupyter grep -n def merkle.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Über dieses Lab und seinen Quellcode: Zero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

Sie unterrichten eine Gruppe? Weisen Sie dieses Modul Ihren Studierenden zu, mit Handbuch für Lehrende, automatisch geprüften Aufgaben und einem Lab für jede Person.