From b90276b15aeef737b3eca2801f6f94a22253a337 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Thu, 28 May 2009 12:48:38 -0400 Subject: Proposal 165: Easy migration for voting authority sets. This proposal tries to do what 134 tried to do, but more securely and with less whiz-bang NP-hard computation. Peter had the basic idea. --- proposals/165-simple-robust-voting.txt | 119 +++++++++++++++++++++++++++++++++ 1 file changed, 119 insertions(+) create mode 100644 proposals/165-simple-robust-voting.txt (limited to 'proposals/165-simple-robust-voting.txt') diff --git a/proposals/165-simple-robust-voting.txt b/proposals/165-simple-robust-voting.txt new file mode 100644 index 0000000..d8993c9 --- /dev/null +++ b/proposals/165-simple-robust-voting.txt @@ -0,0 +1,119 @@ +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. -- cgit v1.2.3-54-g00ecf