Blockchain: Hash Funktionen und Merkle Bäume

Die Blockchain Technologie ist wichtig und wird wichtiger werden. Daher sollte man wissen, worum es überhaupt geht. Nachdem ich letzte Woche beschrieben habe, welche Probleme mit der Blockchain Technologie überhaupt gelöst werden könnten, soll es heute um die technischen Grundlagen dieser Lösung gehen.

Keine Angst, es wird nicht zu technisch werden 🙂

Hash Funktionen

Das englische Verb to hash kann mit „zerhacken“ übersetzt werden.

Eine einfache Anwendung von Hash Funktionen findet sich in jedem Buchladen!

Die Bücher stehen in Regalen und sind oft nach Themen und dem Nachnamen des Autors alphabetisch geordnet. Die Sache mit dem Nachnamen funktioniert mit einem Hash Algorithmus!
Man nimmt den ersten Buchstaben des Nachnamens und sortiert das Buch ins Regal. Wenn zwei Autoren den gleichen Namen haben, nimmt man noch den Vornamen zur Hilfe, damit es übersichtlich wird.

Das System kennt vermutlich jeder und jeder könnte die Bücher einsortieren. Also nicht Besonderes? Es lohnt sich genauer hinzusehen.

• Der Name des Autors wird gehasht (zerhackt)
• Das Ergebnis ist eindeutig.
• Das hashing/zerhacken geht in eine Richtung. Es ist ganz einfach vom Namen auf den Buchstaben zu kommen, es ist aber unmöglich vom Buchstaben auf den Namen zu kommen.

Ein komplexeres Beispiel sind Prüfsummen von Dateien. Um zu wissen, ob die Datei, die man downloaden will, auch wirklich die Original Datei ist, wird mittels einer Hash Funktion eine Prüfsumme ermittelt. Angeboten wird die Datei und die Prüfsumme. Nach dem Download kann die Prüfsumme selbst ermittelt und mit der angebotenen Prüfsumme verglichen werden.

Je, nachdem welcher Algorithmus verwendet wird, hat dieses Bild – 650.jpeg (image/jpeg) – 65826 bytes die folgenden Prüfsummen:

• SHA-1: ea5f869231470bf0daadba43953286a1995256e3
• SHA-256: 864c24b3fdf1b34f78cb0ac702963cf66beb798a0714f142f87d8712a19c0053
• SHA-384: b5eb72fc5833756f00c56e15193b59f6b687167da7be1a57562d4e614d44b8354db170185a4efcc123e1ae9656450c0f
• SHA-512: 2cf9104c4f0e2cd2e08db4f9a316dabe29d7864b006d862bd60a4c5b1b15dec8fb8dc7ee7340023a74e75ecfec6ce1b056c2de7fa69943283e4c9b2bcfc0d40b

Obwohl das sehr kompliziert aussieht, ist es der gleiche Vorgang, wie bei dem Buch Beispiel. Die Prüfsumme wird auf der Basis von Regeln ermittelt und ist eindeutig. Du kannst die Prüfsumme nach dem Download selbst ermitteln und mit der im Blogeintrag vergleichen. Sie muss übereinstimmen! Auch in diesem Beispiel ist es (zumindest für einen Computer) ganz einfach von einer Datei auf die Prüfsumme zu kommen. Der Rückweg ist nicht möglich. Bei den Büchern ging es nur um die richtige Sortierung. In diesem Fall kann die „Echtheit“ einer Datei festgestellt werden.

Die Prüfsummen werden im Beispiel immer länger. Schnelle Computer können ab einer bestimmten Schwelle unter Umständen doch den Rückweg berechnen, daher die Daumenregel: Je aufwendiger der Algorithmus und die daraus entstehende Prüfsumme, desto sicherer ist die „Einbahnstraße“.

Prüfsummen lassen sich im Browser ermitteln, ohne dass die betreffende Datei hochgeladen werden muss, beispielsweise hier: https://md5file.com/calculator.

Die Überprüfung der Prüfsumme stellt sicher, dass du genau die „richtige“ Datei hast. Errechnest du eine andere Prüfsumme, so ist etwas in deiner Datei anders. Das ist sehr praktisch bei ZIP Paketen von Software Downloads. Ein „Original“ Softwarepaket führt immer zur gleichen Prüfsumme.
Bei dem Bild ist es genauso. Wird es mit Photoshop nachträglich bearbeitet, ist die Prüfsumme anders.

Hash Tabelle

In einer Hash Tabelle kann man nun die ursprüngliche Datei, oder den Namen (Key), die verwendete Hash Funktion und die errechneten Prüfsummen (hashes) darstellen.

Hashes sind also prinzipiell recht einfach zu errechnen und durchaus praktisch. Nun stellt sich die Frage, was diese Hashes mit der Blockchain zu tun haben und was man damit anstellen kann? Die entscheidende Eigenschaft von Hashes ist die Eindeutigkeit in die eine Richtung und die Unmöglichkeit, aus dem Hash den Key (in die andere Richtung) zu ermitteln. Wenn wir an die Byzantinischen Generäle denken, so war die Lösung zum Einen eine nicht näher definierte Arbeit von 10 Minuten, die jeder General erbringen muss und zum Anderen das Sammeln aller Botschaften. Mit dem Wissen um Hash Funktionen könnte die Lösung eleganter funktionieren, nämlich mit einer „Hash Chain“ oder Hash Liste.

• General 1 unterschreibt und erzeugt aus dem Text (Key) eine Prüfsumme (Hash)
• General 2 unterschreibt, hängt die Prüfsumme von General 1 dran und erzeugt aus dem Text (Key) eine Prüfsumme (Hash)
• General 3 unterschreibt, hängt die Prüfsumme von General 2 dran und erzeugt aus dem Text (Key) eine Prüfsumme (Hash)
• und so weiter

Wichtig dabei ist, dass Teile der bereits erstellten Nachrichten in den Hash Vorgang der neuen Nachricht einbezogen werden.

Jetzt ergibt das alles plötzlich Sinn, denn in die eine Richtung ist alles nachvollziehbar errechenbar und transparent.
Betrug ist technisch unmöglich!

Die Bäume von Herrn Merkle

Namensgeber Ralph Merkle gehört zu den Pionieren der Kryptosysteme. 1974 entdeckte er das bis dahin für unmöglich gehaltene Schlüsselaustauschprotokoll „Merkles Puzzle“ und begründete damit die Public-Key-Kryptografie.

Für ein Signaturverfahren entwickelte er 1979 Hash Bäume (Merkle Bäume). Außer den Signaturen können die Hash Bäume auch jegliche andere Art von Daten vor Veränderung schützen. Populär geworden sind die Hash Bäume in Peer to Peer Netzwerken wie dem BitTorrent Protokoll. Dort geht es um verteiltes File Sharing. Eine große Datei (Spielfilm) befindet sich in Teilen auf vielen Peers. Der anfordernde Peer muss herausfinden, welche Teile der Datei er von welchem anderen Peer laden kann. Anschließend muss kontrolliert werden, ob die Daten unverändert und unbeschädigt sind. Durch die Nutzung dieser Technik lassen sich die einzelnen Teile der Datei parallel und in Summe mit maximaler Geschwindigkeit downloaden, auch wenn die einzelnen Peers, die die Teile zur Verfügung stellen, gar nicht so schnell ans Internet angebunden sind. Das BitTorrent Protokoll ist völlig legal und nach wie vor die schnellste Möglichkeit Dateien zu verteilen. Viele Linux Distributionen und Computerspiele werden per BitTorrent vertrieben. Rechtliche Probleme entstehen nur, wenn die Dateien urheberrechtlich geschützt sind!

Die Wurzel eines solchen Hash Baums wird Top-, Root- oder Master Hash genannt. Wenn man diesen Hash aus einer vertrauenswürdigen Quelle bekommt, kann der restliche Teil des Baums auch von nicht vertrauenswürdigen Quellen bezogen werden.

Bevor einem nun das Hirn explodiert eine kleine Zeichnung. Um das Beispiel zu verstehen, solltest du die Geschichte mit den byzantinischen Generäle kennen.

Die Generäle schreiben jeweils eine Nachricht und erstellen deren Hash. Um zwei Nachrichten „zusammenzukleben“, wird aus Hash 1 und Hash 2, sowie aus Hash 3 und Hash 4 jeweils ein Hash A und ein Hash B erzeugt. Aus Hash A und Hash B dann der Top Hash.
Jeder, der im Besitz eines „Astes des Baumes“ ist, also Nachricht 1 -> Hash 1 -> Hash A – > Top Hash, kann selbst überprüfen, ob die Zahlen stimmen, sprich, „ob die Nachricht wahr“ ist. Je mehr Äste und Zweige man kennt, desto größer wird die Gewissheit.

Das ist alles recht logisch und das Hirn beruhigt sich nach einer gewissen Zeit auch wieder 🙂

Aber es stellen sich neue Fragen

1. Woher kenne ich den Top Hash?
2. Wie kann ich die Hashwerte dazwischen ermitteln?
3. Was wird überhaupt überprüft?

Nehmen wir die dritte Frage zuerst. Was wird überprüft? Ich muss ermitteln, ob eine Nachricht Teil des einen Baumes ist. Wenn sie das ist, ist sie wahr. Jeder Baum hat einen Top Hash. Wenn alle Nachrichten diesen Top Hash haben, sind sie wahr. Wer gibt mir aber den Top Hash?
Nehmen wir an, ich will wissen, ob die Nachricht von General 3 wahr ist. Ich übermittle meinem Algorithmus die Nachricht von General 3, und frage nach dem Top Hash. Ich erhalte den Wert. Nun will ich wissen, ob Nachricht 4 wahr ist. Diesmal könnte ich auch selbst aus Nachricht 3 und 4 einen Hash bilden, mir fehlt aber noch das Wissen um den gemeinsamen Hash aus Nachricht 1 und 2. Also frage ich wieder meinen Algorithmus nach dem Top Hash für Nachricht 4. Wenn die Antwort die gleiche ist wie bei Nachricht 3, ist Nachricht 4 auch innerhalb dieses Baumes, also wahr.

Die Antwort auf Frage zwei ist einfach. Ich kann das mit einer Hash Funktion machen, wenn ich die entsprechenden Daten und ein Programm habe, das das kann.

Wer mir hier etwas liefert ist jetzt auch klar. Ein (der) Algorithmus, also das verteilte System, das die Regeln kennt.

Jetzt sind wir schon mitten drin in der Blockchain Technologie und den Konsens Algorithmen. Für heute soll es aber genug sein, denn mit diesem Wissen verstehen wir jetzt das zu Weihnachten 2017 in Blockchain Kreisen verwendete Motiv „Frau Merkel steht vor einem Weihnachtsbaum“  🙂

I'll be attending the #merrymerkle party to raise funds for @CovenantHouse https://t.co/JzQD73kUjM. Donate ETH to light the tree. Note that the following is an image of a Merkel Tree, not a Merkle Tree. pic.twitter.com/qFFhAse9at

— Yaron Vorona (@YaronVorona) December 19, 2017

https://twitter.com/mir_btc/status/937661795388526597

Links

• https://de.wikipedia.org/wiki/Hashfunktion
• https://de.wikipedia.org/wiki/Prüfsumme
• https://en.wikipedia.org/wiki/Merkle_tree

• Teil 1: Blockchain: Byzantinische Generäle und das CAP Theorem
• Teil 2: Blockchain: Hash Funktionen und Merkle Bäume
• Teil 3: Blockchain: So unterscheiden sich Bitcoin und Ethereum