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