Proof of work
This page is a stub. Help by expanding it.
A proof of work is the verifiable result that can only be obtained through a given work. Proofs of work are hard to obtain (i.e. require work), but trivial to check. Proofs of work can be applied to information, you can prove that you did work on a particular number.
One application of this idea is a proposed method for preventing email spam, requiring a proof of work on the email's contents (including the To address), on every email. Legitimate emails will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).
This concept is used in bitcoin for block generation. For a block to be valid it must hash to a value less than the current target, this means that each block indicates that work has been done generating it. Each block contains the hash a predecessor block, thus each block has a chain of blocks that together contain a large amount of work. Changing a block (which can only be done by making a new block containing the same predecessor) requires regenerating all successors and redoing the work they contain. This protects the block chain from tampering.
Example
Lets 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 hashes to a value beginning with '000'. We vary the string by adding a integer value to the end called a nonce and incrementing it each time. Finding a match for "Hello, World" takes us 98 tries:
Hello world ! 0 : 3f6fc92516327a1cc4d3dca5ab2b27aeedf2d459a77fa06fd3c6b19fb609106a Hello world ! 1 : b5690c48c2d0a09481186aaa99e4e090901ff2ac4d572e6706dfd30eefc22a27 Hello world ! 2 : 5b6fd9c27fcb54ca23404d9428f081b7c9280ba6370e33a6a20b16f40ce76320 .... Hello world ! 95 : b74f3b2cf1061895f880a99d1d0249a8cedf223d3ed061150548aa6212c88d43 Hello world ! 96 : 447ca2fa886965af084808d22116edde4383cbaa16fd1fbcf3db61421b9990b9 Hello world ! 97 : 000ba61ca46d1d317684925a0ef070e30193ff5fa6124aff76f513d96f49349d
98 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 target (and thus the amount of work required to generate a block) to keep a roughly constant rate of block generation. The probability of a single hash succeeding can be found [1].
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.