diff options
Diffstat (limited to 'doc/spec/proposals/165-simple-robust-voting.txt')
| -rw-r--r-- | doc/spec/proposals/165-simple-robust-voting.txt | 133 |
1 files changed, 0 insertions, 133 deletions
diff --git a/doc/spec/proposals/165-simple-robust-voting.txt b/doc/spec/proposals/165-simple-robust-voting.txt deleted file mode 100644 index f813285a83..0000000000 --- a/doc/spec/proposals/165-simple-robust-voting.txt +++ /dev/null @@ -1,133 +0,0 @@ -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. |