1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
|
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.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
RFC 2119.
Tables of Contents
1. General operation
1.1. Terminology
1.2. A relay's bandwidth
2. Building circuits
2.1. When we build
2.1.0. We don't build circuits until we have enough directory info
2.1.1. Clients build circuits preemptively
2.1.2. Clients build circuits on demand
2.1.3. Relays build circuits for testing reachability and bandwidth
2.1.4. Hidden-service circuits
2.1.5. Rate limiting of failed circuits
2.1.6. When to tear down circuits
2.2. Path selection and constraints
2.2.1. Choosing an exit
2.2.2. User configuration
2.3. Cannibalizing circuits
2.4. Learning when to give up ("timeout") on circuit construction
2.4.1 Distribution choice and parameter estimation
2.4.2. How much data to record
2.4.3. How to record timeouts
2.4.4. Detecting Changing Network Conditions
2.4.5. Consensus parameters governing behavior
2.4.6. Consensus parameters governing behavior
2.5. Handling failure
3. Attaching streams to circuits
4. Hidden-service related circuits
5. Guard nodes
5.1. How consensus bandwidth weights factor into entry guard selection
6. Server descriptor purposes
7. Detecting route manipulation by Guard nodes (Path Bias)
7.1. Measuring path construction success rates
7.2. Measuring path usage success rates
7.3. Scaling success counts
7.4. Parametrization
7.5. Known barriers to enforcement
X. Old notes
X.1. Do we actually do this?
X.2. A thing we could do to deal with reachability.
X.3. Some stuff that worries me about entry guards. 2006 Jun, Nickm.
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).
[Newer versions of Tor (0.2.6.2-alpha and later):
If the consensus contains Exits (the typical case), Tor will build both
exit and internal circuits. When bootstrap completes, Tor will be ready
to handle an application requesting an exit circuit to services like the
World Wide Web.
If the consensus does not contain Exits, Tor will only build internal
circuits. In this case, earlier statuses will have included "internal"
as indicated above. When bootstrap completes, Tor will be ready to handle
an application requesting an internal circuit to hidden services at
".onion" addresses.
If a future consensus contains Exits, exit circuits may become available.]
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.
1.2. A relay's bandwidth
Old versions of Tor did not report bandwidths in network status
documents, so clients had to learn them from the routers' advertised
relay descriptors.
For versions of Tor prior to 0.2.1.17-rc, everywhere below where we
refer to a relay's "bandwidth", we mean its clipped advertised
bandwidth, computed by taking the smaller of the 'rate' and
'observed' arguments to the "bandwidth" element in the relay's
descriptor. If a router's advertised bandwidth is greater than
MAX_BELIEVABLE_BANDWIDTH (currently 10 MB/s), we clipped to that
value.
For more recent versions of Tor, we take the bandwidth value declared
in the consensus, and fall back to the clipped advertised bandwidth
only if the consensus does not have bandwidths listed.
2. Building circuits
2.1. When we build
2.1.0. We don't build circuits until we have enough directory info
There's a class of possible attacks where our directory servers
only give us information about the relays that they would like us
to use. To prevent this attack, we don't build multi-hop
circuits for real traffic (like those in 2.1.1, 2.1.2, 2.1.4
below) until we have enough directory information to be
reasonably confident this attack isn't being done to us.
Here, "enough" directory information is defined as:
* Having a consensus that's been valid at some point in the
last REASONABLY_LIVE_TIME interval (24 hours).
* Having enough descriptors that we could build at least some
fraction F of all bandwidth-weighted paths, without taking
ExitNodes/EntryNodes/etc into account.
(F is set by the PathsNeededToBuildCircuits option,
defaulting to the 'min_paths_for_circs_pct' consensus
parameter, with a final default value of 60%.)
* Having enough descriptors that we could build at least some
fraction F of all bandwidth-weighted paths, _while_ taking
ExitNodes/EntryNodes/etc into account.
(F is as above.)
* Having a descriptor for every one of the first
NUM_USABLE_PRIMARY_GUARDS guards among our primary guards. (see
guard-spec.txt)
We define the "fraction of bandwidth-weighted paths" as the product of
these three fractions.
* The fraction of descriptors that we have for nodes with the Guard
flag, weighted by their bandwidth for the guard position.
* The fraction of descriptors that we have for all nodes,
weighted by their bandwidth for the middle position.
* The fraction of descriptors that we have for nodes with the Exit
flag, weighted by their bandwidth for the exit position.
If the consensus has zero weighted bandwidth for a given kind of
relay (Guard, Middle, or Exit), Tor instead uses the fraction of relays
for which it has the descriptor (not weighted by bandwidth at all).
If the consensus lists zero exit-flagged relays, Tor instead uses the
fraction of middle relays.
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.
Clients consider a circuit to become "dirty" as soon as a stream is
attached to it, or some other request is performed over the circuit.
If a circuit has been "dirty" for at least MaxCircuitDirtiness seconds,
new circuits may not be attached to it.
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. Relays build circuits for testing reachability and bandwidth
Tor relays test reachability of their ORPort once they have
successfully built a circuit (on startup 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
relay 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 relays 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
Clients should tear down circuits (in general) only when those circuits
have no streams on them. Additionally, clients should tear-down
stream-less circuits only under one of the following conditions:
- The circuit has never had a stream attached, and it was created too
long in the past (based on CircuitsAvailableTimeout or
cbtlearntimeout, depending on timeout estimate status).
- The circuit is dirty (has had a stream attached), and it has been
dirty for at least MaxCircuitDirtiness.
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, front to
back. (In other words, for a 3-hop circuit, we first pick hop 3,
then hop 1, then hop 2.) 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. (Two routers are in the same family if each one lists the other
in the "family" entries of its descriptor.)
- 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 "fast" circuits, we only choose nodes with the Fast flag. For
non-"fast" circuits, all nodes are eligible.
For all circuits, we weight node selection according to router bandwidth.
We also weight the bandwidth of Exit and Guard flagged nodes depending on
the fraction of total bandwidth that they make up and depending upon the
position they are being selected for.
These weights are published in the consensus, and are computed as described
in Section "Computing Bandwidth Weights" of dir-spec.txt. They are:
Wgg - Weight for Guard-flagged nodes in the guard position
Wgm - Weight for non-flagged nodes in the guard Position
Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
Wmg - Weight for Guard-flagged nodes in the middle Position
Wmm - Weight for non-flagged nodes in the middle Position
Wme - Weight for Exit-flagged nodes in the middle Position
Wmd - Weight for Guard+Exit flagged nodes in the middle Position
Weg - Weight for Guard flagged nodes in the exit Position
Wem - Weight for non-flagged nodes in the exit Position
Wee - Weight for Exit-flagged nodes in the exit Position
Wed - Weight for Guard+Exit-flagged nodes in the exit Position
Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes
Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
If any of those weights is malformed or not present in a consensus,
clients proceed with the regular path selection algorithm setting
the weights to the default value of 10000.
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 advertised eventdns
support (available in Tor 0.1.2.1-alpha-dev and later).
- All connection requests require an exit node whose exit policy
supports their target address and port (if known), or which "might
support it" (if the address isn't known). See 2.2.1.
- Rules for Fast? XXXXX
2.2.1. Choosing an exit
If we know what IP address we want to connect to or resolve, we can
trivially tell whether a given router will support it by simulating
its declared exit policy.
Because we often connect to addresses of the form hostname:port, we do not
always know the target IP address when we select an exit node. In these
cases, we need to pick an exit node that "might support" connections to a
given address port with an unknown address. An exit node "might support"
such a connection if any clause that accepts any connections to that port
precedes all clauses (if any) that reject all connections to that port.
Unless requested to do so by the user, we never choose an exit node
flagged as "BadExit" by more than half of the authorities who advertise
themselves as listing bad exits.
2.2.2. User configuration
Users can alter the default behavior for path selection with configuration
options.
- If "ExitNodes" is provided, then every request requires an exit node on
the ExitNodes list. (If a request is supported by no nodes on that list,
and StrictExitNodes is false, then Tor treats that request as if
ExitNodes were not provided.)
- "EntryNodes" and "StrictEntryNodes" behave analogously.
- If a user tries to connect to or resolve a hostname of the form
<target>.<servername>.exit, the request is rewritten to a request for
<target>, and the request is only supported by the exit whose nickname
or fingerprint is <servername>.
- When set, "HSLayer2Nodes" and "HSLayer3Nodes" relax Tor's path
restrictions to allow nodes in the same /16 and node family to reappear
in the path. They also allow the guard node to be chosen as the RP, IP,
and HSDIR, and as the hop before those positions.
2.3. Cannibalizing circuits
If we need a circuit and have a clean one already established, in
some cases we can adapt the clean circuit for our new
purpose. Specifically,
For hidden service interactions, we can "cannibalize" a clean internal
circuit if one is available, so we don't need to build those circuits
from scratch on demand.
We can also cannibalize clean circuits when the client asks to exit
at a given node -- either via the ".exit" notation or because the
destination is running at the same location as an exit node.
2.4. Learning when to give up ("timeout") on circuit construction
Since version 0.2.2.8-alpha, Tor clients attempt to learn when to give
up on circuits based on network conditions.
2.4.1. Distribution choice
Based on studies of build times, we found that the distribution of
circuit build times appears to be a Frechet distribution (and a multi-modal
Frechet distribution, if more than one guard or bridge is used). However,
estimators and quantile functions of the Frechet distribution are difficult
to work with and slow to converge. So instead, since we are only interested
in the accuracy of the tail, clients approximate the tail of the multi-modal
distribution with a single Pareto curve.
2.4.2. How much data to record
From our observations, the minimum number of circuit build times for a
reasonable fit appears to be on the order of 100. However, to keep a
good fit over the long term, clients store 1000 most recent circuit build
times in a circular array.
These build times only include the times required to build three-hop
circuits,
|