Algorithm that costs time to run but easy to verify?

Question

I am designing an website for experiment, there will be a button which user must click and hold for a while, then release, then client submits AJAX event to server.

However, to prevent from autoclick bots and fast spam, I want the hold time to be very real and not skip-able, e.g. doing some calculation. The point is to waste actual CPU time, so that you can't simply guess the AJAX callback value or turning faster system clock to bypass it.

Are there any algorithm that

1. fast & easy to generate a challenge on a server
2. costs some time to execute on the client side, no spoof or shortcut the time.
3. easy & fast to verify the response result on a server?

Answer 1

You're looking for a Proof-of-work system.

The most popular algorithm seems to be Hashcash (also on Wikipedia), which is used for bitcoins, among other things. The basic idea is to ask the client program to find a hash with a certain number of leading zeroes, which is a problem they have to solve with brute force.

Basically, it works like this: the client has some sort of token. For email, this is usually the recipient's email address and today's date. So it could look like this:

[email protected]:04102011

The client now has to find a random string to put in front of this:

[email protected]:04202011

such that the hash of this has a bunch of leading 0s. (My example won't work because I just made up a number.)

Then, on your side, you just have to take this random input and run a single hash on it, to check if it starts with a bunch of 0s. This is a very fast operation.

The reason that the client has to spend a fair amount of CPU time on finding the right hash is that it is a brute-force problem. The only know want to do it is to choose a random string, test it, and if it doesn't work, choose another one.

Of course, since you're not doing emails, you will probably want to use a different token of some sort rather than an email address and date. However, in your case, this is easy: you can just make up a random string server-side and pass it to the client.

One advantage of this particular algorithm is that it's very easy to adjust the difficulty: just change how many leading zeroes you want. The more zeroes you require, the longer it will take the client; however, verification still takes the same amount of time on your end.