Proposal: More robust consensus voting with diverse authority sets

[Peter Palfrader]

On Tue, 29 Apr 2008, Nick Mathewson wrote:

> So, afaik, the sole remaining big problem in this proposal is
> migration.  IIUC, the current consensus-method thing won't work, for
> reasons explained in an earlier message of mine on this thread:

The thing Nick came up with on IRC was to simply consider all votes
uploaded by authorities running the old software to have an implicit
| Recognizes-Authorites: <current (as of now, May 2008) list of authorities>
line.  They will behave like this is their clique, and upgraded
authorities will continue to think this is their clique until new
servers not trusted by the old folks outnumber those that haven't
upgraded.

This probably looks fine.


> I decided that I'd eel better about the NP-hard thing if we codde up
> the sample C implementation and found out that it scaled well to a
> large number of authorities.

I have implemented this, with a tweak or two in C, and it all works fine
for up to 50 or 60 nodes but once we go towards 100 it all goes pear
shaped.  It _is_ a simple minded approach after all.
[ git clone http://asteria.noreply.org/~weasel/tor-trunk-maxclique.git
  see src/common/graph* and src/util/graph-bench.c ]


One more problem surfaced: This proposal opens up authorities for DoS
attacks by other authorities:

Remember that per the proposal all uploaded votes are accepted, but only
those reachable (directly or indirectly) from recognized authorities are
considered during the maxclique() run.  This gets rid of any muppetry
done by outsiders.

But if a fellow authority operator introduces a large set of other
authorities and recognizes them all or some of them then that can blow
up our graph to sizes we cannot manage.


While discussing this with Nick and Sebastian on IRC we came up with a
number of ideas, most of which don't work:

Bad idea 1: limit the number of authorities any authority is allowed to
   say it trusts.

   A malicous authority can still introduce any number of extra nodes.
   It only needs to list one of them, and they in turn only need to list
   a few and so on for all of them to end up in our graph.  Now our
   simple algorithm does not do particularly bad on sparse graphs but it
   is likly that a specially crafted graph could still make us spend
   ages on figuring out cliques.

Bad idea 3: only accept authorities in our graph when they are
   recognized by at least two other authorities.

   a) Going from "one authority can screw us over" to "two authorities
      can screw us" is not a huge gain.
   b) Why two?  why not three?  four?  five?

Bad idea 2: only try to find the largest clique that this authority (the
   one doing the computation) is in.

   This is not as obviously bad in my opinion as Nick originally
   suggested:

   Finding the maximum clique that I'm in is bounded by the amount of
   authorities I recognize and nobody can screw me with that.

   True, we no longer can guarantee that *all* authorities arrive at the
   same cliques, but does it matter?  I suppose that we will always
   have a sufficient number of authorities that agree they are in the
   same clique to form a working consensus.

   Some authorities will be left out in the cold if all the people who
   they think are in their clique went with a larger clique instead but
   then this authority doesn't succeed in building a consensus (too few
   sigs from other authories).

   (insert handwaving here, you don't need to see a proof).

   Nick, is there another reason why this idea is really bad, or is my
   handwaving above wrong?)


Peter