Proof of Work:

The concept of proof of work has existed long before blockchains did.

People are often asked to describe the nature of or show their previous work to correctly assess their implicit value. Bitcoin employs a puzzle friendly implementation of a one way hashing algorithm (SHA256) where the initial characters of the to-be generated hash is predefined.

On any input provided to this one way hashing algorithm, the outcome is always a 256 bits or 64 characters in hex format.

Sample SHA 256 Output looks like this: 68e656b251e67e8358bef8483ab0d51c6619f3e7a1a9f0e75838d41ff368f728

The algorithm is designed such that every slight change in the input results in the output being completely different bearing no resemblance to its input.

A live demo of how one way hashes work can be found here, by Anders.

The nature of one way hashing algorithms is to bear no resemblance to its input. A one way hash function is a deterministic algorithm implying that a given input will always yield its corresponding output and none other.

An ideal one way hash function has no collisions. Given that a specific input always returns a specific output, in order to obtain a different output, the input must change. In bitcoin, the designed puzzle is such that a person must recursively hash until they obtain a hash whose initial digits/characters have already been specified.

The difficulty of obtaining a hash that matches the specific pattern increases exponentially as the number of specific digits increases.

In the case of Bitcoin, we can observe on a blockexplorer how the hash of each block from genesis block (block 0) lead with a couple of zeros.

This pattern of obtaining a series of zeroes to lead a hash gets harder as a longer series is demanded. The series of zeros leading a hash required is often used synonymously with the difficulty level.

For example:

Block 1 leads with 8 zeros and the computation required for finding the hashthat leads with 8 zeros is a lot lesser than the computation required to find the hash of block 505751 that leads with 19 zeros.

Block 1:

Block 505751:

Finding the hash involves recursively passing the elements of the proposed block through the hashing function to test for a hash that matches the proposed difficulty and the difficulty level resets every 2016 blocks, roughly about 2 weeks.

The proof of work employed in bitcoin was required to be easy to verify but hard to arrive at. This is solved by using a nonce.A nonce is a non repeating number.

A nonce is included along with other contents of a block and is fed as input to the hashing algorithm. Upon obtaining a hash, if the hash does not correspond to the difficulty level, the nonce is increased by one and hashed again until a hash that appropriately corresponds to the difficulty level is obtained.

This nonce once obtained can be hashed along with the rest of the block’s contents to obtain the hash to verify. This verification process wouldn’t take much time, but in order to come up with the nonce, one must hash the contents of the block and try various multiple iterations to obtain the nonce.

This implies that verification is extremely easy whereas coming up with the nonce in the first place is quite a laborious process.

Upon finding the nonce, the block containing the nonce is hence broadcasted to other bitcoin nodes on the network along with the hash to verify.

The whole process of finding the nonce is described as proof of work.

The nonce is the proof of work to establish that a miner has actually tried computing various iterations before arriving at this number and hence receives a block reward.

This has been adopted from HashCash

References:

Bitcoin Difficulty Chart

Difficulty Wiki

Nonce Wiki

HashCash