[jewel]

People have suggested proof-of-work as a way to stop spam. Legitimate users wouldn't notice if their computer spent a few seconds generating a proof in the background as the email is being sent out. The only problem is that spammers have access to vast amounts of computing power in the form of zombie PCs.

The reason proof-of-work worked for bitcoin back when an army of zombie PCs could have legitimately controlled 51% of the network was that the rewards for a 51% attack were far less than just doing legitimate mining. I think that setting up a system similar to bitcoin won't work when there aren't the same financial incentives to keep the miners honest.

P.S. Isn't the PGP web of trust also a decentralized solution to Sybil attacks?

[david-given]

This has been done; it's possible to exploit the SMTP rules to force the client to do proof-of-work before the server accepts the email. What you do is reply to the client's first connection with a temporary failure; this forces the client to cache the message locally and resubmit. On the client's second connection, you accept the message.

It's called greylisting, and it works really well as a cheap and easy spam prevention mechanism. I wrote an implementation and used it for years as a first-line-of-defence; it let me use a crappy little 32MB ARM box as an SMTP server. (<plug> http://spey.sf.net </plug>)

[desdiv]

P.S. Isn't the PGP web of trust also a decentralized solution to Sybil attacks?

PGP web of trust requires a secure channel to broadcast the public keys, so it's not the type of P2P network that the Sybil attacks is applicable to.

[logicallee]

I didn't read the article but the issue with "a few seconds" to send a legitimate email is this: it's not actually "a few seconds" (as in, ten seconds to send an email, a hundred seconds to send ten emails, 1,000 seconds to send a hundred, 10,000 seconds - which is 2.7 hours - to send a thousand). That would be prohibitive. But it's actually a few seconds at the rate YOUR computing device can solve the problem. Sending from a desktop might be okay. But a laptop? An iPad? A smart phone? It is trivial to imagine cheap dedicated hardware (such as a beefy quad-core server as compared with a smart phone) that can do 50x the rate. And suddenly your "2.7 hours to send a thousand emails" is "2.7 hours to send 50,000 emails from one machine", 27 hours to send half a million, ten days to send ten million. With ten quad-core servers (instead of 1), ten days to send a hundred million. With a hundred quad-core servers, ten days to send a billion emails. (Or adjust the number of servers up if you get less than 50x the performance from a dedicated server.)

And this was assuming TEN SECONDS of your whole smart phone (or PC!) hanging to send an email. That seems rather unacceptable. And what if you have even 3 recipients? Do you have to wait 30 seconds?

So proof-of-work in this way is really a no-go. On the other hand, slowing down spam servers by trickling through the connection with them, saturating their number of active open connections, seems like it's a good way to limit the amount of spam coming from them, assuming you can be sure they're spam-servers. Better doing that at the mail server end than trying to put that work into the client.

--

Incidentally, this is the same reason you can't hash something with a small address space (such as social security number, of which there are one billion possible numbers (according to Google if you google the phrase "how many possible social security numbers are there".)

Say you don't want to send your SSN in the plain, you just want to store a hash so that you can verify it but can't recover it.

Well, this doesn't work. An idea you might have is to securely hash it with a long, random nonce so that nobody can use a precomputed lookup table. Well, if you want to be able to verify the number next time, you need to store the nonce. So you're storing the nonce (salt) and the hash, but not the number.

Okay. Now someone who wants to break your number can just compute the hash with every possible SSN, of which there are a billion. That's only 2^29 and change possibilities. A 4 Ghz computer does 4 billion (2^32) operations every second multiplied by the number of cores. It can easily do 16 times as many flop's per second as your total address space, so just multiply that by the number of FLOP's you need per hash to see how few seconds it takes to brute-force it back.

So, your next idea might be, well, we'll just make the hash take really long. Use a complicated hash that takes several seconds to compute.

This works, as long as nobody has a billion times as many "yourPC-seconds" as you do. The problem is they do. If you take a few minutes to do your hash, someone else might have a billion times as many "yourPC-minutes" to do theirs. Your PC is one puny computer not dedicated to the task. Theirs can be a few thousand PC's - or highly dedicated hardware - that does nothing but that hash.

So while in a practical sense, and at great inconvenience to you, this kind of proof of work might slightly slow the rate of attack -- by making you wait seconds to minutes to computer your hash -- in fact even for cryptographic hashes it often doesn't stop a search of the entire hash space.

The bitcoin network currently performs between three hundred million and four hundred million gigahashes (billion hashes) per second. That is 300 to 400 quadrillion hashes per second. By most estimates on about $300 million in hardware.

And you're not asking for it to stop a brute-force search. You're asking it to be so inconvenient they won't bother to brute-force an address space of 1 possibility. (That even though there is only one possibility, they just won't bother to compute it; but your computer will).

I think the idea is a non-starter.