Proof-of-work is described in the Bitcoin whitepaper. It is Satoshi Nakamoto’s key contribution to Bitcoin and differentiates it from preceding digital currencies. Proof-of-work demonstrates that a hard puzzle was solved. The puzzle consists of hashing the contents of a block and adding a nonce, until the returned hash starts with a defined number of zeros. The amount of zeros that is required determines the difficulty. Finding the right nonce to compute a hash with the right amount of leading zeros is computationally expensive, however verifying its result is comparitively easy. Every transaction on the blockchain has to be backed up by proof-of-work, before it is accepted. Let’s quickly refresh how hashing works and how it’s used in Bitcoin. A short Ruby script gives a simplified idea of how it works in practice.

Hashing

The hashing algorithm SHA-256, which is used by Bitcoin, works by taking an input and returning a deterministic output that is unique to its input. A slight variation of the input will return a completely different output. Also, two different inputs should not generate the same output and the output is of fixed length, independent of the input. It’s infeasible to reverse the hash, so the output does not reveal the input. Hashing relies on math that takes advantage of the fact that multiplying prime numbers is easy, but it is very hard to find the factorials that result in the same output.

If we take the string "hello world" and run it through a SHA-256 hash function, we get b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9.

$ echo -n hello world | shasum -a 256
b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

You can run this code in your terminal or use an online hash generator to test this yourself.

By adding one exclamation mark to the same string the output is completely different.

"hello world!" -> 7509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9

Hashing as proof-of-work

If we now wanted to find the nonce that combined with the string “hello world!” returns a hash output with two leading zeros, we have to try on average 16**2 times. The nonce in this case is a number added to the end of the string.

"hello world!0   ->  07e889f7afef842b21e0ed5bd0075fa59afe3e9f0b4bbd8bcc9a06c70b086e78
"hello world!1"  ->  19a3bc0e649a694d06304c3ed122a20a5350673003302fafc5c5f292407a4d25
"hello world!2"  ->  8d9c79068e59548c71fdab168cd67a7356c7a1d29ea6431c0aef3527216ca673
"hello world!3"  ->  4b5a6a605df3ee03573c8a05e6a41f4740dc48a62c65563885740282400dbc2e
"hello world!4"  ->  d5f7845e425302f3439735991372134233cd2ca02e809813483ac9955f178062
"hello world!5"  ->  ec70092dd9bc002860baff4fb938c05741e32f735338842dc704a2b7363d3ebb
...

"hello world!49" ->  00501ed342b15e0f16e64b463725150ee1216c9237f396863940af1b064700ba

It took us 50 hashes to find the right nonce which, appended to the string “hello world!”, would generate a SHA-256 hash output with 2 leading 0s.

The difficulty exponentially increases relative to the 0s required in the output. To get an ouput with five leading zeros the nonce has to be 2030350, which translates to more than 2 million attemps. At the time of writing this, the Bitcoin proof-of-work algorithm requires a hash output with 19 leading zeros before a Block is accepted by the network and added to the Bitcoin blockchain: Blockexplorer.

While it’s hard to find the right nonce, it is easy to reverse the task and verify that the hash is correct, as the hash function just has to be run once.

"hello world!2030350"  ->  000009b3111cb851956ed3ebda92b68074aa462b2ac3c82b469bbb36e4d2cc21

To change a block the work has to be redone. Since blocks are chained together by referencing the previous block’s hashed header, the further back a block in the chain, the harder it is to change, since all blocks after it would have to be changed as well. That’s why it’s sensible to wait for a transaction to be confirmed by ~6 blocks after it in order to be sure that the transaction cannot be reversed.

Nakamoto writes in the whitepaper:

Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes.

Therin lies the unique solution of the proof-of-work algorithm which secures consensus in a system where more than 50% of the CPU power is “controlled by nodes that are not cooperating to attack the network”.

Proof-of-work in Ruby

Below is a simplified implementation of proof-of-work in Ruby (inspired by Haseeb Qureshi’s lecture).

class ProofOfWork
  require 'digest'

  def initialize(difficulty:)
    @required_number_of_zeros = difficulty
  end

  def find_nonce_for(block_content:)
    nonce = 0

    until found_correct_nonce?(nonce, block_content)
      nonce += 1
    end

    nonce
  end

  private

  attr_reader :required_number_of_zeros

  def hash(block_content_and_nonce)
    Digest::SHA256.hexdigest(block_content_and_nonce)
  end

  def found_correct_nonce?(nonce, block_content)
    hash(block_content + nonce.to_s).start_with? required_number_of_zeros
  end
end

worker = ProofOfWork.new(difficulty: "00000")
nonce = worker.find_nonce_for(block_content: "hello world!")
# => 2030350

proof_of_work.rb

The script let’s you define the diffifculty by specifying the amount of zeros the resulting hash should begin with. It then takes a string, which in our case is "hello world!", but in a Blockchain will be the contents of the block header and the transactions of the block. The find_nonce_for function iterates over a nonce in a loop. The nonce is 0 in the beginning and in each iteration increases by 1, until found_correct_nonce? returns true. It will return true when a nonce has been found which appended to the string "hello world!" and then passed through the SHA256 hash function results in a hash with the defined diffculty, in our case five zeros. When the nonce is found, the loop stops and returns the nonce which is the number our proof-of-work algorithm sought. As we see above it is 2030350. You can run this code and adjust the difficulty to see how much longer it takes on average to find the right hash.

With the nonce and the string we can quickly verify that combined they result in the same right hash.

require 'digest'

Digest::SHA256.hexdigest("hello world!" + "2030350")
# => "000009b3111cb851956ed3ebda92b68074aa462b2ac3c82b469bbb36e4d2cc21"

verify_proof_of_work.rb

The difficulty of proof-of-work is highlighted when compared to the ease of verification, measured by how long it took to complete:

$ time ruby proof_of_work.rb
real    0m3.652s

$ time ruby verify_proof_of_work.rb
real    0m0.051s

On my machine it took 3.65 seconds to find the right nonce and only 0.05 seconds to verify it.

Less than 4 seconds doesn’t sound like much, but an increased diffulty quickly becomes computationally very expensive, to a level where additional hardware is required and energy to power this hardware. When mining popular Cryptocurrencies, finding the right nonce is a competitve race and who finds it first is awarded coins. Cryptocurrencies adjust the difficulty, i.e. the number of zeros match the Hash Power of the network allowing for a consistent creation of blocks. The Hash Power refers to the computation power of the network of all participating miners. Miners run proof-of-work and the nodes in the network verify it.

Proof-of-work has been critisized for its energy consumption and alternative solutions are being discussed, most notably Proof of Stake.

Further reading