Proof of Work

Revision as of 13:55, 29 January 2020 by AlexMackay (talk | contribs)

A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify. Proof of work production usually involves a computational task that includes a random process with low probability of success so that a lot of trial and error is required on average before a valid proof of work is generated. In Bitcoin the proof of work scheme is based on SHA-256.

Example of Proof of Work

Let's say the base string that we are going to perform work on is "Hello, world!". Our target is to find a variation of it that SHA-256 hashes to a value smaller than 2^240. We vary the string by adding an integer value to the end called a nonce and incrementing it each time, then interpreting the hash result as a long integer and checking whether it's smaller than the target 2^240. Finding a match for "Hello, world!" takes us 4251 tries.

"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64 = 2^252.253458683
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8 = 2^255.868431117
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7 = 2^255.444730341
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965 = 2^254.782233115
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6 = 2^255.585082774
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9 = 2^239.61238653

4251 hashes on a modern computer is not very much work (most computers can achieve at least 4 million hashes per second). Bitcoin automatically varies the target (and thus the amount of work required to generate a block) to keep the network wide block discovery rate roughly constant at 10 minutes per block.

In Bitcoin, proof of work is applied to the block header which contains the hash of the block being built upon. The hash result that successfully solves the proof of work function is also used as a reference to the block itself, so somebody might say that their transaction has been mined into Block with hash 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9. The header of a block contains the Merkle Root [1] which depends on the included transactions. This includes the generation transaction which contains the winning miner's block reward.

Proof of Work in Bitcoin SV

Bitcoin SV uses the Hashcash proof of work system for block generation. In order for a block to be accepted by network participants, miners must complete a proof of work which covers all of the data in the block. The difficulty of this work is adjusted to limit the rate at which new blocks can be generated by the network to one every 10 minutes. Due to the very low probability of successful generation, it is impossible to reliably predict which worker computer in the network will generate the next block.

For a block to be valid it must hash to a value less than the current target; this means that each block indicates that work has been done generating it. Each block contains the hash of the preceding block, thus each block has a chain of blocks that together contain a large amount of work. Changing a block (which can only be done by making a new block containing the same predecessor) requires regenerating all successors and redoing the work they contain. This protects the block chain from tampering.

Summary

1. Proof of work is part of the Bitcoin SV consensus mechanism.

2. The Bitcoin SV proof of work algorithm attempts to solve a puzzle with a low probability of success per trial.

3. A miner uses a candidate block header as the input, hashes it to check whether the hash value is below a target. If not, the miner changes the nonce in the block header and tries again. Once the hash value is below the target, the block has been successfully mined.

4. In order for a block to be accepted by the Bitcoin SV network, miners must complete a proof of work which covers all of the data in the block. The difficulty of this work is adjusted so as to limit the rate at which new blocks can be generated by the network to one every 10 minutes on average. Due to the very low probability of successful generation, it is impossible to predict which worker computer will generate the next block.

5. The low probability of successfully finding valid proof of work solutions reduces the likelihood that two or more miners generate a block around the same time.


List of proof-of-work algorithms

Traditional proof of work

  1. hashcash with double iterated SHA256
  2. hashcash with scrypt internal hash
  3. Momentum birthday collision
  4. Cuckoo Cycle proof of work https://github.com/tromp/cuckoo
  5. Various other proof of works functions

Proof of X

  1. Proof of Stake
  2. Proof of Burn

Consensus

  1. Stellar Consensus Protocol


References

Distribution of nonces and hashes