forwarded with thanks to Yakov Shafranovich over at ASRG.
|
| -------- Original Message --------
| Subject: [Asrg] 3. Proof-of-work analysis
| Date: Mon, 17 May 2004 23:15:46 +0100
| From: Richard Clayton <richard(_at_)highwayman(_dot_)com>
| To: asrg(_at_)ietf(_dot_)org
|
| 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
|
|
| _______________________________________________
| Asrg mailing list
| Asrg(_at_)ietf(_dot_)org
| https://www1.ietf.org/mailman/listinfo/asrg
|