Stateless proof-of-work system with 0-roundtrip time I'm designing an API. To avoid abuse, I need to rate limit the requests somehow, but I don't want to do it per user as it's very easy to create new accounts automatically. I think a proof of work algorithm would do this job well, but I thought I would ask an expert, i.e. this community.

These are the properties I would like: 


Stateless, but ahead of time setup of state, such as creating a user account, is ok. Two subsequent requests may hit different servers before they have shared their state with each other.
Preferably zero round trip time, i.e. the user does not have to ask a server what work it should do before actually doing it. This basically implies that the requests are stateless.
Requests should be able to run in parallell, even for the same user.
Adjustable difficulty.


I can think of some systems that fulfill some of the above properties, but not all.


Hash on userid + (request id) + nonce until the prefix of the hash has n bits of zeroes. Request id is some unique number picked by the client. Has properties 2, 3, 4, since we have to keep track of what request-ids have been used already. Otherwise, the same proof-of-work can be used for multiple requests.
Hash on userid + (request-id) + nonce until the prefix of the hash has n bits of zeroes. Request-id is fetched from the server before each request. Has properties 3, 4 and optionally 1, if there's some way to validate that the request-id was generated by one of our servers without touching a database. Since we have to ask the server for a request-id, we need one additional roundtrip time.


Is there a proof of work system that provides all the properties I've listed?
Is the requirement to prevent replaying identical requests? If not, it seems trivial to use a partial inverse hash of the request body.

If you are concerned about replaying identical requests, one possibility might be to use the proof-of-work nonce for your load-balancing algorithm. For example, use the least significant 3 bits to distribute across 8 servers. The long run average should distribute fairly between workers but a replayed request will always end up going to the same worker. SO you can check for duplicates locally without needing access to a global state.