Hash Tree
Ein Hash-Baum (Merkle-Baum) organisiert die Hashes von Datenblöcken in einem Binärbaum: Blätter sind Hashes der Datenblöcke, innere Knoten hashen die Verkettung der Kind-Hashes, und die Wurzel ist der Gesamtdigest.
Zweck
Integrität großer Datenmengen effizient verifizieren — zur Prüfung eines Blatts genügen O(log n) Geschwister-Hashes, ohne den ganzen Baum neu zu berechnen.
Mechanismus
Blatt h_i=H(data_i), innerer Knoten h=H(h_left || h_right), die Wurzel h_root ist der Gesamtdigest. Zur Verifikation von Blatt i werden die Geschwister-Hashes auf jeder Ebene entlang des Blatt-Wurzel-Pfads (der Authentifizierungspfad) benötigt.
Anwendungsfälle
- Git-Commit-Bäume
- Transaktionsverifikation in Blockchains
- P2P-Dateiintegrität (BitTorrent)