Proof of work

In this article proof of work, as used in bitcoin and other cryptocurrencies, is explained. Also a small demonstration, which simulates proof of works inside the browser is linked.

Hashcash

Originally proof of work algorithms were researched to be an effective measure against spam or denial of service attacks. Adam Back released a paper in 2002 were he named this approach as Hashcash. Similar approaches seem to be older than Hashcash, as found in the related work section on the Hashcash website.

The basic idea behind Hashcash is to limit the usage of a service by requesting solutions to computational problems for each use. Metaphorically this can be though as a payment for the service. E.g. everytime an email service can be used to send an email some seconds of computational work have to be done in advance by the service user. This would require lot's of computational work from somebody who wants to send spam mails via this email service. In the following a simple description of the steps of the Hashcash algorithm are given:

• The service operator states the problem: Find a sha256 hash with 3 leading zeros to the input string "hash input problem" by concatenating ascending integers to the end.
• The service user is searching for hashes until the 3 leading zeros requirement is solved: sha256("hash input problem0"), sha256("hash input problem1"), sha256("hash input problem2"), ..., sha256("hash input problem1879")
• After the service user found the solution (1879 in this case) the service can be requested by stating the solution to the service operator.
• The service operator can simply check the solution by doing a single hash operation (sha256("hash input problem1879") = 000dba...) and check if the requirement of 3 leading zeros is solved

Depending on the number of leading zeros to the hash, the computation gets harder and harder. So the Hashcash algorithm can be adjusted with rising computing power available to service users. The Hashcash approach seems like an interesting idea for fighting spam, however at least on the web this approach is not used widely. Captchas which require human involvment are probably more effective.

Proof of work in bitcoin/blockchain

The bitcoin blockchain is a public and distributed database of all valid transactions. As the bitcoin blockchain generally is public, everybody could add transactions to one's own benefit. Proof of work is used to prevent the incorrect addition of transactions to the bitcoin blockchain. This makes the bitcoin blockchain a database which can be read by anyone, however changes can only be added under certain conditions:

• Bitcoin users transmit new transactions to the bitcoin network.
• Transactions are propagated like gosip in the network, so that every node gets to know every new transaction.
• Special mining nodes collect all transactions and store them temporarily in memory (so called mempool).
• Mining nodes select transactions from the mempool and put them in a datastructure called a merkle tree. The root of the merkle tree forms, among other parameters, the block header.
• The block header is the basic input parameter for the proof of work (Hashcash) algorithm. If a mining node finds a valid solution (block header + nonce) the full block is propagated to the bitcoin network.
• The mining node, which found the solution, also puts a so called coinbase transaction as first transaction into the block. This transaction contains the mining reward and mints new bitcoins out of thin air (In bitcoin the mining reward is reduced by half every 210.000 blocks mined).

Difficulty retargeting

The important part with proof of work is the difficulty (number of zeros at the beginning of the hash result). The difficulty specifies the approximate amount of time required to find a solution by the available computing power (hashrate). The bitcoin network specified a block time of 10 minutes, this means that the available computing power should not find a solution before 10 minutes.

The available computing power for the bitcoin blockchain is measured by the hashrate (amount of hashes computed within a second). The more computing power is added to the network, the higher gets the hashrate and thus a solution for the proof of work is found earlier that 10 minutes. Therefore the difficulty target needs to be dynamic based on the available computing power. Bitcoin added an intelligent mechanism to retarget the difficulty every 2016 blocks. Based on the assumption that every 10 minutes one new block is generated, this would mean 2016 blocks take exactly 2 weeks to mine. So if it took more time that 2 weeks to find 2016 blocks the difficulty is decreased otherwise it is increased.

Browser simulation

I created a small simulation, which can be run inside a browser. The simulation should demonstrate how proof of work mining works. The simulation can be found here and the source code is available on github.

Further reading

• Bitcoin mining difficulty calculations: https://en.bitcoin.it/wiki/Difficulty
• Current hashrate: https://blockchain.info/charts/hash-rate
• Hashcash website: http://hashcash.org/