<x-flowed>I wanted to try and get a rough approximation of hardware costs and performance for a hardware based attack against hashcash postage. So I wrote to Nicko van Someren. I chose Niko because I heard him speak that the digital commerce society of Boston on some of the scaling issues regarding a micromint[1] based currency system. A nutshell, he pretty well demolished the feasibility of micromint. In general, Nicko is not a fan of proof of work systems for a variety of reasons but he has some really good information that he gave me permission to share with the hashcash group. In my opinion, the content convinced me that hashcash will provide a degree of defense against Spam. On the downside, there are some serious issues regarding theft of service and bulk generation of stamps but I don't consider them a mortal wound, it's just a wound that bleeds real heavily... Please read the entire message before commenting because I may have addressed some of the points further on. [1]http://theory.lcs.mit.edu/~rivest/RivestShamir-mpay.pdf --- eric ----------------------- my question to Nicko was: """My primary concern is that there is a risk that someone could define a hashcash coin generator using relatively cheap hardware (e.g. FPGA) and enable the at home spammer to generate lots of coins. I'm wondering if you would be willing to do a first-order approximation analysis on the cost versus speed curve for hardware generating hashcash coins? """ to which he replied: At 12:00 PM 6/8/2001 +0100, Nicko van Someren wrote:
Hashcash is different to MicroMint in that, as long as the stamp is correctly constructed it will be hard to do any precomputation to make bulk mailing more efficient and the economies of scale that are both the key to and the downfall of MicroMint do not apply. That said, the cost of repetitive bulk computation is nearly always sub-linear in the amount of work to be done.
The problems with proof of work schemes are many and varied. The most obvious is the inequality of the amount of processing power available to different people, or indeed to the same person in different contexts. I send mail from both a 733 MHz G4 PowerPC (in an Apple Mac) and a 16 MHz 68000 (in a Palm Pilot). Since the mail recipient can not reliably tell from which machine I sent then mail either it is going to take a couple of minutes to send a mail from the Palm or it will only take a second but I can forge spam as having come from the Palm and send hundreds a second from the Mac. To make matters worse, those who would spam have already shown themselves to not be beyond using the computing resources of others so I think that we can be confident that spam would be sent using "stolen stamps".
To address your specific question about hardware, as a rough guess, special hardware can do the same work as a general purpose CPU in about 0.1 to 0.2 as many clock ticks. For hash functions and some block ciphers (e.g. DES) the speed up can be even greater. What's more, since these days the fast FPGAs have more gates than you can shake a stick at you will be able to put multiple engines on one chip and I would expect that an off the shelf Xylinx development card with a big, fast gate array directly on the PCI bus would in practice be able to compute a SHA1 of something as small as an email address, date and integer at a rate a good 500 times faster than my PowerPC. This of course would depend on the hash algorithm and the amount of data used. You could strengthen against the use of hardware by using a system that needed more memory and used functions such as multiply operations which are expensive in hardware but which CPU designers spend a lot of effort upon.
Given that a $2000 PCI bus card will let me send spam to 10,000 people in the same time that a legitimate user can send a party invitation to 20 friends I expect that a SHA-1 based "proof of work" stamp is not going to be useful to spammers. All that it will do is make the sale of email addresses more profitable since there will be a market for "stamped, addresses envelopes" for which you can charge $100 for 100,000 instead of the current rate of $50 per million filtered addresses.
In short, I don't think proof of work based stamps will do much for reducing spam. I think that to do that we need a more innovative solution. If there were a ubiquitous micropayment scheme in circulation then I would go for a system that required cold hard cash to be sent with each email from someone you have not listed in your "free list". For most spam you'll get some cash, making large scale spam less cost effective as an advertising method, and if it is from someone that you really want to talk to you'll just send the cash back with your first mail back to the sender.
So that's my 2 pennies worth (or 2,000,000,000 CPU cycles!)
Nicko
my reply was:
At 12:00 PM 6/8/2001 +0100, Nicko van Someren wrote:
The problems with proof of work schemes are many and varied. The most obvious is the inequality of the amount of processing power available to different people, or indeed to the same person in different contexts. I send mail from both a 733 MHz G4 PowerPC (in an Apple Mac) and a 16 MHz 68000 (in a Palm Pilot). Since the mail recipient can not reliably tell from which machine I sent then mail either it is going to take a couple of minutes to send a mail from the Palm or it will only take a second but I can forge spam as having come from the Palm and send hundreds a second from the Mac. To make matters worse, those who would spam have already shown themselves to not be beyond using the computing resources of others so I think that we can be confident that spam would be sent using "stolen stamps".
on the range of processing power issue, I believe a more realistic bottom-line would be around a Pentium I/200 MHz. Wouldn't any e-mail coming from a PalmPilot go through some form of a conduit on the higher performance machine? That conduit could generate stamps.
On the point about forging what class of machine as a way of getting out of generating "expensive" stamps, we were not going to adjust the stamp based on the senders resources.
On the point about stolen stamps, I was planning on defeating that by making hashcash be a client to client protocol and the only thing intervening machines might do is validate that the stamp is present.
[hardware description snipped] Given that a $2000 PCI bus card will let me send spam to 10,000 people in the same time that a legitimate user can send a party invitation to 20 friends I expect that a SHA-1 based "proof of work" stamp is not going to be useful to spammers. All that it will do is make the sale of email addresses more profitable since there will be a market for "stamped, addresses envelopes" for which you can charge $100 for 100,000 instead of the current rate of $50 per million filtered addresses.
your thoughts are confirming one suspicion which is that even if hashcash hardware was implemented, it would raise the cost of spamming and cut out some of the more cost sensitive portions of the market. Remember that each stamp can only be used once and that it's only good for a finite period of time (for example, eight days). It would make it more difficult for a spammer to deliver continual postage because in their precalculation, they would need to create stamps that would be valid in the future for a limited period of time.
This still opens the market for spammer hardware to the at home spammer where they would sell boards in addition to the list of e-mail addresses.
In short, I don't think proof of work based stamps will do much for reducing spam. I think that to do that we need a more innovative solution. If there were a ubiquitous micropayment scheme in circulation then I would go for a system that required cold hard cash to be sent with each email from someone you have not listed in your "free list". For most spam you'll get some cash, making large scale spam less cost effective as an advertising method, and if it is from someone that you really want to talk to you'll just send the cash back with your first mail back to the sender.
it would be a short-term solution that would work until the hardware folks catch up. I think it's worth moving ahead with the technique anyway because it would create the infrastructure necessary for incorporating micropayments.
I need to run out now but I may send more thoughts later.
I very much appreciate you taking the time to answer my questions.
---eric
to which he replied to my reply... At 05:02 PM 6/8/2001 +0100, Nicko van Someren wrote:
"Eric S. Johansson" wrote:
I would like permission to forward bits of your message to the hashcash mailing list.
Sure, as long as you quote me in context.
The problems with proof of work schemes are many and varied. The most obvious is the inequality of the amount of processing power available to different people, or indeed to the same person in different contexts. I send mail from both a 733 MHz G4 PowerPC (in an Apple Mac) and a 16 MHz 68000 (in a Palm Pilot). Since the mail recipient can not reliably tell from which machine I sent then mail either it is going to take a couple of minutes to send a mail from the Palm or it will only take a second but I can forge spam as having come from the Palm and send hundreds a second from the Mac. To make matters worse, those who would spam have already shown themselves to not be beyond using the computing resources of others so I think that we can be confident that spam would be sent using "stolen stamps".
on the range of processing power issue, I believe a more realistic bottom-line would be around a Pentium I/200 MHz. Wouldn't any e-mail coming from a PalmPilot go through some form of a conduit on the higher performance machine? That conduit could generate stamps.
I post directly from handhelds all the time but if you were to introduce HashCash you could indeed mandate a gateway (with suitable sign-on) for posting from light weight devices.
On the point about forging what class of machine as a way of getting out of generating "expensive" stamps, we were not going to adjust the stamp based on the senders resources.
I think that having one size fit all will either render prefectly legitimate posting way to slow in some circumstances or make it too easy for the commited spammer to produce.
On the point about stolen stamps, I was planning on defeating that by making hashcash be a client to client protocol and the only thing intervening machines might do is validate that the stamp is present.
Unless you plan to rebuild the structure of the internet's email system this is going to be sent in the RFC822 header. You can't have challenge-response stamps for store-and-forward email. Even if you could deal with this there is no way to stop the turely nasty spammer from just cracking someone else's machine and using it to compute stamps for him.
[hardware description snipped] Given that a $2000 PCI bus card will let me send spam to 10,000 people in the same time that a legitimate user can send a party invitation to 20 friends I expect that a SHA-1 based "proof of work" stamp is not going to be useful to spammers. All that it will do is make the sale of email addresses more profitable since there will be a market for "stamped, addresses envelopes" for which you can charge $100 for 100,000 instead of the current rate of $50 per million filtered addresses.
your thoughts are confirming one suspicion which is that even if hashcash hardware was implemented, it would raise the cost of spamming and cut out some of the more cost sensitive portions of the market. Remember that each stamp can only be used once and that it's only good for a finite period of time (for example, eight days). It would make it more difficult for a spammer to deliver continual postage because in their precalculation, they would need to create stamps that would be valid in the future for a limited period of time.
I don't see this as a problem. Most people who spam buy in the mailing list from somewhere. Unless they plan to sit on the list for a long time (i.e. more than a week) then they could buy in the bulk stamps too. I bet the address dealers will cut you a deal if you come back for a second round of stamps too.
This still opens the market for spammer hardware to the at home spammer where they would sell boards in addition to the list of e-mail addresses.
Or allow you to log into their secure server and submit a list of 1,000,0000 addresses which would be stamped in a matter of minutes for a small charge.
In short, I don't think proof of work based stamps will do much for reducing spam. I think that to do that we need a more innovative solution. If there were a ubiquitous micropayment scheme in circulation then I would go for a system that required cold hard cash to be sent with each email from someone you have not listed in your "free list". For most spam you'll get some cash, making large scale spam less cost effective as an advertising method, and if it is from someone that you really want to talk to you'll just send the cash back with your first mail back to the sender.
it would be a short-term solution that would work until the hardware folks catch up. I think it's worth moving ahead with the technique anyway because it would create the infrastructure necessary for incorporating micropayments.
I'm not sure I agree. The design of an infrastructure for incorpoating micropayments is easy. Define the XML for the payment object, base 64 encode the payment, stick it in the X-payment: header line of the mail. Done. What is needed is the mail software on the desktops of tens of millions of users to be changed to be changed to support the system. Furthermore until you have it on the desktop of everyone with whom you talk you'll run into endless trouble.
The crux of the problem is that free email services with no recourse for misuse are all to easy to get hold of. Unless you stop accepting mail from mail servers that don't limit the source and volume of their mail then you will always have spam. If HotMail were to require some sort of ID before you could get an account, and refuse to give a second one on the basis of the same ID if the first account was canceled, then you would quickly stop getting spam from HotMail. If you simply require HotMail to compute stamps on every mail that they send then I can't complain; they've already spent $5,000,000 with nCipher for crypto hardware to speed up their SSL login and I expect that they would do the same for the HashCash stamps.
One way to ensure some sort of recourse is to require that there is a valid, routable reply address. The vast majority of spam mails do not have valid reply addresses. If you requried some sort of challenge-response on the first communication between two parties that would stop untracable spam. Furthermore such a system can be automated by those who care but still be made workable for those who don't want to upgrade their mail software. If you send me a mail and you don't have an automated responder you will simply see an authentication message with a request that you reply with the given subect line.
Anyway, as I've said before I really don't think proof-of-work schemes are the solution. Even if you think that people would accept a ten second per recipient delay before sending their mail then the spammer can still send 50,000 mails a week on a standard machine, and they can compute over the week and splurge them out on some free ISP all in one go. It's not a useful deterant.
Nicko
to which I replied (yes folks, this is the last bit)
On the point about forging what class of machine as a way of getting out of generating "expensive" stamps, we were not going to adjust the stamp based on the senders resources.
I think that having one size fit all will either render prefectly legitimate posting way to slow in some circumstances or make it too easy for the commited spammer to produce.
understood and I agree. It's just like you've pointed out that it's it's easy for a spammer to claim to be a low-power machine and thereby enabling them to get by with less postage. I'm not sure this is a mortal wound but it certainly bleeds heavily.
On the point about stolen stamps, I was planning on defeating that by making hashcash be a client to client protocol and the only thing intervening machines might do is validate that the stamp is present.
Unless you plan to rebuild the structure of the internet's email system this is going to be sent in the RFC822 header. You can't have challenge-response stamps for store-and-forward email.
actually, you can. Think back to the days of UUCP. One model we are trying on for size would have both MUAs talk to each other and communicate certain parameters. Yes, it's potentially very slow especially for people that don't live on the net all the time but only check e-mail once a week.
Even if you could deal with this there is no way to stop the turely nasty spammer from just cracking someone else's machine and using it to compute stamps for him.
yup, that's a hazard and one that can be defended against. The closer one couples the hashcash environment to the MTA, the more difficult it becomes for someone to steal services to generate stamps.
your thoughts are confirming one suspicion which is that even if hashcash hardware was implemented, it would raise the cost of spamming and cut out some of the more cost sensitive portions of the market. Remember that each stamp can only be used once and that it's only good for a finite period of time (for example, eight days). It would make it more difficult for a spammer to deliver continual postage because in their precalculation, they would need to create stamps that would be valid in the future for a limited period of time.
I don't see this as a problem. Most people who spam buy in the mailing list from somewhere. Unless they plan to sit on the list for a long time (i.e. more than a week) then they could buy in the bulk stamps too. I bet the address dealers will cut you a deal if you come back for a second round of stamps too.
let's see, let's work the numbers. Assuming a X-hashcash:string is somewhere in the area of 40 bytes, stamps for one million addresses is roughly 40 MB, 10 million stamps would be 400 MB. One could easily fit this on a CD or download via a DSL or cable modem. So transport would not be a big deal for a single Spam client but it would get rather interesting with thousands of spammer clients.
Using your numbers, (500 times speed up), a spammer could generate one stamp every 0.02 seconds (assuming the average stamp computation time was 10 seconds). This means that one million stamps would take 20,000 (5.5 hours) seconds to generate. If we mixed in to the stamp definition a hash of the message body as well, then it would be more difficult (but not impossible) for the spammer to precompute stamps because they would have to have the message body before they generated stamps.
one board would allow them to service roughly 130 one million address customers per month. servicing 1000 customers would take seven boards. If people wanted to ship more than one piece of spam per month, then the spam stamp creators would need to increase their capital investment and ongoing monthly costs which would in turn increase the cost of spam which would keep some people out of the market.
This conversation is helping me understand how proof of work calculations fail and the rate at which they would fail. The big question is can we exploit the arms race in our favor? I think the answer is yes but only for a relatively short period of time. But that would allow us to lay the groundwork for peer-to-peer postage.
This still opens the market for spammer hardware to the at home spammer where they would sell boards in addition to the list of e-mail addresses.
Or allow you to log into their secure server and submit a list of 1,000,0000 addresses which would be stamped in a matter of minutes for a small charge.
either my math is wrong or I didn't understand just how fast the speedup would go. You still have the bandwidth issue when transferring stamps which will most certainly take more than a few minutes. At least with the bandwidth available to most people. ;-)
it would be a short-term solution that would work until the hardware folks catch up. I think it's worth moving ahead with the technique anyway because it would create the infrastructure necessary for incorporating micropayments.
I'm not sure I agree. The design of an infrastructure for incorpoating micropayments is easy. Define the XML for the payment object, base 64 encode the payment, stick it in the X-payment: header line of the mail. Done. What is needed is the mail software on the desktops of tens of millions of users to be changed to be changed to support the system. Furthermore until you have it on the desktop of everyone with whom you talk you'll run into endless trouble.
well, yes. We do need to change all desktops but we're discussing how to do this without necessarily replacing the clients. The current model favors the development of a proxy which does the hashcash calculation. Obviously, we do want to get this into every e-mail client on the face of the planet. It's not going to happen but with network effects, I think we can encourage enough people to make the transition that it will be worthwhile.
One of the "encouragements" will be the delivery of messages from hashcash users to non hashcash users. This message (created by autoresponder) will instruct the user to click on a URL which will generate a hashcash coin and a "get out of hashcash jail free" card. The "get out of hashcash jail free" card will tell the recipient's MUA to release the trapped message.
The reason why I keep harping on it being an important (but not essential) precursor to using payments is that it will create the infrastructure for handling payments, bounces, double spending and more importantly put in place a code base that will only require minor changes (in theory) to handle real currency instead of proof of work.
as Bob will tell you, I have my own reality distortion field that has been in operation for far longer than I've known Bob.
Anyway, as I've said before I really don't think proof-of-work schemes are the solution. Even if you think that people would accept a ten second per recipient delay before sending their mail then the spammer can still send 50,000 mails a week on a standard machine, and they can compute over the week and splurge them out on some free ISP all in one go. It's not a useful deterant.
60480 stamps in a week @ ten seconds per stamp assuming the machine runs 24 by 7. It won't be a Windows box... ;-)
The analysis we've gone over certainly indicates that this is a high probability. My experience with spammers from the ISP perspective tells me that hashcash (or something like it) will make a dent. It won't be perfect by any stretch of the imagination but I can live with that.
again, I truly appreciate your advice and information. I will keep you informed so that what decisions we make in building the hashcash infrastructure will also be expandable to handle electronic currency when someone is ready to deploy it.
---eric
---------------------------------------------------------------------
To unsubscribe, e-mail: camram-spam-unsubscribe@camram.org
For additional commands, e-mail: camram-spam-help@camram.org
</x-flowed>
--- end forwarded text
--
-----------------
R. A. Hettinga