path-spec.txt

$Id: path-spec.txt 17215 2008-11-08 06:32:46Z arma $

                           Tor Path Specification

                              Roger Dingledine
                               Nick Mathewson

Note: This is an attempt to specify Tor as currently implemented.  Future
versions of Tor will implement improved algorithms.

This document tries to cover how Tor chooses to build circuits and assign
streams to circuits.  Other implementations MAY take other approaches, but
implementors should be aware of the anonymity and load-balancing implications
of their choices.

                    THIS SPEC ISN'T DONE YET.

1. General operation

   Tor begins building circuits as soon as it has enough directory
   information to do so (see section 5 of dir-spec.txt).  Some circuits are
   built preemptively because we expect to need them later (for user
   traffic), and some are built because of immediate need (for user traffic
   that no current circuit can handle, for testing the network or our
   reachability, and so on).

   When a client application creates a new stream (by opening a SOCKS
   connection or launching a resolve request), we attach it to an appropriate
   open circuit if one exists, or wait if an appropriate circuit is
   in-progress. We launch a new circuit only
   if no current circuit can handle the request.  We rotate circuits over
   time to avoid some profiling attacks.

   To build a circuit, we choose all the nodes we want to use, and then
   construct the circuit.  Sometimes, when we want a circuit that ends at a
   given hop, and we have an appropriate unused circuit, we "cannibalize" the
   existing circuit and extend it to the new terminus.

   These processes are described in more detail below.

   This document describes Tor's automatic path selection logic only; path
   selection can be overridden by a controller (with the EXTENDCIRCUIT and
   ATTACHSTREAM commands).  Paths constructed through these means may
   violate some constraints given below.

1.1. Terminology

   A "path" is an ordered sequence of nodes, not yet built as a circuit.

   A "clean" circuit is one that has not yet been used for any traffic.

   A "fast" or "stable" or "valid" node is one that has the 'Fast' or
   'Stable' or 'Valid' flag
   set respectively, based on our current directory information.  A "fast"
   or "stable" circuit is one consisting only of "fast" or "stable" nodes.

   In an "exit" circuit, the final node is chosen based on waiting stream
   requests if any, and in any case it avoids nodes with exit policy of
   "reject *:*". An "internal" circuit, on the other hand, is one where
   the final node is chosen just like a middle node (ignoring its exit
   policy).

   A "request" is a client-side stream or DNS resolve that needs to be
   served by a circuit.

   A "pending" circuit is one that we have started to build, but which has
   not yet completed.

   A circuit or path "supports" a request if it is okay to use the
   circuit/path to fulfill the request, according to the rules given below.
   A circuit or path "might support" a request if some aspect of the request
   is unknown (usually its target IP), but we believe the path probably
   supports the request according to the rules given below.

2. Building circuits

2.1. When we build

2.1.1. Clients build circuits preemptively

   When running as a client, Tor tries to maintain at least a certain
   number of clean circuits, so that new streams can be handled
   quickly.  To increase the likelihood of success, Tor tries to
   predict what circuits will be useful by choosing from among nodes
   that support the ports we have used in the recent past (by default
   one hour). Specifically, on startup Tor tries to maintain one clean
   fast exit circuit that allows connections to port 80, and at least
   two fast clean stable internal circuits in case we get a resolve
   request or hidden service request (at least three if we _run_ a
   hidden service).

   After that, Tor will adapt the circuits that it preemptively builds
   based on the requests it sees from the user: it tries to have two fast
   clean exit circuits available for every port seen within the past hour
   (each circuit can be adequate for many predicted ports -- it doesn't
   need two separate circuits for each port), and it tries to have the
   above internal circuits available if we've seen resolves or hidden
   service activity within the past hour. If there are 12 or more clean
   circuits open, it doesn't open more even if it has more predictions.

   Only stable circuits can "cover" a port that is listed in the
   LongLivedPorts config option. Similarly, hidden service requests
   to ports listed in LongLivedPorts make us create stable internal
   circuits.

   Note that if there are no requests from the user for an hour, Tor
   will predict no use and build no preemptive circuits.

   The Tor client SHOULD NOT store its list of predicted requests to a
   persistent medium.

2.1.2. Clients build circuits on demand

   Additionally, when a client request exists that no circuit (built or
   pending) might support, we create a new circuit to support the request.
   For exit connections, we pick an exit node that will handle the
   most pending requests (choosing arbitrarily among ties), launch a
   circuit to end there, and repeat until every unattached request
   might be supported by a pending or built circuit. For internal
   circuits, we pick an arbitrary acceptable path, repeating as needed.

   In some cases we can reuse an already established circuit if it's
   clean; see Section 2.3 (cannibalizing circuits) for details.

2.1.3. Servers build circuits for testing reachability and bandwidth

   Tor servers test reachability of their ORPort once they have
   successfully built a circuit (on start and whenever their IP address
   changes). They build an ordinary fast internal circuit with themselves
   as the last hop. As soon as any testing circuit succeeds, the Tor
   server decides it's reachable and is willing to publish a descriptor.

   We launch multiple testing circuits (one at a time), until we
   have NUM_PARALLEL_TESTING_CIRC (4) such circuits open. Then we
   do a "bandwidth test" by sending a certain number of relay drop
   cells down each circuit: BandwidthRate * 10 / CELL_NETWORK_SIZE
   total cells divided across the four circuits, but never more than
   CIRCWINDOW_START (1000) cells total. This exercises both outgoing and
   incoming bandwidth, and helps to jumpstart the observed bandwidth
   (see dir-spec.txt).

   Tor servers also test reachability of their DirPort once they have
   established a circuit, but they use an ordinary exit circuit for
   this purpose.

2.1.4. Hidden-service circuits

   See section 4 below.

2.1.5. Rate limiting of failed circuits

   If we fail to build a circuit N times in a X second period (see Section
   2.3 for how this works), we stop building circuits until the X seconds
   have elapsed.
   XXXX

2.1.6. When to tear down circuits

   XXXX

2.2. Path selection and constraints

   We choose the path for each new circuit before we build it.  We choose the
   exit node first, followed by the other nodes in the circuit.  All paths
   we generate obey the following constraints:
     - We do not choose the same router twice for the same path.
     - We do not choose any router in the same family as another in the same
       path.
     - We do not choose more than one router in a given /16 subnet
       (unless EnforceDistinctSubnets is 0).
     - We don't choose any non-running or non-valid router unless we have
       been configured to do so. By default, we are configured to allow
       non-valid routers in "middle" and "rendezvous" positions.
     - If we're using Guard nodes, the first node must be a Guard (see 5
       below)
     - XXXX Choosing the length

   For circuits that do not need to be "fast", when choosing among
   multiple candidates for a path element, we choose randomly.

   For "fast" circuits, we pick a given router as an exit with probability
   proportional to its advertised bandwidth [the smaller of the 'rate' and
   'observed' arguments to the "bandwidth" element in its descriptor].  If a
   router's advertised bandwidth is greater than MAX_BELIEVABLE_BANDWIDTH
   (currently 10 MB/s), we clip to that value.

   For non-exit positions on "fast" circuits, we pick routers as above, but
   we weight the clipped advertised bandwidth of Exit-flagged nodes depending
   on the fraction of bandwidth available from non-Exit nodes.  Call the
   total clipped advertised bandwidth for Exit nodes under consideration E,
   and the total clipped advertised bandwidth for all nodes under
   consideration T.  If E<T/3, we do not consider Exit-flagged nodes.
   Otherwise, we weight their bandwidth with the factor (E-T/3)/E. This 
   ensures that bandwidth is evenly distributed over nodes in 3-hop paths.

   Similarly, guard nodes are weighted by the factor (G-T/3)/G, and not
   considered for non-guard positions if this value is less than 0.

   Additionally, we may be building circuits with one or more requests in
   mind.  Each kind of request puts certain constraints on paths:

     - All service-side introduction circuits and all rendezvous paths
       should be Stable.
     - All connection requests for connections that we think will need to
       stay open a long time require Stable circuits.  Currently, Tor decides
       this by examining the request's target port, and comparing it to a
       list of "long-lived" ports. (Default: 21, 22, 706, 1863, 5050,
       5190, 5222, 5223, 6667, 6697, 8300.)
     - DNS resolves require an exit node whose exit policy is not equivalent
       to "reject *:*".
     - Reverse DNS resolves require a version of Tor with ...