8 Note: This is an attempt to specify Tor as currently implemented. Future
9 versions of Tor will implement improved algorithms.
11 This document tries to cover how Tor chooses to build circuits and assign
12 streams to circuits. Other implementations MAY take other approaches, but
13 implementors should be aware of the anonymity and load-balancing implications
16 THIS SPEC ISN'T DONE OR CORRECT YET.
20 Tor begins building circuits as soon as it has enough directory
21 information to do so (see section 5.1 of dir-spec.txt). Some circuits are
22 built preemptively because we expect to need them later (for user
23 traffic), and some are built because of immediate need (for user traffic
24 that no current circuit can handle, for testing the network or our
25 reachability, and so on).
27 When a client application creates a new stream (by opening a SOCKS
28 connection or launching a resolve request), we attach it to an appropriate
29 open circuit if one exists, or wait if an appropriate circuit is
30 in-progress. We launch a new circuit only
31 if no current circuit can handle the request. We rotate circuits over
32 time to avoid some profiling attacks.
34 To build a circuit, we choose all the nodes we want to use, and then
35 construct the circuit. Sometimes, when we want a circuit that ends at a
36 given hop, and we have an appropriate unused circuit, we "cannibalize" the
37 existing circuit and extend it to the new terminus.
39 These processes are described in more detail below.
41 This document describes Tor's automatic path selection logic only; path
42 selection can be overridden by a controller (with the EXTENDCIRCUIT and
43 ATTACHSTREAM commands). Paths constructed through these means may
44 violate some constraints given below.
48 A "path" is an ordered sequence of nodes, not yet built as a circuit.
50 A "clean" circuit is one that has not yet been used for any traffic.
52 A "fast" or "stable" or "valid" node is one that has the 'Fast' or
53 'Stable' or 'Valid' flag
54 set respectively, based on our current directory information. A "fast"
55 or "stable" circuit is one consisting only of "fast" or "stable" nodes.
57 In an "exit" circuit, the final node is chosen based on waiting stream
58 requests if any, and in any case it avoids nodes with exit policy of
59 "reject *:*". An "internal" circuit, on the other hand, is one where
60 the final node is chosen just like a middle node (ignoring its exit
63 A "request" is a client-side stream or DNS resolve that needs to be
66 A "pending" circuit is one that we have started to build, but which has
69 A circuit or path "supports" a request if it is okay to use the
70 circuit/path to fulfill the request, according to the rules given below.
71 A circuit or path "might support" a request if some aspect of the request
72 is unknown (usually its target IP), but we believe the path probably
73 supports the request according to the rules given below.
79 2.1.1. Clients build circuits preemptively
81 When running as a client, Tor tries to maintain at least a certain
82 number of clean circuits, so that new streams can be handled
83 quickly. To increase the likelihood of success, Tor tries to
84 predict what circuits will be useful by choosing from among nodes
85 that support the ports we have used in the recent past (by default
86 one hour). Specifically, on startup Tor tries to maintain one clean
87 fast exit circuit that allows connections to port 80, and at least
88 two internal circuits in case we get a resolve request or hidden
89 service request (at least three internal circuits if we _run_ a
92 After that, Tor will adapt the circuits that it preemptively builds
93 based on the requests it sees from the user: it tries to have a clean
94 fast exit circuit available for every port seen recently (one circuit
95 is adequate for many predicted ports -- it doesn't keep a separate
96 circuit for each port), and it tries to have the above internal
97 circuits available if we've seen resolves or hidden service activity
98 recently. If there are 12 clean circuits open, it doesn't open more
99 even if it has more predictions. Lastly, note that if there are no
100 requests from the user for an hour, Tor will predict no use and build
101 no preemptive circuits.
103 The Tor client SHOULD NOT store its list of predicted requests to a
106 2.1.2. Clients build circuits on demand
108 Additionally, when a client request exists that no circuit (built or
109 pending) might support, we create a new circuit to support the request.
110 We do so by picking a request arbitrarily, launching a circuit to
111 support it, and repeating until every unattached request might be
112 supported by a pending or built circuit.
114 For hidden service interations, we can "cannibalize" a clean internal
115 circuit if one is available, so we don't need to build those circuits
116 from scratch on demand.
118 We can also cannibalize clean circuits when the client asks to exit
119 at a given node -- either via mapaddress or the ".exit" notation,
120 or because the destination is running at the same location as an
123 2.1.3. Servers build circuits for testing reachability
125 Tor servers test reachability of their ORPort on start and whenever
126 their IP address changes.
129 2.1.4. Hidden-service circuits
133 2.1.5. Rate limiting of failed circuits
135 If we fail to build a circuit N times in a X second period (see Section
136 2.3 for how this works), we stop building circuits until the X seconds
140 2.1.6. When to tear down circuits
143 2.2. Path selection and constraints
145 We choose the path for each new circuit before we build it. We choose the
146 exit node first, followed by the other nodes in the circuit. All paths
147 we generate obey the following constraints:
148 - We do not choose the same router twice for the same path.
149 - We do not choose any router in the same family as another in the same
151 - We do not choose more than one router in a given /16 subnet
152 (unless EnforceDistinctSubnets is 0).
153 - We don't choose any non-running or non-valid router unless we have
154 been configured to do so. By default, we are configured to allow
155 non-valid routers in "middle" and "rendezvous" positions.
156 - If we're using Guard nodes, the first node must be a Guard (see 5
158 - XXXX Choosing the length
160 For circuits that do not need to be not "fast", when choosing among
161 multiple candidates for a path element, we choose randomly.
163 For "fast" circuits, we pick a given router as an exit with probability
164 proportional to its advertised bandwidth [the smaller of the 'rate' and
165 'observed' arguments to the "bandwidth" element in its descriptor]. If a
166 router's advertised bandwidth is greater than MAX_BELIEVABLE_BANDWIDTH
167 (1.5 MB/s), we clip to that value.
169 For non-exit positions on "fast" circuits, we pick routers as above, but
170 we weight the clipped advertised bandwidth of Exit-flagged nodes depending
171 on the fraction of bandwidth available from non-Exit nodes. Call the
172 total clipped advertised bandwidth for Exit nodes under consideration E,
173 and the total clipped advertised bandwidth for non-Exit nodes under
174 consideration N. If E<N/2, we do not consider Exit-flagged nodes.
175 Otherwise, we weight their bandwidth with the factor (E-N/2)/(N+E-N/2) ==
176 (2E - N)/(2E + N). This ensures that bandwidth is evenly distributed over
177 nodes in 3-hop paths.
179 Additionally, we may be building circuits with one or more requests in
180 mind. Each kind of request puts certain constraints on paths:
182 - All service-side introduction circuits and all rendezvous paths
184 - All connection requests for connections that we think will need to
185 stay open a long time require Stable circuits. Currently, Tor decides
186 this by examining the request's target port, and comparing it to a
187 list of "long-lived" ports. (Default: 21, 22, 706, 1863, 5050,
188 5190, 5222, 5223, 6667, 6697, 8300.)
189 - DNS resolves require an exit node whose exit policy is not equivalent
191 - Reverse DNS resolves require a version of Tor with advertised eventdns
192 support (available in Tor 0.1.2.1-alpha-dev and later).
193 - All connection requests require an exit node whose exit policy
194 supports their target address and port (if known), or which "might
195 support it" (if the address isn't known). See 2.2.1.
196 - Rules for Fast? XXXXX
198 2.2.1. Choosing an exit
200 If we know what IP address we want to resolve, we can trivially tell
201 whether a given router will support it by simulating its declared
204 Because we often connect to addresses of the form hostname:port, we do not
205 always know the target IP address when we select an exit node. In these
206 cases, we need to pick an exit node that "might support" connections to a
207 given address port with an unknown address. An exit node "might support"
208 such a connection if any clause that accepts any connections to that port
209 precedes all clauses (if any) that reject all connections to that port.
211 Unless requested to do so by the user, we never choose an exit server
212 flagged as "BadExit" by more than half of the authorities who advertise
213 themselves as listing bad exits.
215 2.2.2. User configuration
217 Users can alter the default behavior for path selection with configuration
220 - If "ExitNodes" is provided, then every request requires an exit node on
221 the ExitNodes list. (If a request is supported by no nodes on that list,
222 and StrictExitNodes is false, then Tor treats that request as if
223 ExitNodes were not provided.)
225 - "EntryNodes" and "StrictEntryNodes" behave analogously.
227 - If a user tries to connect to or resolve a hostname of the form
228 <target>.<servername>.exit, the request is rewritten to a request for
229 <target>, and the request is only supported by the exit whose nickname
230 or fingerprint is <servername>.
232 2.3. Handling failure
234 If an attempt to extend a circuit fails (either because the first create
235 failed or a subsequent extend failed) then the circuit is torn down and is
236 no longer pending. (XXXX really?) Requests that might have been
237 supported by the pending circuit thus become unsupported, and a new
238 circuit needs to be constructed.
240 If a stream "begin" attempt fails with an EXITPOLICY error, we
241 decide that the exit node's exit policy is not correctly advertised,
242 so we treat the exit node as if it were a non-exit until we retrieve
243 a fresh descriptor for it.
247 3. Attaching streams to circuits
249 When a circuit that might support a request is built, Tor tries to attach
250 the request's stream to the circuit and sends a BEGIN or RESOLVE relay
251 cell as appropriate. If the request completes unsuccessfully, Tor
252 considers the reason given in the CLOSE relay cell. [XXX yes, and?]
255 After a request has remained unattached for [XXXX interval?], Tor
256 abandons the attempt and signals an error to the client as appropriate
257 (e.g., by closing the SOCKS connection).
259 XXX Timeouts and when Tor auto-retries.
260 * What stream-end-reasons are appropriate for retrying.
262 If no reply to BEGIN/RESOLVE, then the stream will timeout and fail.
264 4. Hidden-service related circuits
266 XXX Tracking expected hidden service use (client-side and hidserv-side)
277 (From some emails by arma)
279 Right now the code exists to pick helper nodes, store our choices to
280 disk, and use them for our entry nodes. But there are three topics
281 to tackle before I'm comfortable turning them on by default. First,
282 how to handle churn: since Tor nodes are not always up, and sometimes
283 disappear forever, we need a plan for replacing missing helpers in a
284 safe way. Second, we need a way to distinguish "the network is down"
285 from "all my helpers are down", also in a safe way. Lastly, we need to
286 examine the situation where a client picks three crummy helper nodes
287 and is forever doomed to a lousy Tor experience. Here's my plan:
290 - Keep track of whether you have ever actually established a
291 connection to each helper. Any helper node in your list that you've
292 never used is ok to drop immediately. Also, we don't save that
294 - If all our helpers are down, we need more helper nodes: add a new
295 one to the *end*of our list. Only remove dead ones when they have
296 been gone for a very long time (months).
297 - Pick from the first n (by default 3) helper nodes in your list
298 that are up (according to the network-statuses) and reachable
299 (according to your local firewall config).
300 - This means that order matters when writing/reading them to disk.
302 How to deal with network down.
303 - While all helpers are down/unreachable and there are no established
304 or on-the-way testing circuits, launch a testing circuit. (Do this
305 periodically in the same way we try to establish normal circuits
306 when things are working normally.)
307 (Testing circuits are a special type of circuit, that streams won't
308 attach to by accident.)
309 - When a testing circuit succeeds, mark all helpers up and hold
310 the testing circuit open.
311 - If a connection to a helper succeeds, close all testing circuits.
312 Else mark that helper down and try another.
313 - If the last helper is marked down and we already have a testing
314 circuit established, then add the first hop of that testing circuit
315 to the end of our helper node list, close that testing circuit,
316 and go back to square one. (Actually, rather than closing the
317 testing circuit, can we get away with converting it to a normal
318 circuit and beginning to use it immediately?)
320 How to pick non-sucky helpers.
321 - When we're picking a new helper nodes, don't use ones which aren't
322 reachable according to our local ReachableAddresses configuration.
323 (There's an attack here: if I pick my helper nodes in a very
324 restrictive environment, say "ReachableAddresses 18.0.0.0/255.0.0.0:*",
325 then somebody watching me use the network from another location will
326 guess where I first joined the network. But let's ignore it for now.)
327 - Right now we choose new helpers just like we'd choose any entry
328 node: they must be "stable" (claim >1day uptime) and "fast" (advertise
329 >10kB capacity). In 0.1.1.11-alpha, clients let dirservers define
330 "stable" and "fast" however they like, and they just believe them.
331 So the next step is to make them a function of the current network:
332 e.g. line up all the 'up' nodes in order and declare the top
333 three-quarter to be stable, fast, etc, as long as they meet some
335 - If that's not sufficient (it won't be), dirservers should introduce
336 a new status flag: in additional to "stable" and "fast", we should
337 also describe certain nodes as "entry", meaning they are suitable
338 to be chosen as a helper. The first difference would be that we'd
339 demand the top half rather than the top three-quarters. Another
340 requirement would be to look at "mean time between returning" to
341 ensure that these nodes spend most of their time available. (Up for
342 two days straight, once a month, is not good enough.)
343 - Lastly, we need a function, given our current set of helpers and a
344 directory of the rest of the network, that decides when our helper
345 set has become "too crummy" and we need to add more. For example,
346 this could be based on currently advertised capacity of each of
347 our helpers, and it would also be based on the user's preferences
348 of speed vs. security.
353 > I am a bit concerned with performance if we are to have e.g. two out of
354 > three helper nodes down or unreachable. How often should Tor check if
355 > they are back up and running?
357 Right now Tor believes a threshold of directory servers when deciding
358 whether each server is up. When Tor observes a server to be down
359 (connection failed or building the first hop of the circuit failed),
360 it marks it as down and doesn't try it again, until it gets a new
361 network-status from somebody, at which point it takes a new concensus
362 and marks the appropriate servers as up.
364 According to sec 5.1 of dir-spec.txt, the client will try to fetch a new
365 network-status at least every 30 minutes, and more often in certain cases.
367 With the proposed scheme, we'll also mark all our helpers as up shortly
368 after the last one is marked down.
370 > When should there be
371 > added an extra node to the helper node list? This is kind of an
372 > important threshold?
374 I agree, this is an important question. I don't have a good answer yet. Is
375 it terrible, anonymity-wise, to add a new helper every time only one of
376 your helpers is up? Notice that I say add rather than replace -- so you'd
377 only use this fourth helper when one of your main three helpers is down,
378 and if three of your four are down, you'd add a fifth, but only use it
379 when two of the first four are down, etc.
381 In fact, this may be smarter than just picking a random node for your
382 testing circuit, because if your network goes up and down a lot, then
383 eventually you have a chance of using any entry node in the network for
384 your testing circuit.
386 We have a design choice here. Do we only try to use helpers for the
387 connections that will have streams on them (revealing our communication
388 partners), or do we also want to restrict the overall set of nodes that
389 we'll connect to, to discourage people from enumerating all Tor clients?
391 I'm increasingly of the belief that we want to hide our presence too,
392 based on the fact that Steven and George and others keep coming up with
393 attacks that start with "Assuming we know the set of users".
395 If so, then here's a revised "How to deal with network down" section:
397 1) When a helper is marked down or the helper list shrinks, and as
398 a result the total number of helpers that are either (up and
399 reachable) or (reachable but never connected to) is <= 1, then pick
400 a new helper and add it to the end of the list.
401 [We count nodes that have never been connected to, since otherwise
402 we might keep on adding new nodes before trying any of them. By
403 "reachable" I mean "is allowed by ReachableAddresses".]
404 2) When you fail to connect to a helper that has never been connected
405 to, you remove him from the list right then (and the above rule
407 3) When you succeed at connecting to a helper that you've never
408 connected to before, mark all reachable helpers earlier in the list
409 as up, and close that circuit.
410 [We close the circuit, since if the other helpers are now up, we
411 prefer to use them for circuits that will reveal communication
414 This certainly seems simpler. Are there holes that I'm missing?
416 > If running from a laptop you will meet different firewall settings, so
417 > how should Helper Nodes settings keep up with moving from an open
418 > ReachableAddresses to a FascistFirewall setting after the helper nodes
419 > have been selected?
421 I added the word "reachable" to three places in the above list, and I
422 believe that totally solves this question.
424 And as a bonus, it leads to an answer to Nick's attack ("If I pick
425 my helper nodes all on 18.0.0.0:*, then I move, you'll know where I
426 bootstrapped") -- the answer is to pick your original three helper nodes
427 without regard for reachability. Then the above algorithm will add some
428 more that are reachable for you, and if you move somewhere, it's more
429 likely (though not certain) that some of the originals will become useful.
430 Is that smart or just complex?
432 > What happens if(when?) performance of the third node is bad?
434 My above solution solves this a little bit, in that we always try to
435 have two nodes available. But what if they are both up but bad? I'm not
436 sure. As my previous mail said, we need some function, given our list
437 of helpers and the network directory, that will tell us when we're in a
438 bad situation. I can imagine some simple versions of this function --
439 for example, when both our working helpers are in the bottom half of
440 the nodes, ranked by capacity.
442 But the hard part: what's the remedy when we decide there's something
443 to fix? Do we add a third, and now we have two crummy ones and a new
444 one? Or do we drop one or both of the bad ones?
446 Perhaps we believe the latest claim from the network-status concensus,
447 and we count a helper the dirservers believe is crummy as "not worth
448 trying" (equivalent to "not reachable under our current ReachableAddresses
449 config") -- and then the above algorithm would end up adding good ones,
450 but we'd go back to the originals if they resume being acceptable? That's
451 an appealing design. I wonder if it will cause the typical Tor user to
452 have a helper node list that comprises most of the network, though. I'm
455 > Another point you might want to keep in mind, is the possibility to
456 > reuse the code in order to add a second layer helper node (meaning node
457 > number two) to "protect" the first layer (node number one) helper nodes.
458 > These nodes should be tied to each of the first layer nodes. E.g. there
459 > is one helper node list, as described in your mail, for each of the
460 > first layer nodes, following their create/destroy.
462 True. Does that require us to add a fourth hop to our path length,
463 since the first hop is from a limited set, the second hop is from a
464 limited set, and the third hop might also be constrained because, say,
465 we're asking for an unusual exit port?
467 > Another of the things might worth adding to the to do list is
468 > localization of server (helper) nodes. Making it possible to pick
469 > countries/regions where you do (not) want your helper nodes located. (As
470 > in "HelperNodesLocated us,!eu" etc.) I know this requires the use of
471 > external data and may not be worth it, but it _could_ be integrated at
472 > the directory servers only -- adding a list of node IP's and e.g. a
473 > country/region code to the directory and thus reduce the overhead. (?)
474 > Maybe extending the Family-term?
476 I think we are heading towards doing path selection based on geography,
477 but I don't have a good sense yet of how that will actually turn out --
478 that is, with what mechanism Tor clients will learn the information they
479 need. But this seems to be something that is orthogonal to the rest of
480 this discussion, so I look forward to having somebody else solve it for
481 us, and fitting it in when it's ready. :)
483 > And I would like to keep an option to pick the first X helper nodes
484 > myself and then let Tor extend this list if these nodes are down (like
485 > EntryNodes in current code). Even if this opens up for some new types of
486 > "relationship" attacks.
488 Good idea. Here's how I'd like to name these:
490 The "EntryNodes" config option is a list of seed helper nodes. When we
491 read EntryNodes, any node listed in entrynodes but not in the current
492 helper node list gets *pre*pended to the helper node list.
494 The "NumEntryNodes" config option (currently called NumHelperNodes)
495 specifies the number of up, reachable, good-enough helper nodes that
496 will make up the pool of possible choices for first hop, counted from
497 the front of the helper node list until we have enough.
499 The "UseEntryNodes" config option (currently called UseHelperNodes)
500 tells us to turn on all this helper node behavior. If you set EntryNodes,
501 then this option is implied.
503 The "StrictEntryNodes" config option, provided for backward compatibility
504 and for debugging, means a) we replace the helper node list with the
505 current EntryNodes list, and b) whenever we would do an operation that
506 alters the helper node list, we don't. (Yes, this means that if all the
507 helper nodes are down, we lose until we mark them up again. But this is
510 > I am sure my next point has been asked before, but what about testing
511 > the current speed of the connections when looking for new helper nodes,
512 > not only testing the connectivity? I know this might contribute to a lot
513 > of overhead in the network, but if this only occur e.g. when using
514 > helper nodes as a Hidden Service it might not have that large an impact,
515 > but could help availability for the services?
517 If we're just going to be testing them when we're first picking them,
518 then it seems we can do the same thing by letting the directory servers
519 test them. This has the added benefit that all the (behaving) clients
520 use the same data, so they don't end up partitioned by a node that
521 (for example) performs selectively for his victims.
523 Another idea would be to periodically keep track of what speeds you get
524 through your helpers, and make decisions from this. The reason we haven't
525 done this yet is because there are a lot of variables -- perhaps the
526 web site is slow, perhaps some other node in the path is slow, perhaps
527 your local network is slow briefly, perhaps you got unlucky, etc. I
528 believe that over time (assuming the user has roughly the same browsing
529 habits) all of these would average out and you'd get a usable answer,
530 but I don't have a good sense of how long it would take to converge,
531 so I don't know whether this would be worthwhile.
533 > BTW. I feel confortable with all the terms helper/entry/contact nodes,
534 > but I think you (the developers) should just pick one and stay with it
535 > to avoid confusion.
537 I think I'm going to try to co-opt the term 'Entry' node for this
538 purpose. We're going to have to keep referring to helper nodes for the
539 research community for a while though, so they realize that Tor does
540 more than just let users ask for certain entry nodes.
544 ============================================================
545 Some stuff that worries me about entry guards. 2006 Jun, Nickm.
547 1. It is unlikely for two users to have the same set of entry guards.
549 2. Observing a user is sufficient to learn its entry guards.
551 3. So, as we move around, we leak our