doc/spec/proposals/101-dir-voting.txt

   1 $Id: /tor/branches/eventdns/doc/dir-spec.txt 9469 2006-11-01T23:56:30.179423Z nickm  $
   2
   3                      Voting on the Tor Directory System
   4
   5 0. Scope and preliminaries
   6
   7   This document describes a consensus voting scheme for Tor directories.
   8   Once it's accepted, it should be merged with dir-spec.txt.  Some
   9   preliminaries for authority and caching support should be done during
  10   the 0.1.2.x series; the main deployment should come during the 0.1.3.x
  11   series.
  12
  13 0.1. Goals and motivation: voting.
  14
  15   The current directory system relies on clients downloading separate
  16   network status statements from the caches signed by each directory.
  17   Clients download a new statement every 30 minutes or so, choosing to
  18   replace the oldest statement they currently have.
  19
  20   This creates a partitioning problem: different clients have different
  21   "most recent" networkstatus sources, and different versions of each
  22   (since authorities change their statements often).
  23
  24   It also creates a scaling problem: most of the downloaded networkstatus
  25   are probably quite similar, and the redundancy grows as we add more
  26   authorities.
  27
  28   So if we have clients only download a single multiply signed consensus
  29   network status statement, we can:
  30        - Save bandwidth.
  31        - Reduce client partitioning
  32        - Reduce client-side and cache-side storage
  33        - Simplify client-side voting code (by moving voting away from the
  34          client)
  35
  36   We should try to do this without:
  37        - Assuming that client-side or cache-side clocks are more correct
  38          than we assume now.
  39        - Assuming that authority clocks are perfectly correct.
  40        - Degrading badly if a few authorities die or are offline for a bit.
  41
  42   We do not have to perform well if:
  43       - No clique of more than half the authorities can agree about who
  44         the authorities are.
  45
  46 1. The idea.
  47
  48   Instead of publishing a network status whenever something changes,
  49   each authority instead publishes a fresh network status only once per
  50   "period" (say, 60 minutes).  Authorities either upload this network
  51   status (or "vote") to every other authority, or download every other
  52   authority's "vote" (see 3.1 below for discussion on push vs pull).
  53
  54   After an authority has (or has become convinced that it won't be able to
  55   get) every other authority's vote, it deterministically computes a
  56   consensus networkstatus, and signs it.  Authorities download (or are
  57   uploaded; see 3.1) one another's signatures, and form a multiply signed
  58   consensus.  This multiply-signed consensus is what caches cache and what
  59   clients download.
  60
  61   If an authority is down, authorities vote based on what they *can*
  62   download/get uploaded.
  63
  64   If an authority is "a little" down and only some authorities can reach
  65   it, authorities try to get its info from other authorities.
  66
  67   If an authority computes the vote wrong, its signature isn't included on
  68   the consensus.
  69
  70   Clients use a consensus if it is "trusted": signed by more than half the
  71   authorities they recognize. If clients can't find any such consensus,
  72   they use the most recent trusted consensus they have. If they don't
  73   have any trusted consensus, they warn the user and refuse to operate
  74   (and if DirServers is not the default, beg the user to adapt the list
  75   of authorities).
  76
  77 2. Details.
  78
  79 2.1. Vote specifications
  80
  81   Votes in v2.1 are similar to v2 network status documents.  We add these
  82   fields to the preamble:
  83
  84      "vote-status" -- the word "vote".
  85
  86      "valid-until" -- the time when this authority expects to publish its
  87         next vote.
  88
  89      "known-flags" -- a space-separated list of flags that will sometimes
  90         be included on "s" lines later in the vote.
  91
  92      "dir-source" -- as before, except the "hostname" part MUST be the
  93         authority's nickname, which MUST be unique among authorities, and
  94         MUST match the nickname in the "directory-signature" entry.
  95
  96   Authorities SHOULD cache their most recently generated votes so they
  97   can persist them across restarts.  Authorities SHOULD NOT generate
  98   another document until valid-until has passed.
  99
 100   Router entries in the vote MUST be sorted in ascending order by router
 101   identity digest.  The flags in "s" lines MUST appear in alphabetical
 102   order.
 103
 104   Votes SHOULD be synchronized to half-hour publication intervals (one
 105   hour? XXX say more; be more precise.)
 106
 107   XXXX some way to request older networkstatus docs?
 108
 109 2.2. Consensus directory specifications
 110
 111   Consensuses are like v2.1 votes, except for the following fields:
 112
 113      "vote-status" -- the word "consensus".
 114
 115      "published" is the latest of all the published times on the votes.
 116
 117      "valid-until" is the earliest of all the valid-until times on the
 118        votes.
 119
 120      "dir-source" and "fingerprint" and "dir-signing-key" and "contact"
 121        are included for each authority that contributed to the vote.
 122
 123      "vote-digest" for each authority that contributed to the vote,
 124        calculated as for the digest in the signature on the vote. [XXX
 125        re-English this sentence]
 126
 127      "client-versions" and "server-versions" are sorted in ascending
 128        order based on version-spec.txt.
 129
 130      "dir-options" and "known-flags" are not included.
 131 [XXX really? why not list the ones that are used in the consensus?
 132 For example, right now BadExit is in use, but no servers would be
 133 labelled BadExit, and it's still worth knowing that it was considered
 134 by the authorities. -RD]
 135
 136   The fields MUST occur in the following order:
 137      "network-status-version"
 138      "vote-status"
 139      "published"
 140      "valid-until"
 141      For each authority, sorted in ascending order of nickname, case-
 142      insensitively:
 143          "dir-source", "fingerprint", "contact", "dir-signing-key",
 144          "vote-digest".
 145      "client-versions"
 146      "server-versions"
 147
 148   The signatures at the end of the document appear as multiple instances
 149   of directory-signature, sorted in ascending order by nickname,
 150   case-insensitively.
 151
 152   A router entry should be included in the result if it is included by more
 153   than half of the authorities (total authorities, not just those whose votes
 154   we have).  A router entry has a flag set if it is included by more than
 155   half of the authorities who care about that flag.  [XXXX this creates an
 156   incentive for attackers to DOS authorities whose votes they don't like.
 157   Can we remember what flags people set the last time we saw them? -NM]
 158   [Which 'we' are we talking here? The end-users never learn which
 159   authority sets which flags. So you're thinking the authorities
 160   should record the last vote they saw from each authority and if it's
 161   within a week or so, count all the flags that it advertised as 'no'
 162   votes? Plausible. -RD]
 163
 164   The signature hash covers from the "network-status-version" line through
 165   the characters "directory-signature" in the first "directory-signature"
 166   line.
 167
 168   Consensus directories SHOULD be rejected if they are not signed by more
 169   than half of the known authorities.
 170
 171 2.2.1. Detached signatures
 172
 173   Assuming full connectivity, every authority should compute and sign the
 174   same consensus directory in each period.  Therefore, it isn't necessary to
 175   download the consensus computed by each authority; instead, the authorities
 176   only push/fetch each others' signatures.  A "detached signature" document
 177   contains a single "consensus-digest" entry and one or more
 178   directory-signature entries. [XXXX specify more.]
 179
 180 2.3. URLs and timelines
 181
 182 2.3.1. URLs and timeline used for agreement
 183
 184   An authority SHOULD publish its vote immediately at the start of each voting
 185   period.  It does this by making it available at
 186      http://<hostname>/tor/status-vote/current/authority.z
 187   and sending it in an HTTP POST request to each other authority at the URL
 188      http://<hostname>/tor/post/vote
 189
 190   If, N minutes after the voting period has begun, an authority does not have
 191   a current statement from another authority, the first authority retrieves
 192   the other's statement.
 193
 194   Once an authority has a vote from another authority, it makes it available
 195   at
 196       http://<hostname>/tor/status-vote/current/<fp>.z
 197   where <fp> is the fingerprint of the other authority's identity key.
 198
 199   The consensus network status, along with as many signatures as the server
 200   currently knows, should be available at
 201       http://<hostname>/tor/status-vote/current/consensus.z
 202   All of the detached signatures it knows for consensus status should be
 203   available at:
 204       http://<hostname>/tor/status-vote/current/consensus-signatures.z
 205
 206   Once an authority has computed and signed a consensus network status, it
 207   should send its detached signature to each other authority in an HTTP POST
 208   request to the URL:
 209       http://<hostname>/tor/post/consensus-signature
 210
 211
 212   [XXXX Store votes to disk.]
 213
 214 2.3.2. Serving a consensus directory
 215
 216   Once the authority is done getting signatures on the consensus directory,
 217   it should serve it from:
 218       http://<hostname>/tor/status/consensus.z
 219
 220   Caches SHOULD download consensus directories from an authority and serve
 221   them from the same URL.
 222
 223 2.3.3. Timeline and synchronization
 224
 225   [XXXX]
 226
 227 2.4. Distributing routerdescs between authorities
 228
 229   Consensus will be more meaningful if authorities take steps to make sure
 230   that they all have the same set of descriptors _before_ the voting
 231   starts.  This is safe, since all descriptors are self-certified and
 232   timestamped: it's always okay to replace a signed descriptor with a more
 233   recent one signed by the same identity.
 234
 235   In the long run, we might want some kind of sophisticated process here.
 236   For now, since authorities already download one another's networkstatus
 237   documents and use them to determine what descriptors to download from one
 238   another, we can rely on this existing mechanism to keep authorities up to
 239   date.
 240
 241   [We should do a thorough read-through of dir-spec again to make sure
 242   that the authorities converge on which descriptor to "prefer" for
 243   each router. Right now the decision happens at the client, which is
 244   no longer the right place for it. -RD]
 245
 246 3. Questions and concerns
 247
 248 3.1. Push or pull?
 249
 250   The URLs above define a push mechanism for publishing votes and consensus
 251   signatures via HTTP POST requests, and a pull mechanism for downloading
 252   these documents via HTTP GET requests.  As specified, every authority will
 253   post to every other.  The "download if no copy has been received" mechanism
 254   exists only as a fallback.
 255
 256 4. Migration
 257
 258      * It would be cool if caches could get ready to download consensus
 259        status docs, verify enough signatures, and serve them now.  That way
 260        once stuff works all we need to do is upgrade the authorities.  Caches
 261        don't need to verify the correctness of the format so long as it's
 262        signed (or maybe multisigned?).  We need to make sure that caches back
 263        off very quickly from downloading consensus docs until they're
 264        actually implemented.
 265