Hash-Baum
Hash-Baum (eng. Merkle tree) ist ein Baum, in dem jeder Blattknoten mit einem Datenblock beschriftet ist und jeder Nicht-Blattknoten mit dem kryptographischen Hash der Etiketten seiner Kindknoten markiert ist. Hash-Bäume erlauben eine effiziente und sichere Verifikation der Inhalte großer Datenstrukturen. Hash-Bäume sind eine Verallgemeinerung von Hash-Listen und Hash-Ketten.
Ein Blattknoten ist ein Teil eines gegebenen binären Hash-Baums, der die Berechnung einer Anzahl von Hashwerten proportional zum Logarithmus der Anzahl der Blattknoten des Baums erfordert; Dies steht im Gegensatz zu Hash-Listen, bei denen die Anzahl proportional zur Anzahl der Blattknoten selbst ist.
Das Konzept der Hash-Bäume wurde nach Ralph Merkle benannt, der es 1979 patentieren ließ.
Inhaltsverzeichnis
Bitcoin Merkle Baum
Hash-Bäume können verwendet werden, um jede Art von Daten, die in und zwischen Computern gespeichert, verarbeitet und übertragen werden, zu überprüfen. Gegenwärtig wird Hash-Bäumen hauptsächlich verwendet, um 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 zu überprüfen, dass die anderen Kollegen nicht lügen und gefälschte Blöcke schicken. Es wurden Vorschläge gemacht, Hash-Bäume in vertrauenswürdigen Computersystemen zu verwenden. Hash-Bäume werden auch in Hash-basierter Kryptographie verwendet.
Hash-Bäume werden in den IPFS-, Btrfs- und ZFS-Dateisystemen (um der Datenverschlechterung entgegenzuwirken), BitTorrent-Protokoll, Dat-Protokoll, Apache Wave-Protokoll, Git und Mercurial verteilten Revisionskontrollsystemen, dem Tahoe-LAFS-Backup-System, dem Bitcoin und Ethereum-Peer verwendet Peer-to-Peer-Netzwerke, das Zertifikat-Transparenz-Framework und eine Reihe von NoSQL-Systemen wie Apache Cassandra, Riak und Dynamo.
Die anfängliche Bitcoin-Implementierung von Merkle-Bäumen von Satoshi Nakamoto wendet den Kompressionsschritt der Hash-Funktion übermäßig an, was durch die Verwendung von Fast Merkle Bäumen gemildert wird.
Merkle-Hash-Baum Übersicht
Ein Hash-Baum ist ein Baum aus Hashes, in dem die Blätter Hashes von Datenblöcken sind, zum Beispiel in einer Datei oder einem Satz von Dateien. Knoten weiter oben im Baum sind die Hashes ihrer jeweiligen Kinder. Im Beispiel ist Hash 0 das Ergebnis der Hashing der Verkettung von Hash 0-0 und Hash 0-1. Das heißt, Hash 0 = Hash (Hash 0-0 + Hash 0-1), wobei + Verkettung bedeutet.
Die meisten Hash-Tree-Implementierungen sind binär (zwei untergeordnete Knoten unter jedem Knoten), aber sie können genauso gut viele weitere untergeordnete Knoten unter jedem Knoten verwenden.
Normalerweise wird eine kryptografische Hash-Funktion wie SHA-2 für das Hashing verwendet. Wenn der Hash-Baum nur vor unbeabsichtigtem Schaden schützen muss, können viel weniger sichere Prüfsummen wie CRCs verwendet werden.
Am Anfang eines Hash-Baums befindet sich ein Top-Hash (oder Root-Hash oder Master-Hash). Vor dem Herunterladen einer Datei in einem P2P-Netzwerk wird der oberste Hash in den meisten Fällen von einer vertrauenswürdigen Quelle bezogen, z. B. einem Freund oder einer Website, von der bekannt ist, dass sie gute Empfehlungen zum Herunterladen von Dateien hat. Wenn der oberste Hash verfügbar ist, kann der Hash-Baum von jeder nicht vertrauenswürdigen Quelle wie jeder Peer im P2P-Netzwerk empfangen werden. Dann wird der empfangene Hash-Baum mit dem vertrauenswürdigen oberen Hash verglichen, und wenn der Hash-Baum beschädigt oder gefälscht ist, wird ein anderer Hash-Baum von einer anderen Quelle ausprobiert, bis das Programm ein Programm findet, das mit dem obersten Hash übereinstimmt.
Der Zweig des Hash-Baums kann zu einem Zeitpunkt heruntergeladen werden, und die Integrität jedes Zweigs kann sofort überprüft werden, obwohl der gesamte Baum noch nicht verfügbar ist. Zum Beispiel kann in dem Bild die Integrität des Datenblocks 2 sofort verifiziert werden, wenn der Baum bereits Hash 0-0 und Hash 1 enthält, indem der Datenblock hasiert und das Ergebnis iterativ mit Hash 0-0 und dann Hash1 und schließlich kombiniert wird Vergleichen des Ergebnisses mit dem Top-Hash. Ähnlich kann die Integrität des Datenblocks 3 verifiziert werden, wenn der Baum bereits Hash 1-1 und Hash 0 aufweist. Dies kann ein Vorteil sein, da es effizient ist, Dateien in sehr kleinen Datenblöcken aufzuteilen, so dass nur kleine Blöcke sein müssen erneut heruntergeladen, wenn sie beschädigt werden. Wenn die Hash-Datei sehr groß ist, wird eine solche Hash-Struktur oder Hash-Liste ziemlich groß. Aber wenn es sich um einen Baum handelt, kann ein kleiner Zweig schnell heruntergeladen werden, die Integrität der Verzweigung kann geprüft werden, und dann kann das Herunterladen von Datenblöcken beginnen.
Zweiter Urbildangriff
Der Merkle-Hash-Stamm gibt nicht die Baumtiefe an, wodurch ein zweiter Urimage-Angriff ermöglicht wird, bei dem ein Angreifer ein anderes Dokument als das Original erstellt, das denselben Merkle-Hash-Stamm besitzt. Im obigen Beispiel kann ein Angreifer ein neues Dokument erstellen, das zwei Datenblöcke enthält, wobei der erste Hash 0-0 + Hash 0-1 ist und der zweite Hash 1-0 + Hash 1-1 ist.
Ein einfacher Fix ist in Zertifikattransparenz definiert: Beim Berechnen von Blattknoten-Hashwerten wird den Hash-Daten ein 0x00 Byte vorangestellt, während 0x01 beim Berechnen interner Knoten-Hashes vorangestellt wird. Die Beschränkung der Größe des Hash-Baums ist eine Voraussetzung für einige formelle Sicherheitsbeweise und hilft dabei, einige Beweise straffer zu machen. Bei einigen Implementierungen wird die Baumtiefe durch Verwendung von Hash-Strukturtiefenpräfixen vor Hashwerten begrenzt, sodass jede extrahierte Hash-Kette nur dann als gültig definiert wird, wenn das Präfix bei jedem Schritt abnimmt und immer noch positiv ist, wenn das Blatt erreicht ist.
Tiger Baum Hash
Der Tiger Tree Hash ist eine weit verbreitete Form des Hash-Baumes. Es verwendet einen binären Hash-Baum (zwei untergeordnete Knoten unter jedem Knoten), hat normalerweise eine Datenblockgröße von 1024 Byte und verwendet den Tiger-Hash.
Tigerbaum-Hashes werden in Gnutella, Gnutella2 und Direct Connect P2P-Dateifreigabeprotokollen und in Filesharing-Anwendungen wie Phex, BearShare, LimeWire, Shareaza, DC ++ und Valknut verwendet.
Hashbaum Beispiel
Base32 #RFC4648 Base32 Alphabet:
RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
Uniform Resource Name (URN):
urn: tree: tiger: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
Magnet URI scheme:
magnet: ?xt=urn: tree: tiger: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ