From 04e23fd70ae6fa7582244836febdee3808b7e0ca Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 1 Apr 2008 15:23:44 +0000 Subject: Add Peter Palfrader's proposal 134: More robust consensus voting with diverse authority sets svn:r14273 --- proposals/134-robust-voting.txt | 104 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 104 insertions(+) create mode 100644 proposals/134-robust-voting.txt (limited to 'proposals/134-robust-voting.txt') 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. -- cgit v1.2.3-54-g00ecf