Difference between revisions of "Proof of Work"

(Created page with "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. Produci...")
 
 
(24 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
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 a piece of data which is difficult (costly and/or 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 the [[SHA-256]] hashing algorithm.  
  
−
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).
+
== Proof of Work in Bitcoin ==
  
−
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.
+
Bitcoin uses a proof of work system in the process of [[mining]]. In order for a [[block]] to be accepted, the broadcasting node must demonstrate proof of valid work which covers all of the data in the block. The [[difficulty]] of discovering valid work outcomes is adjusted to limit the average growth rate of the [[blockchain]] to one block every 10 minutes.
  
−
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.
+
For a block to be valid, a nonce must be discovered that results in the double SHA-256 hash of the [[Block_hashing_algorithm#Block_Header|block header]], to a value less than the current [[target]]. This indicates that the node which discovered this block is an active participant in the network. Each block header contains the hash of the block being built upon, thus creating the chain of blocks that comprise the ledger. Changing a block can only be done by making a new block, containing the same predecessor, and requires regenerating all subsequent blocks by redoing the work they contain. This protects the blockchain 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.
+
=== Summary ===
  
−
== Example ==
+
1. Proof of work is part of the Bitcoin consensus mechanism.
  
−
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.
+
2. The Bitcoin proof of work algorithm attempts to solve a puzzle with a low probability of success per trial.
  
−
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64 = 2^252.253458683
+
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.
−
"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.  
+
4. In order for a block to be accepted by the Bitcoin network, 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 on average. Due to the very low probability of successful generation, it is impossible to predict which computer will generate the next block.
  
−
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.
+
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 algorithms ==
+
==Attribution==
−
 
+
This content is based on content sourced from https://en.bitcoin.it/wiki/Proof_of_work under [https://creativecommons.org/licenses/by/3.0/ Creative Commons Attribution 3.0]. Although it may have been extensively revised and updated, we acknowledge the original authors.
−
=== 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]]
 
−
 
 
−
=== Consensus ===
 
−
# [https://www.stellar.org/papers/stellar-consensus-protocol.pdf Stellar Consensus Protocol]
 
−
 
 
−
[[Category:Vocabulary]]
 
−
[[Category:Proof-of-x]]
 
−
[[Category:Technical]]
 
−
 
 
−
[[fr:Preuve de travail]]
 
−
 
 
−
==References==
 
−
[[Distribution of nonces and hashes]]
 
−
<references/>
 

Latest revision as of 01:51, 11 January 2022

A proof of work is a piece of data which is difficult (costly and/or 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 the SHA-256 hashing algorithm.

Proof of Work in Bitcoin

Bitcoin uses a proof of work system in the process of mining. In order for a block to be accepted, the broadcasting node must demonstrate proof of valid work which covers all of the data in the block. The difficulty of discovering valid work outcomes is adjusted to limit the average growth rate of the blockchain to one block every 10 minutes.

For a block to be valid, a nonce must be discovered that results in the double SHA-256 hash of the block header, to a value less than the current target. This indicates that the node which discovered this block is an active participant in the network. Each block header contains the hash of the block being built upon, thus creating the chain of blocks that comprise the ledger. Changing a block can only be done by making a new block, containing the same predecessor, and requires regenerating all subsequent blocks by redoing the work they contain. This protects the blockchain from tampering.

Summary

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

2. The Bitcoin 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 network, 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 on average. Due to the very low probability of successful generation, it is impossible to predict which 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.

Attribution

This content is based on content sourced from https://en.bitcoin.it/wiki/Proof_of_work under Creative Commons Attribution 3.0. Although it may have been extensively revised and updated, we acknowledge the original authors.

Retrieved from "https://wiki.bitcoinsv.io/index.php?title=Proof_of_Work&oldid=2766"