Proofs of Useful Work [pdf]
eprint.iacr.org
eprint.iacr.org
The value of PoW in cryptocurrency is that I know for a fact that you have to burn $X million dollars if you want to double-spend my cryptocurrency. That has to be burned in electricity, and that burn can't be used for anything else. It's expensive for you to attack me.
If suddenly we've got useful works, such that you can apply that $X million in electricity to solve problems that are actually not wasteful, and worth perhaps $X million dollars in solutions, then I don't actually have confidence that it costs you money to double-spend my transaction. You might be able to double-spend my transaction as a by-product of computation that you were going to do already.
Further, useful PoW is a centralizing pressure, because not everyone is going to have equal access to people who are willing to pay for solutions of useful work. This unequal access to revenue means unequal ability to compete, favoring people who are able to sell solutions more effectively. For cryptocurrency, we like to remove these advantages as much as possible (granted, the existing system has a lot of room for improvement, but useful work moves things in the wrong direction).
E.g. see discussion of information goods here https://en.wikipedia.org/wiki/Public_good#Challenges_in_iden...
PoW mining just raises the capital cost to control the network without ever improving the speed or functionality. It's a system that increases the waste as time progresses.
https://en.wikipedia.org/wiki/List_of_distributed_computing_...
Useful PoW is totally fine for a cryptocurrency the same way useless PoW is - you have to solve a particular instance of some kind of problem, not just "computation that you were going to do already". I think Primecoin is a good example: the general problem that's being solved for mining happens to have a useful byproduct, but you still have to provide PoW on the particular instance that is on the chain.
Even Bitcoin has provided useful work for a very weak definition: it has created incentives for MASSIVE research and development in cracking or otherwise breaking SHA-256. I don't know where I could find data, but I would bet that there's an inflection point in "crack speed" around 2009, and that further progress probably correlates pretty well with the USD-BTC exchange rate.
In this case, every assumption of trustlessness and censorship resistance has gone out the window.
A consensus algorithm using proof of useful work will become a market of miners for whom the mining rewards and thus the integrity of the network are merely a secondary concern.
However, proof of useful work could be a public good. Though that makes coming up with an algorithm much harder.
And chip performance in general. It wouldn't surprise me if Bitcoin ASICs nudge the state of the art in chip design and fabrication forward.
Another (very marginally) useful bit of work mining does: converting electricity to heat.
I doubt many miners are currently using the heat, but it seems inevitable that eventually most miners would be located in areas where 1) electricity is very cheap, and 2) the heat produced by mining can be used productively
In a stupidly wasteful way, though. Large-scale heat generation with electricity is better done with heat pumps, which have 400-500% efficiency.
1) The difficulty must be adjustable so that you can make it harder or easier as computational power joins or leaves the network -- so it can't be some generically hard problem with no free parameter that affects the hardness.
2) The difficulty must be precisely predictable, so you know how much to adjust it for 1). That probably rules out NP-complete problems, where it's hard to generate random instances while ensuring you'll get one of the hard ones.
3) The problem must be capable of being arbitrarily generated from a random string, so that your work is associated with a specific ledger update (block), and so the work must have started after that node became aware of the block. This would require you to optimally "compress" the problem space so that a random string decompresses to a valid instance. But if you could compress the problem space that way, it wouldn't be hard!
Partial hash inversion (used in Bitcoin) satisfies those because:
1) You can adjust how many digits of a match are required.
2) There is no shortcut to guessing all the nonces, and each output is effectively a random number with predictable properties.
3) You can require the nonce to be prefixed by the Merkle root of the new block + previous Merkle root.
Edit: Primecoin was a good start, but it quickly exhausted all of the academically useful primes, and is unable to meet 1) while still being useful.
[1] At least, I don't know of a rigorous impossibility proof.
750000000000 chance every 10 minutes * say 1,000,000 CPU miners = 1 / 750000 per 10 minutes, and 1 in 14.27 per year. I don't think their are 1,000,000 CPU miners, but I suspect their are at least a few thousand of them for the lul's.
first if we ignore the part "not everyone is going to have equal access to people who are willing to pay for solutions of useful work"
I think this can never happen.
----
People should think PoW as lottery.
Every X minutes there is a prize draw giving you Y coins.
But ticket price converges to market value of:
ticket price = (Y coins)/(total tickets sold)
So if you add a value to 'not winning ticket' by introducing 'useful work', you are changing ticket price to:
ticket price = (Y coins)/(total tickets sold)-'work value'
so you are just giving coins more value, means making 'new ticket' more expensive.
new ticket = old ticket + work value
In the end you will still 'waste' the same amount at equilibrium.
That means the value would change if new ways to solve the problems arise. But currently the value changes based on your electricity bill (new tech could disrupt that too).
Note that it's more of a market for mathematical proofs, not a replacement for proof of work in a currency that needs a new block every 10 minutes.
Still, "miners" (theorem provers) get rewarded for their efforts with tokens.
My mathematician friends say such a genericized proof market should be possible using Model Theory.