I need a problem that has one and only one solution, such that the solution is hard to find but easy to verify. I need to be able to generate the problem deterministically from a random seed.
So essentially, I want to be able to do this:
A random value is produced.
One can then search for the "correct answer" to the random value.
There is one and only one "correct answer".
That a particular answer is correct can easily be verified.
Ideally, the amount of work required would be tunable. The problem with most proof of work systems is either that they don't ensure that there is one and only one correct answer or they require some entity to generate the problem and withhold the solution.
For example, I could require someone to produce something that HMACs with the random value to a very low result. But then there wouldn't be one and only one correct answer. I could multiply two primes together and the lowest factor could be the correct answer. But I have no agent that can do that multiplication. Steps one and two are set in stone, though I can adjust the size of the random number.
Update: It must not be possible to do all of the work before the random number is generated. Ideally, there would be no significant benefit to any precomputation. The random number being revealed must enable you to do the work.