Proof of work for standard computers I'm interested in a proof-of-work system that works well on standard computers without using the GPU.

Properties the system should have:


Seed based proof-of-work.
There is no distinguished challenger who can solve the problem efficiently. A typical seed is a 256 bit hash of a public key.
Minimize the advantage an attacker gains from specialized hardware.
The legitimate worker has a standard desktop or notebook. He's willing to commit about 1GB of memory and his CPU to calculate the proof. The time he spends is a few minutes to a few hours, depending what grade the proof should have.
The attacker can use specialized hardware including GPU, FPGA and ASIC. The amount of money he spends for hardware and electricity to calculate the proof should be maximal.
Efficient verification
Verifying the proof should be cheap. For example taking 1ms and 1MB of memory.
Small proof
A 16 byte proof would be ideal, but a few kilobytes would be OK too.
Predictable duration
For many proof systems each attempt is independent, making it hard to predict when you succeed. Success peaking around the average time would be nice. This is just a nice-to-have feature, and I'd be content with a system that only satisfies 1 to 4.


Systems I know, but that don't satisfy my requirements:


Hash prefixes for standard hash functions such as SHA-2. This fulfills 1, 3 and 4, but utterly fails 2. Specialized hardware is much more efficient than the target hardware.
Hash prefixes for scrypt. This fulfills 1, 2 and 4. But it fails 3, because verification requires just as much memory as working, and verification time is a bit long too.


I believe it is possible to create a system that fulfills the four main requirements. My idea is solving a problem which in principle can be solved with little memory, but the chance of success is small, and thus the amount of work is very large, in that case. But if you are willing to commit significant amounts of RAM, you can run a different algorithm, that solves the problem efficiently.
$\quad$ chosen-prefix partial collisions for scrypt

This does somewhat better at #3 than your second option because

working requires storing previously obtained scrypt outputs.

(I think it would be better to require a at most a given Hamming distance between the outputs rather

than equality of a specific set of bits of the output. $\:$ The first of those would require storing the

entirety of the outputs, while the second would only require storing the relevant bits of the output.)