Underpinning bitcoin is its proof of work algorithm. It is a computational problem which when solved proves you expended work to solve. In bitcoin’s context, work refers to electricity and proof to the ‘target check’.

Hashing

The actual algorithm involves a hash function.

An algorithm is a list of instructions for solving a problem. An abstract flow-chart of a computer program is an algorithm.

Algorithms can be put inside black boxes called functions. Things (input) go into a function, magic happens inside, and things (output) come out.

When programmers talk of algorithms, they mean a set of instructions or a procedure which they are interested in its inner workings. When speaking of a function, a programmer is referring more to what it does rather than how it works. So in this article, when we refer to the proof of work algorithm we are examining how it works. For the hash function which is used by the proof of work, we are less interested how it works and more what are its effects.

A hash function takes a single input and gives a single output that is not easily recognised from the input. Good hash functions (there are many variants from MD5 to SHA) should hardly never generate collisions- that is when two different inputs produce the same output.

In practice, this means that hash functions generate hashes that have many digits.

$ python
>>> import hashlib
>>> hashlib.sha256("hello").hexdigest()
'2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824'


We put hello into the SHA256 hash function, and its algorithm computed the hash value which the function spat out; 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824.

Another property of a good hash function is small changes in input lead to large changes in output. This makes it difficult (practically impossible) to reverse a hash function. Bad hash functions can be reversed with enough computation power. The output hash may not have enough digits and the total search space is too small. Or there are too many collisions in the hash function.

Small changes in the starting conditions lead to large hard to guess changes in output.

A security measure that all websites should employ is to not store your password on their server but a hash of the password. When you login, the website hashes your password and checks whether it matches their hash. This makes it impossible for an attacker who compromises the website to learn of the user’s passwords.

When MtGox had their database leaked online, that they were compromised in the first place was also confounded by their poor choice of a hashing algorithm. It was trivial to run through every possible combination of digits, recreate the hash and check for matches in the list to find user’s passwords. A good hashing algorithm makes this kind of attack infeasible.

Proof of work

The bitcoin proof of work algorithm is simple:

1. Hash a block
2. Calculate the current target from the difficulty
3. Is the block hash value less than the current target?

A bitcoin miner is constantly hashing a block to see if it passes the above check. If not then it slightly modifies the block and tries again. It keeps doing this until it finds a block that passes. A valid block has been found, and the miner will broadcast this block to the network.

The difficulty is set by the network. Around every 2 weeks, the network reconvenes and decides on a new difficulty. If it was too easy to make blocks, then the difficulty rises. If too hard, then difficulty falls.

This is why bitcoin blocks all start with zeros. The block hashes are numbers. Block 163701 has a hash value in hexadecimal representation of:

00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018

In decimal this is:

15072061652479515824586354748403488046119941424972330391289880

Looking at block 163701, note the field labelled “Bits”.

Difficulty: 1307728.360604 ("Bits": 1a0cd43f)

To transform a bits value into a target we use the formula:

t = b2 · 28(b1 - 3)

b1 is the first byte of our “bits” value or 0x1a in hexadecimal (26 in decimal). b2 is the rest of the value or 0x0cd43f (840767).

t = 0x0cd43f · 28(0x1a - 3)

>>> 0x0cd43f * 2**(8*(0x1a - 3))
20615546854515052444405957679617344022137222968655050411343872L
>>> "%x"%(0x0cd43f * 2**(8*(0x1a - 3)))
'cd43f0000000000000000000000000000000000000000000000'

The maximum possible target is a constant defined by 0x1d00ffff.

>>> "%x"%(0x00ffff * 2**(8*(0x1d - 3)))
'ffff0000000000000000000000000000000000000000000000000000'

To find the difficulty we use:

difficulty = maximum possible target / currently agreed on target

Taking from our example:

>>> 0xffff0000000000000000000000000000000000000000000000000000 / float(0xcd43f0000000000000000000000000000000000000000000000)
1307728.3606040676

Which is the same difficulty we noted earlier on block explorer. We know the current target, and we have the block hash. If the block is valid and passes the proof of work test then that block hash will be a smaller number than the current target.

0x00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018 < 0xcd43f0000000000000000000000000000000000000000000000

True

A miner’s task is to make a block and keep modifying that block so that it produces a different hash, until that hash passes the above test. Noting our example block, there is a field called “Nonce”.

Nonce: 2528486661

To modify the blocks, miners usually keep adding one to the nonce and rehash the block. Although they can equally set it to random values or modify the block in other ways such as re-arranging the transactions contained in the block. And if the nonce reaches its maximum value, then miners will perform some trickery on their first transaction and continue on (trickery is increment coinbase nonce or IncrementExtraNonce(...)).

Creating a block is not easy. It takes computational processor cycles. Ergo it takes electricity. Ergo it costs money. Creating a block usually has miniscule profit or even negative expected value. As more people mine and create blocks, the network drives up the difficulty squeezing out all the profit.

Once a miner finds a valid block that passes the proof of work test, it is sent out to the network. Other participants in the network pick up the block, verify that it passes the test, accept it into their own blockchain and relay it on.

Forgive me for including this social media spam but it helps our dinky small site get exposure D:

•