Proposal: More robust consensus voting with diverse authority sets

[Paul Syverson]

On Fri, May 02, 2008 at 10:42:41AM +0200, Peter Palfrader wrote:
> 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.
> 

Sounds like you could use some max_flow/min_cut mechanism as in
advogato so that you are only counting votes proportional to the root
of trust. Unlike advogato you don't want to have just one root, since
that would defeat the purpose, but you could still have a mechanism
like this that is only going add nodes to the graph proportional to
trust of root authorities and you can't recursively add more as
described above out of proportion to the trust level. To add more root
authorities would need a separate external mechanism, which should be
easy to do as long as that is not intended to scale much at all.
Apologies if I am making an irrelevant or already considered and
rejected suggested by jumping into a conversation almost all of which
I have not observed.

aloha,
Paul