[tor-dev] Existing Tor Guard Selection Algorithm

[George Kadianakis]

Reinaldo Junior <rjunior at thoughtworks.com> writes:

> On Thu, Feb 11, 2016 at 7:55 AM, George Kadianakis <desnacked at riseup.net>
> wrote:
>
>> Chelsea Komlo <ckomlo at thoughtworks.com> writes:
>>
>> > Hi George,
>> >
>> > Thanks for your help with this!
>> >
>> > We wrote up our high-level understanding of the current Tor guard
>> selection
>> > algorithm here:
>> >
>> > https://gist.github.com/chelseakomlo/2acbe15314b5a809c6f4
>> >
>> > This has more than our python simulation, but less than the actual Tor
>> > implementation. For example, it is missing conditions like prioritization
>> > by uptime, capacity, etc.
>> >
>> >
>> https://github.com/twstrike/tor_guardsim/blob/develop/lib/original_client.py
>> >
>> > If you wouldn't mind taking a look at this and letting us know anything
>> > that is missing/should change, that would be really helpful.
>> >
>>
>> Your pseudocode looks pretty accurate based on what I remember from the
>> guard
>> algorithm and from quickly skimming the code.
>>
>> One inaccuracy might be that if IIRC in RECEIVE_NEW_CONSENSUS we don't
>> remove
>> guards that are not listed in the latest consensus. Instead we mark them
>> as 'bad'
>> which rules them out of retries etc. till they reappear on the consensus.
>> See entry_guard_set_status() and its caller for how this works.
>>
>
> <snip>
>
> See:
> https://github.com/twstrike/tor_guardsim/commit/1fb7400c0c8e167508753ede15b8fe82bd08ecdd

Hmm, looks pretty good!

One note: I feel that you are hiding information behind the simple phrase
"Build LIVE_GUARDS". Interesting things happen in populate_live_entry_guards()
that are not documented by your algo. For example, in entry_is_live() we call
entry_is_time_to_retry(), which periodically retries guards based on time:

  struct guard_retry_period_s periods[] = {
     {    6*60*60,    60*60 }, /* For first 6 hrs., retry hourly; */
     { 3*24*60*60,  4*60*60 }, /* Then retry every 4 hrs. until the
                                  3-day mark; */
     { 7*24*60*60, 18*60*60 }, /* After 3 days, retry every 18 hours until
                                  1 week mark. */
     {   TIME_MAX, 36*60*60 }  /* After 1 week, retry every 36 hours. */
  };

Also, another function that I'm not sure if you have seen (and whether it fits
with the algorithm) is entries_retry_all().

BTW, I like the way you have splitted the algo into various events
(RECEIVE_NEW_CONSENSUS, BUILD_NEW_CIRCUIT, CHOOSE_A_GUARD, CONNECT_ENTRY_GUARD,
etc.). We should maybe try to shape Ola's new algorithm to fit this event
structure exactly since it resembles the actual Tor networking API.

Cheers!