Proposal 165: Easy migration for voting authority sets
nickm at torproject.org
Thu May 28 16:51:13 UTC 2009
Title: Easy migration for voting authority sets
Author: Nick Mathewson
This proposal describes any easy-to-implement, easy-to-verify way to
change the set of authorities without creating a "flag day" situation.
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
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
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
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
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
We should keep track somewhere of which Tor client versions
recognized which authorities.
The design came out of an IRC conversation with Peter Palfrader. He
had the basic idea first.
More information about the tor-dev