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  and
  76    /tor/status-vote/(current|next)/consensus/<FP1>+<FP2>+<FP3>+....z ,
  77    authorities serve another consensus of each flavor "F" from the
  78    locations /tor/status-vote/(current|next)/consensus-F.z. and
  79    /tor/status-vote/(current|next)/consensus-F/<FP1>+....z.
  80
  81    When caches serve these documents, they do so from the same
  82    locations.
  83
  84    2. Document format: generic consensus.
  85
  86    The format of a flavored consensus is as-yet-unspecified, except
  87    that the first line is:
  88       "network-status-version" SP version SP flavor NL
  89
  90    where version is 3 or higher, and the flavor is a string
  91    consisting of alphanumeric characters and dashes, matching the
  92    corresponding flavor listed in the unflavored consensus.
  93
  94    3. Document format: detached signatures.
  95
  96    We amend the detached signature format to include more than one
  97    consensus-digest line, and more than one set of signatures.
  98
  99    After the consensus-digest line, we allow more lines of the form:
 100       "additional-digest" SP flavor SP algname SP digest NL
 101
 102    Before the directory-signature lines, we allow more entries of the form:
 103       "additional-signature" SP flavor SP algname SP identity SP
 104            signing-key-digest NL signature.
 105
 106    [We do not use "consensus-digest" or "directory-signature" for flavored
 107    consensuses, since this could confuse older Tors.]
 108
 109    The consensus-signatures URL should contain the signatures
 110    for _all_ flavors of consensus.
 111
 112    4. The consensus index:
 113
 114    Authorities additionally generate and serve a consensus-index
 115    document.  Its format is:
 116
 117        Header ValidAfter ValidUntil Documents Signatures
 118
 119        Header = "consensus-index" SP version NL
 120        ValidAfter = as in a consensus
 121        ValidUntil = as in a consensus
 122        Documents = Document*
 123        Document = "document" SP flavor SP SignedLength
 124                                     1*(SP AlgorithmName "=" Digest) NL
 125        Signatures = Signature*
 126        Signature = "directory-signature" SP algname SP identity
 127                            SP signing-key-digest NL signature
 128
 129     There must be one Document line for each generated consensus flavor.
 130     Each Document line describes the length of the signed portion of
 131     a consensus (the signatures themselves are not included), along
 132     with one or more digests of that signed portion.  Digests are
 133     given in hex.  The algorithm "sha256" MUST be included; others
 134     are allowed.
 135
 136     The algname part of a signature describes what algorithm was
 137     used to hash the identity and signing keys, and to compute the
 138     signature.  The algorithm "sha256" MUST be recognized;
 139     signatures with unrecognized algorithms MUST be ignored.
 140     (See below).
 141
 142     The consensus index is made available at
 143        /tor/status-vote/(current|next)/consensus-index.z.
 144
 145     Caches should fetch this document so they can check the
 146     correctness of the different consensus documents they fetch.
 147     They do not need to check anything about an unrecognized
 148     consensus document beyond its digest and length.
 149
 150     4.1. The "sha256" signature format.
 151
 152     The 'SHA256' signature format for directory objects is defined as
 153     the RSA signature of the OAEP+-padded SHA256 digest of the item to
 154     be signed.  When checking signatures, the signature MUST be treated
 155     as valid if the signature material begins with SHA256(document);
 156     this allows us to add other data later.
 157
 158 Considerations:
 159
 160     - We should not create a new flavor of consensus when adding a
 161       field instead wouldn't be too onerous.
 162
 163     - We should not proliferate flavors lightly: clients will be
 164       distinguishable based on which flavor they download.
 165
 166 Migration:
 167
 168     - Stage one: authorities begin generating and serving
 169       consensus-index files.
 170
 171     - Stage two: Caches begin downloading consensus-index files,
 172       validating them, and using them to decide what flavors of
 173       consensus documents to cache.  They download all listed
 174       documents, and compare them to the digests given in the
 175       consensus.
 176
 177     - Stage three: Once we want to make a significant change to the
 178       consensus format, we deploy another flavor of consensus at the
 179       authorities.  This will immediately start getting cached by the
 180       caches, and clients can start fetching the new flavor without
 181       waiting a version or two for enough caches to begin supporting
 182       it.
 183
 184 Acknowledgements:
 185
 186     Aspects of this design and its applications to hash migration were
 187     heavily influenced by IRC conversations with Marian.
 188