Ask HN: Why isn't email spam solved using Proof of Work yet? | Hacker News Reader

Ask HN: Why isn't email spam solved using Proof of Work yet?

23 pointssean_pedersen54 comments

Why not solve spam emails by letting senders work on some cryptographic puzzle (e.g. Proof of Work) that recipients can verify. This would prohibit spammers from sending massive amounts of email, since the required proof of work would scale linearly with the number of recipients.

For example let the sender search for a hash that must satisfy following condition: hash(recipient-email-address+message-content+nonce) % 42 == 0

If the hash does not match this condition, proof of work is missing and the email likely spam.

Another parameter could be the amount of work done by choosing different hash functions or hash functions that have parameters that tweak their run time.

View on HN

This question was answered in 2004 by the paper “proof of work proves not to work” https://www.cl.cam.ac.uk/~rnc1/proofwork.pdf

Abstract: ”A frequently proposed method of reducing unsolicited bulk email (“spam”) is for senders to pay for each email they send. Proof-of-work schemes avoid charging real money by requiring senders to demonstrate that they have expended processing time in solving a cryptographic puzzle. We attempt to determine how difficult that puzzle should be so as to be effective in preventing spam. We analyse this both from an economic perspective, “how can we stop it being cost-effective to send spam”, and from a security perspective, “spammers can access insecure end-user machines and will steal processing cycles to solve puzzles”. Both analyses lead to similar values of puzzle difficulty. Unfortunately, real-world data from a large ISP shows that these difficulty levels would mean that significant numbers of senders of legitimate email would be unable to continue their current levels of activity. We conclude that proof-of-work will not be a solution to the problem of spam.”

Thanks for the reference. But this misses out on another important tool already in use against spamming: White lists.

Yes, in theory PoW makes mass mailing very expensive and thus directly hurts spammers that are not on the common anti-spam white lists. Organizations that need to mass mail users for legitimate reasons are however most likely already on anti-spam white lists and thus need not to do a very hard PoW hash or none at all as they are already proven to not be spamming.

So this paper's conclusion is not the real deal.

I imagine some inbound email could be whitelisted automatically, from some authentication tech. If I sign up for mailings, some app (email? browser) can give a one-use cert or id that can be passed back in email headers. If that company sells my email, I can block further emails from that source. It doesn't seem hard.

If you can get people to use centralized anti-spam white lists, you do not need proof of work at all.

But having such list will make email effectively centrally controlled. I would hope we never end up in this situation. The current system is bad, but making it centralized is even worse - just read what happens to businesses when Facebook/google bans them.

I don't think it needs to be centralized. Why not have a white list per account? When you sign up for a list or service you can add certain domains to you personal list.

Of course some of the larger services may offer a default white list for common domains.

So every time I type my email somewhere, I also have to go to my mail provider and pre-emptively whitelist the sender? This does not sound like a very good UX.

I suppose you can have a special system where you have a browser plugin which automatically generates some sort of subscription token and pastes it alongside email into subscription form.. but this will need cooperation from every mail-sending app, and will not handle non-web uses cases at all...

I use Hey.com which allows me to screen first time senders [1] and it works really well. This is in combination to a spam filter.

[1] https://hey.com/features/the-screener/

OK after giving this idea a little bit more thought. This is the deal: PoW for eMail needs to come with a parameter that controls the amount of work (computation) done to find the PoW hash. This allows senders to choose on a continuous scale how important it is for them to proof they are not mass mailing spammers.

This in turn allows small organizations / private mail servers that are not on common anti-spam white lists to proof their good intentions in a decentralized fashion.

PoW makes mass mailing very expensive and thus directly hurts spammers that are not on the common anti-spam white lists. Organizations that need to mass mail users for legitimate reasons are most likely already on anti-spam white lists and thus need not to do a very hard PoW hash as they are already proven to not be spamming.

What do you mean by “common anti-spam white lists”? AFAIK there are none. There are common black lists. And the only whitelists are per-user, maybe per-org for work email.

Wait what? I thought major players like GMail, Microsoft etc. have some kinda "monopoly" on eMail because they are gatekeeping by using a strict white list.

It's the other way around. In general Gmail, Microsoft etc are whitelisted by other people because they are trusted to deal with spammers using their platforms. Whether they are actually more trustworthy is another matter.

There is no such monopoly - just look at your inbox, and check the headers of the emails you see. (I just did checked a random non-spam mailing, and it was send by cmail9.com - which is pretty suspicious domain if you ask me.. and yet here is it in my inbox)

Sending emails is hard because there is no central authority. Instead, each provider checks if the sender does some “best practices”. And the exact details vary - so if you got it working once with gmail, then there is no guarantee it will work next time with live.com. So you got to do them all.

For example, I have heard an unconfirmed rumor that one of the major provider started penalizing email sender machines without IPv6 address. If I had to maintain a mail sender, this’d mean have to upgrade my architecture to use IPv6 ASAP, which is non trivial at all. This is why most people outsource email sending.

I did not mean monopoly in the literal sense, just used it to express my feeling that a lot ends up flagged as spam that is not from these major corps servers.

This is just a feeling,

Do you know how to read email headers? Are you subscribed to mailing lists? If yes, go to your inbox and check a few messages for the sender. You would be surprised at how many senders are there.

For transactional emails / regular mailing lists, I estimate that you just need like 0.25 FTE working on email, maybe even less. While this is not something everyone can do, there are tens of thousands email senders out there.

This is probably the solution to getting something like this off the ground. If the minimum PoW is zero (so not participating) and a >0 PoW is seen as a positive flag in spam filters. However I guess that most Spammers don't even setup DKIM etc. or fail it. So whoever would implement the PoW to send legitimate emails is probably doing other stuff already that get their emails flagged as legitimate.

>Why not solve spam emails by letting senders work on some cryptographic puzzle (e.g. Proof of Work) that recipients can verify. This would prohibit spammers from sending massive amounts of email, since the required proof of work would scale linearly with the number of recipients.

Because:

(a) that would then have to be applied to every email (not just spam), which means every email infrastructure that needs to be aware of it (e.g. not transparent proxies etc), would need to be updated to be made aware of it and enforce it

(b) if applied to every email, it would increase global energy consumption/waste

(c) if there are "whitelisted" (which can bypass "proof of work") emails, then who would serve as the authority for those?

Regarding B), I thought of thst right away. This would only be acceptable if, by killing some spam, the total amount of computing done and energy consumption goes down.

Because this completely breaks mailing lists.

For example, I am subscribed to my town’s unofficial mailing list, which has tens of thousands of people, dozens of messages per day, and no budget. The mailing lists are also very popular with open source - LKML being most famous example.

And the worst thing, the spammers will not be affected as much. They’d just rent infected windows machines and do the calculations there.

It doesn't have to be a binary check. It could just be another signal that the e-mail receiving system can use to make a determination. Typically, one adds mailing list addresses to an allow list anyways.

if you're blocklisting/allowlisting addresses _anyway_, then spam isn't a problem. just block everything that's not on the allowlist

Than you will have many false positives.

This is a good idea, but there are already puzzles they have to solve (by design) that are disabled. This will sound silly, but FCrDNS was accepted almost unanimously in 2013 when a draft IETF document was created, but never ratified, that caused all the ISP's to add generic reverse DNS for everything. This turned every home PC into a malware magnet over night. Fast forwards a little bit and a gentleman in Japan created a concept to utilize this called "S25R" [1] which is a simple regex methodology to block generic devices from sending email. Problem is, very few people implemented it and instead people opted for throwing a lot of money and anti-spam companies. Multi-billion dollar businesses were created and people like money! So anyway, the mechanism is there already to stop most of the spam, but people choose to not use it. The way it can work is that using 7 or a few more simple regex rules, almost all generic devices are blocked from sending email. This limits the sending devices to those that control forward-reverse DNS. Some anti-spam companies make use of this, but only for flagging things as spam. This method when used correctly makes RBL/RSL databases effective again and forces spammers to rent servers. If a VPS or server rental provider allows abuse, their AS number gets blocked. [2]

In short, if people won't use the simple mechanisms that already exist, they probably won't add a new mechanism or make use of it. One argument against the existing method is friction or false positives, but really it just forces people to update DNS correctly.

To add a math puzzle to email servers, you would also need to update every MTA and email server to understand this concept. All the major providers, all MTA's, etc... All the smtp libraries in all the programming languages would also need to understand this concept. java, golang, python, php, perl, C, C++, C#, etc...

[1] - http://www.gabacho-net.jp/en/anti-spam/anti-spam-system.html

[2] - http://www.uceprotect.net/en/index.php

Sounds like the previous ideas were all flawed, and the trend (which is all that it is— a trend) towards internet centralization stalled progress after that.

Everything has flaws, but this was more about friction and marketing. People like the least path of resistance or friction and buying an anti-spam service was easiest so it won. The methods I described have some friction and require people to set things up correctly. Its a trade-off of human cost vs outsourcing cost and outsourcing often wins.

Yeah, but tech is not a zero-sum game, and the path of history is not linear. Email is becoming a pay to play system where you’re spam if you’re not one the approved senders, and this seems like an elegant idea to correct that.

It is an interesting idea. I am looking forward to how it plays out. I think the first challenge will be getting adoption from MTA's, smtp libraries and major email providers. This can't be done in a silo (server only) because smtp takes two to tango. Both the sender and the receiver have to implement this concept to utilize it. There will for sure be a handful of spammers that can't get their malware updated right away so you would at least have a window of less spam.

Even proof of work has a flaw. It underestimates some of the drive of these people to make make a few bucks. How much would say 200 raspberry PI's cost to network up? For proof of work to 'work' you need to get past the cost they would make on it. All you are doing is slowing them down which they can make up in volume of cheap devices. It does not 'solve' it. I have seen them setup rooms of low end Android devices to do things. This is not out of the realm of possibility.

To add to this, you don't need any raspi's. Most spam today comes from malware running on PC's not owned by the spammer. All they need is a software library that does this math and 100% of the CPU cost is on the malware victim. The software library would have to already exist and be available to everyone or this concept would never be adopted, which means that the spammer gets this for free. They just have to plug the library into their malware. The only cost that would be forced onto spammers would be if the PoW used signed individual keys that could be revoked if abused.

Cheap, but not free. If it means that a spammer can send 100 emails before marked as spam instead of 10,000 or 100,000, it changes the landscape for sure.

If the spammers implement PoW, I am not seeing how the numbers change. Instead of seeing for example 1 million infected PC's and VM's sending email, you would see 1 million infected PC's and VM's doing PoW.

Ill give you an example of how this played out in the past. Up until about a decade ago, if I enforced TLS on my mail servers, about 80% of the malware bots could not connect as their libraries did not support TLS. As more smtp libraries added support for TLS, the malware was updated and now enforcing TLS only limits a smalll subset of spammers. There was no added cost to the spammer. So yes for a while, PoW will create a window of time where there is less spam for those that adopt this. The spammers will eventually catch up. Nowadays malware frameworks are much easier to update.

The diff for a spammer of 100 boxes that run their bot vs 1000 makes no difference to them. The cost is negligible. Even if you make the process slower. They can just scale out or wait it out. If it takes 1 hour vs 2 hours to do their payload there is no real difference to them. They have also already built in the filtering as a % that fails. They are looking for less than 1-2% success which is all they need. The frameworks are no longer some simple script hacked up in VBS. They are packages they can buy from other spammers or rent the bot net with the proper libs built in.

Not every server needs to understand it. Only the ones wanting to participate. If you choose to filter by PoW and a server does not provide PoW, you will still receive all of its emails just flagged as spam. So email PoW roll out can work iteratively.

True, but then a spammer need only implement PoW in their malware framework. Most spam today comes from malware infected PC's and rented VM's. CPU and network resources are free. The biggest challenge for the spammer will be getting updated malware deployed to support PoW, assuming their existing malware can't update itself via a command and control server. Unless you are selling crypto keys that are used in this PoW that can be revoked when abused, the malware need only know how to solve the puzzle.

If they add PoW to their malware, it will slow them down or even alert users / admins because of the high CPU usage it will cause.

If all the spam came from a tiny set of hosts this would for sure be true. This for sure used to be the case. These days spam comes from millions of infected PC's and VM's. You will almost never see more than a few dozen connections come from the same host in a day, with exception to rented VM's because they have more resources. Spammers can control how much is sent from which classes of infected hosts. This also applies to the logic in their malware for things like brute forcing ssh/https/mysql connections. The victim rarely notice the malware any more, as it runs at lower CPU priority. Some of the malware is even polite enough to use a single core. Even telling ISP's and VPS providers a host is infected can take weeks or months to get someone to look into it.

Consider that there are a lot of highly automated email senders that this will never fly for. From small websites/businesses to large (and especially gargantuan!) are more and more likely to contract out email delivery to a specialized provider (e.g. SendGrid, Mandrill/Mailchimp, etc).

Even if you focus on transactional emails only (e.g. signup/order verification, password resets, billing notifications, etc) where users are implicitly or explicitly opted in... the amount of mail volume involved is massive.

Given that this is a pure overhead charge, you can be sure that email providers are going to pass the cost on to the senders (e.g. whoever owns the relationship with the end-user). The larger that organization is the more likely they'll build that into the cost of the product and pass it down to the user.

SPF/DKIM/etc are a huge help. Even when spammers use it correctly it provides reliable attribution for establishing (or rather, destroying) reputation for the domain involved. I would love to see something more and think your intuition is good: an increase to the cost of send email is more likely to weed out illegitimate/unwanted messages.

Yes pass it down to the user by computing eMail PoW client side if that is a concern for your business...

Where's my password reset email? Hasn't come through yet because the email-miner is still searching for the right nonce

I think the answer is that machine learning solved the problem better. My GMail spam folder used to be in the tens of thousands from the last 30 days. Now it's in the low hundreds. (Low enough to locate the occasional false positive.)

I can't tell if Google is just not telling me about the vast ocean that the filter considers obvious, or if it's just gotten so effective that the spammers gave up. Whatever it is, it's working. I dunno if other email providers are similarly effective, but the tech exists if they want it.

Now, there's still web forms, which don't have the vast spraying power of SMTP, and also don't have the same kind of access to data to drive email spam filters. They usually try to de-automate the process with CAPTCHAs, which are also kind of a proof-of-work system (a "work" that's supposed to be cheap for humans and expensive for computers).

Maybe you could install a proof-of-work based system there? Not being email, it sidesteps some of the issues on the form reply that SI_Rob reposted.

Proof of burn is more efficient and harder to game. Emails are already being send from botnets, which are already used for mining.

Spam will exist as long as it is profitable. If inboxes only show email which has paid a very small cost (like .001 cents), it would quickly make spam unaffordable.

> Anecdotal reports place the retail price of spam delivery at a bit under $80 per million [22]. This cost is an order of magnitude less than what legitimate commercial mailers charge, but is still a signiﬁcant overhead; sending 350M e-mails would cost more than $25,000. Indeed, given the net revenues we estimate, retail spam delivery would only make sense if it were 20 times cheaper still.

https://www.zdnet.com/article/how-email-spammers-really-make...

sigh refer to https://trog.qgl.org/20081217/the-why-your-anti-spam-idea-wo...

In this case, proof-of-work is proof-of-waste.

I did a sort of PoS proof of concept for spam mitigation. The idea was a small refundable fee would be defined at an inbox-level on a distributed ledger. If a recipient flagged content as offensive or spam, the gas fee required to transmit the message was retained, otherwise, it was returned, such that legitimate mail was free to send and spam was expensive.

While the fees were outstanding prior to receipt (or rejected by the recipient), they could participate in interest-earning liquidity pools to fund global efforts, like planting trees.

@Sean_Pedersen, I've been working in the messaging field for years and I share your frustration this hasn't been solved. I'm not a big Twitter user but followed you (@chiefexcitement) on there just now, if you DM me I'd be glad to setup a time to discuss.

guess this old girl needs another walk around her paddock:

  Your post advocates a

  (x) technical ( ) legislative ( ) market-based ( ) vigilante

  approach to fighting spam. Your idea will not work. Here is why it won't work. (One or more of the following may apply to your particular idea, and it may have other flaws which used to vary from state to state before a bad federal law was passed.)

  ( ) Spammers can easily use it to harvest email addresses
  (x) Mailing lists and other legitimate email uses would be affected
  ( ) No one will be able to find the guy or collect the money
  ( ) It is defenseless against brute force attacks
  (x) It will stop spam for two weeks and then we'll be stuck with it
  (x) Users of email will not put up with it
  (x) Microsoft will not put up with it
  ( ) The police will not put up with it
  (x) Requires too much cooperation from spammers
  (x) Requires immediate total cooperation from everybody at once
  (x) Many email users cannot afford to lose business or alienate potential employers
  ( ) Spammers don't care about invalid addresses in their lists
  ( ) Anyone could anonymously destroy anyone else's career or business

  Specifically, your plan fails to account for

  ( ) Laws expressly prohibiting it
  ( ) Lack of centrally controlling authority for email
  ( ) Open relays in foreign countries
  ( ) Ease of searching tiny alphanumeric address space of all email addresses
  ( ) Asshats
  ( ) Jurisdictional problems
  ( ) Unpopularity of weird new taxes
  (x) Public reluctance to accept weird new forms of money
  ( ) Huge existing software investment in SMTP
  ( ) Susceptibility of protocols other than SMTP to attack
  ( ) Willingness of users to install OS patches received by email
  (x) Armies of worm riddled broadband-connected Windows boxes
  ( ) Eternal arms race involved in all filtering approaches
  ( ) Extreme profitability of spam
  ( ) Joe jobs and/or identity theft
  ( ) Technically illiterate politicians
  (x) Extreme stupidity on the part of people who do business with spammers
  ( ) Dishonesty on the part of spammers themselves
  ( ) Bandwidth costs that are unaffected by client filtering
  (x) Outlook

  and the following philosophical objections may also apply:

  (x) Ideas similar to yours are easy to come up with, yet none have ever been shown practical (specifically, HashCash)
  ( ) Any scheme based on opt-out is unacceptable
  ( ) SMTP headers should not be the subject of legislation
  ( ) Blacklists suck
  ( ) Whitelists suck
  ( ) We should be able to talk about Viagra without being censored
  ( ) Countermeasures should not involve wire fraud or credit card fraud
  ( ) Countermeasures should not involve sabotage of public networks
  (x) Countermeasures must work if phased in gradually
  (x) Sending email should be free
  ( ) Why should we have to trust you and your servers?
  ( ) Incompatiblity with open source or open source licenses
  ( ) Feel-good measures do nothing to solve the problem
  ( ) Temporary/one-time email addresses are cumbersome
  ( ) I don't want the government reading my email
  ( ) Killing them that way is not slow and painful enough

  Furthermore, this is what I think about you:

  (x) Sorry dude, but I don't think it would work.
  ( ) This is a stupid idea, and you're a stupid person for suggesting it.
  ( ) Nice try, assh0le! I'm going to find out where you live and burn your house down!

Cool template! I just think you ticked too much off.

This is my take: Your post advocates a

  (x) technical ( ) legislative ( ) market-based ( ) vigilante

  approach to fighting spam. Your idea will not work. Here is why it won't work. (One or more of the following may apply to your particular idea, and it may have other flaws which used to vary from state to state before a bad federal law was passed.)

  ( ) Spammers can easily use it to harvest email addresses
  (x) Mailing lists and other legitimate email uses would be affected
  ( ) No one will be able to find the guy or collect the money
  ( ) It is defenseless against brute force attacks
  ( ) It will stop spam for two weeks and then we'll be stuck with it
  ( ) Users of email will not put up with it
  ( ) Microsoft will not put up with it
  ( ) The police will not put up with it
  ( ) Requires too much cooperation from spammers
  ( ) Requires immediate total cooperation from everybody at once
  ( ) Many email users cannot afford to lose business or alienate potential employers
  ( ) Spammers don't care about invalid addresses in their lists
  ( ) Anyone could anonymously destroy anyone else's career or business

  Specifically, your plan fails to account for

  ( ) Laws expressly prohibiting it
  ( ) Lack of centrally controlling authority for email
  ( ) Open relays in foreign countries
  ( ) Ease of searching tiny alphanumeric address space of all email addresses
  ( ) Asshats
  ( ) Jurisdictional problems
  ( ) Unpopularity of weird new taxes
  ( ) Public reluctance to accept weird new forms of money
  ( ) Huge existing software investment in SMTP
  ( ) Susceptibility of protocols other than SMTP to attack
  ( ) Willingness of users to install OS patches received by email
  (x) Armies of worm riddled broadband-connected Windows boxes
  ( ) Eternal arms race involved in all filtering approaches
  ( ) Extreme profitability of spam
  ( ) Joe jobs and/or identity theft
  ( ) Technically illiterate politicians
  (x) Extreme stupidity on the part of people who do business with spammers
  ( ) Dishonesty on the part of spammers themselves
  ( ) Bandwidth costs that are unaffected by client filtering
  ( ) Outlook

  and the following philosophical objections may also apply:

  (x) Ideas similar to yours are easy to come up with, yet none have ever been shown practical (specifically, HashCash)
  ( ) Any scheme based on opt-out is unacceptable
  ( ) SMTP headers should not be the subject of legislation
  ( ) Blacklists suck
  ( ) Whitelists suck
  ( ) We should be able to talk about Viagra without being censored
  ( ) Countermeasures should not involve wire fraud or credit card fraud
  ( ) Countermeasures should not involve sabotage of public networks
  (x) Countermeasures must work if phased in gradually
  (x) Sending email should be free
  ( ) Why should we have to trust you and your servers?
  ( ) Incompatiblity with open source or open source licenses
  ( ) Feel-good measures do nothing to solve the problem
  ( ) Temporary/one-time email addresses are cumbersome
  ( ) I don't want the government reading my email
  ( ) Killing them that way is not slow and painful enough

  Furthermore, this is what I think about you:

  (x) Sorry dude, but I don't think it would work.
  ( ) This is a stupid idea, and you're a stupid person for suggesting it.
  ( ) Nice try, assh0le! I'm going to find out where you live and burn your house down!

  (x) It will stop spam for two weeks and then we'll be stuck with it

PoW hardness can be controlled with a parameter.

  (x) Users of email will not put up with it

It is optional (no one is forced to use it).

  (x) Microsoft will not put up with it

Microsoft will put up eventually if the majority uses it.

  (x) Public reluctance to accept weird new forms of money

There is no new form of money involved.

Don't SPF and DKIM already work towards making sure emails are sent from legitimate people?

Will the genuine mass mailers also have to do it?

How will doing the work reduce spam? There is already a cost of sending spam in terms of infra.

I think spam is more a trust issue.

because of environmental disaster

Very interesting idea. Drop me a line and let’s discuss: nelewel291@maksap.com

You might want to google "hashcash," for a little history on PoW and email. It's an idea that goes back before Bitcoin and was one of its influences.

poyeta8130@majorsww.com

PoW was looked at well over a decade ago by Bill Gates personally (and obviously others)

It's never been adequately explained why no one implemented it.

It might be the obvious, incremental gains from filtering spam have kept users happy enough. No one company wants to take the first hit of educating users and the incompatibility with other systems.

It might complex processes like the engineers asked to implement it think users give a shit about mailing lists (maybe they did in 2004 when Gates told Davos he'd kill spam). Maybe marketing drones on about big business in all the meetings, crushing a good idea. Or maybe Microsoft went for micro payments over PoW, not realising micro payments was in itself an impossible dream.

Ask Bill next AMA on Reddit.

Reply on news.ycombinator.com