Reusable hashcash for spam prevention

Anonymous cripto at ecn.org
Mon May 17 22:45:42 PDT 2004


Recently someone proposed a system which combined ecash and hashcash
for email postage.  The effect is to get a form of reusable hashcash.
Here is some analysis.

There are already proposals and even some working code for hashcash email
postage.  See http://www.camram.org/.  This is intended as an anti-spam
measure.  The idea is that to send email, the sender has to create a
"proof of work" token, something which takes a relatively long time to
compute but which can be checked quickly.  The simplest proposal is a
hash collision, as suggested by Adam Back at http://www.hashcash.org/.

Spam filter software could be configured so that email containing
a valid hashcash token would be presumptively viewed as non-spam.
Most non-spammers have low volumes of outgoing mail and so they can
generate the necessary hashcash at mail sending time, introducing only
a modest delay.  Spammers however rely on being able to send enormous
volumes of email practically for free, so having to expend potentially
several minutes of CPU time for each outgoing email would make their
actions unprofitable.

The alternative being proposed here is to let there be a way of exchanging
hashcash tokens for ecash-like tokens at one or more trusted servers.
These ecash tokens would not actually be "cash" any more than is hashcash,
i.e. they would not have a specific monetary value, nor would the ecash
servers exchange ecash tokens for cash.  Rather, ecash tokens would
be exchangeable only for other such tokens, and they could also be
"purchased" with hashcash.  These ecash tokens would then be used as a
sort of postage stamp, instead of the straight hashcash tokens in Camram.

There is not a particularly strong need for the ecash tokens to be blinded
or unlinkable, since the value of them is so low.  The servers just need
a way to distinguish good and unspent ecash from bad or spent ecash.
However if they are used and reused for email postage, allowing linkable
tokens would show who was sending mail to whom, infringing email privacy.
Hence it would be desirable for the tokens to be unlinkable, which will
be possible after the Chaum patent expires in 2005.

This is not a crypto anarchy system which would bring down the government
and usher in a cypherpunk utopia.  The value of these cash tokens would
be small, pennies at best.  However it represents an adaptation of ecash
technology for a useful purpose and it would potentially introduce a
limited form of cash-like tokens into widespread use.

This system has pros and cons in terms of spam resistance, versus the
straight hashcash approach.  The biggest difference is that this system
allows for effective reuse of tokens.  You receive a token in an incoming
email, you exchange it at the server for a new one (validating it in the
process), and you use the new one to send out a message.  Reuse is not
possible with straight hashcash, because if people could reuse them,
then people could double-spend them.  If hashcash reuse were allowed,
a spammer could generate a single hashcash token and put identical copies
in all of his outgoing email.

In order to prevent reuse, hashcash tokens must include enough
information embedded in the hash collision to make them unique for a
particular message.  Typically this would include the recipient's email
address, date/time information, and possibly even a message body hash.
Hashcash verification involves checking not only the mathematical validity
of the collision, but that these embedded fields are correct, as well.

The implication of this requirement is that the hashcash token cannot be
generated in advance, but must be created at the time the mail is sent.
This reduces the acceptable amount of time required for a typical user
to create it.  If hashcash could be precomputed overnight, it might be
okay to take even an hour to produce a token.  But if it has to be done
at mail sending time, only a much lower time limit will be acceptable.

As a result, the size of hashcash collisions has to be set low enough for
end users to generate a token in no more than a few seconds or minutes
at most.  And this increases the chance that spammers may be able to
incorporate economies of scale and generate hashcash fast enough to
make spamming still be economical.  Some analyses suggest exactly this
possibility - see for instance
http://www.dtc.umn.edu/weis2004/clayton.pdf.

Making hashcash reusable by exchanging it for ecash tokens would fix
this problem.  Instead of the hashcash including information within it
to prevent double use, this would be handled by validating the ecash
or hashcash at the server to make sure it had not been used before.
Now, this means that the spam filter must make an Internet access to
check validity, which was not necessary with straight hashcash.  However,
most spam filters today make many Internet accesses, to check black lists
and other communal resources intended to fight spam.  Adding a check to
validate an ecash token would not change the basic functionality of the
spam filter, or materially slow down its operation.

Preventing reuse via this method means that hashcash will no longer have
to embed the destination and mail-sending times as it does now.  This will
allow hashcash to be precomputed, and therefore much larger computation
thresholds will be acceptable for widespread use.  These larger thresholds
will make the spammers' jobs that much harder.

Another reason why a larger threshold will work is because people will
have other ways of getting ecash tokens besides computing hashcash.
The most obvious would be reusing tokens in incoming email.  Anyone who
gets about as many (non-spam) emails as he sends, which is probably the
case for most people, would have little or no need to compute hashcash
tokens.  Spammers, however, send vastly more email than they receive,
hence they would not be able to benefit from this shortcut.

Switching from hashcash to ecash allows a single hashcash token to be the
foundation for the ecash used to send many pieces of email, sequentially.
This is another advantage of ecash: it is far less wasteful of compute
resources.  Hashcash is thrown away after each use.  Ecash is conserved
and reused.  Eventually we may find that our computer cycles are important
and valuable enough that wasting several minutes of computation on every
outgoing email is unacceptable.  In the long run we need something more
like ecash than hashcash for email postage.

If this system became widespread, it's likely that there will be another
way of getting ecash tokens.  You will be able to buy them.  I proposed
above that the ecash server would not be in the business of buying and
selling, only exchange.  But that wouldn't stop other people from selling
ecash tokens.  Initially this might be done on a small scale via eBay
and Paypal, just like people sell virtual gold and armor from Everquest.
Later companies could spring up which would sell tokens on a larger scale,
all major credit cards accepted.

The reason for such markets is that some people would have a need
for many ecash tokens, and others would have a surplus of such tokens.
People with extra tokens would include those who receive a lot of email;
students and researchers who have access to unused server farms where
they can generate many coins during off hours; and pirates who have
broken into end user computers and commandeered them to compute coins,
without the owners even knowing it.  People who want to buy tokens would
include legitimate businesses with opt-in email lists, and spammers.

It may appear that this system will degenerate into one where hackers
break into systems and generate coins, which are then sold to spammers.
We would get the worst situation possible, where computer thieves have
even more incentive than they do today to attack systems (since they
will be able to make money at it), and spammers are still as much of a
problem as ever.

However, I don't see this outcome as likely.  First, even if such a
market appeared, the spammers wouldn't be getting their tokens for
free.  They'd still have to pay to get them from the computer hackers.
Even a modest fee would enormously increase the per-message cost for the
spammers, who are often sending tens of thousands of messages at a time.
Spam is not going to be made profitable by such a market.

And second, once people start to realize that their unused computer cycles
are at least slightly valuable, they are more likely to take steps to
protect them.  Grad students who misuse server farms to generate stamps
are going to get in trouble, once the Uni realizes that this is theft
of something valuable.  End user break-ins will be more noticeable if
the system is busy all the time generating stamps, and owners will have
more motivation to police their systems and keep them updated if they
know they could be losing money.  (I also believe that we will have much
more secure end-user machines in a year or two with the next generation
of software, which will make this even less of an issue.)

What we are likely to see is that commercial email advertising will
continue, but not in the form of the absurd, scatter-shot spam we see
today, with ads for medications carefully misspelled to evade filters.
For email advertising to be effective in the future, response rates
must rise, which means it will be crafted and targeted.  Your spam email
will be on subjects that interest you, it will be legible and literate,
and won't be such an annoyance.  That seems like an acceptable balance
between freedom of communication and efficient use of email.

If we do see ecash postage being bought and sold for small sums, then
it could evolve into a micropayment architecture good for other purposes
as well.  You're not going to be able to efficiently pay someone thousands
of dollars for some illicit activity using two-penny stamps.  But maybe
you could send a few dozen stamps to a starving musician each time you
download one of his songs, and that could make a difference for him if
all his fans did that.

There are other issues to consider, which are also discussed in the
hashcash proposals.  Over time the threshold for postage needs to
be raised, as Moore's Law makes stamp generation cheaper.  And users
would have to instruct their spam filters to white-list any email lists
they sign up for (a process which should be automated) as mailing list
exploders wouldn't generate stamps for each subscriber.

The biggest problem, of course, is belling the cat: convincing spam
filter makers to include hashcash and/or ecash as a filtering mechanism,
and providing options to include it in outgoing email.  There is an IRTF
(related to the IETF, the technical governing body of the Internet)
task force studying anti-spam technology, http://asrg.sp.am/, and maybe
someone could propose these ideas there for comment.  It might be possible
to write plugins based on the Camram work that could be used as a proof
of concept.

The technical implementation is not the hard part.  The real work is in
deciding whether this technology would accomplish our goals, and then
convincing people that it is worthwhile installing it.  Given that the
spam problem shows no sign of abating, hopefully it will be possible to
make progress on this issue.





More information about the cypherpunks-legacy mailing list