Deterring Spam with Cycles and Latency

Cynthia Dwork
Ted Wobber
MSR Silicon Valley

If the sender of a piece of email has to pay to have it delivered, bulk mailing becomes unattractive.  One form of payment is that the sender must solve a recipient-defined puzzle in which computation of the solution is moderately and provably hard.  An agent of the recipient can check very cheaply that the sender has indeed solved the puzzle.  We have developed practical algorithms that do this.

We treat all unsolicited e-mail equally. While much unsolicited e-mail is annoying, some is desirable. The technique described here changes the economics of sending unsolicited e-mail. The impact is significant on bulk mailings and insignificant on individual transmissions.

The Technique in Vitro

In order to send a message m, the sender will be required to compute f(m) for a suitable function f.  Call f(m) a certificate for m. Intuitively, the certificate proves to the recipient that the sender has expended (or paid a third party to expend) computational effort specifically for sending m.  The real cost to the sender is not only computation, but also latency.

The function f is chosen so that:

• Checking is cheap; that is, it is much easier to check the validity of a certificate than it is to compute one.  For example, to compute f(x) = x^1/2 mod p, where p is a large prime, requires about log₂ p large multiplications, while checking  whether or not y = x^1/2 mod p requires only one.

• f is not amenable to amortization: the cost of computing f on many (even slightly) different messages m₁, ..., m_k is no less than the sum of the costs of computing f(m₁), ..., f(m_k). In other words, there is no ``volume discount.''

• f is only moderately hard to compute, say, requiring 10, 30, or 60 seconds of CPU time.  To an individual taking several seconds or minutes to compose an unsolicited message to a single recipient, this extra cost is negligible (the computation is done in the background).

For completeness: m should include a few extra pieces of information, such as the sender's and recipient's e-mail addresses, and a timestamp.  This ensures that in a bulk mailing the function would need to be recomputed for every recipient, and that multiple transmissions to the same recipient will each incur the cost of a computation of f.

Specific families of moderately hard functions suitable for this technique are proposed in [DN92], where they are called pricing functions.

The Technique in Vivo

We describe just one of many ways in which the technique can be implemented autonomously by any individual. In other words, the basic e-mail transmission protocols do not need to be altered.

Each recipient chooses his own pricing function.  In addition, the recipient may maintain a list of correspondents from whom he is willing to receive uncertified mail.

On receipt of a pair (m,y) from a sender not on the list of correspondents, the recipient's mail program checks whether m is timely and if y = f(m) (checking is cheap).  If so, m is revealed to the recipient. Otherwise the mail program automatically "bounces" m back to the sender.  One possibility is for the automatic reply to contain a program for computing f, say in C# managed code. Alternatively, the reply may contain a link to a web site from which the code can be obtained.  Whether or not the sender must become involved manually at this point depends on whether or not the sender's mail program is compliant.

Summary

The potential value to email users is clear.  There is additional value to application service providers like Hotmail and Yahoo, where spam is a serious problem because of the storage costs. Email services can either implement the pricing function approach, allowing users to chose the computational "price" of their own incoming messages, or implement a single pricing function for all incoming transmissions. One might also consider charging users for computation of certificates for unsolicited outgoing messages.
 

• [DN92]   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
  (Draft)
   
• A conference poster describing the idea and possible implementations.