There are a couple approaches to consider.
POW via hashing goes for a relatively simple to implement approach. However, this incurs a high cost for all clients, and also environmental damage, per previous email.
Another approach similar to the above (but more environmentally friendly) can be Proof of Storage (or proof of space), as in https://eprint.iacr.org/2013/796.pdf
With both of the above approaches, there will be a tradeoff to what the cost is to deter a would-be attacker, versus the cost to real but bandwidth/cpu limited clients, such as on mobile platforms.
More involved approaches include anonymous blacklists/whitelists, blinded tokens, etc. Previous work has been done in this space, here is one example: https://crysp.uwaterloo.ca/courses/pet/F11/cache/www-users.cs.umn.edu/~hoppe...
While designs using a token-based approach such as what Jeff mentions below may require more design/thought up front, the benefit is that clients won't be penalized every time they connect to an onion service. Considering the goal of scaling of the Tor network and of "onions everywhere", this seems like a good tradeoff.
On 2019-06-16 18:03, Jeff Burdges wrote:
As a rule, proof-of-work does not really deliver the security properties people envision. We’ve no really canonical anti-sibel criteria in this case, but maybe some mixed approach works:
First, introduction points have a default mode in which they rate limit new connections and impose some artificial latency. Second, an onion service can issue rerandomizable certificates, blind signature, or oblivious PRFs that provide faster and non-rate limited access through a specific introduction points.
Coconut would suffice for the rerandomizable certificates of course, but sounds like overkill.. and slow.
We should consider an oblivious PRF for this use case too:
It’s easy to make an oblivious PRF from the batched DLEQ proof implemented in https://github.com/w3f/schnorrkel/blob/master/src/vrf.rs I suppose Tor might adapt this to not use Ristretto, or maybe choose an Ed25519 to Ristretto map, but regardless the whole scheme is not too much more complex than a Schnorr signature.
We require the oblivious PRF secret key be known by both the introduction point for verification and the onion service for issuing. In this, we do not share the oblivious PRF key among different introduction points because introduction points cannot share a common double redemption database anyways.
I’m worried about different oblivious PRF keys being used to tag different users though. There are complex mechanisms to prevent this using curves created with Cocks-Pinch, but..
We could simply employ blind signatures however, which avoids sharing any secrets, and thus permits binding the key uniquely to the hidden service. As a rule, blind signatures require either slow cryptography like pairings or RSA, or else issuing takes several round trips and have weak soundness. I think weak soundness sounds workable here, although I’m no longer sure about all the issues with such scheme.
Best, Jeff
p.s. We’re hiring in security https://web3.bamboohr.com/jobs/view.php?id=38 and several research areas like cryptography https://web3.bamboohr.com/jobs/view.php?id=29
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev