Penny Black
Penny Black

The Penny Black project is investigating several techniques to reduce spam by making the sender pay. We're considering several currencies for payment: CPU cycles, memory cycles, Turing tests (proof that a human was involved), and plain old cash.

 Overview

The introduction of the Penny Black stamp played an important role in the reform of the British Postal System during the 1830's. Before this time, postage fees were based on weight and on distance involved. Postage had to be calculated for each letter, and was typically paid by the addressee. The introduction of the Penny Black shifted the cost of postage to the sender and eliminated the complexity of postage computation by requiring a uniform, low rate.

As with the British Post of the 1830's, Internet email is becoming increasingly expensive for message recipients. In the current case, the culprit is spam. Although spam does not constitute a monetary expense for most users, it does require time and attention (and hence productivity) to deal with spam. Moreover, measurable costs associated with spam are incurred by providers of network services, and these costs are increasing daily.

In a nutshell, the idea is this: "If I don't know you, and you want to send me mail, then you must prove to me that you have expended a certain amount of effort, just for me and just for this message." The approach is fundamentally an economic one. Suppose we measure effort in CPU cycles. Since there are about 80,000 seconds in a day, a computational "price" of just ten seconds per message would limit a spamming computer to at most 8,000 messages daily. So spammers would have to invest heavily in hardware in order to send high volumes of spam. (While this idea is simple, people often misunderstand its implications. We encourage potential critics to look here first.)

The Penny Black project has investigated several techniques to reduce spam by making the sender pay. We've considered several currencies for payment: CPU cycles, memory cycles, and Turing tests (proof that a human was involved) are the leading candidates. There are multiple system organizations that can support this: senders can pre-compute the appropriate function, tied to a particular message; senders can come up with the payment in response to a challenge after they've submitted their message; senders can acquire a ticket pre-authorizing the message. Recipients would aggressively safe-list good senders.

The ticket scheme involves creating a ticket service that would issue tickets, which can then be submitted with an email message. The recipient would then call the ticket service to validate and cancel the ticket. There are some interesting ramifications to the ticket server idea. For example, 1000 pre-paid tickets might be bundled with each new PC. A detailed description of the Ticket Server design is available here.

The CPU-based approach was proposed and analyzed in [DW-92]; see also [B-02]. Four Stanford undergraduates, under the supervision of Dan Boneh, implemented the computational approach using a very simple proxy architecture, described in more detail here. We are still investigating memory-based functions, first proposed and constructed here. An alternate solution is more amenable to theoretical analysis. Here are some of our talks on the subject: Stanford-MIT, HP.

The research component of this project is largely complete. We continue to investigate how these ideas might be realized in practice.

Reference Material

  • [B-02] A. Back, "HashCash -- A Denial of Service Counter-Measure" (5 years on), Tech Report, 2002.
  • [DN-92] C. Dwork and M. Naor, "Pricing via Processing or Combatting Junk Mail",
    Lecture Notes in Computer Science 740 (Proceedings of CRYPTO'92), 1993, pp. 137--147.
Publications
  • Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber, Moderately Hard, Memory-bound Functions, in ACM Transactions on Internet Technology, vol. 5, no. 2, pp. 299-327, Association for Computing Machinery, Inc., May 2005
  • Martín Abadi, Andrew D. Birrell, Mike Burrows, Frank Dabek, and Ted Wobber, Bankable Postage for Network Services, in Proceedings of the 8th Asian Computing Science Conference, Springer-Verlag, Mumbai, India, December 2003
  • Cynthia Dwork, Andrew Goldberg, and Moni Naor, On Memory-Bound Functions for Fighting Spam, in Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003), Springer-Verlag, Santa Barbara, CA, August 2003
  • Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber, Moderately Hard, Memory-bound Functions, in Proceedings of the 10th Annual Network and Distributed System Security Symposium (NDSS), Internet Society, February 2003