WikiDer > Haschbaum

EIN hashbaum ( (und) Merkle-Baum ) ist ein Baum die verwendet werden können Daten (Termine) sicher zwischen zwei Computers senden. Sie werden derzeit hauptsächlich verwendet, um zu überprüfen, ob alle Daten angekommen sind und ob die Daten unbeschädigt sind. Der Hash-Baum wurde 1979 von Ralph Merkle erfunden und deshalb werden Hash-Bäume auch als Merkle-Bäume bezeichnet.

Struktur

Der Haschbaum

Ein Hash-Baum ist oft a Binärbaum. Dies bedeutet, dass jeder Elternknoten zwei Kindknoten hat. Es ist möglich, einen Hash-Baum mit mehreren untergeordneten Knoten zu erstellen. Um einen Hash-Baum zu erstellen, beginnen wir unten mit den Blättern des Baumes. Wir hacken die Nachricht ${Anzeigestil M}$ in Stücken ${displaystyle {m_{1},m_{2},...,m_{n}}}$ und wir wandeln jedes Stück mit a . in einen Hash-Wert um Hash-Funktion${Anzeigestil H}$. jedes Blütenblatt ${displaystyle v_{1,j}}$ bekommt also den Hashwert ${Anzeigestil H(m_{j})}$. Die Elternknoten ${displaystyle v_{i,j}}$ können wir durch den Hashwert der beiden Kinder bestimmen ${displaystyle v_{i-1,j*2-1}}$ und ${displaystyle v_{i-1,j*2}}$ in einen neuen Hashwert umwandeln ${Anzeigestil H(v_{i-1,j*2-1}||v_{i-1,j*2})}$ . So wird der ganze Baum bis zur Spitze aufgebaut ${displaystyle v_{d,1}}$. Dieser oberste Knoten ist der Hauptknoten des Baums und wird von einer vertrauenswürdigen Quelle übermittelt. Der Empfänger kann nach Erhalt dieses Tops mit dem Herunterladen der Datenblöcke beginnen.

Nachdem der gesamte Baum heruntergeladen wurde, kann überprüft werden, ob die Daten korrekt sind. Die eingehenden Datenblöcke werden in Hash-Werte umgewandelt und der gesamte Baum aufgebaut. Wenn ein Datenblock falsch ist, hat er einen anderen Hash-Wert als der richtige Datenblock. Zum Beispiel erhalten die Eltern dieses Kindes auch unterschiedliche Hash-Werte und die Spitze des Baums stimmt nicht mit der gesendeten Spitze überein. Der Baum ist daher falsch und muss erneut heruntergeladen werden.

Anwendungen

Hash-Bäume sind besonders nützlich in Peer-To-PeerNetzwerke. Eine zuverlässige Quelle berechnet den gesamten Baum und schickt ihn an die Spitze. Der Rest der Datenblöcke kann aus einer beliebigen Quelle stammen. Mit Hilfe von Hash-Funktion dann kann festgestellt werden, ob alle Daten angekommen sind und ob keine Fehler vorliegen oder ob jemand Änderungen vorgenommen hat.

Der ursprüngliche Zweck von Hash-Trees war es, einen effizienten Umgang mit Lamport-Einmalsignaturen. Lamport-Signaturen sind sehr schwer zu knacken, aber jeder Lamport-Schlüssel kann nur für eine Nachricht verwendet werden. In Kombination mit Hash-Bäumen können sie plötzlich für mehrere Nachrichten verwendet werden, was Lamport-Signaturen viel effizienter macht, da nur die Spitze eine Signatur benötigt.

Beispiel

Person A möchte die Nachricht "Dies ist ein Hashbaum" innerhalb eines Netzwerks herunterladen. Person B erhält diese Frage und beginnt den Baum aufzubauen. Er beginnt damit, die Nachricht zu zerhacken. Das gibt ihm 5 Stück. Es verwendet eine 8-Bit-Hash-Funktion. Dies dient nur zur Veranschaulichung, da im wirklichen Leben viel längere Hashfunktionen verwendet werden. Er wandelt jedes Bit der Nachricht in Hash-Werte um und hat damit nun die Blätter des Baumes geschaffen.

Der nächste Schritt besteht darin, die Hashwerte jedes Elternknotens zu berechnen, indem die beiden Hashwerte der Kindknoten zusammengenommen und in einen neuen Hashwert umgewandelt werden. Dies wird fortgesetzt, bis es den obersten Knoten erreicht. Er schickt diesen Knoten an Person A.

Person A erhält somit den Top-Node von Person B. Er kann nun mit dem Download der Nachricht beginnen. Alle Stücke stammen von verschiedenen Leuten. Sobald alles drin ist, beginnt er, den Baum zu bauen, wie es Person B getan hat. Wandeln Sie also zunächst alle Teile der Nachricht in Hash-Werte um und bestimmen Sie die Parentnodes. Er vergleicht den so erhaltenen Top-Node mit dem Hash-Wert des Top-Nodes, den er von Person B erhalten hat. Wenn alles richtig eingegeben wurde, sollten diese Hashwerte daher gleich sein. Wenn dies nicht der Fall ist, stimmt etwas mit den eingehenden Teilen nicht.

Verweise

• Merkle-Baum-Patent 4.309.569 
• Tree Hash EXchange-Format (THEX)
• Dieser Artikel oder eine frühere Version ist eine (Teil-)Übersetzung des Artikels Haschbaum auf der englischsprachigen Wikipedia, die unter der Creative Commons Namensnennung/Weitergabe unter gleichen Bedingungen Stürze. Siehe die Verlauf bearbeiten Dort.
• Effiziente Nutzung von Merkle-Bäumen – RSA-Labore