Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Common Misconceptions about Computational Spam-Fighting

Common Misconceptions about Computational Spam-Fighting

Cynthia Dwork
Andrew V. Goldberg
Microsoft Research

Computational spam-fighting is a practical but frequently misunderstood way to reduce unwanted electronic mail without significant changes to the existing email infrastructure. The idea behind the computational approach to fighting spam, proposed by Dwork and Naor over a decade ago, is simple. The sender attaches to a message a computational proof of effort specific to the message, sender, receiver, and date, and the receiver verifies that the required computation has been performed. Although a high degree of technical knowledge is required to understand the details of how this can be implemented securely, the basic idea is accessible to anybody with moderate understanding of how electronic mail works. In essence, the computation serves as a postage stamp, "paid for" with computation (no money is involved); hence the name "Penny Black" of the project that further studies this idea, in honor of the 19th century British postage stamp.

Computer mail works well. The system is highly reliable, efficient, and decentralized. The basic concepts are well-understood. From its inception, a guiding principle in designing the computational approach to fighting spam is to tamper with the infrastructure as little as possible and to cause minimal inconvenience to all users except the senders of unsolicited bulk mail.

In particular:

  • No money is charged under the computational approach. In addition to unpopularity in the user community, charging money for e-mail involves major infrastructure changes (e.g. micropayment support).
  • No challenge-response mechanism is required. Unlike challenge-response approaches, we do not require additional communication between the sender and the receiver.
  • No third party is required for electronic mail communication.
  • Control of mail servers remains as it is now. With users and their delegates.
  • Once in place, virtually no maintenance is needed (unlike spam filters that need constant updates).

Additional Details

The heart of the computational approach is to "pay" for e-mail in computational time. Computer resources are already being spent on e-mail. We propose increasing this cost to about ten seconds for unsolicited e-mail. A user sending a couple of unsolicited messages will hardly notice. Someone sending 120 messages will experience a twenty minute delay. Spammers sending millions of messages a day will have to invest heavily into computational resources. We are betting they cannot afford to do so. Note that this "charge" applies to unsolicited e-mail only. Users may choose to keep a "safe list," and messages from the list members are considered to be solicited.

Consider a large online retailer like Amazon. There are several reasons why Amazon will not be inconvenienced by the computational scheme. Ten seconds of computer time adds a fraction of a penny to the cost of processing an order and has a minor effect on the overall cost. Furthermore, a right user interface can make it easy for consumers to put Amazon on their safe lists, temporarily (when placing orders) or permanently.

The proof of computational effort is based on cryptographic techniques. Several papers describing different solutions have been published.

Note that participation in the computational scheme is voluntary. If e-mail users choose not to require proofs of computational effort, nobody will need to produce them, and the current system -- including spam -- will not be affected. If users choose to require proofs, then those wishing to send unsolicited mail will have to produce stamps for it.

For the computational scheme to be accepted, one needs standards that will enable vendors or third parties to produce the required software. As no infrastructure changes are required, this is technically simple -- four Stanford students implemented the scheme on two platforms as a quarter programming course project. Technological feasibility of the computational scheme has been demonstrated. Making the scheme a reality is now a social, political, and business question.

There are many other approaches to combating spam. Filtering, Turing tests, ticket servers, micropayments, posting bonds, regulation of mail servers, and prosecuting spammers are some of the alternatives. The purpose of this note is to distinguish the computational approach from other approaches, not to argue about their relative strengths and weaknesses.