Ein Merkle-Baum ordnet Datenhashes in einer Baumstruktur an. Der oberste Hash, die Merkle-Wurzel, fasst die gebundene Datensammlung zusammen. Jeder Elternknoten wird nach festgelegten Regeln aus seinen Kindern berechnet. Die Änderung eines Blattes verändert gewöhnlich alle Hashes auf seinem Pfad zur Wurzel.
Einen einzelnen Eintrag prüfen
Ein Inklusionsnachweis liefert die Nachbarhashes, die zur Neuberechnung dieses Pfades nötig sind, statt sämtliche Einträge. In einem ausgeglichenen Binärbaum mit acht Blättern braucht ein Nachweis typischerweise drei Geschwisterhashes sowie Positionsinformationen. Außerdem benötigt der Prüfer den Eintrag oder dessen Hash und eine vertrauenswürdige Wurzel.
Verwendung in Bitcoin
Bitcoin bindet Transaktionskennungen über eine Merkle-Wurzel in jeden Blockheader ein. Die Konstruktion legt Reihenfolge, paarweises Hashen und das Duplizieren bei einer ungeraden Anzahl von Einträgen auf einer Ebene fest. Andere Systeme können andere Baumstrukturen und Kodierungen nutzen.
Aussagekraft eines Nachweises
Ein gültiger Nachweis zeigt unter den Hashannahmen, dass ein Eintrag zur Sammlung der Referenzwurzel gehört. Er beweist nicht eigenständig die Transaktionsgültigkeit, den aktuellen ungenutzten Status eines Outputs oder die Finalität der Chain. Die Wurzel offenbart auch nicht sämtliche Ausgangsdaten. Für eine vollständige Prüfung müssen diese weiterhin anderweitig verfügbar sein.