Cheap to validate yet expensive to compute hashing algorithm

Question

I am looking for a hashing algorithm somewhat like bcrypt, except that I would like validation to be extremely cheap.

As an anti-spam measure I would like to require my clients spend say, half a second of compute time, before they submit information. I would like to assign them information to hash and then on my end quickly check that the information was hashed correctly. To protect myself from a DoS using something like bcrypt would not be feasible.

As it is an anti spam measure, I am not looking for perfection, the hashing algorithm can be weak.

Is there a name for such an algorithm? What could I use?

Answer 1

It's called a "proof of work" algorithm. The basic idea is you force the caller to do some extra work after creating the hash. You can use any hashing algorithm. Here's one simple form:

1. The client computes the hash of the data. (Say, it's 160 bits.)

2. The client creates a block containing the hash and the rest of the data all zeroes. (Say the block is 512 bits.)

3. The client computes the hash of this block.

4. If this final hash is below the target, the client submits the entire block it just hashed and is done.

5. The client increments the data in the block other than the hash and jumps to step 3.

When the server gets the block, it computes the hash of the block. If the hash is below the target, the server accepts the block and reads the hash from the beginning of the block. If the hash is above the target, the server rejects it.

So, if the target is 0fffffff.. the client will typically have to perform step 3 (the hash operation) 16 times before it gets a final hash below the target. (There's a 1 in 16 chance a given hash will, in hex, start with a zero.) If that's too easy, set the target to 00fff... and the client will typically have to do 256 block hashes.

You can force the client to do, on average, as many hashes as you want. The actual number of hashes the client will need to do follows a Poisson distribution. The downside is there's always a chance the client will be unlucky and have to do a large amount of work.

If you need to prevent the client from 'reusing' work, you can make the client ask you for a sequence number. The block then contains the hash, then the sequence number, then the nonce (the part the client increments). You can then validate the sequence number, so the client can't reuse a block it did before and can't pre-compute the blocks.

If you don't like this, you can also pick two random primes and send the product of those primes. Force the client to factor that number. Accept one hash per number factored. Of course, you can make the primes as big or as small as you want to control the amount of work the client needs to do.