Difference between revisions of "Proof of work"

From Bitcoin Wiki
Jump to: navigation, search
(edit the page for style)
(Consensus: removed)
 
(44 intermediate revisions by 20 users not shown)
Line 1: Line 1:
{{stub}}
+
A '''proof of work''' is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required ''on average'' before a valid proof of work is generated.  Bitcoin uses the [[Hashcash]] proof of work system.
  
A '''proof of work''' is the verifiable result obtained through a given work. Anyone should be able to make sure that a given share of work was accomplished.
+
One application of this idea is using Hashcash as a method to preventing email spam, requiring a proof of work on the email's contents (including the To address), on every email. Legitimate emails will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).
  
This is used in bitcoin for block generation. The block hash itself is a proof of work, proving that whoever generated that block deserves the associated transaction fees and reward.
+
Hashcash proofs of work are used in Bitcoin for block generation. In order for a block to be accepted by network participants, [[Mining|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. Due to the very low probability of successful generation, this makes it unpredictable which worker computer in the network will be able to 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 [[block chain|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.
 +
 
 +
The most widely used proof-of-work scheme is based on [[SHA-256]] and was introduced as a part of [[Bitcoin]]. Some other hashing algorithms that are used for proof-of-work include [https://en.wikipedia.org/wiki/Scrypt Scrypt], [https://en.wikipedia.org/wiki/BLAKE_(hash_function) Blake-256], [[CryptoNight]], [https://heavycoin.github.io/ HEFTY1], [https://131002.net/quark/quark_full.pdf Quark], [https://en.wikipedia.org/wiki/SHA-3 SHA-3], [https://github.com/floodyberry/scrypt-jane scrypt-jane], scrypt-n, and combinations thereof.  
  
 
== Example ==
 
== Example ==
  
Let's say our base work is "Hello world" and our work is to find a hash starting with "000". We are going to increase an integer value (nonce) hashed alongside "Hello world", until we reach our goal.
+
Let's say 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 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
  
Hello world ! 0 : 3f6fc92516327a1cc4d3dca5ab2b27aeedf2d459a77fa06fd3c6b19fb609106a
+
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 a roughly constant rate of block generation.  
Hello world ! 1 : b5690c48c2d0a09481186aaa99e4e090901ff2ac4d572e6706dfd30eefc22a27
 
Hello world ! 2 : 5b6fd9c27fcb54ca23404d9428f081b7c9280ba6370e33a6a20b16f40ce76320
 
Hello world ! 3 : 9c5d769416aa0ca894abf22bd17bd30fbb6959291423ae1903a9f86a1fe7ce78
 
Hello world ! 4 : 4efc65df7933e4f5cc21947c61d5cc6bd11d644794bfa210603b0547c4b1cc3e
 
Hello world ! 5 : 441b15b67d791620cd50ea537144e3115422e33bdb1b1b9b110d3265f7a9199b
 
Hello world ! 6 : d368331386f0cf773ad53910fefcef4bdceeb526e408d3fbc9408d6f6e481ca4
 
Hello world ! 7 : 013cc9722f38d2eb6186b75e2e7cbe6e7818e0612a2774d4400416b17ae03b87
 
Hello world ! 8 : 3a92631799b478c3bcc554df8401b09900fbdb58cc0e58efe711cc475ee097b3
 
Hello world ! 9 : 66658881696164fcb04f32ec505bb5e515000a85baf691beb63fc9d3f4d0fee2
 
....
 
Hello world ! 88 : 80d009db72c6ad35241bb3dbac77cbe177c6a803fe67527c159dbfaf2cbf9f5c
 
Hello world ! 89 : a5b1e789f691f9793f8a84f8ebae3d8e28d49cbe0eeea2da621cd409e3bdee2b
 
Hello world ! 90 : 4eba5b2459caac3d9ff3b787aaa5cac481aaa4a0232fbbe02a8ee4d1101c2ca2
 
Hello world ! 91 : c811722c68b53614d58d37dcad9d540c2bce9f85b5ccae94424ff4716eea1765
 
Hello world ! 92 : e30c716fccda22f394a8e80a2670b97968b5416b8b39e2061a7b7d1a9f41e0a9
 
Hello world ! 93 : 965425c39d4e24c532721d7f7b77a00b31b0c0d0e316d46240c4e6bec9c09f65
 
Hello world ! 94 : 7090a0e5d88cff635e42ea33fcd6091a058e9cdd58ab8cd5c21c1c70421e35c6
 
Hello world ! 95 : b74f3b2cf1061895f880a99d1d0249a8cedf223d3ed061150548aa6212c88d43
 
Hello world ! 96 : 447ca2fa886965af084808d22116edde4383cbaa16fd1fbcf3db61421b9990b9
 
Hello world ! 97 : 000ba61ca46d1d317684925a0ef070e30193ff5fa6124aff76f513d96f49349d
 
  
And here we are. Now we just have to let the network know our block, made of "Hello world" and 97, won.  
+
In Bitcoin the hash value is also used as a reference to the block itself, so somebody might say that their [[transaction]] has been mined into [[block]] with hash <code>0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9</code>. The [[header]] of a [[block]] contains the [[Protocol_documentation#Merkle_Trees|Merkle tree]] which depends on the included [[transactions]]. This includes the generation transaction, a transaction "out of nowhere" to our own address, which in addition to providing the miner with incentive to do the work, also ensures that every miner hashes a unique data set.
 +
 
 +
== List of algorithms ==
 +
 
 +
=== Traditional proof of work ===
 +
# hashcash with double iterated SHA256
 +
# hashcash with [[scrypt]] internal hash
 +
# [[Momentum]] birthday collision
 +
# Cuckoo Cycle proof of work https://github.com/tromp/cuckoo
 +
# Various other proof of works functions
 +
 
 +
=== Proof of X ===
 +
# [[Proof of Stake]]
 +
# [[Proof of Burn]]
  
In bitcoin things are a bit more complex, especially since the header contains the [http://en.wikipedia.org/wiki/Merkle_tree merkle tree] which depends on the included transactions. This includes the generation transaction, a transaction "out of nowhere" to our own address, which in addition to providing the miner with incentive to do the work, also ensures that every miner hashes a unique data set.
 
  
 
[[Category:Vocabulary]]
 
[[Category:Vocabulary]]
 +
[[Category:Proof-of-x]]
 +
[[Category:Technical]]
  
 
[[fr:Preuve de travail]]
 
[[fr:Preuve de travail]]
[[{{ns:file}}:Example.jpg]]
+
 
 +
==References==
 +
[[Distribution of nonces and hashes]]
 +
<references/>

Latest revision as of 13:54, 6 June 2020

A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required on average before a valid proof of work is generated. Bitcoin uses the Hashcash proof of work system.

One application of this idea is using Hashcash as a method to preventing email spam, requiring a proof of work on the email's contents (including the To address), on every email. Legitimate emails will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).

Hashcash proofs of work are used in Bitcoin 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 so as 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, this makes it unpredictable which worker computer in the network will be able to 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.

The most widely used proof-of-work scheme is based on SHA-256 and was introduced as a part of Bitcoin. Some other hashing algorithms that are used for proof-of-work include Scrypt, Blake-256, CryptoNight, HEFTY1, Quark, SHA-3, scrypt-jane, scrypt-n, and combinations thereof.

Example

Let's say 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 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 a roughly constant rate of block generation.

In Bitcoin the hash value 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 tree which depends on the included transactions. This includes the generation transaction, a transaction "out of nowhere" to our own address, which in addition to providing the miner with incentive to do the work, also ensures that every miner hashes a unique data set.

List of 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

References

Distribution of nonces and hashes