[tor-bugs] #27359 [Core Tor/Tor]: Store family lists more efficiently

[Tor Bug Tracker & Wiki]

#27359: Store family lists more efficiently
-------------------------------------------------+-------------------------
 Reporter:  nickm                                |          Owner:  nickm
     Type:  defect                               |         Status:
                                                 |  accepted
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  0.3.6.x-final
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  035-roadmap-master, 035-triaged-     |  Actual Points:
  in-20180711                                    |
Parent ID:  #27243                               |         Points:
 Reviewer:                                       |        Sponsor:
                                                 |  Sponsor8-can
-------------------------------------------------+-------------------------

Comment (by nickm):

 So the idea of the scheme here is to encode families in a more compact
 representation: roughly, as a sorted array of 21-byte elements, where each
 element is a one byte tag, and 20 bytes of either a sha1 ID or a nickname.
 These objects are reference-counted, so that they can be shared by relays
 with the same family members.

 To optimize the number of family objects that are shared by multiple
 relays, I want to add each relay's hex ID to its own family -- doing this
 will make all the relays in the same family have the same encoded family.
 (It's harmless to consider a relay a member of its own family.)

 I've run into a few issues with this, and I'm not sure which of them need
 to be solved pre-merge, and how.

   1) A small number of relays specify invalid hex IDs in their family
 lines -- typically, with the wrong number of hex digits.

   2) A small number of relays use the $hexid=nickname syntax, which can't
 be encoded in the manner above, and which is probably not what they want
 anyway.

   3) Authorities need to process family lines exactly as they are
 received, and rely on a lossless encoding of their inputs.

   4) When parsing a microdescriptor, we do not know which relay it is
 associated with, so we can't easily add its own ID to its family when
 parsing it.  (Further, it is in theory possible for two misconfigured
 relays to wind up with the same microdescriptor, I think.)

 I'm not sure quite what to do about each of these issues.

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