Merkles Hash-Baum beweist, dass ein Datensatz in einer riesigen Datei enthalten ist – mit einer Handvoll Hashes

Der Nachweis, dass ein Datensatz Teil eines großen Datensatzes ist, bedeutete üblicherweise, den Datensatz zu übermitteln. Das ist für eine Sicherung, eine Datei mit Transaktionen oder einen Web-Cache unpraktisch.

Merkles Dissertation von 1979 und sein Aufsatz von 1989 beschreiben einen Baum, in dem jeder Block gehasht und Hashes paarweise zusammengeführt werden, bis eine Wurzel übrig bleibt. Die Verifizierung eines Elements erfordert die log-n Hashes auf dem Pfad, nicht die Datei.

Der Baum verwandelt einen Zugehörigkeitstest in einen Gleichheitstest an der Wurzel, und eine Änderung an beliebiger Stelle zeigt sich als geänderter Pfad. So kann für eine gesamte Datenstruktur gebürgt werden, ohne dass jedes Byte eingesehen werden muss.

Bindung an die Blätter durch paarweises Hashen bis zu einer Wurzel

Die Beweisgröße ist logarithmisch, sodass die Verifizierung auch bei den größten Datensätzen günstig bleibt.

Die Wurzel bindet den gesamten Datensatz, sodass jede Manipulation erkannt wird.

Ein Verifizierer benötigt nur die Wurzel und einen kurzen Pfad, nicht das Vertrauen in den Server.

Es handelt sich um eine Kette von Einweg-Hashes, sodass keine Informationen über die Daten preisgegeben werden.

Um eine Tatsache über ein riesiges Ganzes zu beweisen, übermittle nicht das Ganze. Reduziere es auf einen einzigen Digest und gib dann nur den kurzen Pfad an, der die eine Behauptung mit diesem Digest verbindet.

Merkle-Bäume sind grundlegend in Git, Kryptowährungs-Blockchains, der Zertifikatstransparenz und verteiltem Speicher. Sie ermöglichen es einem Client, ein kleines Stück eines großen, nicht authentifizierten Speichers zu verifizieren, indem er nur einer kurzen Wurzel vertraut.