1
$\begingroup$

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:

  1. 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.
  2. 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.
  3. Requests should be able to run in parallell, even for the same user.
  4. 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?

Improve this question
$\endgroup$
  • $\begingroup$ Is it an an unencrypted UDP based API, or how else do you want to achieve zero-RT? Both TCP and TLS already add round trips. $\endgroup$ – CodesInChaos Feb 27 '16 at 15:12
  • $\begingroup$ There are multiple use-cases. Established connections, UDP and QUIC are a few where this would be beneficial. It could still be encrypted, since ahead of time setup is ok. $\endgroup$ – Filip Haglund Feb 27 '16 at 17:53
2
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ If we use more bits, like 10+ bits, we can point multiple id's to the same server, allowing for changing the server count dynamically by moving the pointers, and still have good load balance. $\endgroup$ – Filip Haglund Feb 27 '16 at 17:56
1
$\begingroup$

Yes. ​ It's…

hash on

prefixfree(server id) + prefixfree(userid) + prefixfree(request-id) + nonce

until the prefix of the hash has n bits of zeroes.

For more information on prefixfree, check the related Wikipedia article.

Improve this answer
$\endgroup$
  • $\begingroup$ This assumes that the client knows what server it uses, so load-balanced servers would have to share state to avoid a single request-id being used once on each server, right? $\endgroup$ – Filip Haglund Dec 29 '15 at 19:43
  • $\begingroup$ I don't know how to formalize things; it might be possible for the servers to use communication instead of state. $\endgroup$ – user991 Dec 29 '15 at 20:06
  • $\begingroup$ Simply put: if the client doesn't know what server it connects to, since they are load balanced, what should it use for the server-id field? This looks like my first example solution that fails condition 1. $\endgroup$ – Filip Haglund Dec 29 '15 at 20:48
  • $\begingroup$ In that case, It uses the id of a random one of the servers. $\endgroup$ – user991 Dec 29 '15 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.