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
| Begriff | Was er bedeutet |
|---|---|
| Blatt | der Hash eines Elements der Liste |
| Knoten | der Hash aus zwei verbundenen Hashes |
| Wurzel | der einzige Hash an der Spitze des Baums |
| Geschwister | der andere Hash in einem Paar |
| Mitgliedschaftsbeweis | die 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
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
docker exec jupyter python3 steps/membership.pyHier 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 Liste | Ebenen über den Blättern | Hashes im Beweis |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 3 | 3 |
| 1024 | 10 | 10 |
| 1048576 | 20 | 20 |
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
docker exec jupyter grep -n def merkle.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.