Online Advertising
Hashcash
Hashcash is a
proof-of-work system designed to limit
email
spam and
denial of service attacks. It was proposed in March 1997 by Adam Back
[1].
How it works
A sender of non-spam email attaches a
header line to his email which proves that he has invested a modest amount
of computer time into solving a small puzzle involving the recipient's email
address. The receiver can, at negligible computational cost, verify that a
sender had solved the puzzle. This can be regarded as a form of numerical stamp,
where the 'cash' part is the effort invested by the sender.
The theory is that spammers, whose business model relies on their ability to
send large numbers of emails with very little cost per message, cannot afford
this investment into each individual piece of spam they send. Receivers can
verify whether a sender made such an investment and use the results to help
filter email.
Technical details
The header line looks something like
[2]
X-Hashcash: 0:030626:adam@cypherspace.org:6470e06d773e05a8
Technically the system is implemented as follows:
- The recipient's computer calculates the 160 bit
SHA-1
hash of the entire string
"0:030626:adam@cypherspace.org:6470e06d773e05a8". This takes about two
microseconds on a 1 GHz machine -- far shorter than the time it took for the
rest of the e-mail to be received. If the first 19 bits are all zero, then
it is valid (later versions may require more bits to be zero).
- The recipient's computer checks the date in that header "030626"
(2003-06-26). If it's within 2 days of today, it's valid (to compensate for
clock skew and routing time).
- The recipient's computer checks to see if the e-mail address in that
header is (any of) the valid e-mail address(es) of the recipient (or any
mailing lists to which the recipient is subscribed).
- If all the other checks are valid, the recipient's computer puts that
string in a database. If that string was *not* already in the database, it
is valid.
All these tests take far less time and disk space than receiving the rest of
the e-mail.
The sender "merely" needs to generate a header line that will pass all the
tests. The sender's computer first generates an initial Hashcash string (the
date, the e-mail address, and a random number at the end). The sender's computer
then repeatedly increments that random number and runs SHA-1, over and over
again, until SHA-1 gives enough zeros. Getting the first 19 bits to be zero
requires about 2^19 iterations, or about 1 second on a 1 GHz machine. A normal
person wouldn't even notice the computer taking a second to generate the
Hashcash string. Currently, spammers would prefer to spend that one second
sending out hundreds of pieces of spam, rather than calculating Hashcash for a
single piece of spam.
The time needed to compute such a hash collision is
exponential with the number of zero bits. So one can keep adding zero bits
(doubling the amount of time needed to send with each zero bit) until it is too
expensive for spammers to generate valid header lines. (Confirming the header is
valid always takes the same amount of time, no matter how many zero bits one
adds.)
Advantages and disadvantages
The Hashcash system has the advantage over
micropayment proposals applying to legitimate email that no real money is
involved. Neither the sender nor recipient need pay, thus the administrative
issues involved with all micropayment systems are entirely avoided.
On the other hand, as Hashcash requires significant computational resources
to be expended on each e-mail being sent, it is impractical to use with low-end
or battery-powered hardware without the help of an external server.
Hashcash is also fairly simple to implement in mail user agents and spam
filters. No central server is needed. Hashcash can be incrementally deployed --
the extra Hashcash header is ignored when it is received by mail clients that do
not understand it.
One vital problem of hash cash is that it is not clear whether there exist
effective parameters at all, i.e. parameters that allow the good people to get
on with their business while prohibiting bad people from getting on with theirs.
Some plausible estimates
[3] come to the conclusion that you can only have one of these: Either good
e-mail will get stuck due to lack of processing power of the sender, or bad
e-mail is bound to still get through. The reasons for this are botnets or
cluster farms with which spammers can increase their processing power
enormously, or centralized e-mail-topologies like mailing lists, in which some
server is to send an enormous amount of legitimate e-mails.
Most of these issues may be addressed. E.g., botnets may expire faster
because users notice the high CPU load and take counter-measures, and mailing
list servers can be registered in white lists on the subscribers' hosts and thus
be relieved from the hashcash challenges. But they represent serious obstacles
to hashcash deployment that need to be adressed somehow.
Another problem is that computers continue to get faster according to
Moore's
law. So the difficulty of the calculations required must be increased
continuously over time. In other words, the number of bits of the 160 bit hash
compared to zero must be increased over time. If current trends continue, those
160 bits will run out in about 200 or so years.
References
- Adam Back, "Hashcash - A Denial of Service Counter-Measure", technical
report, August 2002
(PDF).
- Ben Laurie and Richard Clayton, "'Proof-of-Work' Proves Not to Work",
WEAS 04.
(PDF).
External links
Home | Up
Online Advertising, made by MultiMedia | Free content and software
This guide is licensed under the GNU
Free Documentation License. It uses material from the Wikipedia.
|