123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133 |
- 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.
|