Proposal 165: Easy migration for voting authority sets

[Nick Mathewson]

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.

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

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

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


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.

yrs,
-- 
Nick