Proposal: More robust consensus voting with diverse authority sets

[Peter Palfrader]

For those reading along at home, such fully connected subgraphs as
written about in the procedure are called cliques.
See http://en.wikipedia.org/wiki/Clique_problem for a short overview.
Finding the maximum clique is an NP hard problem, but it might just
scale to up to our 20 nodes.  There is literature on how to solve it,
for instance Steven Murdoch found "An Exact Parallel Algorithm For The
Maximum Clique Problem" by  Panos M. Pardalos, Jonas Rappe, Mauricio
G.C. Resende - <URL:http://citeseer.ist.psu.edu/pardalos98exact.html>.


Also, it's easy to reduce our directed graph to an undirected graph.  An
edge in the new, undirected graph exists between nodes A and B iff there
is an edge from A to B and an edge from B to A in the undirected graph.
Doing the clique finding dance on that simplified graph should yield the
same result as doing it on the original one.

On Tue, 01 Apr 2008, Nick Mathewson wrote:

>   Q: What does this do for cacheing?  Currently, there is at most once
>      live consensus at a time, and caches cache that.  What do caches
>      do if there are multiple consensuses?  Do they act as clients do
>      now, and only accept a consensus if it is signed by a majority of
>      the authorities they recognize?  If so, will this ever lead to
>      caches holding documents clients don't want, or repeatedly
>      bugging the authorities for a consensus they don't have?  If so,
>      what can be done?

I think that caches should only cache one consensus, and it should be
one they trust.  As long as each authority only ever signs one consensus
document at a time where will at most be one such consensus.

Also, maybe the procedure in the proposal should be changed slightly to
add one more point:  No authority signs a consensus that it itself
wouldn't trust - i.e. if the clique it is in is not larger than the
number of authorities it recognizes (including itself) then it bails
out and doesn't create any consensus this round.

This results in having fewer useless consensus documents that caches
need to fetch only to learn that - with all likelyhood - they will not
trust it either.


>   Q: How do we do this in a backward compatible way?  There should be
>      a spec for that too.

I didn't look into this yet, since we first should figure out what we
want it to do.  Then I guess we do the same thing we did when we
introduced Unnamed, i.e. add a new consensus method (#3) that we
advertise as supporting.

I would assume - I haven't checked the spec or code - that once half of
the authorities advertise consensus method 3 this is the one they'll
use?  In which case they better be able to build a consensus but we're
no worse off than we were before when adding a new authority.  We just
need this last coordinated round of upgrades.


>   A less technical Q: What opportunities does this create for social
>      attacks?  One of the reasons for choosing the current voting
>      approach was to limit the incentives for a social attacker to
>      attempt to peel off authorities by convincing only some of them
>      to accept a slightly looking bogus authority.  There have been
>      similar attacks in the remailer world, I believe.  How can we
>      make this less likely?

I do not have an answer here, other than only make clueful people
directory authorities.

Peter