Proof-of-work

[themuffinking]

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 proof-of-work 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.

[Drostie]

Question: does this work need to be done by humans, or can it be done by computers?

(I'm just thinking, e.g., that if you're trying to avoid spambots sending you e-mails, then having an algorithm which a spambot can perform would, well, defeat the purpose and such.)

[bitwiseshiftleft]

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). Number-theoretical 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]

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" (pre-computed 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]

Borrowing a tactic from public-key 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. 256-bit 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.

[davean]

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]

256-bit 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.

[Yakk]

256-bit 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]

256-bit 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.

[Sartak]

256-bit 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:

...brute force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

[Rysto]

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 symmetric-key algorithms or assymetric(public) key algorithms? I might believe that about symmetric-key algorithms.

[EvanED]

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 symmetric-key algorithms or assymetric(public) key algorithms? I might believe that about symmetric-key algorithms.

He was clearly talking about symmetric-key algorithms. In the RSA factoring challenge, essentially a 640-bit key was broken a year and a half ago.

You can't brute force a 256-bit 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]

Was Schneier talking about symmetric-key algorithms or assymetric(public) key algorithms? I might believe that about symmetric-key algorithms.

Schneier was talking about a 256-bit 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 256-bit 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 256-bit 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.