Proofofwork
Moderators: phlip, Moderators General, Prelates

 Posts: 52
 Joined: Sat Mar 10, 2007 4:42 am UTC
Proofofwork
This may or may not belong in Computer Science, but everything in CS belongs in Coding and most questions in Coding belong here, so... yeah. (Let's compromise and put it in Coding  Hermaj.)
Question: I want to make it difficult for people to send me letters (or email). I want proof that whoever is sending me something has done some finite amount of work  hence, I need a proofofwork system. How can I prove that someone has done the work, and not cheated off the guy next to them?
Without stealing any ideas from the internet, come up with such a system. The protocol can be interactive or not, whatever.
Example:
Alice wants to send Bob an email, and Bob wants to make sure Alice did x amount of work. So here's what happens:
1. Alice sticks her email address next to Bob's and makes them all one word.
2. Alice then has to use something called a hash function on the result of step 1  a hash function takes something like alice@alice.combob@bob.com and turns it in to something like 199132ffe5fbbe3d135d79edd0a4bfd01dfc17fa, and it's (hopefully) extremely impossible to reverse the operation.
3. If the result of step 2 doesn't start with, say, 00000, then Alice sticks a 0 on to the end of the result from step 1 and does a new hash: alice@alice.combob@bob.com0 > f154b7acf5641ab027720751eb164b87a97f1291
4. Alice keeps incrementing that number at the end of alice@alice.combob@bob.com until she gets a hash that begins with 00000.
5. Alice sends her email, along with a line that says alice@alice.combob@bob.com and that number at the end.
6. Bob can now check that the hash begins with 00000, and because Alice couldn't have found that hash without trying a whole bunch of other hashes, he knows she has done some work and accepts the email.
Question: I want to make it difficult for people to send me letters (or email). I want proof that whoever is sending me something has done some finite amount of work  hence, I need a proofofwork system. How can I prove that someone has done the work, and not cheated off the guy next to them?
Without stealing any ideas from the internet, come up with such a system. The protocol can be interactive or not, whatever.
Example:
Alice wants to send Bob an email, and Bob wants to make sure Alice did x amount of work. So here's what happens:
1. Alice sticks her email address next to Bob's and makes them all one word.
2. Alice then has to use something called a hash function on the result of step 1  a hash function takes something like alice@alice.combob@bob.com and turns it in to something like 199132ffe5fbbe3d135d79edd0a4bfd01dfc17fa, and it's (hopefully) extremely impossible to reverse the operation.
3. If the result of step 2 doesn't start with, say, 00000, then Alice sticks a 0 on to the end of the result from step 1 and does a new hash: alice@alice.combob@bob.com0 > f154b7acf5641ab027720751eb164b87a97f1291
4. Alice keeps incrementing that number at the end of alice@alice.combob@bob.com until she gets a hash that begins with 00000.
5. Alice sends her email, along with a line that says alice@alice.combob@bob.com and that number at the end.
6. Bob can now check that the hash begins with 00000, and because Alice couldn't have found that hash without trying a whole bunch of other hashes, he knows she has done some work and accepts the email.
 bitwiseshiftleft
 Posts: 295
 Joined: Tue Jan 09, 2007 9:07 am UTC
 Location: Stanford
 Contact:
There are already protocols to do this, and they usually look something like what you suggested. For instance, consider Hash Cash or Penny Black. Generally, the schemes look something like this:
0) If the sender is on the receiver's white list, he does nothing and the message goes through.
1) The sender hashes some function of the message, which hopefully is unique per message won't be mangled by the gateways.
2) The sender computes some function of the hash which is difficult to compute but easy to verify.
The function you proposed (x such that H(x  h) begins with 0000...) is the most obvious one, but it has two minor disadvantages. One is that the scheme is probabilistic, and might on occasion keep people waiting a while. The other is that some computers have hash accelerators (and in general, hashing is easily computed in hardware) so that some spammers will have to do disproportionately little work. This can be avoided by using functions that require significant amounts of memory to compute (and so are hard to accelerate in hardware). Numbertheoretical functions are common here.
Ultimately, though, the problem with things like Hash Cash is that they inconvenience regular users more than spammers. Spammers are probably sending their crap from a network of compromised Windows boxes, so they don't care how much CPU time they burn. Regular users get annoyed if their CPU spins when sending emails.
An occasional variant is to require a CAPTCHA. Unfortunately, CAPTCHAs piss legitimate users even more than proofs of work, and are vulnerable to the Porn Redirect Attack.
0) If the sender is on the receiver's white list, he does nothing and the message goes through.
1) The sender hashes some function of the message, which hopefully is unique per message won't be mangled by the gateways.
2) The sender computes some function of the hash which is difficult to compute but easy to verify.
The function you proposed (x such that H(x  h) begins with 0000...) is the most obvious one, but it has two minor disadvantages. One is that the scheme is probabilistic, and might on occasion keep people waiting a while. The other is that some computers have hash accelerators (and in general, hashing is easily computed in hardware) so that some spammers will have to do disproportionately little work. This can be avoided by using functions that require significant amounts of memory to compute (and so are hard to accelerate in hardware). Numbertheoretical functions are common here.
Ultimately, though, the problem with things like Hash Cash is that they inconvenience regular users more than spammers. Spammers are probably sending their crap from a network of compromised Windows boxes, so they don't care how much CPU time they burn. Regular users get annoyed if their CPU spins when sending emails.
An occasional variant is to require a CAPTCHA. Unfortunately, CAPTCHAs piss legitimate users even more than proofs of work, and are vulnerable to the Porn Redirect Attack.
 Yakk
 Poster with most posts but no title.
 Posts: 11025
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
The probablistic problem is a problem: ideally you want a problem that has an average time that is close to the maximium time it can take.
But other than that, it is pretty good. Someone with a mailing list would either have to do the work whenever someone signed up, and could cache it afterwards: or they could require people signing up to include a "SASE" (precomputed envelope) as it where.
In fact, the system should be transitive: if you send an email to bob, bob should be able to send an email to you at no cost: reply should be free. That is as simple as alphabetically sorting the two email addresses before doing your mojo.
But other than that, it is pretty good. Someone with a mailing list would either have to do the work whenever someone signed up, and could cache it afterwards: or they could require people signing up to include a "SASE" (precomputed envelope) as it where.
In fact, the system should be transitive: if you send an email to bob, bob should be able to send an email to you at no cost: reply should be free. That is as simple as alphabetically sorting the two email addresses before doing your mojo.
 entropomorphic
 Posts: 23
 Joined: Mon Apr 02, 2007 2:51 pm UTC
Borrowing a tactic from publickey crypto, the sender (Alice) could factorize some largeish number supplied to them by the receiver(Bob). Factorizing large prime products is not impossible, only very hard. In this case, you only need to pick a key size that requires the desired amount of work to factorize. 256bit keys are generally breakable on desktop computers in a couple hours, so you can use that as a starting point for judging how much work you really want the sender to do.
Keys are easy to generate, but hard to break, so the work on Bob's part is minimal. Bob only needs to publish a new key on a regular schedule that is moderately longer than the expected time it would take to do the work. Alice would wait until a new key is published, break it, and send her answer to Bob before that key is invalidated and a new problem is created.
Keys are easy to generate, but hard to break, so the work on Bob's part is minimal. Bob only needs to publish a new key on a regular schedule that is moderately longer than the expected time it would take to do the work. Alice would wait until a new key is published, break it, and send her answer to Bob before that key is invalidated and a new problem is created.
Re: Proofofwork
themuffinking wrote:This may or may not belong in Computer Science, but everything in CS belongs in Coding and most questions in Coding belong here, so... yeah.
No, coding is the application of a subset of the results of computer science.
Also, you might want to look into a related topic called "zero knowlege proofs".
 necroforest
 Posts: 195
 Joined: Tue Apr 10, 2007 3:46 pm UTC
 Contact:
 Yakk
 Poster with most posts but no title.
 Posts: 11025
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
necroforest wrote:entropomorphic wrote:256bit keys are generally breakable on desktop computers in a couple hours
Is that true? I thought the best known factoring algorithm ran in O(2^n) time. Even if you could do a billion steps a second, that algorithm would still take 2^226 seconds to run. Maybe I'm wrong.
You are assuming constants. You can't assume an O(2^n) algorithm will take at least 2^n instructions.
In addition, we have faster than 2^n algorithms.
One of the best ones out there is:
O( e^(64/9b^(1/3)*ln(b)^(2/3)))
(GNFS)
 necroforest
 Posts: 195
 Joined: Tue Apr 10, 2007 3:46 pm UTC
 Contact:
Yakk wrote:necroforest wrote:entropomorphic wrote:256bit keys are generally breakable on desktop computers in a couple hours
Is that true? I thought the best known factoring algorithm ran in O(2^n) time. Even if you could do a billion steps a second, that algorithm would still take 2^226 seconds to run. Maybe I'm wrong.
You are assuming constants. You can't assume an O(2^n) algorithm will take at least 2^n instructions.
In addition, we have faster than 2^n algorithms.
One of the best ones out there is:
O( e^(64/9b^(1/3)*ln(b)^(2/3)))
(GNFS)
It would take quite a small constant to make 2^256 tractable But your second point answered my question.
entropomorphic wrote:256bit keys are generally breakable on desktop computers in a couple hours
See http://www.everything2.com/index.pl?nod ... ptanalysis which quotes (who else but) Bruce Schneier:
Bruce Schneier wrote: ...brute force attacks against 256bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
Wikipedia:
Was Schneier talking about symmetrickey algorithms or assymetric(public) key algorithms? I might believe that about symmetrickey algorithms.
Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys.
Was Schneier talking about symmetrickey algorithms or assymetric(public) key algorithms? I might believe that about symmetrickey algorithms.
Rysto wrote:Wikipedia:Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys.
Was Schneier talking about symmetrickey algorithms or assymetric(public) key algorithms? I might believe that about symmetrickey algorithms.
He was clearly talking about symmetrickey algorithms. In the RSA factoring challenge, essentially a 640bit key was broken a year and a half ago.
You can't brute force a 256bit key; this is what the Schneier quote is talking about. But you don't need to brute force public keys, you just have to factor them.
 bitwiseshiftleft
 Posts: 295
 Joined: Tue Jan 09, 2007 9:07 am UTC
 Location: Stanford
 Contact:
Rysto wrote:Was Schneier talking about symmetrickey algorithms or assymetric(public) key algorithms? I might believe that about symmetrickey algorithms.
Schneier was talking about a 256bit brute force attack, that is, attempting to break any type of code whatsoever by trying 2^256 possibilities. It is not possible to do this with a high chance of success because, according to thermodynamics, there is not enough energy in the galaxy to do 2^256 computations at the temperature of the cosmic microwave background. Of course, you might always get lucky and guess it on the first try.
A 256bit RSA key can be broken more efficiently than by trying 2^256 possible factors. In fact, the most obvious brute force attack (trial division) factors it in at most 2^128 tries (still not possible with any technology likely to be built by humans in the next century). But there are better ways, like the Quadratic Sieve (which tries to find square roots of 1) or the faster Number Field Sieve.
Schneier's claim doesn't apply to any particular 256bit symmetric cipher (since the cipher might be weak), but rather to an ideal "secure" symmetric cipher, for which there is no faster way to break it than brute force. There are plenty of ciphers for which no known attack is faster than brute force, but nobody knows how to prove that there aren't any.
Who is online
Users browsing this forum: Exabot [Bot] and 5 guests