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

Piers Powlesland <pierspowlesland@gmail.com> Fri, 02 November 2018 17:38 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 F1354126DBF for <din@ietfa.amsl.com>; Fri, 2 Nov 2018 10:38:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, 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 NiXA_JznGXH2 for <din@ietfa.amsl.com>; Fri, 2 Nov 2018 10:38:35 -0700 (PDT)
Received: from mail-lj1-x22c.google.com (mail-lj1-x22c.google.com [IPv6:2a00:1450:4864:20::22c]) (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 763191252B7 for <din@irtf.org>; Fri, 2 Nov 2018 10:38:35 -0700 (PDT)
Received: by mail-lj1-x22c.google.com with SMTP id u6-v6so2468996ljd.1 for <din@irtf.org>; Fri, 02 Nov 2018 10:38:35 -0700 (PDT)
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=35cdMl7D75bEaoyfA+laszA1rlvJsATP4ImYYkzwiH0=; b=MrALNpQl6cEafq6OdIp+AUqYrBYuyEfZPuTPT0N3loX2rKAn2nixm/89ZGwWgdTn5Q aAGcyzbHaMcJKmBJucwUlVFEvd3neJMY+UQjoGsxrzbLseiZCjMYegj8icWjXQoxnlje yRskacNldqQH+TPvdurKZOdOaDhV57ocvJn57+9AyNRgS0ej8dN7gOPVmSxbKGLgQEMK EKDQ7hYvWB/yiq17F+2JqtNVBON/W7jd1bUIEvDBIIMAGpj2BTgsUSvxdZDtJh3qoRzv 69nH7iz4882JfI8EKboNhRQfubGEbE7k/805KIFXnm787Mp+cziUjyuQRmLg1z0SVisu cs8Q==
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=35cdMl7D75bEaoyfA+laszA1rlvJsATP4ImYYkzwiH0=; b=j7mBdsRKhgbLQNAna9Kce4aLA0kJ9Auq31zWq9+iT2G8OEUls6RbmMoWXeZRPz9qm8 vY3tJFssGWM++8eO2EJ16xkVW0lKHiQpW5uEA+eHxgKjASbdYV5ydTmWC1nWZYnu+sTh 4WaTkqOU9EIPG6RwOMbI+zLsJgRi7wuS7LLgMtHAvG1Obtnxi8mnhxWzLQrJuW32Gt97 uSa09XuyfdRXgeyopyJEQXIx5Io09dQVq5OnDt48qKPNA+6oceZA7sVj/emLaGnMkmla NLuNoaW6oS/WGz0QJ4jKJ9X39KNhX3Req7M3keNncP50ONSR3jziDtK1decSGdI+PkHB H7JA==
X-Gm-Message-State: AGRZ1gJ9xotSqO7VFO/WLB94+gkE93j/cEHsBYKXWfGChZEkCTaM3xuu qeKdileyK6LRYJbW3MaijrVtjHyAWzk40GWgKP+2GNgs
X-Google-Smtp-Source: AJdET5e9ceWdrFV+FWFKjKeaZ7Zwf+AMK3SFJAkp7jBl0UdElAotuyEjh6BPw2Tom8Pw3BnXUjOKhcksF/AiMkF06/o=
X-Received: by 2002:a2e:9e10:: with SMTP id e16-v6mr8271987ljk.169.1541180313333; Fri, 02 Nov 2018 10:38:33 -0700 (PDT)
MIME-Version: 1.0
References: <CAFXacXm5U6VNEyQ3ienwgcGaAj1yQ1YVJNFT1eY9EMRsNFZ9hA@mail.gmail.com> <87va5fsexn.fsf@ta.scs.stanford.edu>
In-Reply-To: <87va5fsexn.fsf@ta.scs.stanford.edu>
From: Piers Powlesland <pierspowlesland@gmail.com>
Date: Fri, 2 Nov 2018 17:38:21 +0000
Message-ID: <CAFXacXnWJN8d8SutKEj0OyvUWKnp7EgnpX-bA8SBPcX=K-zsdQ@mail.gmail.com>
To: mazieres-z84dy9p9kp8ehixwsvr9w28cns@temporary-address.scs.stanford.edu
Cc: din@irtf.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/din/3TTxgtS62RnYFCfURdWSkComEr8>
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: Fri, 02 Nov 2018 17:38:38 -0000

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
<dm-list-ietf-ilc@scs.stanford.edu> wrote:
>
> Piers Powlesland <pierspowlesland@gmail.com> 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