Proposal: More robust consensus voting with diverse authority sets

[Peter Palfrader]

On Thu, 01 May 2008, Peter Palfrader wrote:

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


Hah.  But we can use this.

First, realize that all we care about is how the authorities that are in
our cliques.  I.e. we only care how the authorities vote that we
recognize.  We only want to know if they are part of our voting clique
or not.

Then we no longer need to solve maxclique() over the entire graph, but
we only need to solve maxclique_that_has_point_A_in_it() with A being
each of the authorities we trust.

Now maxclique_that_has_point_P_in_it() in itself hard also*, however we
can make our live easier by limiting the number of authorities that one
may list.  If we discard votes with too many neighbors early we
effectively have created a reasonable upper bound for the amount of work
we have to do while clique finding.

weasel


(I still like the bad idea #2 from the previous post, but that's not as
easy to show as correct.)

* (if maxclique_that_has_point_P_in_it() was in P then I could just run
   it for each point A in the graph and use the largest clique I found
   as my answer for maxclique().)