In computer science, a proof of work (PoW) is a method that is intended to prevent the excessive use of a service, such as denial-of-service attacks or the mass sending of e-mails (spam). Proof-of-work usually represents the solution of a moderately difficult task by the user or his/her computer. The result, on the other hand, can be checked by the service provider without much effort.
The idea of proof-of-work is that a service user must first do some work themselves before they are allowed to use the service – a kind of user fee. It was first proposed in 1992 by Cynthia Dwork and Moni Naor to curb the sending of junk mail. One implementation of this method is Hashcash.
Proof-of-work is intended to discourage excessive use or even misuse of a service. It delays the processing of the request a bit because the service user has to solve the task first. The delay should therefore be chosen in such a way that it does not disturb the further process. For example, a delay of a few seconds when sending an email is usually acceptable, but significantly slows down the number of emails that can be sent within a time interval. This doesn’t bother the average email sender, but it may prevent spamming.
---
There are numerous problems in areas such as cryptology or numerics, the solution of which is difficult to calculate, but which can then be easily checked for correctness. Ideally, problems should be solved, the solution effort of which can also be influenced by slightly adapting the task. In this way, the effort that the user has to make can be adapted to the circumstances, such as the available computing power.
Examples of such problems include, but are not limited to:
- Solving differential equations,
- Brute force attacks on attenuated cryptographic primitives,
- Operations on large, densely populated matrices, such as solving systems of linear equations or inverting.
In 1999, two employees of RSA Laboratories, proposed the following task: The user receives the hash value of a string, as well as an incomplete part of the string. He has to use the hash value to determine the missing characters. A widespread variation of this method is also used, for example, in the cryptocurrency Bitcoin: A nonce must be found for a given string, so that the first m bits in the hash via the string and the nonce are zeros. By choosing the number of m of these zero bits, the difficulty and thus the duration of the calculation can be controlled.
Illustration credit: https://forkast.news/proof-of-work-what-is-it-bitcoin-halving/
Variants
There are two classes of proof-of-work protocols:
- Challenge-Response: This variant requires a direct connection between the service and its user. The service searches for a challenge, the user solves it (with effort) and the service can easily verify it. Since the prompt is selected spontaneously by the service, it can adjust its difficulty to the current load. The effort may be limited on the user side if the prompt-response protocol has a known solution (selected by the service) or if it is known to be in a limited search space.
- Solution verification: This variant does not require a direct connection. Therefore, the problem must be self-explanatory and omnipresent. The service then has to verify the choice of problem and the calculated solution. Most of these methods are unbounded, probabilistic, iterative methods such as Hashcash.
The effort put into a solution must be reflected in the consumption of material resources and energy. Therefore, a distinction is made between the following classes of problems:
- Compute bound: Energy and time are consumed. Depending on the computing power, a solution can be calculated more easily.
- 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 or hard-to-reach network nodes for his calculation. As a result, it is slowed down in terms of time or artificially limited by artificially limiting the requests.
