https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Hash-BaumHash-Baum - Versionsgeschichte2026-05-28T11:51:19ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Hash-Baum&diff=2228493&oldid=prev~2026-10671-00: /* Funktionsweise */ Grammatik: "deren Hash-Werte den Kindern … des … Hash-Baumes entsprechen"2026-03-17T14:00:38Z<p><span class="autocomment">Funktionsweise: </span> Grammatik: "deren Hash-Werte den Kindern … des … Hash-Baumes entsprechen"</p>
<p><b>Neue Seite</b></p><div>[[Datei:Hash Tree.svg|mini|Ein binärer Hash-Baum]]<br />
<br />
Ein '''Hash-Baum''' ({{enS|'''hash tree'''}} oder {{lang|en|'''Merkle tree'''}}, nach dem Wissenschaftler [[Ralph Merkle]]) ist eine [[Datenstruktur]] in der [[Kryptographie]] und [[Informatik]]. Ein Hash-Baum ist ein [[Baum (Datenstruktur)|Baum]] aus [[Hashfunktion|Hashwerten]] von [[Datenblock|Datenblöcken]], beispielsweise von einer [[Datei]]. Hash-Bäume sind eine Erweiterung von [[Hashliste|Hash-Listen]] und dienen gleichermaßen dazu, die [[Integrität (Informationssicherheit)|Integrität]] von Daten sicherzustellen. Wenn sie die [[Tiger (Hashfunktion)|Tiger]]-Hashfunktion als Grundlage verwenden, so werden sie als '''Tiger Trees''' oder '''Tiger Tree Hashes''' bezeichnet.<br />
<br />
== Geschichte ==<br />
Hash-Bäume wurden 1979 von [[Ralph Merkle]] erfunden.<ref>R. C. Merkle: ''A digital signature based on a conventional encryption function'', Crypto ’87</ref> Der ursprüngliche Zweck war die effiziente Handhabung vieler [[Lamport-Einmal-Signaturverfahren|Lamport-Einmalsignaturen]], die zu den [[Post-Quanten-Kryptographie|quantensicheren]] Verfahren zählen. Jedoch kann ein einzelner Lamport-Schlüssel nur verwendet werden, um eine einzige Nachricht zu signieren. In Kombination mit Hash-Bäumen kann jedoch ein Lamport-Schlüssel für viele Nachrichten verwendet werden, was im [[Merkle-Signatur]]verfahren realisiert wird.<br />
<br />
== Anwendungen ==<br />
Neben Signaturen können Hash-Bäume verwendet werden, um jegliche Art von Daten, die gespeichert und ausgetauscht werden, vor Veränderungen zu schützen. Die Hauptanwendung ist derzeit die Sicherstellung in [[Peer-to-Peer|P2P-Netzwerken]], dass [[Datenblock|Datenblöcke]], die von anderen Peers empfangen werden, unbeschädigt und unverändert sind. Es gibt Vorschläge, Hash-Bäume beim [[Trusted Computing]] einzusetzen. [[Sun Microsystems]] verwendet sie im [[ZFS (Dateisystem)|ZFS]].<ref>{{Webarchiv |url=http://blogs.sun.com/bonwick/entry/zfs_end_to_end_data |wayback=20101012070122 |text=''ZFS End-to-End Data Integrity.''}} In: ''Jeff Bonwick’s Blog''</ref> Hash-Bäume werden auch bei [[Google Wave]],<ref>{{Webarchiv |url=http://www.waveprotocol.org/protocol/whitepapers/wave-protocol-verification |wayback=20101112071410 |text=''Wave Protocol Verification Paper.''}} Google Wave Federation Protocol</ref> Apples Signed System Volume und der [[Online-Datensicherung]] [[Tarsnap]] eingesetzt.<br />
<br />
Bekannte Implementationen von Hash-Bäumen sind die [[Blockchain]] der [[Kryptowährung]] [[Bitcoin]],<ref>{{Internetquelle |autor=Satoshi Nakamoto |url=https://bitcoin.org/files/bitcoin-paper/bitcoin_de.pdf |titel=Bitcoin: Ein elektronisches Peer-to-Peer-Cash-System |titelerg=(Übersetzung des Original-Papers von Daniel Deckner) |format=PDF; 323&nbsp;kB |werk=bitcoin.org |hrsg= |datum= |abruf=2024-03-11 |sprache=de}}</ref> Apples „Signed System Volume“<ref>{{Internetquelle |url=https://support.apple.com/de-de/guide/security/secd698747c9/web |titel=Sicherheit des Signed System Volume bei macOS |sprache=de |abruf=2022-01-09}}</ref> sowie die [[Versionsverwaltung]] [[Git]].<br />
<br />
== Funktionsweise ==<br />
Ein Hash-Baum ist ein [[Baum (Graphentheorie)|Baum]] von Hash-Werten, wobei die [[Blatt (Graphentheorie)|Blätter]] Hash-Werte von Datenblöcken sind, beispielsweise einer Datei. [[Knoten (Graphentheorie)|Knoten]] weiter oben im Baum sind Hash-Werte ihrer Kinder. Die meisten Implementierungen benutzen einen [[Binärbaum]] (jeder Knoten besitzt höchstens zwei Kindknoten), jedoch kann genauso gut ein höherer [[Ausgangsgrad]] verwendet werden.<br />
<br />
Normalerweise wird eine [[kryptographische Hashfunktion]] wie [[Secure Hash Algorithm|SHA-1]], [[Whirlpool (Algorithmus)|Whirlpool]] oder Tiger verwendet. Soll der Hash-Baum lediglich gegen unbeabsichtigte Beschädigungen schützen, so kann eine (kryptografisch unsichere) [[Prüfsumme]] wie [[Zyklische Redundanzprüfung|CRC]] verwendet werden.<br />
<br />
Die Wurzel des Hash-Baums wird als ''Top-Hash'', ''Root-Hash'' oder ''Master-Hash'' bezeichnet. Vor dem Herunterladen einer Datei in einem P2P-Netzwerk wird meist der Top-Hash von einer vertrauenswürdigen Quelle bezogen, beispielsweise einem Freund oder einer Website mit guter Bewertung. Liegt der Top-Hash vor, so kann der restliche Hash-Baum auch von einer nicht vertrauenswürdigen Quelle bezogen werden, also auch von jedem Peer eines P2P-Netzwerks. Er kann dann gegen den vertrauenswürdigen Top-Hash geprüft und gegebenenfalls abgelehnt werden.<br />
<br />
Der Hauptunterschied zu einer [[Hashliste|Hash-Liste]] ist, dass jeder Zweig des Hash-Baums einzeln heruntergeladen und sofort auf Integrität geprüft werden kann, selbst wenn der komplette Baum noch nicht verfügbar ist. So kann zum Beispiel die Integrität des Datenblocks L2 im Bild überprüft werden, sobald der Baum die Hashwerte 0-0 und 1 enthält. Dazu wird zuerst aus dem Datenblock L2 der ''Hash 0-1'' berechnet und mit ''Hash 0-0'' verknüpft, um ''Hash 0'' zu erhalten. ''Hash 0'' wird schlussendlich mit ''Hash 1'' verknüpft und das Ergebnis mit dem (vertrauenswürdigen) ''Top-Hash'' verglichen. Es ist effizienter, Dateien zwecks Übertragung in sehr kleine Blöcke aufzuspalten, sodass bei Beschädigungen nur kleine Teile neu geladen werden müssen. Dadurch entstehen bei sehr großen Dateien allerdings auch relativ große Hash-Listen oder Hash-Bäume. Werden Bäume verwendet, so können aber einzelne Zweige schnell geladen und auf Integrität geprüft werden, sodass das Herunterladen der eigentlichen Datei beginnen kann. Ist der ganze Baum verfügbar, so kann ein fehlerhafter Datenblock in einer Datenintegritätsprüfung in <math>\mathcal{O}(\operatorname{ld}(n))</math> ermittelt werden.<br />
<br />
Da im Top-Hash keine Informationen über die Tiefe des Baumes enthalten sind, lassen sich zweite [[Preimage-Angriff|Urbild-Angriffe]] durchführen, indem ein Hash-Baum mit Datenblöcken erzeugt wird, deren Hash-Werte den Kindern des Top-Hashes des anzugreifenden Hash-Baumes entsprechen. So kann also ein Angriff auf den Hash-Baum im Bild ausgeführt werden, indem zwei Datenblöcke erzeugt werden, deren Hash-Werte jeweils ''Hash 0'' und ''Hash 1'' entsprechen, um so den gleichen Top-Hash zu erzeugen.<br />
<br />
== Tiger-Tree-Hash ==<br />
Der '''Tiger-Tree-Hash''' ist ein weit verbreiteter [[Binärer Baum|binärer]] Hash-Baum, der auf der kryptographischen Hashfunktion [[Tiger (Hashfunktion)|Tiger]] basiert. Er wird häufig dazu genutzt, die Integrität großer Dateien bei oder nach der Übertragung zu überprüfen. Der Tiger-Tree-Hash hasht auf der Blattebene typischerweise je 1024 Byte große Datenblöcke aus der Datei. Der Roothash ist dann – mit hoher Wahrscheinlichkeit – ein eindeutiger Identifikator für die Datei. Liegt dem Client der vollständige Tiger-Hashbaum vor, kann er einerseits verifizieren, ob die einzelnen Dateiblöcke korrekt sind, sowie andererseits gleichzeitig überprüfen, ob der Hashbaum selbst korrekt ist.<br />
<br />
Tiger-Tree-Hashes werden von den [[Filesharing]]-Protokollen [[Gnutella]], [[Gnutella2]] und [[Direct Connect]] verwendet, sowie von Filesharing-Anwendungen wie [[Phex]], [[BearShare]], [[LimeWire]], [[Shareaza]] und [[DC++]].<ref>{{Internetquelle |url=https://dcplusplus.sourceforge.io/features.html |titel=Features |titelerg=Funktionen von D++ |werk=dcplusplus.sourceforge.io |abruf=2024-03-11 |sprache=en}}</ref><br />
<br />
In Textdarstellung werden die Werte üblicherweise als [[Base32]] kodiert angegeben, entweder direkt oder als [[Uniform Resource Name]], z.&nbsp;B. <code><nowiki>urn:tree:tiger:LWPNACQDBZRYXW3VHJVCJ64QBZNGHOHHHZWCLNQ</nowiki></code> für eine 0-Byte-Datei.<br />
<br />
== Weblinks ==<br />
* Gil Schmidt: [https://www.codeproject.com/Articles/9336/ThexCS-TTH-Tiger-Tree-Hash-Maker-in-Csharp Tiger Tree Hash (TTH) Quelltext in C#]<br />
* [https://sourceforge.net/projects/tigertree/ Tiger Tree Hash (TTH) Implementierung in C und Java]<br />
* [https://rhash.sourceforge.io/ RHash], ein [[Open Source]] Kommandozeilentool, welches TTHs und [[Magnet-Link]]s mit TTHs berechnen kann.<br />
<br />
== Quellen ==<br />
* {{Patent|Land=US|V-Nr=4309569|Titel=Method of providing digital signatures|V-Datum=1982-01-05 |Erfinder=Ralph C. Merkle|Kommentar = Erklärt sowohl die Struktur von Hash-Bäumen als auch deren Verwendung für viele Einmalsignaturen}}<br />
* {{Webarchiv |url=http://www.open-content.net/specs/draft-jchapweske-thex-02.html |wayback=20080316033726 |text=Tree Hash EXchange format (THEX)}} – Eine detaillierte Beschreibung von Tiger-Trees.<br />
* {{Webarchiv |url=http://www.rsasecurity.com/rsalabs/node.asp?id=2003 |wayback=20061206235144 |text=Efficient Use of Merkle Trees}} – Erklärung von [[RSA Security]] zum ursprünglichen Zweck von Merkle-Bäumen: der Handhabung vieler Lamport-Einmalsignaturen.<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
[[Kategorie:Hash]]<br />
[[Kategorie:Datenstruktur]]</div>~2026-10671-00