Proof-of-work system

A proof-of-work (POW) system (or protocol, or function) is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer. The concept may have been first presented by Cynthia Dwork and Moni Naor in a 1993 journal article. The term "Proof of Work" or POW was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels.

A key feature of these schemes is their asymmetry: the work must be moderately hard (but feasible) on the requester side but easy to check for the service provider. This idea is also known as a CPU cost function, , computational puzzle or CPU pricing function. It is distinct from a CAPTCHA, which is intended for a human to solve quickly, rather than a computer. Proof of space (PoS) proposals apply the same principle by proving a dedicated amount of memory or disk space instead of CPU time. Proof of bandwidth approaches have been discussed in the context of . Proof of ownership aims at proving that specific data are held by the prover.

One popular system—used in bitcoin mining and Hashcash— uses partial hash inversions to prove that work was done, as a good-will token to send an e-mail. For instance the following header represents about 2⁵² hash computations to send a message to calvin@comics.net on January 19, 2038:

It is verified with a single computation by checking that the SHA-1 hash of the stamp (omit the header name X-Hashcash: including the colon and any amount of whitespace following it) begins with 52 binary zeros, that is 13 hexadecimal zeros:

Whether POW systems can actually solve a particular denial-of-service issue such as the spam problem is subject to debate; the system must make sending spam emails obtrusively unproductive for the spammer, but should also not prevent legitimate users from sending their messages. Proof-of-work systems are being used as a primitive by other more complex cryptographic systems such as bitcoin which uses a system similar to Hashcash.

...
Wikipedia