What challenge should I use in a challenge-response proof-of-work? In order to guard against denial-of-service attacks, I want to require clients to do some work (more work than the server does fulfilling the request) before talking to them.


Client connects
Server sends a challenge, including a piece of data

"Find bytes x such that hash(challengeData + x) has n zeros at the beginning"
Client finds x, sends it to the server
Server verifies that hash(challengeData + recv()) has n zeros at the beginning
The actual request is handled


I found a few different methods to generate this "challengeData" thing, and some problems with each of them:


Random bytes

Here, the client can just exhaust the server's PRNG by repeatedly connecting to it. Which brings us back to square one (denial of service).
Current time of day

This seems like a good idea to me, but I'd like to know what attacks you could have against it.
A string involving something dependent on this particular request (like hashcash)

In order to make sure evil connections are dropped as soon as possible, I'd like to avoid handing anything about the request before making sure the client has done some work. The idea is that the client should always do much more work than the server before it starts handling the request.


I have some constraints: firstly I'd like the server to be completely stateless. I don't want to save "hashcash" and make sure it isn't spent twice, instead I want to challenge the client to do work that, inherently, can't be pre-computed. Secondly I don't want to know anything about the request itself at this stage (such as authentication). This is so the server sends and recieves as little data as possible. For instance, the current time (nanosecond or millisecond precision, depending on the OS, hardware and implementation) is 8 bytes (a double), and 2^64-1 tries (i.e. an 8-byte response) should be more than enough before resetting the connection (for the foreseeable future).

In short:


What properties does this challenge need to have?
What easily generated data has all of these properties? Is the current time any good?


As usual when I ask something about protocol-design, this may well be reinventing the wheel. If there are any existing protocols that do this, I don't know about them yet.
A good PRNG can't be exhausted, so your argument against random bytes doesn't matter.


  firstly I'd like the server to be completely stateless. 


Sounds impossible to me.


a PRNG needs state. A clock needs state.
An open connection is state too
You probably want to store open challenges too. This part isn't strictly necessary, but very convenient.




You might also want to include something unique to the server in the challenge(for example its domain or IP address) so clients can't be tricked by one server into solving the challenge for another.

I'd go with the server sending 16 random bytes as challenge, and the client responding with something like ServerIP || HMAC(proof, Challenge || ServerID)