Algorithm that costs time to run but easy to verify? -

i designing website experiment, there button user must click , hold while, release, client submits ajax event server.

however, prevent autoclick bots , fast spam, want hold time real , not skip-able, e.g. doing calculation. point waste actual cpu time, can't guess ajax callback value or turning faster system clock bypass it.

are there algorithm that

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

you're looking proof-of-work system.

the popular algorithm seems hashcash (also on wikipedia), used bitcoins, among other things. basic idea ask client program find hash number of leading zeroes, problem have solve brute force.

basically, works this: client has sort of token. email, recipient's email address , today's date. this:

bob@example.com:04102011 

the client has find random string put in front of this:

asdlkfjasdlbob@example.com:04202011 

such hash of has bunch of leading 0s. (my example won't work because made number.)

then, on side, have take random input , run single hash on it, check if starts bunch of 0s. very fast operation.

the reason client has spend fair amount of cpu time on finding right hash is brute-force problem. know want choose random string, test it, , if doesn't work, choose one.

of course, since you're not doing emails, want use different token of sort rather email address , date. however, in case, easy: can make random string server-side , pass client.

one advantage of particular algorithm it's easy adjust difficulty: change how many leading zeroes want. more zeroes require, longer take client; however, verification still takes same amount of time on end.