proposals/158-microdescriptors.txt

   1 Filename: 158-microdescriptors.txt
   2 Title: Clients download consensus + microdescriptors
   3 Author: Roger Dingledine
   4 Created: 17-Jan-2009
   5 Status: Open
   6
   7 0. History
   8
   9   15 May 2009: Substantially revised based on discussions on or-dev
  10   from late January.  Removed the notion of voting on how to choose
  11   microdescriptors; made it just a function of the consensus method.
  12   (This lets us avoid the possibility of "desynchronization.")
  13   Added suggestion to use a new consensus flavor.  Specified use of
  14   SHA256 for new hashes. -nickm
  15
  16   15 June 2009: Cleaned up based on comments from Roger. -nickm
  17
  18 1. Overview
  19
  20   This proposal replaces section 3.2 of proposal 141, which was
  21   called "Fetching descriptors on demand". Rather than modifying the
  22   circuit-building protocol to fetch a server descriptor inline at each
  23   circuit extend, we instead put all of the information that clients need
  24   either into the consensus itself, or into a new set of data about each
  25   relay called a microdescriptor.
  26
  27   Descriptor elements that are small and frequently changing should go
  28   in the consensus itself, and descriptor elements that are small and
  29   relatively static should go in the microdescriptor. If we ever end up
  30   with descriptor elements that aren't small yet clients need to know
  31   them, we'll need to resume considering some design like the one in
  32   proposal 141.
  33
  34   Note also that any descriptor element which clients need to use to
  35   decide which servers to fetch info about, or which servers to fetch
  36   info from, needs to stay in the consensus.
  37
  38 2. Motivation
  39
  40   See
  41   http://archives.seul.org/or/dev/Nov-2008/msg00000.html and
  42   http://archives.seul.org/or/dev/Nov-2008/msg00001.html and especially
  43   http://archives.seul.org/or/dev/Nov-2008/msg00007.html
  44   for a discussion of the options and why this is currently the best
  45   approach.
  46
  47 3. Design
  48
  49   There are three pieces to the proposal. First, authorities will list in
  50   their votes (and thus in the consensus) the expected hash of
  51   microdescriptor for each relay. Second, authorities will serve
  52   microdescriptors, directory mirrors will cache and serve
  53   them. Third, clients will ask for them and cache them.
  54
  55 3.1. Consensus changes
  56
  57   If the authorities choose a consensus method of a given version or
  58   later, a microdescriptor format is implicit in that version.
  59   A microdescriptor should in every case be a pure function of the
  60   router descriptor and the consensus method.
  61
  62   In votes, we need to include the hash of each expected microdescriptor
  63   in the routerstatus section. I suggest a new "m" line for each stanza,
  64   with the base64 of the SHA256 hash of the router's microdescriptor.
  65
  66   For every consensus method that an authority supports, it includes a
  67   separate "m" line in each router section of its vote, containing:
  68     "m" SP methods 1*(SP AlgorithmName "=" digest) NL
  69   where methods is a comma-separated list of the consensus methods
  70   that the authority believes will produce "digest".
  71
  72   (As with base64 encoding of SHA1 hashes in consensuses, let's
  73   omit the trailing =s)
  74
  75   The consensus microdescriptor-elements and "m" lines are then computed
  76   as described in Section 3.1.2 below.
  77
  78   (This means we need a new consensus-method that knows
  79   how to compute the microdescriptor-elements and add "m" lines.)
  80
  81   The microdescriptor consensus uses the directory-signature format from
  82   proposal 162, with the "sha256" algorithm.
  83
  84
  85 3.1.1. Descriptor elements to include for now
  86
  87   In the first version, the microdescriptor should contain the
  88   onion-key element, and the family element from the router descriptor,
  89   and the exit policy summary as currently specified in dir-spec.txt.
  90
  91 3.1.2. Computing consensus for microdescriptor-elements and "m" lines
  92
  93   When we are generating a consensus, we use whichever m line
  94   unambiguously corresponds to the descriptor digest that will be
  95   included in the consensus.
  96
  97   (If different votes have different microdescriptor digests for a
  98   single <descriptor-digest, consensus-method> pair, then at least one
  99   of the authorities is broken.  If this happens, the consensus should
 100   contain whichever microdescriptor digest is most common.  If there is
 101   no winner, we break ties in the favor of the lexically earliest.
 102   Either way, we should log a warning: there is definitely a bug.)
 103
 104   The "m" lines in a consensus contain only the digest, not a list of
 105   consensus methods.
 106
 107 3.1.3. A new flavor of consensus
 108
 109   Rather than inserting "m" lines in the current consensus format,
 110   they should be included in a new consensus flavor (see proposal
 111   162).
 112
 113   This flavor can safely omit descriptor digests.
 114
 115   When we implement this voting method, we can remove the exit policy
 116   summary from the current "ns" flavor of consensus, since no current
 117   clients use them, and they take up about 5% of the compressed
 118   consensus.
 119
 120   This new consensus flavor should be signed with the sha256 signature
 121   format as documented in proposal 162.
 122
 123 3.2. Directory mirrors fetch, cache, and serve microdescriptors
 124
 125   Directory mirrors should fetch, catch, and serve each microdescriptor
 126   from the authorities.  (They need to continue to serve normal relay
 127   descriptors too, to handle old clients.)
 128
 129   The microdescriptors with base64 hashes <D1>,<D2>,<D3> should be
 130   available at:
 131     http://<hostname>/tor/micro/d/<D1>-<D2>-<D3>.z
 132   (We use base64 for size and for consistency with the consensus
 133   format. We use -s instead of +s to separate these items, since
 134   the + character is used in base64 encoding.)
 135
 136   All the microdescriptors from the current consensus should also be
 137   available at:
 138     http://<hostname>/tor/micro/all.z
 139   so a client that's bootstrapping doesn't need to send a 70KB URL just
 140   to name every microdescriptor it's looking for.
 141
 142   Microdescriptors have no header or footer.
 143   The hash of the microdescriptor is simply the hash of the concatenated
 144   elements.
 145
 146   Directory mirrors should check to make sure that the microdescriptors
 147   they're about to serve match the right hashes (either the hashes from
 148   the fetch URL or the hashes from the consensus, respectively).
 149
 150   We will probably want to consider some sort of smart data structure to
 151   be able to quickly convert microdescriptor hashes into the appropriate
 152   microdescriptor. Clients will want this anyway when they load their
 153   microdescriptor cache and want to match it up with the consensus to
 154   see what's missing.
 155
 156 3.3. Clients fetch them and cache them
 157
 158   When a client gets a new consensus, it looks to see if there are any
 159   microdescriptors it needs to learn. If it needs to learn more than
 160   some threshold of the microdescriptors (half?), it requests 'all',
 161   else it requests only the missing ones.  Clients MAY try to
 162   determine whether the upload bandwidth for listing the
 163   microdescriptors they want is more or less than the download
 164   bandwidth for the microdescriptors they do not want.
 165
 166   Clients maintain a cache of microdescriptors along with metadata like
 167   when it was last referenced by a consensus, and which identity key
 168   it corresponds to.  They keep a microdescriptor
 169   until it hasn't been mentioned in any consensus for a week. Future
 170   clients might cache them for longer or shorter times.
 171
 172 3.3.1. Information leaks from clients
 173
 174   If a client asks you for a set of microdescs, then you know she didn't
 175   have them cached before. How much does that leak? What about when
 176   we're all using our entry guards as directory guards, and we've seen
 177   that user make a bunch of circuits already?
 178
 179   Fetching "all" when you need at least half is a good first order fix,
 180   but might not be all there is to it.
 181
 182   Another future option would be to fetch some of the microdescriptors
 183   anonymously (via a Tor circuit).
 184
 185   Another crazy option (Roger's phrasing) is to do decoy fetches as
 186   well.
 187
 188 4. Transition and deployment
 189
 190   Phase one, the directory authorities should start voting on
 191   microdescriptors, and putting them in the consensus.
 192
 193   Phase two, directory mirrors should learn how to serve them, and learn
 194   how to read the consensus to find out what they should be serving.
 195
 196   Phase three, clients should start fetching and caching them instead
 197   of normal descriptors.
 198