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

Piers Powlesland <pierspowlesland@gmail.com> Thu, 08 November 2018 12:30 UTC

Return-Path: <pierspowlesland@gmail.com>
X-Original-To: din@ietfa.amsl.com
Delivered-To: din@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 63E9F128A5C for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 04:30:33 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id B7Tua_-zUumN for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 04:30:31 -0800 (PST)
Received: from mail-lf1-x131.google.com (mail-lf1-x131.google.com [IPv6:2a00:1450:4864:20::131]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B940312D4E8 for <din@irtf.org>; Thu, 8 Nov 2018 04:30:30 -0800 (PST)
Received: by mail-lf1-x131.google.com with SMTP id i26so14050591lfc.0 for <din@irtf.org>; Thu, 08 Nov 2018 04:30:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=p7T3tzYL8Nn0KuphjC+WdMmww9HBkun9ijOKGceKEIM=; b=NNssBlXRFzcN9Q55BQp3y31eDHFzI4By5FwftROlrU2IUgzE41jV0UYpeH7jI5jBd8 BPoeAXb0CtoUd67P3gK2XBYG55FWRhYq/JxcUtyHqt5glp9/p+R1JIIA6IKyERoVAmDl VlAGCUG0rgYm/AS8N5ucs/hKlqU60gJDc1W4owyqtpFBTX1i3C+Xd6Mq6V7JofaqFIRG O6LY0ogVNBqb33P0eFjj0c005sFrNlph0d3QLqRwkVsa2/RXkiB16+Fbl3eGzIH0jaan ZEWOODg12KzVOykpSL+VFOkcncc9cmHOQ/Ppotrz0mqNcHrzN/riY8ejFewe12gQClRV ip+w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=p7T3tzYL8Nn0KuphjC+WdMmww9HBkun9ijOKGceKEIM=; b=EyshUAS8t0AG1+IhG+oNxWPEgzq0LEMUaHt2hOjeF3MnNZ5oZRVBxBVIhCNQ6n1bKZ XDN4+pyTqalzQ+DsQLFHxFV0UkrxgjcrNUjoc841u77KPsm1k/jxr0MRMHsS3tM7oZvL WsPNBylMWiPCye5ZlliT6cNiVzgFuBuuERteXphVyYj2L1D+SZ2PRNb9ptJqlqg17lQM DgOUpVJIsug+ifacp41jgiJJxVfkIBukYG2TSOWzFUdX/XH+YpC51XxxyU4PVQNBCkc6 z97TjIXk6GFDPmW54xYRTmi/LGwqcn+kKS68cS10nFRk3NIsqv+zrfvKFY997HA/ywq/ ht1w==
X-Gm-Message-State: AGRZ1gI0CPqywm9K4T300g9Sfa3/7NuWn7L+WrUYlBYNbvpn+1C4m4IR 8UodG1ziwrqNMdZhxM0N3lxL8ZwkcOSOiXqqYsLoSqo/
X-Google-Smtp-Source: AJdET5cKsi9j9juDrMNyjnPZjbul4eC875KYt5oARVh2Dch4uSpc16VmSxPAsxrQyRswfnv3vkDwcwKd10US3j3h4nY=
X-Received: by 2002:a19:7111:: with SMTP id m17mr2587761lfc.64.1541680228495; Thu, 08 Nov 2018 04:30:28 -0800 (PST)
MIME-Version: 1.0
References: <CAFXacXm5U6VNEyQ3ienwgcGaAj1yQ1YVJNFT1eY9EMRsNFZ9hA@mail.gmail.com> <87va5fsexn.fsf@ta.scs.stanford.edu> <CAFXacXnWJN8d8SutKEj0OyvUWKnp7EgnpX-bA8SBPcX=K-zsdQ@mail.gmail.com> <875zxezkus.fsf@ta.scs.stanford.edu>
In-Reply-To: <875zxezkus.fsf@ta.scs.stanford.edu>
From: Piers Powlesland <pierspowlesland@gmail.com>
Date: Thu, 8 Nov 2018 12:30:17 +0000
Message-ID: <CAFXacXnXihDveCZSRBk4ESiFS1j1inS+5H=hAO0AiFwc2=BY7A@mail.gmail.com>
To: mazieres-upwjsxfjp64x9ptkyhebxjqata@temporary-address.scs.stanford.edu
Cc: din@irtf.org
Content-Type: multipart/alternative; boundary="000000000000608a27057a26663c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/din/Drue0058IeCamO_peFmtk5R-b0U>
Subject: Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) Potential improvement to balloting protocol, setting cCounter
X-BeenThere: din@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussion of distributed Internet Infrastructure approaches, aspects such as Service Federation, and underlying technologies" <din.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/din>, <mailto:din-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/din/>
List-Post: <mailto:din@irtf.org>
List-Help: <mailto:din-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/din>, <mailto:din-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 08 Nov 2018 12:30:33 -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"
>
> *  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 <dm-list-ietf-ilc@scs.stanford.edu
wrote:

> Piers Powlesland <pierspowlesland@gmail.com> 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
>