Merkle Tree – Eine Basis der Blockchain

1979 patentierte Ralph Merkle das Konzept der Hash Trees, besser bekannt als Merkle Tree. Gemeint ist damit eine Methode zur Bereitstellung einer digitalen Signatur zum Zwecke der Authentifizierung einer Nachricht. Das Konzept des Blockchains, das Merkle Trees nutzt, erfreut sich jenseits des Bitcoins wachsender Beliebtheit. Unternehmen, die Daten nachverfolgen und die Integrität der Daten überprüfen müssen, beginnen zu erkennen, wie die neue Technologie diesen Prozess unterstützen.

Merkle Tree – Definition und Nutzen

In der Kryptographie und Informatik ist ein Hash-Baum oder Merkle-Tree ein Baum, in dem jeder Blattknoten mit dem Hash eines Datenblocks und jeder Nicht-Blattknoten mit dem kryptographischen Hash der Labels seiner Kindknoten beschriftet ist.

Hash Trees ermöglichen eine effiziente und sichere Verifikation der Inhalte großer Datenstrukturen. Hash Trees sind eine Verallgemeinerung von Hash-Listen und Hash-Ketten. Um zu zeigen, dass ein Blattknoten ein Teil eines gegebenen binären Hash-Baums ist, muss eine Anzahl von Hashes berechnet werden, die proportional zum Logarithmus der Anzahl der Blattknoten des Baums ist. Dies steht im Gegensatz zu Hash-Listen, bei denen die Anzahl proportional zur Anzahl der Blattknoten selbst ist.

Merkle Trees (und Variationen davon) werden von Bitcoin, Ethereum, IOTA, Apache Cassandra und anderen Systemen verwendet.

Sie dienen der Konsistenzprüfung, Datenverifizierung und Datensynchronisation. Hash Trees können verwendet werden, um jede Art von Daten zu verifizieren, die in und zwischen Computern gespeichert, verarbeitet und übertragen werden. Sie können helfen, sicherzustellen, dass Datenblöcke, die von anderen Peers in einem Peer-to-Peer-Netzwerk empfangen werden, unbeschädigt und unverändert empfangen werden, und sogar prüfen, dass die anderen Peers nicht lügen und gefälschte Blöcke senden.

Hash Trees ermöglichen eine effiziente und sichere Verifikation der Inhalte großer Datenstrukturen

Geplante Anwendungen der Merkle Trees

• Globale Lieferkette: Beispielsweise arbeiten IBM und Laersk zusammen, um Blockketten für das Management der globalen Lieferkette zu nutzen – Transaktionen zwischen den weltweit operierenden Verladern, Spediteuren, Reedereien, Seefrachtführern, Häfen und Zollbehörden, die an der Lieferkette beteiligt sind
• Gesundheitswesen: Googles Tochtergesellschaft, DeepMind Health, plant, eine neue Technologie zu verwenden, die lose auf Bitcoin basiert, damit Krankenhäuser und schließlich sogar Patienten verfolgen können, was mit persönlichen Daten in Echtzeit geschieht

Schutz vor Manipulation

Die Blätter des Merkle Trees sind gewissermaßen Hashes von Datenblöcken, z.B. in einer Datei oder einem Satz von Dateien. Knoten weiter oben im Baum sind die Hashes ihrer jeweiligen Kinder.

Zum Beispiel ist Hash 0 das Ergebnis des Hashens der Verkettung von Hash 0-0 und Hash 0-1. Das heißt, Hash 0 = Hash (Hash 0-0 + Hash 0-1) wobei + die Verkettung bezeichnet.

Die meisten Hash-Tree-Implementierungen sind binär (zwei Kindknoten unter jedem Knoten), aber sie können genauso gut viel mehr Kindknoten unter jedem Knoten verwenden. In der Regel wird eine kryptographische Hash-Funktion wie SHA-2 für das Hashing verwendet.

Wenn der Hash-Baum nur gegen unbeabsichtigte Beschädigung geschützt werden soll, können ungesicherte Prüfsummen wie CRCs verwendet werden. In der Spitze eines Merkle Trees befindet sich ein Top-Hash (Master-Hash oder Root-Hash). Vor dem Herunterladen der Datei in einem Netzwerk wird in den meisten Fällen der initiale Top-Hash von einer als vertrauenswürdig geltenden Quelle erworben, z.B. von einer Website, von der bekannt ist, dass sie gute Empfehlungen für Dateien zum Herunterladen hat. Wenn der Top-Hash verfügbar ist, kann der Merkle Tree von jeder nicht vertrauenswürdigen Quelle empfangen werden – jedem Peer im P2P-Netzwerk. Dann wird der empfangene Hash Tree mit dem vertrauenswürdigen Top-Hash verglichen und wenn der Merkle Tree beschädigt oder gefälscht ist, wird ein anderer Merkle Tree aus einer anderen Quelle ausprobiert, bis das Programm einen findet, der mit dem Top-Hash übereinstimmt.

Unterschied zur Hash-Liste

Der wesentliche Unterschied zu einer Hash-Liste besteht darin, dass jeweils ein Zweig des Merkle Trees heruntergeladen werden kann und die Integrität jedes Zweigs sofort überprüft werden kann, auch wenn der komplette Baum noch nicht vorhanden oder verfügbar ist.

Beispielsweise kann die Integrität von Datenblock 2 sofort überprüft werden, wenn der Merkle Tree bereits Hash 0-0 und Hash 1 enthält, indem der Datenblock gehasht und das Ergebnis iterativ mit Hash 0-0 und dann Hash 1 kombiniert wird und schließlich das Ergebnis mit dem Top-Hash verglichen wird. Ebenso kann die Integrität des Datenblocks 3 überprüft werden, wenn der Merkle Tree bereits Hashwert 1-1 und Hashwert 0 hat.

Dies kann von Vorteil sein, da es effizient ist, Dateien in sehr kleine Datenblöcke aufzuteilen, so dass nur kleine Blöcke erneut heruntergeladen werden müssen, wenn sie beschädigt werden. Wenn die Hash-Datei sehr groß ist, wird ein solcher Merkle Tree oder eine solche Hash-Liste ziemlich groß. Aber wenn es sich um einen Baum handelt, kann ein kleiner Zweig schnell heruntergeladen werden, die Integrität des Zweigs kann überprüft werden, und dann kann das Herunterladen von Datenblöcken beginnen.