Copied from bitcoinmedia.com/proof-of-work-exposed
Proof of work exposed
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.
We put
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:
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:
In decimal this is:
Looking at block 163701, note the field labelled “Bits”.
To transform a bits value into a target we use the formula:
The maximum possible target is a constant defined by
To find the difficulty we use:
difficulty = maximum possible target / currently agreed on target
Taking from our example:
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.
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”.
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
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.
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:
- Hash a block
- Calculate the current target from the difficulty
- Is the block hash value less than the current target?
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:
00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018In decimal this is:
15072061652479515824586354748403488046119941424972330391289880Looking 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.3606040676Which 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 < 0xcd43f0000000000000000000000000000000000000000000000TrueA 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: 2528486661To 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.
