Glossar / Mining und Konsens
Merkle-Baum
- Was ist ein Merkle-Baum?
- Ein Merkle-Baum ist die Hash-Pyramide, die jede Transaktion in einem Block auf einen einzigen Wert von 32 Byte verdichtet, sodass jede einzelne Zahlung ohne den Rest bewiesen werden kann.
Paaren Sie die Transaktions-Hashes, hashen Sie jedes Paar und wiederholen Sie das, bis ein einziger Hash übrig bleibt. Dieser eine Wert steht im Block-Header, und um zu beweisen, dass eine Transaktion dazugehört, sind nur die Hashes entlang eines Pfades nötig: elf davon, 352 Byte, für einen Block mit 2.000 Zahlungen. Deshalb kann eine Wallet auf dem Smartphone prüfen, dass Ihre Bitcoin angekommen sind, ohne den Block herunterzuladen.
So funktioniert es
Ein Merkle-Baum verwandelt eine Liste in eine Pyramide, indem benachbarte Einträge Ebene für Ebene paarweise gehasht werden, bis nur noch ein Hash übrig bleibt.
Die Blätter sind die Transaktions-IDs in der Reihenfolge, in der der Miner sie platziert hat. Bitcoin kombiniert jedes Paar, indem es die beiden Werte von 32 Byte aneinanderhängt und SHA-256 zweimal auf das Ergebnis anwendet. Wenn eine Ebene eine ungerade Anzahl von Einträgen enthält, wird der letzte mit einer Kopie seiner selbst gepaart, was den Algorithmus einfach hält und einmal echten Ärger verursacht hat: Die als CVE-2012-2459 katalogisierte Schwachstelle, offengelegt im Mai 2012 und im selben Monat behoben, missbrauchte diese Verdopplung, um einen Block zu konstruieren, der für Nodes ungültig aussah, obwohl die zugrunde liegenden Transaktionen in Ordnung waren.
Der Nutzen ist logarithmisch. Eine Verdopplung der Transaktionszahl fügt eine Ebene hinzu, nicht einen Hash pro Transaktion. Ein Block mit 1.024 Zahlungen benötigt zehn Hashes für den Zugehörigkeitsbeweis, 320 Byte. Viertausendsechsundneunzig benötigt zwölf, 384 Byte. Wer den Beweis prüft, berechnet den Pfad nach oben neu und vergleicht das Ergebnis mit der Wurzel, der er aus dem Header bereits vertraut, und es gibt keine Möglichkeit, einen Pfad zu fälschen, ohne SHA-256 zu brechen.
Nichts davon stammt von Bitcoin. Ralph Merkle beschrieb die Konstruktion in der Patentanmeldung, aus der das US-Patent 4.309.569 wurde, eingereicht 1979 und erteilt im Januar 1982. Das Whitepaper zitiert seine Arbeit und setzt den Baum für zwei Zwecke ein: das Entfernen ausgegebener Transaktionen aus alten Blöcken, um Speicherplatz zu sparen, in Abschnitt 7, und die Möglichkeit für einen Client, eine Zahlung zu verifizieren, während er nur Header speichert, in Abschnitt 8.
Wo er auftritt
Merkle-Bäume erscheinen überall dort, wo ein System beweisen muss, dass ein Element zu einer großen Menge gehört, ohne die Menge zu übertragen.
Innerhalb von Bitcoin trägt jeder Block-Header die Spitze eines solchen Baums. Ein Node baut den Baum aus den empfangenen Transaktionen neu auf und lehnt den Block ab, wenn das Ergebnis nicht übereinstimmt. Bitcoin Core legt den Mechanismus direkt offen: gettxoutproof erzeugt einen serialisierten Beweis, dass eine Transaktion in einen Block aufgenommen wurde, und verifytxoutproof prüft einen solchen, was ein praktischer Weg ist, jemandem einen Nachweis einer Zahlung zu geben, ohne ihm eine Wallet zu überlassen.
An anderer Stelle in Bitcoin baut Taproot einen zweiten Baum: Die alternativen Ausgabebedingungen eines Taproot-Outputs sind als Baum angeordnet, sodass das Offenlegen des verwendeten Zweigs nichts über die nicht verwendeten Zweige verrät. Außerhalb von Bitcoin liegt dieselbe Form der Commit-Historie von Git zugrunde, den Certificate-Transparency-Logs, die fehlerhaft ausgestellte Webzertifikate aufdecken, und den Datenintegritätsprüfungen des ZFS-Dateisystems.
Für einen Wallet-Nutzer ist die sichtbare Folge klein und nützlich. Ein leichter Client, der ein paar Dutzend Megabyte an Headern speichert, kann bestätigen, dass Ihre Transaktion in einem bestimmten Block steckt, in einer bestimmten Tiefe, und erhält nur dann eine falsche Antwort, wenn jemand gültigen Proof of Work auf einer gefälschten Chain erzeugt hat, was echtes Geld kostet.
Merkle-Baum vs. Merkle-Root
Der Merkle-Baum ist die Arbeitsstruktur; die Merkle-Wurzel ist der eine Wert, der danach erhalten bleibt. Ein Node baut die ganze Pyramide im Speicher auf, während er einen Block validiert, und wirft sie dann weg, wobei er nur die 32 Byte speichert, die oben übrig geblieben sind, denn alles darunter lässt sich aus den Transaktionen neu erzeugen. Wenn ein Explorer Ihnen ein Feld namens Merkle-Root zeigt, ist das der übrig gebliebene Wert. Niemand speichert den Baum, und niemand muss es.