no circuit loops?

[Roger Dingledine]

On Thu, Oct 23, 2003 at 01:06:06PM -0400, Paul Syverson wrote:
> I was just looking over the tor-spec and was thereby reminded that we
> don't allow any loops in a circuit. I don't remember talking about
> this. Remind me if we have already.

Oops. The spec is wrong.

The current deal is that we choose paths such that no two adjacent
hops are the same router (where router also means its twins). This is
enforced because routers don't connect to their twins (or to themselves,
obviously), and when we get a new onionskin, if we're not already
connected to the next hop we send back a destroy.

The main reason why we've needed to allow repeats up until now is because
the test network was small, so disallowing them would often result in
no possible path.

But actually, the path choosing code is old and rickety. It still chooses
the whole path at the beginning, even though the path is actually built
incrementally. So if any hop fails to build it just gives up.

It's tricky because we have constraints, such as who can be our exit
node, that mean we need to think ahead a little bit, so we don't e.g.
choose the only valid exit node as our second-to-last hop and then look
around for an exit node.

Fixing it up is on my todo list,
* So we can more robustly handle failed nodes
* So we can extend circuits, or make new ones, while the socks application
  is waiting for us. This way we can retry connections that fail, rather
  than just giving the application a "sorry, no" response.

> On the other hand, the absence of loops gives information about a
> circuit. E.g., there is an observer on OR_1's network connections.
> Alice connects through OR_1, OR_2, OR_3, OR_4, OR_5.  OR_4 is bad.

Remember that for performance and usability our path length is actually
just OR_1, OR_2 by default. So the whole loop question is a bit moot. :)

--Roger