proposals/101-dir-voting.txt

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