Proposal: More robust consensus voting with diverse authority sets

[Nick Mathewson]

On Wed, Apr 02, 2008 at 10:58:34AM +0200, Peter Palfrader wrote:
 [...]
> 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 is a good idea, I think.

> 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.

Hm.  I'm still not at all fond of the failure mode where a client
downloads a consensus, decides it doesn't like it, and downloads
another and another ad infinitum.  This seems like a potential
problem: the network would run find for a while until one day the set
of authorities signing the dominant consensus was not one that older
clients liked... and then, those clients would start eating bandwidth.
I agree that this would happen only rarely, but it has potential to be
quite nasty when it _does_ happen.  Perhaps we could add a URL format
in order to request a consensus only if it's endorsed by certain
authorities?
 
> >   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.

The 'consensus method' thing is only meant to determine which
algorithm the voting authorities use to produce the consensus from the
votes, not which authorities' votes count.  We should take a close
look at the spec and implementation for it to make sure it can be
extended this way.

> >   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.

Yeah, I tend to believe this one.

Another question, based on our brief IRC conversation the other day:
There seems to be a goals/methods disconnect in this proposal.  Given
that the only application for this proposal is to be able to add or
remove authorities from the list without, it seems like overkill to
solve the more general problem of what do we do with an arbitrarily
screwed-up authority trust graph.  Is there a simpler approach that
does what we want, or do we really need to do the NP-hard thing?

yrs,
-- 
Nick Mathewson