Lesson 21

Proof of Work

VIDEO: Bitcoin Protocol Tutorial: Proof of Work

Why it is needed?


The block chain is collaboratively maintained by anonymous peers on the network, so the guarantee of major consensus about valid transactions is needed. To prevent Sybil attack, when malicious participant creates a lot of voting power,  Bitcoin requires that significant amount of work was invested in each block creation. It ensures that untrustworthy peers who want to modify past blocks have to work harder than honest peers who only want to add new blocks to the block chain.

Chaining blocks together makes it impossible to modify transactions included in any block without modifying all following blocks. As a result, the cost to modify a particular block increases with every new block added to the block chain, magnifying the effect of the proof of work.


How it is constructed?


The proof of work used in Bitcoin takes advantage of the apparently random nature of cryptographic hashes. A good cryptographic hash algorithm converts arbitrary data into a random number. If the data is modified in any way and the hash re-run, a new random number is produced, so there is no way to modify the data to make the hash number predictable.

To prove you did some extra work to create a block, you must create a hash of the block header which does not exceed a certain value. For example, if the maximum possible hash value is 2256− 1, you can prove that you tried up to two combinations by producing a hash value less than 2255.

In the example given above, you will produce a successful hash on average every second try. You can even estimate the probability that a given hash attempt will generate a number below the target threshold. Bitcoin assumes a linear probability that the lower it makes the target threshold, the more hash attempts (on average) will need to be tried.


How it is done?

For example the base string that we are going to do work on is "Hello, world!". Our target is to find a variation of it that SHA-256 hashes to a value beginning with '000'. We vary the string by adding an integer value to the end called a nonce (in Bitcoin - nonce is a part of a block, see pic. 1)and incrementing it each time. Finding a match for "Hello, world!" takes us 4251 tries (but happens to have zeroes in the first four digits):


"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64

"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8

"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7


"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965

"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6

"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9


4251 hashes on a modern computer is not very much work (most CPUs can achieve at least 4 million hashes per second). Bitcoin automatically varies the difficulty (and thus the amount of work required to generate a block) to keep the same time of block generation - 10 minutes. The probability of a single hash succeeding can be foundhere.

But not only CPU are used to do proof-of-work - due to SHA2 architecture that requires only 16KB of memory, hi-end video cards we used to produce in this task (for example Radeon 7950 is able to produce 800 million hashes per second). Compare it with modern ASICs that can produce 4500 billion hashes per second. Nowadays people don’t use CPU and GPU for mining Bitcoins, but other currencies are suitable for this kind of hardware - like Monero for CPU and Litecoin for GPU - both of them use memory-hard hash functions like scrypt and cryptonight.


Pic. 1 - Nonce is a part of a block

How difficulty is adjusted?


New blocks will only be added to the block chain if their hash is at least as challenging as a difficulty value expected by the consensus protocol. Every 2,016 blocks, the network uses timestamps stored in each block header to calculate the number of seconds elapsed between generation of the first and last of those last 2,016 blocks. The ideal value is 1,209,600 seconds (two weeks).

If it took fewer than two weeks to generate the 2,016 blocks, the expected difficulty value is increased proportionally (by as much as 300%) so that the next 2,016 blocks should take exactly two weeks to generate if hashes are checked at the same rate.

If it took more than two weeks to generate the blocks, the expected difficulty value is decreased proportionally (by as much as 75%) for the same reason.



Pic. 2 - How difficulty has been changed in 2 years

51% attack and proof of work


Because each block header must hash to a value below the target threshold, and because each block is linked to the block that preceded it, it requires (on average) as much hashing power to propagate a modified block as the entire Bitcoin network spent between the time the original block was created and the present time. Only if you acquired a majority of the network’s hashing power could you reliably execute such a 51% attack against transaction history (although, it should be noted, that even less than 50% of the hashing power still has a good chance of performing such attacks).

The block header provides several easy-to-modify fields, such as a dedicated nonce field, so obtaining new hashes doesn’t require waiting for new transactions. Also, only the 80-byte block header is hashed for proof-of-work, so adding more bytes of transaction data to a block does not slow down hashing with extra I/O.


Alternatives to proof of work


Proof of work ensures that probability of mining a block is dependent on how much work is done by the miner. A proof-of-stake (POS) is an alternative approach where a miner can “mine” by holding coins on his account. For example, a person owning 5% of coins can mine 5% of the blocks in the same way that a person owning 5% of the hashing power will theoretically mine 5% of the blocks.

There are fears that POW systems can lead to low network security, due to the Tragedy of the Commons, and this has led to some coins adopting a POS system. A tragedy of the commons for Bitcoin means that as block reward becomes smaller (especially it is a threat in a moments when reward is halved), there is less incentive to avoid a 51% attack. The POS systems makes any 51% attack more expensive. Someone trying to double-spend would have to own a majority of the coins, and the attacker would suffer from his actions. From the other side proof-of-stake systems are not safe if very small amount of coins is staked -  if there are 1,000 coins in existence, but only 100 coins staked, an attacker only needs 101 coins to perform the double-spending attack.



comments powered by Disqus

You will get an awesome place to trade your
Bitcoin and more. Click for further information!

Choose your topic

and start the journey