Microsoft Notebook: Making spammers pay -- a very British idea

Microsoft Corp. is searching all over the place for weapons to battle spam. But who knew the company would find one in the 19th century British Postal System?

Microsoft researchers are drawing inspiration from the Penny Black stamp, introduced in the United Kingdom in 1840. Although it's a basic concept these days, the Penny Black was a radical move at the time, shifting the cost of postage from a letter's recipient to its sender.

Researchers involved in the company's Penny Black Project are studying ways to do essentially the same thing in the e-mail system.

Their plan would have computers perform a computation to produce a binary "stamp" -- a short series of ones and zeros -- prior to sending an e-mail. In that way, the sending computer would essentially "pay" for every e-mail it transmits with a small amount of extra computing time.

The basic idea has been around for some time, and people outside the company are pursuing similar concepts. But the Penny Black Project has been getting more attention since Microsoft Chairman Bill Gates, speaking last month in Davos, Switzerland, listed such computational methods among the techniques that he believes could help solve the spam problem within two years.

During the same speech, Gates also advocated a spam-fighting system in which e-mail senders would make actual monetary payments. But Microsoft says that concept is not far enough along in its development process to describe in detail.

Under the Penny Black concept, the computation would take place behind the scenes, and individual computer users, sending ordinary amounts of e-mail, wouldn't even notice the change, Microsoft says. But when multiplied over millions of messages, the seconds would become very noticeable -- and costly -- to anyone involved in mass e-mailing.

The idea is to change the fundamental economics of the spam business. For example, if the computation required to produce one of the binary stamps took 10 seconds to complete, a machine that under ordinary circumstances could send millions of messages a day would, with the extra computation time, be able to produce only about 8,000 messages.

To maintain their e-mailing volume, people and companies who send out huge amounts of messages would need to invest heavily in additional computers, plus space to house them and related costs.

Under one proposed model, a small program on the sending side would make the computation and tack the result to the message, perhaps in the header, the normally unseen portion of an e-mail that precedes the body of the message. A program on the receiving end would check incoming e-mails for the required computational stamp.

The calculation would incorporate the e-mail address, the date and time, and the text of the message. Those variables would require a computation to be made, and a stamp produced, for every message sent.

Individual recipients would choose what to do with messages that don't come with the necessary stamps -- putting them into special folders, for example, or sending them to the trash. Recipients could also compile individual safe lists of people and companies from whom they want to receive mail, and therefore don't require a stamp.

By tweaking the requirements on the receiving end, the amount of time needed to compute each "stamp" could be increased or decreased.

"What's enough (in computation time) depends on how much money there is in the spam industry," said Cynthia Dwork, a senior researcher in Microsoft's Silicon Valley research lab.

Although the Penny Black concept itself makes no distinction between "legitimate" bulk e-mailers and "illegitimate" ones, established commercial operations would tend to be in a better economic position to incur the extra cost. In that way, many of the fly-by-night spam houses would tend to be weeded out.

Others engaged in similar efforts include Camram, an open-source project developing software based on the same computational concept, also known as "proof of work" stamps. Camram is also working on an open standard for e-mail stamps.

Eric Johansson, the project leader, runs the Camram software on his own computer. Non-stamped messages are checked against his safe list and, if the sender isn't on that list, run through a spam filter. Stamped messages skip those steps and go straight to his in-box. All messages are ultimately categorized as good, bad or indeterminate.

For now, Johansson receives stamped messages from only two or three people, but the system will become more advantageous with more widespread participation.

"As other people in your network start adopting the same system, the quality of your e-mail goes up in terms of being able to get through," Johansson said. "This is why it's so important to have a public standard for a stamp -- everybody's got to use the same one."

Others believe that actual monetary payments may be a better solution. Gates, in his speech in Switzerland last month, was reported to be leaning more heavily toward a monetary method, which Microsoft researchers are also investigating.

And a company called Goodmail Systems, in Mountain View, Calif., is developing a money-based system that has attracted attention from companies, including Yahoo.

Under Goodmail's system, bulk e-mailers would pay a penny per message for stamps that would let their e-mails pass unblocked through Internet service providers' spam filters. Bulk e-mailers taking part in the system would need to have a reliable unsubscribe mechanism, and no anonymity would be allowed. Goodmail and the ISPs would share the payments.

The idea is to create "a trusted class" of e-mail, while shifting the burden to the bulk senders, said Goodmail's president and CEO, Richard Gingras.

Microsoft's Dwork started looking into the computational solution in the early 1990s, when she was working at IBM's Almaden Research Center. A colleague there, Moni Naor, was also involved. At the time, spam wasn't a serious problem, but they anticipated that it might ultimately become one. And it certainly had become one by 2001, when Dwork came to work for Microsoft.

"I realized that things were very different and there might be a chance to have an impact," Dwork recalled. After all, as she put it, "I was now working for a company that wrote the e-mail software for a significant fraction of the planet."

She and a Microsoft colleague, Ted Wobber, showed a poster describing the concept during Microsoft Research's annual Tech Fest two years ago, and the project has gained steam since then. Others involved include Naor, who is now at the Weizmann Institute of Science, and Microsoft's Andrew Goldberg.

Microsoft Research comes up with many of the technologies that Microsoft ultimately brings to market, sometimes as elements of larger products. For example, the company last year introduced new spam filtering technology, called SmartScreen, based on work that came out of Microsoft Research. The Microsoft programs Outlook 2003, MSN 8 and Hotmail use SmartScreen.

George Webb, group business manager in the company's Anti-Spam Technology and Strategy team, said it is continuing to work with Microsoft Research and "actively considering where and how to integrate" Penny Black and other techniques the research group is working on.

In addition to technological solutions, Microsoft's approach includes anti-spam legislation, consumer education, industry partnerships and suits against deceptive spammers.