[6845] in cryptography@c2.net mail archive
A non-parellelizable form of hashcash
daemon@ATHENA.MIT.EDU (Bram Cohen)
Sat Mar 25 17:49:31 2000
Date: Sat, 25 Mar 2000 14:19:00 -0800 (PST)
From: Bram Cohen <bram@gawth.com>
To: cryptography@c2.net
Message-ID: <Pine.LNX.4.10.10003251345300.9678-100000@ultra.gawth.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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
