Proof of work isn’t, but could be

(I posted this on the Bitcoin Forum, cross-posting it here for archival purposes)

We accept “proof of work” based on the assumption that there is no faster way to find a nonce which will give a new block a good enough hash value than brute-force search (currently requiring sextillions of guesses on average). But what if there were a hole in the crypto, a shortcut to finding likelier nonces? It would obviously be in the interests of the Bitcoin community to know whether someone had developed such a thing.

As things stand now, this isn’t detectable, but only because of the presumption that a successful hash represents work. Everyone who really has done the work, though, not only knows about the successful guess, but also about quintillions or sextillions of unsuccessful guesses which can be compactly represented by specifying the method by which they were generated; in the usual case, it will be possible to say not only that your nonce gives a good hash, but that a large number of others don’t–most likely, that yours is the first example in a very long arithmetic progression which succeeds after 10^20 or however many failures.

The success is quickly verifiable, but the failures aren’t; however, if I note the first term and common difference of the arithmetic progression I used, and assert that there are no earlier solutions than the one I found, I establish for the record that I am an honest miner who has done the work, because a shortcut to finding solutions while testing a lot fewer of them wouldn’t allow me to confidently specify a long enough solution-free progression to avoid suspicion. If the community randomly checked 1% of the new blocks that made such an assertion, someone who was using such a shortcut would eventually be found out or would have to maintain a suspicious silence about his search space or claim a statistically infeasible amount of good luck.

This can be started right away. No change in the protocol is needed for miners to document search space parameters as an “extended proof of work”, but it would be socially beneficial to do so, because we would all want to know if someone possessed and was using a secret shortcut to finding good hashes. If this behavioral norm spread, eventually those who refused to go along would invite suspicion. The whole system would thereby acquire protection limiting the damage someone with a secret shortcut could do–the shortcutter could still fake it by verifying enough of a progression including his nonce to avoid suspicion for non-compliance, but it would quickly be noticed that he was consistently much more lucky than he ought to be unless he ended up doing a significant fraction of the brute-force work anyway.

If this practice spread enough, there might be support to change the protocol to include it, though I have no proposal for how to apply sanctions to violators whose purported unsuccessful search space was found to include a valid solution. Even if you think SHA is the pinnacle of secure hash functions, you shouldn’t object to such a protocol change, because even though you don’t need reassurance there is no hole in the crypto, it’s good for Bitcoin overall if more people believe this.