Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) Potential improvement to balloting protocol, setting cCounter

[Piers Powlesland <[e-mail]>]

Yes I did mix up the hCounters in my example, your interpretation was
correct. Your last explanation does make sense but seems to be at odds with
your previous statement which confused me.

>It's only safe to vote to commit a ballot b if
>ballot == b at the time b was confirmed prepared

I think that statement is too strict, since it precludes voting to commit
ballots (3,x)...(7,x) from my previous example. In fact I think this
statement would be correct if it is describing the point at which a node
starts voting to commit a ballot. (I.E when c changes from NULL to some
integer)

So instead we can say it is only safe to vote to commit a ballot if the
ballot has been confirmed prepared and we have not voted or accepted abort
for it.

So put simply, my original suggestion, was to modify the algorithm to vote
to commit all confirmed prepared ballots that have not been voted or
accepted aborted. I see that my proposed update step doesn't quite achieve
that, since as you pointed out it might set c such that we are voting to
commit a ballot that we previously voted to abort.

I've modified the update step again, I think this would work correctly.

Replacing the first update step for c with the following three steps.

> * If "c != NULL" and "(preparedPrime > c && preparedPrime.value !=
c.value)"
>   raise c.counter to the lowest value such that c > preparedPrime.
>
> * If "c != NULL" and "(prepared > c && prepared.value != c.value)"
>   raise c.counter to the lowest value such that c > prepared.
>
> * If c.counter > hCounter then reset "c = NULL"

We can see that this update step precludes voting to commit and voting to
abort the same ballot. Since when c != NULL we know that a ballot has been
confirmed prepared (we know this because c cannot be set unless hCounter is
set and hCounter represents a confirmed prepared ballot). Given that a
ballot has been confirmed prepared, we know nomination has stopped, so the
only way that this node can change it's ballot.value is to accept an
incompatible *higher* ballot prepared via blocking threshold and then
confirm it, the next time ballot.counter changes ballot.value will take the
value of the newly confirmed prepared ballot. So we can see that given a
state where cCounter and hCounter have been set, it is impossible to vote
to abort any ballot we are currently voting to commit without first
accepting it prepared and when it is accepted prepared c will be updated to
ensure that we are no longer voting to commit that ballot.

So the full set of update steps for c would then be.

> * If "c != NULL" and "(preparedPrime > c && preparedPrime.value !=
c.value)"
>   raise c.counter to the lowest value such that c > preparedPrime.
>
> * If "c != NULL" and "(prepared > c && prepared.value != c.value)"
>   raise c.counter to the lowest value such that c > prepared.
>
> * If c.counter > hCounter then reset "c = NULL"
>
> *  If "c == NULL" and "hCounter == ballot.counter" (meaning
>    "ballot" is confirmed prepared), then set "c" to "ballot".

I hope that makes sense. And yes I think putting this rationale into the
document would make it much easier to understand. The way the algorithm is
presented currently gives you a lot of isolated update steps but it is not
clear how they are linked to each other and it is even less clear why they
are as they are. For myself at least it would have been really useful to
see a derivation of sorts from the high level concepts behind the protocol
to the very compact form in which the protocol is specified in the IETF
document.

On Sat, 3 Nov 2018, 07:22 David Mazieres <[e-mail]
wrote:

> Piers Powlesland <[e-mail]> writes:
>
> > I have a few things I'm not clear on.
> >
> > I don't see that this statement is correct.
> >
> >>You mean transition to voting to commit nothing?  (Though still
> >>vote-or-confirm (n,x) for 4 <= n <= 8.)
> >
> > So following the update steps for c, first the c will be set to NULL
> > and then the next step will be executed.
> >
> >> * If "c == NULL" and "hCounter == ballot.counter" (meaning
> >>    "ballot" is confirmed prepared), then set "c" to "ballot".
> >
> > Resulting in the following node state.
> >
> > ballot = (8,x)
> > prepared = (8,x)
> > preparedPrime = (4,z)
> > cCounter = 8
> > hCounter = 8
> >
> > Which as described in the IETF document would I think means the node
> > now is voting to commit(8,x) ?
>
> Oh, yes, sorry.  But importantly you are no longer voting to commit
> (5,x) and (6,x).
>
> >> * If "cCounter != 0": "vote commit(<n, ballot.value>)" for every
> "cCounter <= n <= hCounter"
> >
> > Also what is "vote-or-confirm" ?
>
> Sorry, another mistake on my part.  I meant vote-or-accept.
>
> > I can imagine the following scenario that seems to be allowable via
> > the IETF update rules that would allow a node to illegally vote for a
> > range of ballots that the node has never set its ballot equal to.
> >
> > The node starts with the following state. It is currently voting to
> > commit(2,x) among other things.
> >
> > ballot =(2,x)
> > prepared =(2,x)
> > preparedPrime =(1,y)
> > cCounter =2
> > hCounter =2
> >
> > Now we see blocking threshold for accept prepare(8,x)
> >
> > ballot =(8,x) // ballot.counter was also updated by the blocking
> threshold.
> > prepared =(8,x)
> > preparedPrime =(1,y)
> > cCounter =2
> > hCounter =8
> >
> > Now we see quorum threshold for accept prepare(8,x) (we have confirmed
> > prepared (8,x) and h.value == b.value so we set hCounter to 8)
> >
> > ballot =(8,x)
> > prepared =(8,x)
> > preparedPrime =(1,y)
> > cCounter =2
> > hCounter =8
>
> Sorry, what's the difference between this and above?  I'm assuming you
> meant hCounter=2 above, and hCounter=8 here.
>
> > So now we are voting to commit, 2...8 with value == x but ballot has
> > never been set to a ballot with counter  3...7 and value == x. Doesn't
> > this make it illegal to vote to commit (3,x)...(7,x)?
>
> No, that's okay.  The thing we actually need to avoid is voting to abort
> and commit the same ballot b.  In this case that's fine because you
> never voted to abort any of (3,x)...(7,x).  The protocol could of course
> keep track of very vote you have ever cast to make sure this is okay.
> Instead, to keep the state small, it uses the trick that you reset c to
> 0 whenever the ballot might contain a new value, and then you have to
> set c to the current ballot number, because the (conservative)
> assumption is that if c == 0, then you might have voted to abort any
> ballot less than the current ballot.
>
> Does that make sense?  Maybe some of this rationale needs to go into the
> document...
>
> David
>