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

-
Thinking out loud, have you checked this work? people.cs.pitt.edu/~mehmud/docs/abliz09tourpuzzle.pdf‎ – absinthe Feb 14 '14 at 3:32
Two candidates come to mind. (1) Find an input to scrypt that makes the first 20 bits of its output all zeros. Verification is now pretty cheap. (2) Use timelock puzzles. They admit a very large ratio between the time to solve the puzzle vs the time to construct the puzzle (or to verify the solution). – D.W. Feb 18 '14 at 0:50
@D.W. 1) Scrypt with sufficient memory (say 1GB) use isn't cheap to verify. Scrypt is pretty much the baseline against which to compare a better scheme. 2) The only time lock puzzles I know are sequential, but don't need much memory. So you can solve many instances in parallel with many cheap cores. – CodesInChaos Feb 18 '14 at 8:33

$\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

I designed Cuckoo Cycle at https://github.com/tromp/cuckoo as the first trivially verifiable, scalable and time-memory-trade-off-hard proof-of-work system. It parallellizes reasonably well up to at least 12 CPU-threads, but is expected to saturate the memory due to random access latencies for some small multiple of that. A GPU has memory with tons of bandwidth but much worse random access latencies, so may not be able to compete. See the whitepaper for details.

-