Proof of Work

Proof of Work ist ein verbreitetes Verfahren für einen Konsensalgorithmus, dessen Merkmale ein Arbeitsnachweis sowie Asymmetrie sind. Dabei nehmen am Verfahren zwei Entitäten teil (im Folgenden Alice und Bob). Alice und Bob haben sich auf einen Proof of Work-Algorithmus geeignet. Gemäß diesem führt Alice mittelschwere Berechnungen durch, die Bob mit geringem Aufwand nachprüfen kann. Das Ausführen dieses Verfahrens im Zusammenhang mit der Blockchain wird auch als Mining bzw. Schürfen bezeichnet.

Inhaltsverzeichnis

Vereinfachtes Beispiel

Ein vereinfachtes Beispiel für eine solche Berechnung wäre eine Primfaktorzerlegung: die Zahl [math]424242[/math] benötigt zur Faktorisierung mit einem in Python implementierten Algorithmus ca. 80 Schritte (und deutlich mehr CPU-Zyklen), um auf das Ergebnis [math]2 \cdot 3 \cdot 3 \cdot 7 \cdot 13 \cdot 37[/math] zu kommen. Für Bob ist der Zerlegung vergleichsweise einfach zu überprüfen: er muss die Zahlen einfach nur wieder zusammenmultiplizieren und schauen, ob wieder die Ausgangszahl herauskommt. Bei der Zahl 42424242 wäre es für Alice bereits ~220 Schritte, bei 4242424242 über 1000.

Soll dieser Arbeitsnachweis in Verbindung mit einer Nachricht (z.B. eines Blocks) erbracht werden, muss die Nachricht natürlich mit der Proof of Work-Aufgabe, im Folgenden Challenge genannt, verbunden werden, damit Alice nicht auf Vorrat für beliebige Nachrichten Arbeitsnachweise auf Vorrat berechnen kann. Man könnte sich hier z.B. darauf einigen, die dezimalen ASCII-Werte der Nachricht zu konkatinieren, also die Zahlen hintereinander zu schreiben. Bei der Nachricht TEST und den ASCII-Werten T = 84, E = 69, S = 83 wäre das [math]84698384[/math].

Das Verfahren, das hier mit einer Faktorisierung realisiert wurde, kann natürlich entsprechend ausgetauscht werden. In der Praxis kommej häufig (krytographische) Hashfunktionen vor: hier werden Eingangswerte einer (großen) Eingabemenge auf eine kleinere Zielmenge abgebildet. Dadurch, dass die Abbildung nicht injektiv ist, kann es also Hashwerte geben, die durch verschiedene Eingaben erzeugt werden können. Es ist möglich, eine 10 GB große ISO-Datei zu hashen – aus dem Hash lässt sich aber sehr unwahrscheinlich (abh. vom Verfahren) eindeutig wieder die gleiche ISO-Datei ableiten. Deswegen ist hier auch die Rede von Einwegfunktionen.

Anwendung in der Blockchain

Bei vielen Blockchain-Systemen werden folgende Regeln für den Konsens aufgestellt:

1. Jeder Block enthält die Pflichtfelder "vorheriger Hash" und "Nonce".
2. Von jedem Block lässt sich ein Hash erzeugen.
3. Jeder Block ist genau dann gültig, wenn er eine festgelegte Aufgabe erfüllen kann.
4. Es wird der Zweig der Blockchain verwendet, der den größten Arbeitsaufwand benötigte.

Schematisch sieht das Verfahren so aus:

Im Folgenden wird jeder Punkt genauer erläutert. Die Python-Beispiele sollen beim Verständnis helfen.

Punkt 1: Datenstruktur

Hier wird eine Festlegung zur Datenstruktur getroffen, damit die Blockchain als Solches funktioniert.

class Block:
    prev_hash = None
    nonce = -1
    ...

Der vorherige Hash prev_hash sorgt für die Verkettung durch den Merkle tree bzw. Hash-Baum, sodass die Blöcke in der Reihenfolge gehalten werden. Der nonce (Abkürzung sinnbildlich für "number used once") ist für die Challenge wichtig.

Punkt 2: Hashing

Der Block muss hashbar sein. Der Hash muss alle Informationen enthalten, die den Block eindeutig indentifzieren, d.h. im einfachsten Fall vorherigen Hash, Nonce sowie die eigentlichen Daten / Payload (z.B. Transaktionen).

class Block:
    # -- Attribute aus Punkt 1 weggelassen --

    @property
    def block_string(self):
        return "{0}-{1}-{2}".format(self.prev_hash, self.data, self.nonce)

    def hash(self):
        return hashlib.sha256(bytes(self.block_string, "utf-8")).hexdigest()

In diesem Beispiel wird der Hashalgorithmus SHA256 eingesetzt. Der zu hashende Wert ist ein String, in dem alle wichtigen Informationen hintereinander geschrieben werden. Wie genau nun der String erzeugt wird, ist unerheblich. Das Verfahren muss allerdings immer das gleiche sein (damit zum Nachprüfen auch in drei Jahren für die SHA256-Eingabe der gleiche String generiert werden kann) und muss natürlich alle eindeutig identifzierbaren Informationen enthalten.

Punkt 3: Aufgabe

Hier liegt der Kern des Proof of Works. Damit ein Block als gültig angesehen werden kann, muss eine mittelschwere (aber trotzdem lösbare) Aufgabe gelöst werden. Bei Bitcoin muss z.B. der Hash am Anfang eine bestimmte Anzahl an Nullen haben. Dies ist schwer, weil der Hashalgorithmus für Diffusion (Lawineneffekt) und Konfusion (Einbahnstraße) ausgelegt ist: es muss also solange etwas an der Hashfunktioneneingabe geändert werden, bis ein Hash mit führenden Nullen herauskommt und die Aufgabe somit gelöst ist.

Aber an welcher Stelle können wir jetzt noch was am Block ändern, damit wir den Eingabewert variieren können? Hier kommt der Nonce ins Spiel, dessen einzige Aufgabe in diesem Zusammenhang genau diese Funktion als variabler Wert zum Verändern der Hashfunktioneingabe ist.

class Block:
    # -- Attribute und Methoden aus vorherigen Punkten weggelassen --

    def mine(self, difficulty):
        found = False  # initiale Werte setzen
        while not found:  # arbeiten, bis found = True ist
            self.nonce += 1  # nonce um 1 erhoehen
            self.current_hash = self.hash()  # hash des Blocks bilden
            # pruefen ob das Ergebnis so viele fuehrerende Nullen hat
            # wie in der Schwierigkeit vorgegeben
            if self.current_hash[0:difficulty] == "0" * difficulty:
                # wenn ja, found = True und somit Schleife abschliessen
                found = True

Diese Funktion mine() arbeitet so lange, bis die Aufgabe gelöst ist. Die difficulty ist hier in Form von "Anzahl führender Nullen" gegeben und kann je nach Anforderung der Blockchain variabel verändert werden. Je mehr führende Nullen benötigt werden, desto schwieriger ist praktisch die Berechnung.

Punkt 4: Verfizierbarkeit

Eine Blockchain. Alle schwarzen Blöcke gehören zu dem Zweig / Branch / Strang, der für die Knoten verbindlich ist.

Anhand der im Block abgespeicherten Nonce kann nun die Aufgabe nun von anderen Teilnehmern nachgestellt werden und somit verifziert werden. Schafft man das rekursiv bis zum Genesis-Block, dem ersten Block (der keinen weiteren prev_hash hat), ist der Branch / Zweig valide.

Hat man nun konkurrierende Blöcke, kann mit Rücksicht auf die difficulty ermittelt werden, welcher die größte Difficulty hat und somit nun verwendet wird.

Beispiel: eine Blockchain hat die Difficulty 10 für alle Blöcke. Es liegen nun zwei konkurrierende Blöcke vor: ein schwarzer und ein lilafarbener Block (siehe Grafik rechts, gemeint sind die Blöcke ersten schwarzen resp. lilalen Blöcke von oben aus gesehen). Mit der Annahme, dass die Ketten für sich valide sind, kann nun die Anzahl der validaten Blöcke der jeweiligen Kette ermittelt werden. Bei Schwarz sind das 9, bei Lila 8. Multipliziert mit der Schwierigkeit 10 sind das für Schwarz 90 und für Lila 80. Der gültige Zweig ist nun der schwarze, da er mit dem höheren Aufwand erstellt wurde.

Auffallen sollte hierbei die lilane Kette in der Mitte des Bildes: wenn man die Kette gedanklich durchgeht, lässt sich erkennen, dass zum Zeitpunkt in der Mitte des Bildes die lilane Kette die zu verwendende Blockchain hätte sein müssen. Das war auch so – allerdings hat sich herausgestellt, dass dieser Teil der Kette verwaist ist, weil er kein zukünftiger Block diesen Block als Vorgänger wählt. Die Transaktionen sind also vom verwaisten Zweig hinfällig.

Aus diesem Grund sollte generell erst auf Informationen aus einem Block zurückgegriffen werden, wenn

1. dieser Block aus der Hauptkette stammt und
2. der Block eine bestimmte Anzahl von Nachfolgern hat.

Die Anzahl der Nachfolger ist unterschiedlich, so wird bei Bitcoin üblicherweise auf den Wert 6 verwiesen.

Siehe auch

• Video Blockchain selber bauen
  • Quelltext für die Beispiele in diesem Artikel: chain.py

Weblinks

• Proff of work im bitcoin.it-Wiki
• ASCII-Tabelle