Making the rendezvous faster

[Roger Dingledine <arma@mit.edu>]

Now that we've got a bit of experience with building and using the
rendezvous system, I have some proposals for making it faster. Once you
convince me that they won't hurt anonymity much, I should implement them.

The basic problem is that the initial rendezvous is slow, because it
requires two new circuits on Alice's side and one new one on Bob's side.

a) Alice could preemptively build a rendezvous circuit, and establish
a rendezvous cookie, before she even knows the service ID in question.
Then when she needs a rendezvous circ, she first checks to see if there
are any established rendcircs with the special service ID zero, and
cannibalizes one. So building the rendezvous circ isn't in the critical
path anymore.

b) Intro points could ack or nack whether they've heard of that
service ID. One of the mis-behaviors we're seeing is that sometimes
Bob isn't established on some of the intro points he's advertised,
so Alice introduces, the Tor node quietly logs "No intro circ found",
and Alice patiently waits at her rendezvous point (and eventually times
out). If the intro point could send something to Alice saying "sorry,
he's not here", then Alice could respond much more quickly.
b') If we do this, can Alice re-use her rendezvous point after a denied
introduction? Can she re-use the intro circ by extending it to the
next try?

c) Alice could preemptively build n-1 hops of the intro circuit. Then
when she learns about an intro point, she can build the final hop and
send the introduction.
OR
c') Alice could cannibalize an established unused general circuit for her
intro circs. She does this by extending the open circ to the chosen intro
point, and then introducing. Having n+1 hops rather than n hops in the
intro circ doesn't affect performance much because it's only used briefly.

d) Bob could preemptively build n-1 hops of the rend circ. Then when he
learns about Alice's rend point, he can build the final hop and send
the rendezvous. We probably don't want him to cannibalize-and-extend
another circ, since another hop in a rendezvous circ means more latency.

Whether we choose c) or c') depends on the answers to b'). Based on d),
it looks like we'll be building the "n-1 hops" primitive anyway. Maybe
we should build the "extend to another hop before you're open" primitive
too. Hm. Thoughts on which Alice should prefer? Any other ideas on how
to speed the rendezvous?

--Roger