Proof-of-work system | Hacker News Reader

Proof-of-work system

en.wikipedia.org

42 pointsolalonde13 comments

The canonical proof-of-work system, hashcash, tries to solve the problems "free e-mail makes spamming profitable" and "users won't pay for e-mail" by imposing a cost in CPU time on the sender: this is free[1] for a normal sender, but a spammer will only be able to send out a limited number of e-mails.

Unfortunately, this idea doesn't actually work. If an old "dumb" phone can send e-mail to a couple of your friends, a cool gaming rig can send zillions[2]. (Limiting senders by memory bandwidth instead of CPU power helps, but I'm not sure if that's enough.) Spammers have been using botnets for a long time. I'm also not aware of any scheme that has considered attacks based on custom hardware.

Mailing lists are also a problem.

[1] Of course, the extra calculations do increase power use, but that's sufficiently invisible that people won't actually care. For instance, SETI@home and other BOINC projects may consume ~$7.40 per month in electricity, but people generally don't care (source: http://boinc.berkeley.edu/wiki/Heat_and_energy_consideration...).

[2] [EDIT: added in response to andrewcooke.] Let's substitute a cheaper computer (because it's indeed more cost-effective than a gaming rig), and guess at some figures.

Assume your 100x speedup (four-core 2GHz vs single-core 100MHz gets you to 80x; highly-optimized vs crappy code can probably get you far higher, but let's stick with 100x for now.) If the phone can send one message per 10 seconds, the PC would send out 100 x 24 x 60 x 60 / 10 = 864 000 messages per day (assuming it's only limited by the proof-of-work!) http://www.icsi.berkeley.edu/pubs/networking/2008-ccs-spamal.... cites a ~0.00001% conversion rate on a ~$100 product, or a profit of $1/10 000 messages; that would allow a mind-blowing $86 of scalable profit per day.

In reality, that message count sounds unreasonably high - I'd guess the spammer runs into bandwidth/antispam limitations before CPU limitations.

i'm not sure how much "zillions" is, but it's not at all clear to me that it's large enough for spam to remain profitable if they use their own machines. i suspect the difference in computing power is only 100 or so (you can get low-power servers using atoms...) and that a spammer needs to send millions of emails to get an edge.

however, it doesn't work well against bot nets (and i think that's where most spam comes from).

I am currently working on a course project that involves bolting a proof-of-work system onto DNS to throttle connections to servers. Using IPv6, the DNS server can return an IPv6 address that is usable only by the requesting client because it was randomized in the lower 64-bits and is firewalled from other clients. I've put the project on GitHub and would appreciate any comments!

https://github.com/jevinskie/SlothNS

The idea is cool, but I'm somewhat unclear on the economic model that would make it work. Certainly, if I can connect to visa.com within a reasonable time, Anonymous would have no meaningful trouble DDoS'ing it. Requiring a new unit of work for every new connection may or may not allow legitimate requests while making DDoS infeasible; the linked Wikipedia page gives to some papers that may help you build such an economic model, if you want to look at this. Note that http://www.csoonline.com/article/220336/how-a-bookmaker-and-... suggests that DDoS attacks were (in 2005) quite a bit more profitable than spam runs. Google "dos extortion" for much more, including Symantec saying that DoS extortion was no longer profitable in 2007.

I'm not sure you actually need IPv6; can't you just use 2^15 (optionally unused) ports in the registered ports range (1024-49151) for your scheme? If you're worried about firewalls blocking traffic to such uncommon ports, you could use a single port on a class C network (256 hosts) if you're willing to blacklist anyone connecting to the wrong host (which runs a risk of wrongly blacklisting people behind a NAT).

Have you chosen which PoW function you are going to use yet? I've looked into this stuff a bit and I thought http://www.wisdom.weizmann.ac.il/~naor/PAPERS/mem_abs.html looked cool, but I've never seen an implementation. If you happen to implement something like that, could you drop me a line on your experiences/benchmarks (e-mail in profile)? Questions are also welcome.

Of course, you're aware that this proposal is never going to be implemented, right? People won't accept extra connection latency, it requires every single resolver to be updated (because you need to block clients that didn't do the PoW), it's incompatible with caching, etc. I don't think this is that big of a problem - it's just an exercise - but don't expect to convince the BIND maintainers.

I do think the idea is quite cool, though.

Did anyone ever think of creating a proof-of-work system that would allocate some CPU time to do something useful for humanity? Maybe for medical research or something... Could it even work technically?

Yes, see "bread pudding protocol". Or reCAPTCHA, for a less-cryptographic take on the same problem.

I suppose its not worth distributing this task across the network if each node will only have .5 second computing time each time.

It is if that work is only a byproduct of a system such as described in the article. It's essentially "free" computation, even if it is only in tiny chunks. If the system became widespread, it would quickly add up. And why not?

For most applications of a proof-of-work system, you need to be able to verify the results quickly,. In addition, while the aggregate CPU power is pretty hefty, communication overhead is huge. There are not many useful problems that fit these constraints.

There are a few systems like this already, e.g. SETI@home (try to analyze signals to find aliens) or Folding@home (model protein folding to help with cancer (?) research)

But that's not really a proof of work system, that just uses your computer's idle time to work on something.

This is a really good read when you start getting into the technicalities of bitcoins implementation.

Could an unintended side effect of this be that it encourages spammers to create even more botnets to run these computations?

Reply on news.ycombinator.com