Idea: Hashcash based HTTP server throttling

Gordon Mohr
Fri, 24 Aug 2001 18:28:37 -0700

Hey, HTTP server/app gurus! Comments wanted on the following idea...

Let's say you have an HTTP server, serving out valuable 
information through GETs, that might get so heavily loaded 
that its availability suffers. You'd like it to be able to 
"ration" access in such situations, with a bias against 
frivolous/volume queries, while maintaining high-liklihood 
that individual queries can be answered in a bounded amount 
of time.

Proposal: when in such a loaded situation, demand that requestors 
supply along with their request a string which is a partial
hash collision with their target-URI. 

If such a token is not provided, respond with a "503" error
code, and a header indicating the type of partial collision
required. For example:

  HTTP/1.1 503 rationing mode!
  Retry-after: 99999999
  Retry-hashcash: sha1;16

This indicates that the client should only retry its request
after finding a 16-bit prefix-collision with the target-URI
it has requested.

The client would demonstrate the collision via headers on
the request like:

  GET / HTTP/1.1
  Ration-hashcash: 0xC7046E

To prevent reuse of hashcash tokens, across servers or time,
a nonce could be supplied with the "retry-hashcash" header, 
changed as often or as rarely as the server wishes.

Servers would set their collision-demand parameters to 
whatever level keeps them humming at nearly-full capacity,
while still answering all hashcash-paid requests promptly.

To discourage the deployment of naive, just-keep-asking
clients, the server could require a token, somewhat random
amount of hashcash at all times, so that to use the service
at all, you'd need to have a minimally hashcash-aware client.

Possible benefits:
  - A virtual queue is maintained, with only client-side
    per-patron state.
  - Clients can give a reasonably accurate indication of 
    time remaining to users, without ongoing communication
    with server.
  - If requests can be served in multiple ways, from
    multiple places, clients can use hashcash-demands
    as feedback indicating when it is or isn't worthwhile
    to try secondary sources.

Can anyone think of problems with this approach? Other
potential applications?

- Gordon