1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
Filename: 165-simple-robust-voting.txt
Title: Easy migration for voting authority sets
Author: Nick Mathewson
Created: 2009-05-28
Status: Rejected
Status: rejected as too complex.
Overview:
This proposal describes an 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 picks votes from
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 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.
|
