1 files changed, 133 insertions, 0 deletions
diff --git a/doc/spec/proposals/165-simple-robust-voting.txt b/doc/spec/proposals/165-simple-robust-voting.txt
new file mode 100644
index 0000000000..f813285a83
--- /dev/null
+++ b/doc/spec/proposals/165-simple-robust-voting.txt
@@ -0,0 +1,133 @@
+Filename: 165-simple-robust-voting.txt
+Title: Easy migration for voting authority sets
+Author: Nick Mathewson
+Created: 2009-05-28
+Status: Open
+
+Overview:
+
+  This proposal describes any easy-to-implement, easy-to-verify way to
+  change the set of authorities without creating a "flag day" situation.
+
+Motivation:
+
+  From proposal 134 ("More robust consensus voting with diverse
+  authority sets") by Peter Palfrader:
+
+      Right now there are about five authoritative directory servers
+      in the Tor network, tho this number is expected to rise to about
+      15 eventually.
+
+      Adding a new authority requires synchronized action from all
+      operators of directory authorities so that at any time during the
+      update at least half of all authorities are running and agree on
+      who is an authority.  The latter requirement is there so that the
+      authorities can arrive at a common consensus: Each authority
+      builds the consensus based on the votes from all authorities it
+      recognizes, and so a different set of recognized authorities will
+      lead to a different consensus document.
+
+  In response to this problem, proposal 134 suggested that every
+  candidate authority list in its vote whom it believes to be an
+  authority.  These A-says-B-is-an-authority relationships form a
+  directed graph.  Each authority then iteratively finds the largest
+  clique in the graph and remove it, until they find one containing
+  them.  They vote with this clique.
+
+  Proposal 134 had some problems:
+
+    - It had a security problem in that M hostile authorities in a
+      clique could effectively kick out M-1 honest authorities.  This
+      could enable a minority of the original authorities to take over.
+
+    - It was too complex in its implications to analyze well: it took us
+      over a year to realize that it was insecure.
+
+    - It tried to solve a bigger problem: general fragmentation of
+      authority trust.  Really, all we wanted to have was the ability to
+      add and remove authorities without forcing a flag day.
+
+Proposed protocol design:
+
+   A "Voting Set" is a set of authorities.  Each authority has a list of
+   the voting sets it considers acceptable.  These sets are chosen
+   manually by the authority operators. They must always contain the
+   authority itself.  Each authority lists all of these voting sets in
+   its votes.
+
+   Authorities exchange votes with every other authority in any of their
+   voting sets.
+
+   When it is time to calculate a consensus, an authority votes with
+   whichever voting set it lists that is listed by the most members of
+   that set.  In other words, given two sets S1 and S2 that an authority
+   lists, that authority will prefer to vote with S1 over S2 whenever
+   the number of other authorities in S1 that themselves list S1 is
+   higher than the number of other authorities in S2 that themselves
+   list S2.
+
+   For example, suppose authority A recognizes two sets, "A B C D" and
+   "A E F G H".  Suppose that the first set is recognized by all of A,
+   B, C, and D, whereas the second set is recognized only by A, E, and
+   F.  Because the first set is recognize by more of the authorities in
+   it than the other one, A will vote with the first set.
+
+   Ties are broken in favor of some arbitrary function of the identity
+   keys of the authorities in the set.
+
+How to migrate authority sets:
+
+   In steady state, each authority operator should list only the current
+   actual voting set as accepted.
+
+   When we want to add an authority, each authority operator configures
+   his or her server to list two voting sets: one containing all the old
+   authorities, and one containing the old authorities and the new
+   authority too.  Once all authorities are listing the new set of
+   authorities, they will start voting with that set because of its
+   size.
+
+   What if one or two authority operators are slow to list the new set?
+   Then the other operators can stop listing the old set once there are
+   enough authorities listing the new set to make its voting successful.
+   (Note that these authorities not listing the new set will still have
+   their votes counted, since they themselves will be members of the new
+   set.  They will only fail to sign the consensus generated by the
+   other authorities who are using the new set.)
+
+   When we want to remove an authority, the operators list two voting
+   sets: one containing all the authorities, and one omitting the
+   authority we want to remove.  Once enough authorities list the new
+   set as acceptable, we start having authority operators stop listing
+   the old set.  Once there are more listing the new set than the old
+   set, the new set will win.
+
+Data format changes:
+
+   Add a new 'voting-set' line to the vote document format.  Allow it to
+   occur any number of times.  Its format is:
+
+      voting-set SP 'fingerprint' SP 'fingerprint' ... NL
+
+   where each fingerprint is the hex fingerprint of an identity key of
+   an authority.  Sort fingerprints in ascending order.
+
+   When the consensus method is at least 'X' (decide this when we
+   implement the proposal), add this line to the consensus format as
+   well, before the first dir-source line.  [This information is not
+   redundant with the dir-source sections in the consensus: If an
+   authority is recognized but didn't vote, that authority will appear in
+   the voting-set line but not in the dir-source sections.]
+
+   We don't need to list other information about authorities in our
+   vote.
+
+Migration issues:
+
+   We should keep track somewhere of which Tor client versions
+   recognized which authorities.
+
+Acknowledgments:
+
+   The design came out of an IRC conversation with Peter Palfrader.  He
+   had the basic idea first.