Merkle Tree
Ein Merkle-Baum legt Daten-Hashes in den Blättern und Hashes der Kinder in inneren Knoten ab und ermöglicht effiziente Integritätsprüfung großer Daten; er wird in Git und Blockchains verwendet.
Zweck
Integritätsprüfung großer Datenmengen effizient und auf konkrete Datenblöcke lokalisierbar machen.
Mechanismus
Die Blätter halten die Hashes der Datenblöcke H(d_i). Innere Knoten hashen die Verkettung ihrer Kinder, H(left||right). Der Root-Hash steht für das Ganze. Die Prüfung eines Blocks erfordert nur die O(log n) Geschwister-Hashes entlang des Pfads von der Wurzel zum Blatt (ein Merkle-Proof). Jede Änderung an einem Datenblock verändert den Root-Hash.
Anwendungsfälle
- Verifikation des Git-Objektbaums
- Verifikation von Blockchain-Transaktionen
- IPFS-Content-Adressierung
- Konsistenz verteilten Speichers
Beispiele
- Eingabe
4 data blocks → a 2-level Merkle treeOutputThe root hash represents all of themO(log n) verification
Häufige Fehler
- Weak hashes enable collision forgery
- Use a secure hash such as SHA-256
Verwandte Begriffe
Bloom Filter
Ein Bloom-Filter approximiert die Zugehörigkeit zu einer Menge mit k Hashfunktionen und einem Bit-Array und bietet Platzeffizienz zum Preis einer False-Positive-Rate. GLOSSAR
Consistent Hashing
Consistent Hashing remappt beim Hinzufügen oder Entfernen von Knoten nur 1/n der Keys neu und minimiert die Umverteilung; es wird in verteiltem Caching und Sharding eingesetzt. GLOSSAR
SHA-256
SHA-256 ist das 256-Bit-Ausgabemitglied der SHA-2-Familie, weit verbreitet in TLS, Blockchains und Kryptoanwendungen, ohne bekannte praktische Angriffe. GLOSSAR