Well, the same problems apply to postal mail, IM and phone calls, etc.
I think the two properties which a comms method needs to have a spam problem are:
1) it is inexpensive to communicate with someone
2) it is has a fixed, human-memorable "address" which can be communicated out of band (business card, verbally etc)
Once you have these two things, such lists of fixed address can accumulate and be circulated - and they can be spammed.
(2) implies that your comms method accept comms from unknown people. (1) is necessary for spammers to bother to do to use that channel to communicate with you.
I think you have to give up one or the other of these things to avoid spam. Note that (1) is a sliding scale. Physical post is significantly more expensive than email to send, and suffers less spam - but it is not non-zero.
Basically if cost of "customer acquisition" < "cost to send spam" on that comms channel, then you'll get some (if (2) is met).
[*] I suppose some heuristics to decide if it is OK for "random unknown user X" to contact me can help. But false positives are the very devil here...
Why can't I be asked the first time someone communicates with me? (This is ofc client-side spam prevention, but it should be passed upstream ideally)
However, this isn't necessary for all communications. For instance, if a communication is signed by a reputable company (bank, for instance), then don't bother asking. ISPs should keep the list of reputable companies as short as possible and, regardless, it gets rid of phishing emails.
It's trivially easy for you to greylist everything, and trawl through that everyday, and whitelist what you want and blacklist the rest. Anything whitelisted is automatically whitelisted forever. Anything blacklisted is automatically blacklisted for ever.
The problem comes when spammers forge From headers which leads to:
-1: Very many emails in the greylist everyday
-2: False positives if they use a From that you've previously accepted (ie that person gets infected)
-3: False negatives if you get a spam that you reject which was sent from an address that you really want whitelisted.
Some of the failure modes are similar to challenge-response systems.
Nothing stops you from doing greylisting today, and it can be a very effective means of stopping most spam. There are tons of software solutions for greylisting.
Some require manual approval first time. Some sends a message back to ask the sender to do something (anything from just clicking a link to entering a captcha) and relies on you to do manual approval now and again (to catch automated but valid messages).
Some just defers delivery and waits for a second delivery attempt (because most spammers practice "fire and forget" and just ignores errors). Our office mail server is in the latter category - first time someone e-mails us,a second delivery attempt needs to happen after 10 minutes for the message to get through (it's ok if there are attempts in between too, but the assumption is that most of even the few spammers that retry will go away too quickly to send another attempt after 10 minutes). It gets rid of the vast majority of our spam before our real spam filter even kicks in.
If people see a message saying "x has tried to contact you, do you wish to allow them", some of them will say yes. So spammers will continue to spam just as hard as they always have.
Also, considering how easy it would be to spoof "x", they could probably make people click "yes" a significant amount of the time.
'"get-viagra-cheap-now" has tried to contact you, do you wish to allow them'
- the spammer has just succeeded in putting their message in front of you. If you had 500 of those per day, it would constitute spam which would again need the same filtering.
Directly, it doesn't. However, I can block your certificate., or better, I can block the CA signing certificates that represent either businesses I don't want to talk to or people who don't really exist.
Whilst I don't generally believe governments should intervene in the internet, this is one area they could intervene in. They could act as a certificate authority.
Of course, CAs will make mistakes, but they can revoke certificates when things go wrong.
You can also currently block IPs, domains, URLs and specific message content. There are even globally distributed lists of such things.
This is already how we manage to block most spam on the edge. What you're proposing is just a small iteration on the existing defences. An expensive one, which wouldn't work unless you managed to get everyone doing it at the same time.
There is a proposal for a proof of work system that does not require the sender to pay direct monetary fees and does not, significantly, slow down sending emails since it can be computed while the sender is writing the email.
I can't remember what it is called, but I hope somebody else can chime in with the name.
The smart thing about it is that you can use it as a filter in your baysian spam filtering systems. That way it can be implemented gradually, with no need to cut out everybody who doesn't yet use it.
Nice, but it would impact legitimate mailing lists.
(In the 90s Bill Gates touted the idea that the recipient of the email would receive the fee, and routinely refund it to the sender for legitimate messages.)
Wouldn't using the mailing list's email address in the hashcash algorithm work? Then the mailing list's server or recipients' clients' spam filters could utilize the hashcash header, comparing it to the mailing list address in the To field.
Mailing lists could even demand a lower hash target, requiring more energy to send messages to lists. This could rate-limit flame wars, for example.
HashCash would make it more expensive for everybody to send email, not just spammers. It's also one of those things that doesn't really work unless everybody starts using it.
What are you going to do to emails without the HashCash header when 95% of the World is still sending email without it? Does it matter to anyone else what you do to those emails if you're the only one doing it?
HashCash would have some benefits, even if only a few people start using it, and would give incentives to participate: Just don't use it for a binary decision, but as one factor in your probabilistic spam filtering. And make the filter also discriminate on the amount of work put into the hash.
Spam filtering is already 99.x% effective. So you're basically increasing the cost for everyone in order to gain one extra SpamAssassin rule?
There are plenty of reasons why "Payment" anti-spam methods have been soundly debunked over the years. You're not the first one to think it's a good idea, and you probably won't be the last, but do the research yourself first into why they can't work.
I think the two properties which a comms method needs to have a spam problem are:
1) it is inexpensive to communicate with someone
2) it is has a fixed, human-memorable "address" which can be communicated out of band (business card, verbally etc)
Once you have these two things, such lists of fixed address can accumulate and be circulated - and they can be spammed.
(2) implies that your comms method accept comms from unknown people. (1) is necessary for spammers to bother to do to use that channel to communicate with you.
I think you have to give up one or the other of these things to avoid spam. Note that (1) is a sliding scale. Physical post is significantly more expensive than email to send, and suffers less spam - but it is not non-zero.
Basically if cost of "customer acquisition" < "cost to send spam" on that comms channel, then you'll get some (if (2) is met).
[*] I suppose some heuristics to decide if it is OK for "random unknown user X" to contact me can help. But false positives are the very devil here...