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

[Piers Powlesland <[e-mail]>]

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) ?

> * If "cCounter != 0": "vote commit(<n, ballot.value>)" for every "cCounter <= n <= hCounter"

Also what is "vote-or-confirm" ?

>> Out of the ballots that the node was previously voting to commit only
>> (4,x) has been accepted aborted due to setting preparedPrime = (4,z),
>> so it seems that it would still be legal to vote to commit ballots
>> with value == x and counters 5...8.
>
>Not necessarily.  Whether or not it's safe to commit (5,x) depends on
>history.  It's only safe to vote to commit a ballot b if ballot == b at
>the time b was confirmed prepared.  If, for instance, hCounter jumps
>from 0 to 8 in the history, then the node has no memory of whether it
>is, say voted to prepare (4,z), which would make it illegal to vote to
>commit (4,x).

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

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)?




On Fri, Nov 2, 2018 at 2:59 PM David Mazieres
<[e-mail]> wrote:
>
> Piers Powlesland <[e-mail]> writes:
>
> > I think it may be possible to improve the chances of nodes being able
> > to accept ballots as committed during the prepare phase.
> >
> > The following instructions are given to update cCounter.
> >
> >> * If either "(prepared > c && prepared.value != c.value)" or
> >>   "(preparedPrime > c && preparedPrime.value != c.value)", then
> >>   reset "c = NULL".
> >>
> >> * If "c == NULL" and "hCounter == ballot.counter" (meaning
> >>    "ballot" is confirmed prepared), then set "c" to "ballot".
> >
> >
> > If we consider an example where a node has the following state.
> >
> > ballot = (8,x)
> > prepared = (8,x)
> > preparedPrime = (3,y)
> > cCounter = 4
> > hCounter = 8
> >
> > If the node accepts prepared (4,z) then using the update steps above c
> > will be set to NULL and then c will be set to ballot.
>
> That's correct.  This is because the messages only encode cCounter
> instead of c.  Since c.value is implicit, you don't want to vote to
> commit the wrong ballot.  (In fact, I will change preparedPrime to be
> preparedPrimeCounter in the next version, too.)
>
> > This means that the node will transition from voting to commit ballots
> > with value == x and counters 4...8 to just the single ballot (8,x).
>
> You mean transition to voting to commit nothing?  (Though still
> vote-or-confirm (n,x) for 4 <= n <= 8.)
>
> > Out of the ballots that the node was previously voting to commit only
> > (4,x) has been accepted aborted due to setting preparedPrime = (4,z),
> > so it seems that it would still be legal to vote to commit ballots
> > with value == x and counters 5...8.
>
> Not necessarily.  Whether or not it's safe to commit (5,x) depends on
> history.  It's only safe to vote to commit a ballot b if ballot == b at
> the time b was confirmed prepared.  If, for instance, hCounter jumps
> from 0 to 8 in the history, then the node has no memory of whether it
> is, say voted to prepare (4,z), which would make it illegal to vote to
> commit (4,x).
>
> > So I am proposing that the first part of the above update step is
> > changed to the following, to allow for that.
> >
> >> * If c != NULL set c.counter to the counter of the lowest ballot with value ==
> >>   h.value and not accepted aborted according to p and p'. If c.counter >
> >>   hCounter, then set c=NULL
>
> To be correct, you might also need to raise h such that you've never
> voted to abort anything between h and the new c, but I don't think nodes
> have enough state to do that.  So the current algorithm is safe but
> "wasteful" of potentially useful ballots.
>
> David