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:

1. 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.
2. 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.
3. Efficient verification
Verifying the proof should be cheap. For example taking 1ms and 1MB of memory.
4. Small proof
A 16 byte proof would be ideal, but a few kilobytes would be OK too.
5. 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:

1. 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.
2. 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.)

-
Great answer. –  David Schwartz Jun 30 '12 at 19:57
At least exact collisions do not solve the problem of requiring more memory on the work side than on the verifier side; finding exact collisions can be done with little memory, see Parallel Collision Search with Cryptanalytic Applications. I do not know what happens for partial collisions, but I suspect there are shortcuts. –  fgrieu Jun 30 '12 at 21:05
I already considered this idea. The main issue with this idea is that you store the output in shared memory, allowing an attacker to use a high number of workers on that memory. So it still fails 3. –  CodesInChaos Jul 1 '12 at 0:57
@CodeInChaos: Huh. It passes 3. To verify, you just compute the two hashes and see how close they are. You don't have to use hash operations that require lots of memory, so verification can be cheap. –  David Schwartz Jul 1 '12 at 1:34
@fgrieu: That's why he suggested Hamming distance. Matching specific bits reduces the memory needed. And exact matches make it too easy to use cryptographic shortcuts. You could also use the hash of the two hashes concatenated (if that's less than the proof of work target, then the PoW is accepted). –  David Schwartz Jul 1 '12 at 1:35
show 10 more comments