Write proposal for proof-of-work service
aagbsn and I dreamed up a simple proof-of-work service a week or two ago. It would work like this:
A web service runs at a url and provides signed or HMACed products-of-primes combined with a timestamp and a unique sequence number. The primes should be chosen such that factoring their product takes on the order of several seconds on most hardware.
Torbutton periodically fetches batches of these products-of-primes over Tor and factors them into their component integers in a background thread, until a reserve pool is met.
DoS-sensitive websites can advertise an additional header and/or accept N factored products issued from within the last T minutes in exchange for captcha-free/unblocked service. The products are encoded as either cookies, GET parameters, or POST parameters.
Factored products can be reused on a site until the user either clicks "New Identity" or they become too old for use at a particular site.
This system provides two knobs for sites to throttle traffic in response to current scraping levels. On days where scraping query volume is low, sites can be lenient in terms of how many proof of work units they require for use, and how recently they must have been issued. If scraping volume increases, sites can increase N and/or reduce T, to change the amount of work that must be done by scrapers in order to receive service.
Alternatively or in addition, we can investigate using a Nymble-like (or possibly simpler) system to allow the creation of single identifiers in exchange for some number of proof-of-work units as well. Converting units of work into identifiers (and preventing re-use of work using sequence numbers) may simplify implementation on the DoS-sensitive service side, by enabling the service to concern itself only with limiting the rate of queries per identifier.