[tor-bugs] #12595 [Tor]: Think of better data structures for guard nodes

[Tor Bug Tracker & Wiki]

#12595: Think of better data structures for guard nodes
------------------------+--------------------------------
     Reporter:  asn     |      Owner:
         Type:  defect  |     Status:  new
     Priority:  normal  |  Milestone:  Tor: 0.2.6.x-final
    Component:  Tor     |    Version:
   Resolution:          |   Keywords:  tor-guard
Actual Points:          |  Parent ID:
       Points:          |
------------------------+--------------------------------

Comment (by nickm):

 Replying to [comment:3 asn]:
 > Some more thoughts on the new data structures:
 >
 > - Since we want our circuit guards to also be our directory guards (if
 >   possible), we should probably use a single entry guard list (like we
 >   do currently), instead of using separate lists for circuit guards
 >   and directory guards. Reasons for this can be found here:
 >   https://lists.torproject.org/pipermail/tor-dev/2014-May/006824.html

 Seems plausible to me.

 > - Furthermore, we want to make sure that if our directory guard claims
 >   that it doesn't have a microdescriptor, we will go ahead and ask
 >   other directory caches too:
 >   https://lists.torproject.org/pipermail/tor-dev/2014-May/006820.html
 >
 >   I wonder if this behavior is any different from the corresponding
 >   behavior of circuit guards: "If our circuit guard fails our circuit,
 >   we have to go ahead and ask the next circuit guard"
 >
 >   If not, maybe we could just switch NumDirectoryGuards to 1 too, and
 >   just make sure that if a microdescriptor gets denied we move to the
 >   next directory guard, till we have enough microdescriptor to be happy?
 >   (logic similar to compute_frac_paths_available()).

 Watch out there.  "compute_frac_paths_available()" still allows some
 epistemic bias.  It only insists that we have a large proportion of
 possible microdescriptors before we're happy enough to build circuits, not
 that we have all of them.  That's not such a big deal with multiple
 noncolluding directory guards, but with only one guard, it's possibly
 trouble.



 > - As a further point to the paragraph above, I uploaded an image of 3
 >   different possible entry guard lists:
 >   https://people.torproject.org/~asn/guards2/entry_guard_list.jpg
 >
 >   With the current code, and if NumDirectoryGuards was 3, from the
 >   first entry guard list we would select a directory guard between
 >   (entry2, entry4, entry6). On the second list, we would select
 >   between (entry1, entry4, entry6).  On the third list, the worst case
 >   scenario, we would select between (entry4, entry5, ...).
 >
 >   I'd argue that we should strongly prefer the *top* directory guard
 >   every time, and only move to the lower ones if the top one doesn't
 >   give us what we want.

 "Strongly prefer" seems good; can we turn this into an algorithm?


 Reading through all of the above stuff, in fact, I think that the right
 way to approach design here might be to step back from the "what is the
 right data structure" question and ask ourselves, "what interface must
 these algorithms expose, and how should they implement it?"  IOW, can we
 enumerate their inputs and outputs, the events that affect them, and the
 operations they need to perform?  If we figure that out, we should be able
 to examine some ideas in pseudocode and converge on something clever.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/12595#comment:7>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online