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

From: Piers Powlesland <[email-masked]>
Date: Fri, 2 Nov 2018 14:41:08 +0000

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

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.

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

---

From: David Mazieres <[email-masked]>
Date: Fri, 02 Nov 2018 07:59:48 -0700

Piers Powlesland <[email-masked]> writes:

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

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

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

---

From: Piers Powlesland <[email-masked]>
Date: Fri, 2 Nov 2018 17:38:21 +0000

I have a few things I'm not clear on.

I don't see that this statement is correct.

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

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

>is, say voted to prepare (4,z), which would make it illegal to vote to

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

---

From: David Mazieres <[email-masked]>
Date: Sat, 03 Nov 2018 00:22:19 -0700

> now is voting to commit(8,x) ?

Oh, yes, sorry.  But importantly you are no longer voting to commit
(5,x) and (6,x).

> Also what is "vote-or-confirm" ?

Sorry, another mistake on my part.  I meant vote-or-accept.

> prepared (8,x) and h.value == b.value so we set hCounter to 8)

Sorry, what's the difference between this and above?  I'm assuming you
meant hCounter=2 above, and hCounter=8 here.

> 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

---

From: Piers Powlesland <[email-masked]>
Date: Thu, 8 Nov 2018 12:30:17 +0000

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

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.

---

From: David Mazieres <[email-masked]>
Date: Thu, 08 Nov 2018 06:03:18 -0800

> ballot has been confirmed prepared and we have not voted or accepted abort

Yes, what you say is correct, but not possible to verify with the fixed
amount of state that SCP keeps around.  So the rule I stated is a
conservative approximation.  Maybe I shouldn't have said only.  I should
have said it is safe to vote in this case, and you can check this case.

>> * If c.counter > hCounter then reset "c = NULL"

I think this is correct, but not necessarily more efficient.  If h is
the highest confirmed prepared ballot, then prepared >= h.  So if you
suddenly raise prepared to be greater than and incompatible h, that
means you are now trying to confirm something prepared that has a
different value from h, meaning h.value is no longer your best guess as
to the value to externalize, so I don't see much point in continuing to
vote to commit ballots with value h.value.

With preparedPrime, there is a similar argument, that after confirming c
prepared, a quorum confirmed an incompatible preparedPrime prepared.  So
maybe by coincidence after that everyone went back to c.value, but
c.value is no more likely to be the ultimate consensus value than
anything else.

Basically the only reason it might be a win to avoid setting c to NULL
is if you still think everyone is working on confirming c.value, which
won't be the case if something incompatible but higher was prepared.

David

---

From: Piers Powlesland <[email-masked]>
Date: Thu, 8 Nov 2018 17:02:28 +0000

So to clarify

> vote to commit ballots with value h.value.

In the case where either prepared or preparedPrime are greater than or
incompatible to h then c is set to NULL, so the node stops voting for
anything.

The case where I envisage this being a win is:

After a node confirms c and has subsequently gone on to confirm
several higher and compatible ballots, such that the node is now
voting to commit several ballots. The node then accepts a
preparedPrime that is greater than and incompatible to c but less than
h. Rather than dropping everything and starting to vote to commit just
the highest ballot that it was previously voting to commit, it just
stops voting to commit any ballots that are now considered aborted due
to the new preparedPrime. In this case everyone is still working on
confirming committed c.value, we have just updated our "lower bound"
below which we consider everything aborted.

Using this approach provides more opportunities for the network to
come to agreement and so in certain situations, I think, could reduce
the time taken to agree on a value.