Proof of Computational Work / by Roger Kapsi

A novel idea to fight Spam in Distributed Systems with no or minimum State.

I was having dinner with a good friend and former co-worker a few weeks ago and we ended up philosophizing about the things we were doing at LimeWire. An important part of our day to day work was detection and prevention of Spam on the Gnutella Network.

I believe this idea is somewhat related to Bitcoins that use computational complexity for proof of work. Hashcash

The first question you should ask yourself is why Spammers do what they do? They do it because it's profitable and cheap. What if we make it (possibly very) expensive for them? CAPTCHA are one method to do it by introducing Human labor to the process but what if that is not an option or not desired?

The idea is to force clients to do work for us and have them provide some proof of their work. We can do this by introducing a secure Hash-Function to the system and requiring that the output of the Hash-Function meets some pre-defined requirement. The requirement can be something like the 20 bits of the hash must be zero. This can be achieved by appending (possibly) random padding information to the original message and keeping doing it (work - O(n) or worse) until some data has been found that yields to an acceptable hash. It then sends the original message along with the padding information to the server and the server can verify it in one step by using the same Hash-Function (proof - O(1)).

Here is a diagram of the workflow:

The number of bits and the complexity of the Hash-Function can be used as a crank to drive the cost up and down. I would also recommend using some random one-time token that is provided by the server (state in the session context) to make sure that messages can't be sent multiple times. In case of Web-Apps you may even use the fact that they've to run your JavaScript for your advantage.

No more simple spamming with curl & Co. Your users will ideally notice nothing but for Spammers it's translating directly into CPU Hours and hard cash.