Unter einem Proof of Work (auch computational puzzle oder cryptographic puzzle ; auf Deutsch etwa ?Arbeitsnachweis‘ oder auch ?-beweis‘, kurz PoW ) versteht man in der Informatik eine Methode, die den ubermaßigen Gebrauch eines Dienstes, wie beispielsweise Denial-of-Service-Attacken oder das massenweise Versenden von E-Mails ( Spam ), verhindern soll.

Der Proof-of-Work stellt in der Regel die Losung einer maßig schweren Aufgabe durch den Nutzer oder dessen Computer dar. Das Ergebnis kann vom Diensterbringer dagegen ohne großen Aufwand nachgepruft werden.

Die Idee des Proof-of-Work ist, dass ein Dienstnutzer zuerst selbst etwas Arbeit verrichten muss, bevor er den Dienst in Anspruch nehmen darf ? eine Art Benutzungsentgelt. Sie wurde erstmals im Jahr 1992 von Cynthia Dwork und Moni Naor vorgeschlagen, um den Versand von Junk-Mails einzudammen. ^{[1] [2]} Eine Implementierung dieses Verfahrens ist Hashcash .

Der Proof-of-Work soll davon abhalten, einen Dienst ubermaßig in Anspruch zu nehmen oder gar missbrauchlich zu verwenden. Es verzogert die Bearbeitung der Anfrage etwas, da der Dienstnutzer erst die Aufgabe losen muss. Die Verzogerung sollte daher so gewahlt werden, dass sie keine Storung im weiteren Ablauf darstellt.

Zum Beispiel ist eine Verzogerung von wenigen Sekunden beim Versand einer E-Mail meist hinnehmbar, bremst aber deutlich die Anzahl der versendbaren E-Mails innerhalb eines Zeitintervalls aus. Das stort den durchschnittlichen E-Mail-Versender kaum, verhindert aber u. U. das Spamming.

Es existieren zahlreiche Probleme aus Bereichen wie der Kryptologie oder Numerik , deren Losung nur aufwendig zu berechnen ist, die anschließend aber leicht auf Korrektheit gepruft werden kann. Ideal sind Probleme, deren Losungsaufwand man zusatzlich noch durch leichte Anpassung der Aufgabenstellung beeinflussen kann. So lasst sich der Aufwand, den der Nutzer erbringen muss, an die Gegebenheiten, beispielsweise die verfugbare Rechenleistung, anpassen.

Beispiele fur solche Probleme sind u. a.

• das Losen von Differentialgleichungen ,
• Brute-Force-Angriffe auf abgeschwachte kryptographische Primitiven ,
• Operationen auf großen, dicht besetzten Matrizen , wie das Losen linearer Gleichungssysteme oder Invertieren .

Im Jahr 1999 schlugen Ari Juels und John Brainard, zwei Mitarbeiter der RSA Laboratories , folgende Aufgabe vor: Der Benutzer erhalt den Hashwert einer Zeichenkette, sowie einen unvollstandigen Teil der Zeichenkette. Er muss anhand des Hashwerts die fehlenden Zeichen bestimmen. ^{[3] [4]}

Eine weitverbreitete Abwandlung dieses Verfahrens findet beispielsweise auch bei der Kryptowahrung Bitcoin Anwendung: Zu einer gegebenen Zeichenkette muss ein Nonce gefunden werden, sodass im Hash uber die Zeichenkette und den Nonce die ersten m Bits Nullen sind. Durch die Wahl der Anzahl m dieser Null-Bits lasst sich die Schwierigkeit und damit auch die Dauer der Berechnung steuern.

Es gibt zwei Klassen von Proof-of-Work -Protokollen:

• Challenge-Response : Diese Variante benotigt eine direkte Verbindung zwischen dem Dienst und seinem Nutzer. Der Dienst sucht eine Herausforderung (Aufforderung), der Nutzer lost sie (mit Aufwand) und der Dienst kann sie leicht verifizieren. Da die Aufforderung spontan vom Dienst ausgewahlt wird, kann er ihre Schwierigkeit an die aktuelle Auslastung anpassen. Der Aufwand kann auf Nutzerseite begrenzt sein, wenn das Aufforderung-Antwort-Protokoll eine (vom Dienst ausgewahlte) bekannte Losung hat oder wenn von ihr bekannt ist, sich in einem begrenzten Suchraum zu befinden.

• Losungsverifikation : Bei dieser Variante wird keine direkte Verbindung benotigt. Daher muss das Problem selbsterklarend und omniprasent sein. Der Dienst muss dann die Problemwahl und die errechnete Losung verifizieren. Die meisten dieser Verfahren sind unbeschrankte, probabilistische, iterative Verfahren wie Hashcash.

Der in eine Losung gesteckte Aufwand muss sich im Verbrauch materieller Ressourcen und Energie niederschlagen. Daher unterscheidet man folgende Klassen von Problemen:

• Rechenbasiert ( compute bound ): Es wird Energie und Zeit verbraucht. Je nach Rechenleistung kann eine Losung einfacher berechnet werden.
• Speicherbasiert ( memory bound ): Die Losung des Problems benotigt viel Speicher. Dadurch wird die Anzahl gleichzeitiger Anfragen limitiert. Je nach Große spielen Speicherbandbreite und Latenz eine Rolle (Cache-misses)
• Netzwerkbasiert: Der Konsument muss fur seine Berechnung viele oder schlecht erreichbare Netzknoten kontaktieren. Dadurch wird er zeitlich gebremst oder kunstlich, indem die Anfragen kunstlich limitiert werden.

• Bitmessage
• Proof of Stake

• Xiao-Weng Fang: Encyclopedia of Cryptography and Security, Band 1: Computational Puzzles . 2. Auflage. Springer, 2011, ISBN 978-1-4419-5905-8 , S.   244   f .  

1. ↑ Pricing via Processing or Combatting Junk Mail. Abgerufen am 18. Marz 2014 (englisch).  
2. ↑ Pricing via Processing or Combatting Junk Mail. Abgerufen am 18. Marz 2014 (englisch).  
3. ↑ Proceedings of the 1999 Network and Distributed System Security Symposium. Abgerufen am 18. Marz 2014 (englisch).  
4. ↑ Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks. Abgerufen am 18. Marz 2014 (englisch).