I am wondering if there would be any security deficiencies if cryptocurrencies such as Bitcoin were to change their proof-of-work problems to optimization contests. For example, suppose Bitcoin were to change its proof-of-work problem to an optimization problem. In this scenario, the goal each instance of the proof-of-work problem would be to minimize the output of the hash function, and the winner of each block is the entity who finds the input with the lowest hash after 10 minutes. Would an optimization proof-of-work problem cause any security weaknesses, other deficiencies, or complications for the cryptocurrency? Are there any cryptocurrencies which use an optimization proof-of-work problem instead of a search problem as a proof-of-work?
Would an optimization proof-of-work problem where the entity with the lowest hash wins have any security weakness or other disadvantage?
It would not work, because it causes weaknesses. See bitcoin.stackexchange.com/questions/53654/…– abelenkyMay 26, 2017 at 21:50
It seems like this would be a major problem if there were entities who control much of the mining network. On the other hand, if each entity only controlled a very small portion of the network, then I do not see how this problem would be fatal. For example, if Alice only controlled 10% of all the mining power, and Alice gets a 5 minute head start, then Alice would only have a 15% chance of mining the next block, so Alice will have a hard time of producing a 51% attack. I therefore wonder if there are any other weaknesses than a "work-ahead" attack.– Joseph Van NameMay 26, 2017 at 22:42
There is also a question how you'd achieve such a feat. You basically need to collect all solutions for the optimization problem which would mean unnecessary flooding of the network. And an unfair advantage since all solutions are not able to arrive at exactly the same moment.– fictionJul 3, 2017 at 20:45
fiction. As for collecting all solutions, one can instill a protocol stating that only hashes below a certain threshold are acceptable so that one only collects a handful of solutions.– Joseph Van NameJul 3, 2017 at 22:50
Generally, one could predict the "average" hash that is successful.
When a miner is lucky enough to find a hash that is unusually better than normal, it could keep that block to itself, and get a headstart mining the next block, and the next block.
When a competing block is released by a competing miner, the original miner can release its previously secret block with an exceptionally low hash, which is known to be a guaranteed "winner".
This would invalidate the work of other miners, and enforce the miner's headstart on future work, giving it an unfair advantage and greater control over the blockchain.
1Is that especially different than selfish mining in Bitcoin-style POW? What's the expected value of each strategy? May 26, 2017 at 21:57
You're not thinking like an attacker yet. ;)
Beside this incentivizing selfish mining, a miner can do the following attack: Mallory sends all her funds to herself every block. As soon as she finds a block with a very low hash, she can execute the following attack: Make a payment to someone that accepts first confirmation with a substantial fee ensuring it will be in the next block. Wait for the next block. Receive the counterside of the deal (e.g. coins on another chain). Publish their block and laugh.