-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I hope this is useful: I'm in the Security Group of the Computer Laboratory at the University of Cambridge. Ben Laurie (yes, that Ben Laurie) and I have recently been doing some sums on proof-of-work / client puzzles / hashcash methods of imposing economic constraints upon the sending of spam... Ben wanted to know how big a proof was needed for a practical scheme he was considering -- and I told him it wasn't going to work. We then carefully worked through all the calculations, using the best data that we could obtain -- and we did indeed come to the conclusion that proof-of-work is not a viable proposal :( The paper we wrote about this was presented last week in Minneapolis at the (academic, peer-reviewed) "Third Annual Workshop on Economics and Information Security" (WEAS04) We've doubtless duplicated the figures on the back of many an envelope, but it is clearly useful to have the analysis in the formal literature where our assumptions and figures can be considered and possibly even improved upon by others. Paper: http://www.cl.cam.ac.uk/~rnc1/proofwork.pdf Slides from talk: http://www.cl.cam.ac.uk/~rnc1/talks/040514-ProofWork.pdf Abstract: A frequently proposed method of reducing unsolicited bulk email ("spam") is for senders to pay for each email they send. Proof- of-work schemes avoid charging real money by requiring senders to demonstrate that they have expended processing time in solving a cryptographic puzzle. We attempt to determine how difficult that puzzle should be so as to be effective in preventing spam. We analyse this both from an economic perspective, "how can we stop it being cost-effective to send spam", and from a security perspective, "spammers can access insecure end-user machines and will steal processing cycles to solve puzzles". Both analyses lead to similar values of puzzle difficulty. Unfortunately, real- world data from a large ISP shows that these difficulty levels would mean that significant numbers of senders of legitimate email would be unable to continue their current levels of activity. We conclude that proof-of-work will not be a solution to the problem of spam. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- For the avoidance of doubt, the type of scheme we believe we have shown is not viable is one where all email (except "mailing list" email) carries a "proof-of-work" along with it. It may be that it is still sensible to consider composite schemes where puzzles are only solved per sending host or where receivers use puzzles to admit senders into whitelists... ... however, we would consider it incumbent on any proposer of such a scheme to do similar calculations to ours before putting it forward. [ off-topic for here, but we also suspect that a number of proof- of-work schemes in peer-to-peer networks would fall to our type of real-world analysis :( people tend to use client puzzles as a kind of "magic fairy dust" to scatter over systems when they get stuck in their design :( ] - -- richard Richard Clayton They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. Benjamin Franklin -----BEGIN PGP SIGNATURE----- Version: PGPsdk version 1.7.1 iQA/AwUBQKk5khfnRQV/feRLEQIcyACcCrGw1ZZIHV+qP7AZy9M8XJU4920AnjcW M35kvXsj8cv/ujtY9xpf79av =wEUV -----END PGP SIGNATURE----- _______________________________________________ Asrg mailing list Asrg@ietf.org https://www1.ietf.org/mailman/listinfo/asrg --- end forwarded text --- end forwarded text -- ----------------- R. A. Hettinga <mailto: rah@ibuc.com> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'