Proposal 165: Easy migration for voting authority sets

[Nick Mathewson <nickm@xxxxxxxxxxxxxx>]

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 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 comes time to calculate a consensus, an authority votes with
   whichever voting set it lists that is listed by the most members of
   that set.

   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 should list only the current actual
   voting set as accepted.

   When we want to add an authority, we 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 preferring that
   set because of its size.

   When we want to remove an authority, we 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 authorities 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 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.