Proof of work (PoW) describes a system that requires a not insignificant but feasible amount of effort to deter frivolous or malicious computer power users, such as sending spam emails or launching denial of service attacks. The concept was subsequently adapted to securing digital money by Hall Finney in 2004 through the idea of "reusable proof of work" using the SHA-256 hashing algorithm.
Following its introduction in 2009, Bitcoin became the first widely adopted application of Finney's PoW idea (Finney was also the recipient of the first Bitcoin transaction). However, proof of work forms the basis of many other cryptocurrencies, allowing for secure, decentralized transactions.
Understanding proof of work
This explanation will focus on proof of work as it functions in the bitcoin network. Bitcoin is a digital currency underpinned by a kind of distributed ledger known as a "blockchain." This ledger contains a record of all bitcoin transactions, arranged in sequential "blocks," so that no user is allowed to spend any of their holdings twice. Furthermore, to prevent tampering, the ledger is public or "distributed"; other users would quickly reject an altered version.
Users detect tampering in practice through hashes, long strings of numbers that serve as proof of work. Put a given data set through a hash function (bitcoin uses SHA-256), and it will only ever generate one hash. Due to the "avalanche effect," however, even a tiny change to any portion of the original data will result in an unrecognizable hash. Furthermore, whatever the size of the original data set, the hash generated by a given function will be the same length. Thus, the hash is a one-way function: it cannot obtain the original data, only to check that the data generated matches the original hash.
Generating just any hash for a set of bitcoin transactions would be trivial for a modern computer, so to turn the process into "work," the bitcoin network sets a certain level of "difficulty." This setting is adjusted so that a new block is "mined" – added to the blockchain by generating a valid hash – approximately every 10 minutes. Setting difficulty is accomplished by establishing a "target" for the hash: the lower the target, the smaller the set of valid hashes, and the harder it is to generate one. In practice, this means a hash that starts with a very long string of zeros.