menu

Proof Of Work

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, client puzzle, 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.

Example

Let’s say the base string that we are going to do work on is “Hello, world!”. Our target is to find a variation of it that SHA-256 hashes to a value beginning with ‘000’. We vary the string by adding an integer value to the end called a nonce and incrementing it each time. Finding a match for “Hello, world!” takes us 4251 tries (but happens to have zeroes in the first four digits):


"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9
        
4251 hashes on a modern computer is not very much work (most computers can achieve at least 4 million hashes per second). Bitcoin automatically varies the difficulty (and thus the amount of work required to generate a block) to keep a roughly constant rate of block generation.

In Bitcoin things are a bit more complex, especially since the header contains the Merkle tree which depends on the included transactions. This includes the generation transaction, a transaction “out of nowhere” to our own address, which in addition to providing the miner with incentive to do the work, also ensures that every miner hashes a unique data set.