proposals/162-consensus-flavors.txt

   1 Filename: 162-consensus-flavors.txt
   2 Title: Publish the consensus in multiple flavors
   3 Author: Nick Mathewson
   4 Created: 14-May-2009
   5 Target: 0.2.2
   6 Status: Open
   7
   8 Overview:
   9
  10    This proposal describes a way to publish each consensus in
  11    multiple simultaneous formats, or "flavors".  This will reduce the
  12    amount of time needed to deploy new consensus-like documents, and
  13    reduce the size of consensus documents in the long term.
  14
  15 Motivation:
  16
  17    In the future, we will almost surely want different fields and
  18    data in the network-status document.  Examples include:
  19       - Publishing hashes of microdescriptors instead of hashes of
  20         full descriptors (Proposal 158).
  21       - Including different digests of descriptors, instead of the
  22         perhaps-soon-to-be-totally-broken SHA1.
  23
  24    Note that in both cases, from the client's point of view, this
  25    information _replaces_ older information.  If we're using a
  26    SHA256 hash, we don't need to see the SHA1.  If clients only want
  27    microdescriptors, they don't (necessarily) need to see hashes of
  28    other things.
  29
  30    Our past approach to cases like this has been to shovel all of
  31    the data into the consensus document.  But this is rather poor
  32    for bandwidth.  Adding a single SHA256 hash to a consensus for
  33    each router increases the compressed consensus size by 47%.  In
  34    comparison, replacing a single SHA1 hash with a SHA256 hash for
  35    each listed router increases the consensus size by only 18%.
  36
  37 Design in brief:
  38
  39    Let the voting process remain as it is, until a consensus is
  40    generated.  With future versions of the voting algorithm, instead
  41    of just a single consensus being generated, multiple consensus
  42    "flavors" are produced.
  43
  44    Consensuses (all of them) include a list of which flavors are
  45    being generated.  Caches fetch and serve all flavors of consensus
  46    that are listed, regardless of whether they can parse or validate
  47    them, and serve them to clients.  Thus, once this design is in
  48    place, we won't need to deploy more cache changes in order to get
  49    new flavors of consensus to be cached.
  50
  51    Clients download only the consensus flavor they want.
  52
  53 A note on hashes:
  54
  55    Everything in this document is specified to use SHA256, and to be
  56    upgradeable to use better hashes in the future.
  57
  58 Spec modifications:
  59
  60    1. URLs and changes to the current consensus format.
  61
  62    Every consensus flavor has a name consisting of a sequence of one
  63    or more alphanumeric characters and dashes.  For compatibility
  64    current descriptor flavor is called "ns".
  65
  66    The supported consensus flavors are defined as part of the
  67    authorities' consensus method.
  68
  69    For each supported flavor, every authority calculates another
  70    consensus document of as-yet-unspecified format, and exchanges
  71    detached signatures for these documents as in the current consensus
  72    design.
  73
  74    In addition to the consensus currently served at
  75    /tor/status-vote/(current|next)/consensus.z , authorities serve
  76    another consensus of each flavor "F" from the location
  77    /tor/status-vote/(current|next)/F/consensus.z.
  78
  79    When caches serve these documents, they do so from the same
  80    locations.
  81
  82    2. Document format: generic consensus.
  83
  84    The format of a flavored consensus is as-yet-unspecified, except
  85    that the first line is:
  86       "network-status-version" SP version SP flavor NL
  87
  88    where version is 3 or higher, and the flavor is a string
  89    consisting of alphanumeric characters and dashes, matching the
  90    corresponding flavor listed in the unflavored consensus.
  91
  92    3. Document format: detached signatures.
  93
  94    We amend the detached signature format to include more than one
  95    consensus-digest line, and more than one set of signatures.
  96
  97    After the consensus-digest line, we allow more lines of the form:
  98       "additional-digest" SP flavor SP algname SP digest NL
  99
 100    Before the directory-signature lines, we allow more entries of the form:
 101       "additional-signature" SP flavor SP algname SP identity SP
 102            signing-key-digest NL signature.
 103
 104    [We do not use "consensus-digest" or "directory-signature" for flavored
 105    consensuses, since this could confuse older Tors.]
 106
 107    The consensus-signatures URL should contain the signatures
 108    for _all_ flavors of consensus.
 109
 110    4. The consensus index:
 111
 112    Authorities additionally generate and serve a consensus-index
 113    document.  Its format is:
 114
 115        Header ValidAfter ValidUntil Documents Signatures
 116
 117        Header = "consensus-index" SP version NL
 118        ValidAfter = as in a consensus
 119        ValidUntil = as in a consensus
 120        Documents = Document*
 121        Document = "document" SP flavor SP SignedLength
 122                                     1*(SP AlgorithmName "=" Digest) NL
 123        Signatures = Signature*
 124        Signature = "directory-signature" SP algname SP identity
 125                            SP signing-key-digest NL signature
 126
 127     There must be one Document line for each generated consensus flavor.
 128     Each Document line describes the length of the signed portion of
 129     a consensus (the signatures themselves are not included), along
 130     with one or more digests of that signed portion.  Digests are
 131     given in hex.  The algorithm "sha256" MUST be included; others
 132     are allowed.
 133
 134     The algname part of a signature describes what algorithm was
 135     used to hash the identity and signing keys, and to compute the
 136     signature.  The algorithm "sha256" MUST be recognized;
 137     signatures with unrecognized algorithms MUST be ignored.
 138     (See below).
 139
 140     The consensus index is made available at
 141        /tor/status-vote/(current|next)/consensus-index.z.
 142
 143     Caches should fetch this document so they can check the
 144     correctness of the different consensus documents they fetch.
 145     They do not need to check anything about an unrecognized
 146     consensus document beyond its digest and length.
 147
 148     4.1. The "sha256" signature format.
 149
 150     The 'SHA256' signature format for directory objects is defined as
 151     the RSA signature of the OAEP+-padded SHA256 digest of the item to
 152     be signed.  When checking signatures, the signature MUST be treated
 153     as valid if the signature material begins with SHA256(document);
 154     this allows us to add other data later.
 155
 156 Considerations:
 157
 158     - We should not create a new flavor of consensus when adding a
 159       field instead wouldn't be too onerous.
 160
 161     - We should not proliferate flavors lightly: clients will be
 162       distinguishable based on which flavor they download.
 163
 164 Migration:
 165
 166     - Stage one: authorities begin generating and serving
 167       consensus-index files.
 168
 169     - Stage two: Caches begin downloading consensus-index files,
 170       validating them, and using them to decide what flavors of
 171       consensus documents to cache.  They download all listed
 172       documents, and compare them to the digests given in the
 173       consensus.
 174
 175     - Stage three: Once we want to make a significant change to the
 176       consensus format, we deploy another flavor of consensus at the
 177       authorities.  This will immediately start getting cached by the
 178       caches, and clients can start fetching the new flavor without
 179       waiting a version or two for enough caches to begin supporting
 180       it.
 181
 182 Acknowledgements:
 183
 184     Aspects of this design and its applications to hash migration were
 185     heavily influenced by IRC conversations with Marian.
 186