Proposal 165: Easy migration for voting authority sets

[Paul Syverson]

On Thu, May 28, 2009 at 04:23:57PM -0400, Nick Mathewson wrote:
> On Thu, May 28, 2009 at 03:58:42PM -0400, Paul Syverson wrote:
> > Hi Nick et al.,
> > 
> > Two things:
> > 
> > 1. I think you mean that an authority votes with whatever the largest
> > set is that it lists that is listed by the most members of that set. 
> > (I added "largest" to your criterion.)
> > 
> > I guess there is an ambiguity of 'most' but if you have a set and a
> > proper subset, both of which are listed by all the members of each,
> > then the ones in the smaller set have no basis to prefer the larger
> > one and will never drop the smaller one. If by 'most' you implicitly
> > mean biggest rather than largest fraction, it is confusing since
> > it is no longer relative to the givne voting set but relative to
> > others.
> 
> Okay, I'll try again.  What I meant is that, given two sets S1 and S2 that an
> authority lists, that authority will prefer S1 over S2 whenever the
> number of other authorities in S1 that themselves list S1 is higher
> than the number of other authorities in S2 that themselves list S2.
> 

Much clearer, at least to me.


> > 2. More significantly, there is something I don't get about the
> > proposal. I think I understand the problem with proposal 134. It seems
> > like a standard byzantine failure when there are not at least 3n+1
> > honest and correct voters, where n is the number of dishonest, but I
> > didn't look at it closely to see if there are some differences.
> > 
> > The new proposal is not that bad, but it still allows a single
> > hostile authority to prevent the addition of a new authority.
> > 
> > If Alice does not want to add authority Bob, then she
> > refuses to make a voting set containing him. Other honest-correct
> > authorities will not prefer the new voting set until some of them drop
> > the old one that did not have Bob in it. But none of them should
> > ever do that because the voting set without Bob in it is preferred by
> > a larger majority of its members.
> 
> Right.
> 
> Please take the entire section "How to migrate authority sets" as
> normative rather than a complete description of how to upgrade: if one
> of the authority operators doesn't participate, then the other
> operators need to manually intervene and either stop listing sets that
> include that operator's authority, or convince that operator to
> upgrade.

Yes. I was going to suggest something like that, but I wanted to make
sure I understood first. Also, I wasn't confident exactly what else
could happen once that were allowed. I'm still not sure, but maybe
it's fine. I need to think about it more or to be convinced.
Anyway, might be moot. See below.

> 
> > If 'most' is interpreted as discussed in 1. above, the same problem
> > applies, but you need two hostile authorities to make sure Bob can never
> > get in no matter what the rest of the authorities do.
> 
> Well, that's only unless 3 other authorities stop listing the sets
> that _don't_ include Bob.
> 

Right, but they shouldn't if they are honest. See below.

> > Similarly, if the honest authorities want to drop Bob, as long as two
> > existing authorities (possibly but not necessarily one being Bob) want
> > to maintain him, then none should ever delist the larger set because
> > it will always be preferred over the smaller one. So he won't
> > get dropped.
> 
> Here you're missing the line that says
> 
>    Once enough authorities list the new set as acceptable, we start
>    having authorities stop listing the old set.  Once there are more
>    listing the new set than the old set, the new set will win.
> 
> In other words, once the operators notice that enough authorities are
> listing the set-minus-Bob, they manually stop listing
> sets-including-Bob.  Assuming that there are N authorities (including
> Bob), once N-1 authorities list the set without Bob, we need just 2
> authorities to drop the set including Bob and we'll be fine.
> 

I didn't miss the line. My point is that you won't ever get
any honest authorities to drop the set including Bob, so you will
never make it to 2 without changing something in the protocol.
if either of those two authorities drop the list that includes Bob,
they will not be honest (following the proposed protocol), because
they are supposed to prefer the voting set for which the number of
authorities that list themselves in it is higher not just the
one that is moving in the direction they would like to go.
It's the criterion for delisting a set that does not work.



You don't want to force simultaneous action: that was the whole point.
And you don't want to let a minority remove Bob on their own.  I think
you need to add something like an explicit suggested voting set change
to the protocol rather than it just being implicit in the voting sets
everyone has. If there is an explicit suggestion to replace one voting
set with another, then once a majority have started listing the new
set any one of them can correctly delist the old one. Maybe you
had something like that implicitly in mind, but I didn't see it in
the proposal. (Or maybe I'm still wrong and still dont see it?)


> 
> The important insight about the difference between this proposal and
> proposal 134 is that proposal 165 fails conservatively, and only fails
> during migration: Given a functional authority set endorsed by all
> honest authorities, I think there is nothing a hostile minority can do
> on their to make the honest authorities stop generating a correct
> consensus with that authority set.
> 

I kind of agree. My intuition is that what they can do, however,
is prevent the set of authorities from ever changing, and "they"
can be even smaller than just a minority: two authorities suffice.
See if you think the above fixes it.

aloha,
Paul