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?
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.
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.