Proof-of-work system

Under a Proof of Work ( also computational puzzle or cryptographic puzzle, in German as, proof of work ' or even - proof ', short PoW ) is understood in computer science, a method that the excessive use of a service, such as denial-of- to prevent service attacks or the masses of sending e- mails.

The proof-of -work is usually the solution of a moderately difficult task by the user or its computer Represents the result can be verified by the service provider, however, without much effort.

Idea

The idea of ​​the proof-of -work is that a service user himself first has to do some work before he can take up the service - a kind of usage charge. It was first proposed in 1992 to curb the sending of junk mail. An implementation of this method is Hashcash.

The proof-of -work to discourage to take a service excessively in claim or even to use abusive. It delays the processing of the request something because the service user only has to solve the task. The delay should therefore be chosen so that it is not a fault in the further course.

For example, a delay of a few seconds when sending an e- mail is usually acceptable, but slows considerably number of sent e- mails within a time interval of. That does not matter to the average e- mail senders, but may be stopping the spamming.

There are numerous problems in fields such as cryptology or numerics, the solution of which is only difficult to calculate, but which can be then easily checked for correctness. Ideal are problems whose solution effort you may additionally be influenced by slight adjustment of the task. This allows the effort that the user must provide to the conditions, such as the available computing power, adjust.

Examples of such problems are, inter alia,

• Solving differential equations,
• Brute-force attacks on cryptographic primitives attenuated,
• Operations on large, densely populated matrices, like solving systems of linear equations or invert.

Example

In 1999, Ari Juels and John Brainard hit, two employees of RSA Laboratories, the following task steps: The user receives the hash value of a string, as well as an incomplete part of the string. He needs based on the hash value given the missing characters.

A common variation of this method can be found, for example, even when the crypto currency Bitcoin Application: For a given string, a hash must be found in which the first m bits are zeros. By the choice of the number m of the null bits, the complexity and hence the duration of the calculation to be controlled. In addition, there is still a selectable value, the nonce, to ensure that a solution can be found.

Variants

There are two classes of proof-of -work protocols:

• Challenge Response: This variant requires a direct connection between service and consumer. The service is looking for a challenge ( task), the consumer solves it ( with effort ) and the service may easily verify.
• Solution verification: no direct connection is required in this variant. Therefore, the problem must be self-explanatory and omnipresent. The service then has to verify the problem choice and the calculated solution.

The inserted into a solution effort must be reflected in the consumption of material resources and energy. Therefore, we distinguish the following classes of problems:

• CPU - centric: It consumes time and energy. Depending on the computing power of a solution can be easily calculated.
• Memory-based: The solution of the problem requires a lot of memory. Thus, the number of concurrent requests is limited. Depending on the size of memory bandwidth and latency play a role (cache misses )
• Network -based: The consumer must contact many or poorly accessible network nodes for its calculation. This time he is braked or artificially by the inquiries will be artificially limited.