It turns out I don't need an answer to the question I asked earlier - a
special case can be used.
The problem is to find a form of hashcash which can't be paralellized.
Alice wants to force Bob to do w 'units' of computation, in such a way
that he can't benefit from parallel machines and she can verify he
actually did the work without redoing it all herself.
There is a standard large prime p which it's hard to compute square roots
modulo which Alice and Bob have agreed on beforehand.
Alice picks some random number s, and tells Bob
s + 1/s (mod p)
Bob can't compute s because that would involve taking a square root. She
then challenges him to compute f(w) where
f(n+1) = (f(n))^2 - 2 (mod p)
and
f(0) = s + 1/s (mod p)
(Ten points to anyone who can figure out where this is headed without
reading the rest.)
Alice is capable of computing f(w) quickly using the formula
f(n) = s^(2^n) + s^(-(2^n)) (mod p)
Which can be easily proven by induction.
Not only does this technique prevent paralellization, but it sets the
amount of work Bob has to do very precisely.
A surprisingly simple result.
-Bram Cohen
