Proof of work
In computer science, a proof of work (also computational puzzle or cryptographic puzzle ; in German for example 'proof of work' or 'proof', PoW for short ) is a method that prevents excessive use of a service, such as denial of work. To prevent service attacks or the mass sending of emails ( spam ).
The proof-of-work usually represents the solution of a moderately difficult task by the user or his computer. The result, on the other hand, can be checked by the service provider without great effort.
idea
The idea of proof-of-work is that a service user must first do some work himself before he can use the service - a kind of user fee. It was first proposed by Cynthia Dwork and Moni Naor in 1992 to curb junk mail. One implementation of this method is Hashcash .
The proof-of-work is intended to discourage users from using a service excessively or even misusing it. It delays the processing of the request a little because the service user first has to solve the task. The delay should therefore be chosen so that it does not represent a disturbance in the further process.
For example, a delay of a few seconds when sending an e-mail is usually acceptable, but it slows down the number of e-mails that can be sent within a time interval. This hardly disturbs the average e-mail sender, but it prevents U. the spamming.
There are numerous problems from areas such as cryptology or numerics , the solution of which is difficult to calculate, but which can then easily be checked for correctness. Problems are ideal whose solution effort can also be influenced by slightly adapting the task. In this way, the effort that the user has to provide can be adapted to the circumstances, for example the available computing power.
Examples of such problems include a.
- solving differential equations ,
- Brute force attacks on weakened cryptographic primitives ,
- Operations on large, densely populated matrices , such as solving linear systems of equations or inverting .
example
In 1999, Ari Juels and John Brainard, two employees at RSA Laboratories , suggested the following task: The user receives the hash value of a character string and an incomplete part of the character string. He must use the hash value to determine the missing characters.
A widespread modification of this method is also used, for example, with the crypto currency Bitcoin : A nonce must be found for a given string so that the first m bits in the hash over the string and the nonce are zeros. By choosing the number m of these zero bits, the difficulty and thus also the duration of the calculation can be controlled.
variants
There are two classes of proof-of-work protocols:
- Challenge-Response : This variant requires a direct connection between service and consumer. The service seeks a challenge (task), the consumer solves it (with effort) and the service can easily verify it.
- Solution verification: With this variant, no direct connection is required. Therefore, the problem must be self-explanatory and omnipresent. The service then has to verify the choice of problem and the calculated solution.
The effort put into a solution must be reflected in the consumption of material resources and energy. Therefore one differentiates between the following classes of problems:
- CPU-centric ( compute bound ): Energy and time are consumed. Depending on the computing power, a solution can be calculated more easily.
- Memory-based ( memory bound ): Solving the problem requires a lot of memory. This limits the number of simultaneous requests. Depending on the size, memory bandwidth and latency play a role (cache misses)
- Network-based: The consumer has to contact many network nodes or those that are difficult to reach for his calculation. This slows it down temporarily or artificially by artificially limiting the requests.
See also
literature
- Xiao-Weng Fang: Encyclopedia of Cryptography and Security, Volume 1: Computational Puzzles . 2nd Edition. Springer, 2011, ISBN 978-1-4419-5905-8 , pp. 244 f .
Individual evidence
- ↑ Pricing via Processing or Combatting Junk Mail. Retrieved March 18, 2014 .
- ↑ Pricing via Processing or Combatting Junk Mail. Retrieved March 18, 2014 .
- ^ Proceedings of the 1999 Network and Distributed System Security Symposium. Retrieved March 18, 2014 .
- ↑ Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks. Retrieved March 18, 2014 .