Filename: 134-robust-voting.txt
Title: More robust consensus voting with diverse authority sets
Author: Peter Palfrader
Created: 2008-04-01
Status: Rejected
History:
2009 May 27: Added note on rejecting this proposal -- Nick
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.
------------------------------
I'm rejecting this proposal as insecure.
Suppose that we have a clique of size N, and M hostile members in the
clique. If these hostile members stop declaring trust for up to M-1
good members of the clique, the clique with the hostile members will
in it will be larger than the one without them.
The M hostile members will constitute a majority of this new clique
when M > (N-(M-1)) / 2, or when M > (N + 1) / 3. This breaks our
requirement that an adversary must compromise a majority of authorities
in order to control the consensus.
-- Nick