The Penny Black Project

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.

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. 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 white-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.  Look here for some initial thoughts on this scheme.

The CPU-based approach was proposed and analyzed by Dwork and Naor; see also Back.  We are now investigating memory-based functions, first proposed and constructed by Abadi et al  (NDSS 2003).  An alternate solution by Dwork et al, more amenable to theoretical analysis, will appear in CRYPTO 2003. Here are some of our talks on the subject: Stanford-MIT, HP, Obervulfach.

We're still fleshing out the designs, arguing about the merits of the various challenge schemes and architectures.  Four Stanford undergraduates, under the supervision of Dan Boneh, implemented the computational approach using a very simple proxy architecture, described in more detail here.

It's quite likely that this form of lightweight cash-free payment scheme could be useful in other arenas.

Project Members

        Andrew Birrell
        Mike Burrows
        Cynthia Dwork
        Andrew Goldberg
        Mark Manasse
        Ted Wobber