https://en.bitcoin.it/w/api.php?action=feedcontributions&user=Distribution&feedformat=atomBitcoin Wiki - User contributions [en]2021-01-17T19:51:37ZUser contributionsMediaWiki 1.30.0https://en.bitcoin.it/w/index.php?title=Proof_of_work&diff=45051Proof of work2014-03-17T00:21:36Z<p>Distribution: Fixed typo (hascash>hashcash)</p>
<hr />
<div>A '''proof of work''' is a piece of data which was difficult (costly, time-consuming) to produce so as to satisfy certain requirements. It must be trivial to check whether data satisfies said 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.<br />
<br />
One application of this idea is using [http://en.wikipedia.org/wiki/Hashcash 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).<br />
<br />
Hashcash proofs of work are used in Bitcoin for block generation. Proofs of work that are tied to the data of each block are required for the blocks to be accepted. 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.<br />
<br />
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.<br />
<br />
== Example ==<br />
<br />
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 beginning with '000'. We vary the string by adding an integer value to the end called a [[nonce]] and incrementing it each time. Finding a match for "Hello, world!" takes us 4251 tries (but happens to have zeroes in the first four digits):<br />
<br />
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64<br />
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8<br />
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7<br />
...<br />
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965<br />
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6<br />
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9<br />
<br />
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 [[difficulty]] (and thus the amount of work required to generate a block) to keep a roughly constant rate of block generation. The probability of a single hash succeeding can be found [http://blockexplorer.com/q/probability here].<br />
<br />
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.<br />
<br />
== List of algorithms ==<br />
<br />
=== Traditional proof of work ===<br />
# hashcash with double iterated SHA256<br />
# hashcash with [[scrypt]] internal hash<br />
# [[Momentum]] birthday collision<br />
# Cuckoo cycle proof of work https://github.com/tromp/cuckoo <br />
# Various other proof of works functions (e.g. [[Ethereum]] had a few candidates)<br />
<br />
=== Proof of X ===<br />
# [[Proof of Stake]] (Used in [[Peercoin]], [[Nxt]])<br />
# [[Proof of Burn]] (Used for the [[Counterparty]] IPO)<br />
<br />
[[Category:Vocabulary]]<br />
<br />
[[fr:Preuve de travail]]</div>Distribution