Proof of Work {cannot, can, does currently} Work

L Jean Camp Debin Liu
ljean@ljean.com deliu@indiana.edu
Associate Professor Doctoral Student
901 E 10th St School of Informatics
Indiana University
Bloomington, IN

Abstract

The core enabling factor of spam is that spam is cheap to send. Spam is so profitable that estimates of the percentage of email as spam ranges from 56% [Brightmail, 04] in 2003 to 80% [Ciphertrust, 2005] in 2006. Spam is a malicious network activity enabled by the otherwise virtuous cycle of network expansion. As the network expands, spam becomes more profitable, and thus increases. A proposed economic and cryptographic solution to the profitability of spam is proof of work. Proof of work comprises a set of proposals, in which email senders would be required to pay money, perform a resource [Dwork and Noar, 1993], perform a series of memory operations, [Dwork, Goldberg and Naor, 2003], or post a bond, [Krihsamurthy and Blackmond, 2004] for each message sent. Thus the cost to send an email or initiate a connection is usually expressed in seconds as a measure of processing power or memory operations.

The design goal of POW is to deter spam by making it unprofitable to send a large number of messages, while enabling legitimate users to send small numbers of messages. Therefore, POW reverses the economics of email, to prevent spam. Yet by reversing the economics of email, POW can significantly hinder senders of legitimate email. This cost to legitimate email is exactly the reason that the first economic analysis illustrated that POW would not work. The argument was that any work requirement sufficient to prevent spammers from profiting is so high that it would harm senders of legitimate emails, especially on low power devices. [Laurie and Clayton, 2004] The basic argument underlying that analysis is that legitimate and malicious email producers have very different production costs. Legitimate senders of email purchase equipment and connectivity on the open market. Spammers have at their disposal large networks of subverted machines that provide automated networked platforms for mass production of illegal activities. The networks of subverted machines are called botnets. Botnets available for rent are as large as 10,000. Botnets are the criminal leveraging of peer production.

Recently, using a simple model of reputation systems, the authors illustrated that proof of work can work when combined with the currently used commercial anti-spam technologies. Our proof of concept illustrates the simple observation that email characteristics, particularly the characteristics of the sender, can be used to offer varying POW costs to different senders. This work an expansion of that initial analysis to include not only a sensitivity analysis, but also an analysis about the definition of Proof of Work. An analytic understanding of proof of work is particularly timely, as Microsoft is embedding a proof of work mechanism in its next generation of products. [Abadi et al, 2003] Because there are public reliable data on the diffusion of Microsoft products, in particular the market share, this moment in time provides a window to produce hypotheses that will be effectively tested by the uncontrolled experiment of Microsoft diffusion of proof of work technologies in the future.

The paper work builds upon our previous proof of concept to produce three new and significant results. The first is a sensitivity analysis of the basic POW model previously presented. What duration of punishment is required? How many people must participate? The second is an analysis of the nature of Proof of Work both as functional money (token versus notational) and as mechanisms in practice. For example, in this paper we argue that POW effectively also already exist in the form of reverse Turing tests and response requirements. The final expansion is one of scaling and costs. How large a reputation system would be necessary, or can this be implemented in a distributed manner? The cost issue can begin to address the question of how much is spam prevention worth, and how much POW costs. The possible cost would have to be presented as range of possible values, not an absolute.

References

M. Abadi, A. Birrell, M. Burrows, F. Dabek, and T. Wobber, Bankable Postage for Network Services. 2003. In LNCS: Lecture Notes in Computer Science, Springer-Verlag, Berlin, DE.

Brightmail Inc., Spam Percentages and Spam Categories, 2004. White Paper on Spam.

CipherTrust Inc., The Next-Generation Reputation System, 2005. White Paper on Spam, Mountain View, CA.

C. Dwork, A. Goldberg, and M. Naor, On Memory-Bound Functions for Fighting Spam, 2004. In D. Boneh (Ed.): Proceedings of Crypto 2003, Springer, Berlin, DE, pp. 426-444.

C. Dwork and M. Naor, Pricing via Processing or Combating Junk Mail, 1992. In E. F. Brick (Ed.): Advances in Cryptology-CRYPTO 1992, Springer-Verlag, pp. 139-147.

B. Laurie and R. Clayton, Proof of Work Proves Not to Work, 2004. The Third Annual Workshop on Economics and Information Security (WEIS04).

 

Full Paper Posted Soon