10 ms·

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

23 points by sean_pedersen 6y ago

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.

tarun_anand 6y ago
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.
tboyd47 6y ago
Very interesting idea. Drop me a line and let’s discuss: nelewel291@maksap.com
- SI_Rob 6y ago
  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.
- amakia 6y ago
  poyeta8130@majorsww.com
  - amakia 6y ago
    poyeta8130@majorsww.com
LinuxBender 6y ago
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 http://www.gabacho-net.jp/en/anti-spam/anti-spam-system.html [2] - http://www.uceprotect.net/en/index.php http://www.uceprotect.net/en/index.php
- tboyd47 6y ago
  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.
  - LinuxBender 6y ago
    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.
prower 6y ago
Don't SPF and DKIM already work towards making sure emails are sent from legitimate people?
mr-wendel 6y ago
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.
- sean_pedersen 6y ago
  Yes pass it down to the user by computing eMail PoW client side if that is a concern for your business...
sean_pedersen 6y ago
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.
- theamk 6y ago
  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.
  - sean_pedersen 6y ago
    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.
    - robjan 6y ago
      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.
    - theamk 6y ago
      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.
theamk 6y ago
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.
- throwaway9870 6y ago
  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.
  - _alex_ 6y ago
    if you're blocklisting/allowlisting addresses _anyway_, then spam isn't a problem. just block everything that's not on the allowlist
    - sean_pedersen 6y ago
      Than you will have many false positives.
kitkat_new 6y ago
because of environmental disaster
coldtea 6y ago
>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?
- toper-centage 6y ago
  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.
_alex_ 6y ago
Where's my password reset email? Hasn't come through yet because the email-miner is still searching for the right nonce
fanf2 6y ago
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 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.”
- sean_pedersen 6y ago
  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.
  - JoeAltmaier 6y ago
    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.
  - theamk 6y ago
    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.
SI_Rob 6y ago
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!
pjc50 6y ago
sigh refer to https://trog.qgl.org/20081217/the-why-your-anti-spam-idea-wont-work-checklist/ https://trog.qgl.org/20081217/the-why-your-anti-spam-idea-wo... In this case, proof-of-work is proof-of-waste.
iryanbell 6y ago
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.
60secz 6y ago
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-their-money/ https://www.zdnet.com/article/how-email-spammers-really-make...
jfengel 6y ago
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.
aaron695 6y ago
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.
djyaz1200 6y ago
@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.

sumtechguy 6y ago

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.

LinuxBender 6y ago
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.
- tboyd47 6y ago
  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.
  - LinuxBender 6y ago
    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.
    - sumtechguy 6y ago
      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.

sean_pedersen 6y ago
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!
sean_pedersen 6y ago
(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.