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

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.”

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.

>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?

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.

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

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.

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 significant 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!

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

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.