[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[or-cvs] [tor/master] Proposal 165: Easy migration for voting authority sets.
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Thu, 28 May 2009 12:48:38 -0400
Subject: Proposal 165: Easy migration for voting authority sets.
Commit: 2c8b56c029988adf65c38fc34fdba6d91cd0608c
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.
---
doc/spec/proposals/000-index.txt | 2 +
doc/spec/proposals/165-simple-robust-voting.txt | 119 +++++++++++++++++++++++
2 files changed, 121 insertions(+), 0 deletions(-)
create mode 100644 doc/spec/proposals/165-simple-robust-voting.txt
diff --git a/doc/spec/proposals/000-index.txt b/doc/spec/proposals/000-index.txt
index b2907e0..b26f382 100644
--- a/doc/spec/proposals/000-index.txt
+++ b/doc/spec/proposals/000-index.txt
@@ -85,6 +85,7 @@ Proposals by number:
162 Publish the consensus in multiple flavors [OPEN]
163 Detecting whether a connection comes from a client [OPEN]
164 Reporting the status of server votes [OPEN]
+165 Easy migration for voting authority sets [OPEN]
Proposals by status:
@@ -111,6 +112,7 @@ Proposals by status:
162 Publish the consensus in multiple flavors [for 0.2.2]
163 Detecting whether a connection comes from a client [for 0.2.2]
164 Reporting the status of server votes [for 0.2.2]
+ 165 Easy migration for voting authority sets
ACCEPTED:
110 Avoiding infinite length circuits [for 0.2.1.x] [in 0.2.1.3-alpha]
117 IPv6 exits [for 0.2.1.x]
diff --git a/doc/spec/proposals/165-simple-robust-voting.txt b/doc/spec/proposals/165-simple-robust-voting.txt
new file mode 100644
index 0000000..d8993c9
--- /dev/null
+++ b/doc/spec/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.
--
1.5.6.5