Add Peter Palfrader's proposal 134: More robust consensus voting with diverse authority sets

svn:r14273

1 files changed, 104 insertions, 0 deletions

diff --git a/proposals/134-robust-voting.txt b/proposals/134-robust-voting.txt
new file mode 100644
index 0000000..8e2173d
--- /dev/null
+++ b/proposals/134-robust-voting.txt
@@ -0,0 +1,104 @@
+Filename: 134-robust-voting.txt
+Title: More robust consensus voting with diverse authority sets
+Author: Peter Palfrader
+Created: 2008-04-01
+Status: Draft
+
+Overview:
+
+  A means to arrive at a valid directory consensus even when voters
+  disagree on who is an authority.
+
+
+Motivation:
+
+  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.
+
+
+Objective:
+
+  The modified voting procedure outlined in this proposal obsoletes the
+  requirement for most authorities to exactly agree on the list of
+  authorities.
+
+
+Proposal:
+
+  The vote document each authority generates contains a list of 
+  authorities recognized by the generating authority.  This will be 
+  a list of authority identity fingerprints.
+
+  Authorities will accept votes from and serve/mirror votes also for
+  authorities they do not recognize.  (Votes contain the signing,
+  authority key, and the certificate linking them so they can be 
+  verified even without knowing the authority beforehand.)
+
+  Before building the consensus we will check which votes to use for
+  building:
+
+   1) We build a directed graph of which authority/vote recognizes
+      whom.
+   2) (Parts of the graph that aren't reachable, directly or
+      indirectly, from any authorities we recognize can be discarded
+      immediately.)
+   3) We find the largest fully connected subgraph.
+      (Should there be more than one subgraph of the same size there
+      needs to be some arbitrary ordering so we always pick the same.
+      E.g. pick the one who has the smaller (XOR of all votes' digests)
+      or something.)
+   4) If we are part of that subgraph, great.  This is the list of 
+      votes we build our consensus with.
+   5) If we are not part of that subgraph, remove all the nodes that
+      are part of it and go to 3.
+
+  Using this procedure authorities that are updated to recognize a
+  new authority will continue voting with the old group until a
+  sufficient number has been updated to arrive at a consensus with
+  the recently added authority.
+
+  In fact, the old set of authorities will probably be voting among
+  themselves until all but one has been updated to recognize the
+  new authority.  Then which set of votes is used for consensus 
+  building depends on which of the two equally large sets gets 
+  ordered before the other in step (3) above.
+
+  It is necessary to continue with the process in (5) even if we
+  are not in the largest subgraph.  Otherwise one rogue authority
+  could create a number of extra votes (by new authorities) so that
+  everybody stops at 5 and no consensus is built, even tho it would
+  be trusted by all clients.
+
+
+Anonymity Implications:
+
+  The author does not believe this proposal to have anonymity
+  implications.
+
+
+Possible Attacks/Open Issues/Some thinking required:
+
+ Q: Can a number (less or exactly half) of the authorities cause an honest
+    authority to vote for "their" consensus rather than the one that would
+    result were all authorities taken into account?
+
+
+ Q: Can a set of votes from external authorities, i.e of whom we trust either
+    none or at least not all, cause us to change the set of consensus makers we
+    pick?
+ A: Yes, if other authorities decide they rather build a consensus with them
+    then they'll be thrown out in step 3.  But that's ok since those other
+    authorities will never vote with us anyway.
+    If we trust none of them then we throw them out even sooner, so no harm done.
+
+ Q: Can this ever force us to build a consensus with authorities we do not
+    recognize?
+ A: No, we can never build a fully connected set with them in step 3.