101-dir-voting.txt 11 KB

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