On a previous answer to a question about making proof-of-work more useful, two challenges were provided:
"1. The work must be much, much easier to verify than to do, and
2. The work must in fact secure the transactions and not be severable from them. If I see that you sent me 10 Bitcoins and then billions of computations are piled on top of that, it must not be possible to remove that transaction and then pile those same computations on top of a conflicting transaction."
To address these, has anyone considered a zero-knowledge / Arthur-Merlin proof of work (of some NP problem or co-NP problem, e.g.), with the public coin flips being the hash of the most recent blocks?
After each new block is mined, a number of other random instances of the problem may be publicly announced. The instances could be created based on the hash of the block. Whoever solves (the most number of) outstanding problems is the winner for that block. She then uses the hash of that block as the coin flips for the validation of the proof-of-work.
E.G. for graph non-isomorphism, every block that is solved spawns, say, 128 new graphs added to a pool. The first miner to find proofs of non-isomorphism for, say, the most number of the graphs in the pool wins.
It's also a truism that most instances in NP may, in fact, be "easy." Depending on how instances are added to a pool, the instances that have been "in the pool" the longest are probably harder to solve, and may be worth more when finally mined. (An easy 3-SAT with 20 literals may be easier to solve than a hard 3-SAT with 5 literals right at the percolation point. The profit from mining may reflect that.)
Engaging in more rounds of commitment, with more rounds of random coin flips based off of more blocks in the chain, may lead to more complicated problems being mined (e.g. IP=PSPACE.)
A fraudster might try to buy Merlin/Peggy the miner's PoW form her, but as instances are spawned randomly, it might not do the fraudster much good. Also it’s a little harder to buy solutions to PSPACE or co-NP problems I think, without having to engage in actually finding the solution.