Re: [freehaven-dev] Another distributed project!

[dmolnar <dmolnar@hcs.harvard.edu>]

On Sat, 19 Aug 2000, Roger Dingledine wrote:


> If we actually develop a timewasting system that works well, can we make
> it not just waste time but actually help solve some interesting problems?

Heh. I seem to recall you coming up with this idea during office hours
back in fall. As in "how do I know that this thing you want me to do
isn't helping you crack somebody else's key?"

Maybe something to look at is Markus Jakobsson's 
"Proofs of Work and Bread Pudding Protocols" paper, which
has some of the same speculations.

http://www.bell-labs.com/user/markusj/breadpudding.ps

in fact, they discuss this in terms of everyone's favourite
micropayment system, MicroMint! 

(distributed MicroMint cracking effort hidden as a bunch of 
proofs of work clandestinely smuggled into each and every server
on the Internet? POWs where the prover doesn't know what he's 
proving? Millions of clients unwittingly turning their cycles to
forgery and malefice, busy being exploited for 1/10 of a cent as
they download the latest Britney Spears album?
Dan Simmons, call your office. 

could it be? well, Jakobsson has another paper on "proving without
knowing" - where you don't want the prover to know the results of the
proof protocol. not quite the same thing. still, maybe there's a way to do
this in such a way that you have a proof of work but NO IDEA what you just
did to prove that you did enough work to have access?

at least for randomly self-reducible problems, this seems doable. if you
want to compute g^x mod p, but don't want to do it yourself, and don't
want anyone to know x, then you tell a client "here's g, here's x+r" where
r \in_R Z_p^* , and ask somebody else to compute g^-r, and then multiply
them your own self...there's a hash function based on discrete logs
due to Chaum, van Heijst, and Pfitzmann which may have this nice property)
(hey, there's that midterm problem from 6.857 again!) 

Have I mentioned yet that I think Markus Jakobsson's a genius?

-David