8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Thinking out loud, have you checked this work? people.cs.pitt.edu/~mehmud/docs/abliz09tourpuzzle.pdf‎ $\endgroup$
    – absinthe_minded
    Feb 14, 2014 at 3:32
  • $\begingroup$ 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). $\endgroup$
    – D.W.
    Feb 18, 2014 at 0:50
  • $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Feb 18, 2014 at 8:33
  • $\begingroup$ Equihash might fit the requirements. $\endgroup$
    – CodesInChaos
    May 28, 2016 at 21:01

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
15
  • $\begingroup$ Great answer. $\endgroup$
    – David Schwartz
    Jun 30, 2012 at 19:57
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Jun 30, 2012 at 21:05
  • $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Jul 1, 2012 at 0:57
  • $\begingroup$ @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. $\endgroup$
    – David Schwartz
    Jul 1, 2012 at 1:34
  • 1
    $\begingroup$ @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). $\endgroup$
    – David Schwartz
    Jul 1, 2012 at 1:35
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.