[tor-dev] Proposal 236 and the guardiness of a guard
George Kadianakis
desnacked at riseup.net
Thu Jul 31 16:24:32 UTC 2014
One of the aims of proposal 236 is to reduce the period of
inactiveness when a relay becomes a guard (see 'Phase three' of
[0]). This phenomenon will become worse when the lifetime of the guard
gets increased to 9 months, so we need to find a good fix.
Proposal 236 tries to make young guards more likely to be picked as
middle nodes by clients: this way their guard inactivity will be
compensated by working as middle nodes . This is specified in section
1.3 of proposal 236 [1] and you can read a discussion about this in [2].
I quote here the most relevant part of that section:
A guard N that has been visible for V out of NNN*30*24 consensuses
has had the opportunity to be chosen as a guard by approximately
F = V/NNN*30*24 of the clients in the network, and the remaining
1-F fraction of the clients have not noticed this change. So when
being chosen for middle or exit positions on a circuit, clients
should treat N as if F fraction of its bandwidth is a guard
(respectively, dual) node and (1-F) is a middle (resp, exit) node.
Let Wpf denote the weight from the 'bandwidth-weights' line a
client would apply to N for position p if it had the guard
flag, Wpn the weight if it did not have the guard flag, and B the
measured bandwidth of N in the consensus. Then instead of choosing
N for position p proportionally to Wpf*B or Wpn*B, clients should
choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
The relevant trac ticket is #9321 and I asked myself various
engineering questions in [3]. These engineering questions can be
ignored for now but they will need to resolved eventually.
This email is more concerned with the research side of this task.
I recently wrote a python script that calculates in how many
consensuses a guard appears and then calculates the guard/middle
weights and probabilities according to section 1.3 of proposal 236 [1].
The results were as expected for the biggest part. That is, new guards
got a boost in their middle probabilities. You can see the output of
my script here https://people.torproject.org/~asn/guards3/output
and you can see boxplots of the guard and middle probabilities here:
https://people.torproject.org/~asn/guards3/guard_boxplot.png
https://people.torproject.org/~asn/guards3/middle_boxplot.png
I mainly uploaded them so that the outliers probs are seen better.
I also highlighted some snippets of the output at [4].
Here are some notes:
- You can see that old guards (like RichardFeynman) see a shrinkage
both on their guard and on their middle probabilities. This happens
because both the total guard weight and the total middle weight get
bigger [5], so their weight percentage gets smaller.
- You can see that weird things happen to relays that are *both* a
Guard and an Exit (like thevillage1 and TorLand1). Specifically,
even for young guards, their middle probability gets decreased and
their guard probability gets increased. This is especially visible
for the village1 for which the guard probability gets increased by
0.008 making it the most probable guard of all, with probability
0.0101.
This happens because of the Guard+Exit bandwidth weights [6].
Specifically, it happens because Wgd << Wgm.
We should decide whether this behavior is a feature or a bug (it
might be a feature, since we don't really want to overload exit
nodes with middle traffic if they also happen to be young guards)
- You can also see that for young guards (like freefrcv2), the feature
works as intended: pumping up their middle probability.
This is just an update on this task and any comments are welcome :)
[0]: https://blog.torproject.org/blog/lifecycle-of-a-new-relay
[1]: https://gitweb.torproject.org/torspec.git/blob/7bd906b6ecef7a0dcf3b420944da0d08db5a2553:/proposals/236-single-guard-node.txt#l101
[2]: https://lists.torproject.org/pipermail/tor-dev/2014-March/006571.html
https://lists.torproject.org/pipermail/tor-dev/2014-April/006654.html
[3]: https://trac.torproject.org/projects/tor/ticket/9321#comment:13
[4]:
A685A493342B15476A8AA35CE2868B62C0331D6B in 22 out of 1966 consensuses (1%) (tingPLrice5)
A685A493342B15476A8AA35CE2868B62C0331D6B: guard prob 0.00001466095664981207628234955862 -> 0.00001236359278611040906223472603 (delta: -0.00000229736386370166722011483259)
A685A493342B15476A8AA35CE2868B62C0331D6B: middle prob 0.00001411262320417776315899083553 -> 0.00002313283079875486344342985726 (delta: 0.00000902020759457710028443902173)
2009F87590E626C98E1A5C8D08C23366C58B7951 in 46 out of 1966 consensuses (2%) (thevillage1)
2009F87590E626C98E1A5C8D08C23366C58B7951: guard prob 0.001799671590571654712486494434 -> 0.01018493194688813591277789142 (delta: 0.008385260356316481200291396986) (exit)
2009F87590E626C98E1A5C8D08C23366C58B7951: middle prob 0.002531389208535432867885203535 -> 0.00003970964677012672298440629596 (delta: -0.002491679561765306144900797239) (exit)
B1A88CFED023588C713E42B9ABA0AD2A294BECCF in 470 out of 1966 consensuses (23%) (ChronosDaKnObNET)
B1A88CFED023588C713E42B9ABA0AD2A294BECCF: guard prob 0.00002846894283361195170183376972 -> 0.0001308372445794862073501048856 (delta: 0.0001023683017458742556482711159) (exit)
B1A88CFED023588C713E42B9ABA0AD2A294BECCF: middle prob 0.00004004395860053895959111507317 -> 0.000006418213054140890599306823457 (delta: -0.00003362574554639806899180824971) (exit)
2D958EED2BC8EB672187C99CF6A4D8D8EBDBE412 in 474 out of 1966 consensuses (24%) (freefrcv2)
2D958EED2BC8EB672187C99CF6A4D8D8EBDBE412: guard prob 0.00004462030284725414520715083057 -> 0.00003762832587077081018941003575 (delta: -0.00000699197697648333501774079482)
2D958EED2BC8EB672187C99CF6A4D8D8EBDBE412: middle prob 0.00004295146192575840961431993422 -> 0.00006073004942478721908966913122 (delta: 0.00001777858749902880947534919700)
4A5ADDBAC82BC071D9516FB01429A1CAD493D36C in 865 out of 1966 consensuses (43%) (monoversum)
4A5ADDBAC82BC071D9516FB01429A1CAD493D36C: guard prob 0.008658463528693363891387601646 -> 0.007301687043971002453421233128 (delta: -0.001356776484722361437966368518)
4A5ADDBAC82BC071D9516FB01429A1CAD493D36C: middle prob 0.008334628921307881865635891998 -> 0.01016060938520887622674424842 (delta: 0.001825980463900994361108356422)
B7A4718F146139B8137BBD7CF2890AFA61C2BAB7 in 1065 out of 1966 consensuses (54%) (PPTOR0001)
B7A4718F146139B8137BBD7CF2890AFA61C2BAB7: guard prob 0.00001880427048562853262301356431 -> 0.00001585765161696769857982280078 (delta: -0.00000294661886866083404319076353)
B7A4718F146139B8137BBD7CF2890AFA61C2BAB7: middle prob 0.00001810097324014104405174911514 -> 0.00002026262077783844197435510639 (delta: 0.00000216164753769739792260599125)
E1E922A20AF608728824A620BADC6EFC8CB8C2B8 in 1616 out of 1966 consensuses (82%) (TorLand1)
E1E922A20AF608728824A620BADC6EFC8CB8C2B8: guard prob 0.001442840154510033519493482607 -> 0.002483448551109987826331785865 (delta: 0.001040608396599954306838303258) (exit)
E1E922A20AF608728824A620BADC6EFC8CB8C2B8: middle prob 0.002029475830980993592356240765 -> 0.001118418926871964944505332348 (delta: -0.000911056904109028647850908417) (exi)
8699371415DC052A60BCA3AAD68E55D9B759CAE0 in 1858 out of 1966 consensuses (94%) (torrorist)
8699371415DC052A60BCA3AAD68E55D9B759CAE0: guard prob 0.000009508374059117252371523807943 -> 0.000008018417060557113123695710000 (delta: -0.000001489956998560139247828097943)
8699371415DC052A60BCA3AAD68E55D9B759CAE0: middle prob 0.000009152752005608042048765795507 -> 0.000006628989446427573975351367609 (delta: -0.000002523762559180468073414427898)
3FE4CF4366E128154E951FEBB3B448CC2F3E1EBA in 1966 out of 1966 consensuses (100%) (RichardFeynman)
3FE4CF4366E128154E951FEBB3B448CC2F3E1EBA: guard prob 0.0003304027187022866466529501978 -> 0.0002786287939478505230692028838 (delta: -0.0000517739247544361235837473140)
3FE4CF4366E128154E951FEBB3B448CC2F3E1EBA: middle prob 0.0003180453490216872711917499891 -> 0.0002132317299501384937260708373 (delta: -0.0001048136190715487774656791518)
7E43F05A970431239898FDDCE014B1BA5134703F in 1966 out of 1966 consensuses (100%) (PrivacyRepublic0003)
7E43F05A970431239898FDDCE014B1BA5134703F: guard prob 0.0002102202590710855289154482723 -> 0.0001772788598061129408325756509 (delta: -0.0000329413992649725880828726214) (exit)
7E43F05A970431239898FDDCE014B1BA5134703F: middle prob 0.0002956924463418544427572802405 -> 0.0001982453510501193425034660120 (delta: -0.0000974470952917351002538142285) (exit)
[5]:
total guard weight: 11176705.8531
new total guard weight: 13253526.12584313326551373350
total middle weight: 7945992.6321
new total middle weight: 11851828.99651449643947100714
[6]:
Wme=0 # Weight for Exit-flagged nodes in the middle Position
Wmd=867 # Weight for Guard+Exit flagged nodes in the middle Position
Wmg=4063 # Weight for Guard-flagged nodes in the middle Position
Wmm=10000 # Weight for non-flagged nodes in the middle Position
Wgd=867 # Weight for Guard+Exit-flagged nodes in the guard Position
Wgg=5937 # Weight for Guard-flagged nodes in the guard position
Wgm=5937 # Weight for non-flagged nodes in the guard Position
More information about the tor-dev
mailing list