a life of coding

Wednesday, August 18, 2004

HashCash Postage

No, its not a tight roll of twenties used to buy ziplock baggies. HashCash is an automatic system for generating Proof Of Work, that your computer spent some time doing something. The idea here is that I could promote emails that have postage above a threshold - 21 bits takes about 4 seconds on a modern computer. To make sure that someone can't use postage more than once, its based on the current date and the recipient's email address. If the date is in the future, or too far in the past, or isn't based on my email, or I've already seen that exact postage, then it gets the same treatment as a mail with no postage.

How do I know that the postage actually represents time spent? A hash is a computation that generates a number based on some input data. Practially speaking, a hash is only interesting if hash(x) != hash(y) implies that x != y. MD5 and SHA-1 do a pretty good job of this. Its possible, but hard (meaning, it takes a long time) to find an x and a y such that hash(x) == hash(y). However, if you are given x, finding a y such that hash(x) == hash(y) is very hard - as far as we know it would take forever. In fact, there has recently been exciting news about someone breaking a weaker SHA-0 hash in 80,000 CPU hours on a 256 node Itanium cluster (Slashdot.org ). So, to require only a few seconds of time, we look for y such that n bits of hash(a) == hash(b). This means that we can charge more postage as computers become faster. Thats the mathematical way to show someone spent some time doing something. To apply this to email, I say that someone has paid the postage if they attach y, where hash(y) matches 21 bits of hash(x), and x = "0:" + today's date + ":" + my email address.

It would be inconvenient for everyone to always pay postage (of course, email takes a while to get delivered anyway - a few seconds won't be noticed), and many people won't be able to attach postage (they might not have the software, or might have a very slow computer), so you need a white list of people who you will accept postage-less email from. Also, you would have to accept postage for the address of mailing lists that you are subscribed to. And, spammers will probably still spam, even if they have to pay postage. If they do, they've been limited from their current 10,000 per minute to around 15, and that certainly takes away from the profit of spamming.


Post a Comment


Create a Link

<< Home