Return-Path: X-Original-To: mls@ietfa.amsl.com Delivered-To: mls@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1BC9A12785F for ; Tue, 23 Oct 2018 05:15:58 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.898 X-Spam-Level: X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no 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 myjhReBNcuSY for ; Tue, 23 Oct 2018 05:15:54 -0700 (PDT) Received: from mail.smeinc.net (mail.smeinc.net [209.135.209.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 65BA4130E35 for ; Tue, 23 Oct 2018 05:15:54 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by mail.smeinc.net (Postfix) with ESMTP id 0C35C300A40 for ; Tue, 23 Oct 2018 08:15:52 -0400 (EDT) X-Virus-Scanned: amavisd-new at mail.smeinc.net Received: from mail.smeinc.net ([127.0.0.1]) by localhost (mail.smeinc.net [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id 6xnamSbAyCif for ; Tue, 23 Oct 2018 08:15:49 -0400 (EDT) Received: from [5.5.33.214] (vpn.snozzages.com [204.42.252.17]) by mail.smeinc.net (Postfix) with ESMTPSA id 8D381300258; Tue, 23 Oct 2018 08:15:48 -0400 (EDT) From: Russ Housley Message-Id: Content-Type: multipart/alternative; boundary="Apple-Mail=_69371053-640A-4148-BEDE-FD2E765E6DC0" Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\)) Date: Tue, 23 Oct 2018 08:15:48 -0400 In-Reply-To: Cc: mls@ietf.org To: Raphael Robert , Richard Barnes References: X-Mailer: Apple Mail (2.3445.9.1) Archived-At: Subject: Re: [MLS] Move / Add-in-place / Compounding X-BeenThere: mls@ietf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Messaging Layer Security List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Oct 2018 12:15:58 -0000 --Apple-Mail=_69371053-640A-4148-BEDE-FD2E765E6DC0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Don't add and move make synchronization concerns worse? Can two clients = ask for the same empty-when-they-looked node? Russ > On Oct 22, 2018, at 2:59 PM, Raphael Robert wrote: >=20 > I think these two operations make perfect sense (had the same ones in = mind). Some comments: >=20 > Regarding Move: > We should work on a recommendation of when to do a Move instead of an = Update, and also of when to do a Move even if no Update was planned. > The recommendation could initially be something naive, such as: when = the ratio of blank leaves / full leaves is greater than xxx, do a Move.=20= >=20 > Regarding Add-in-place: > I think this has the potential of becoming the default, as opposed to = the current Add. Maybe both operations could be one and the same if we = just add an index to the current Add. In that case the recommendation = for the index would simply be the left-most empty leaf node. >=20 > If both operations are correctly applied by clients, the tree should = have the optimal size. > There is however a case where trees will not shrink, but only if the = following three conditions are met: >=20 > - A large number of members left the group (large is relative to the = group size) > - A large number of the remaining members never come online again and = therefore cannot move themselves (large is again relative to the = remaining group size) > - Only very few new members are added subsequently >=20 > I suspect that the above scenario is however an edge case. If it = occurs =E2=80=9Cin the wild=E2=80=9D it might eventually get solved on a = social level (when unresponsive members get removed by active ones). >=20 >=20 >> On 22 Oct 2018, at 20:34, Richard Barnes > wrote: >>=20 >> Hey MLS folks, >>=20 >> tl;dr:=20 >> - Would there be interest in a Move operation? >> - How about an operation to Add a new member in an open slot instead = of the right edge? >>=20 >> In looking at the "partial tree" stuff (#67), it occurred to me that = once you have partial trees with blank leaves, you can in principle do = two new operations: An existing member can move from one leaf in the = tree to another; and an existing member can add a new member at a leaf = that is currently blank. These operations would work roughly as = follows: >>=20 >> - Move: >> - Blank out old dirpath >> - Move credential from old slot to new slow >> - Send update along new dirpath >> - Add-in-place: >> - Blank out dirpath for slot >> - Install new member's leaf key in slot >> - Install new member's credential in slot >>=20 >> For Move, you would also want to have people step down the size of = the tree. For example, if you go from having 10 leaves (X _ X X _ _ _ _ = _ X) to four leaves (X X X X) as the result of a move, then the = resulting tree should only have height 2, not 4 (as is required for 10 = leaves). Fortunately, this is trivial with the tree math defined in the = document; you just truncate the node vector, and the calculated root = gets correspondingly smaller. >>=20 >> I've prototyped this out in my JS stack [1][2]. Once you've built a = tree, and removed a couple of members, you can click one of the "Move" = buttons to move that node to the lowest open slot. As you can see, it's = not a ton of code. >>=20 >> In any case, this seems to me to be potentially useful, since it = addresses the issue that was raised in the BoF that the size of the = resources for a group increases monotically. Move allows you to reclaim = resources that are unused (assuming some orchestration outside of MLS), = and Add-in-place allows us to be conservative with resources that are = already allocated (cf. realloc). >>=20 >> If folks think these sound like useful tools, I'll write up a PR and = we can discuss in BKK. >>=20 >> --Richard >>=20 >> [1] https://ipv.sx/treekem/ >> [2] = https://github.com/bifurcation/treekem/commit/7f470422ba61ce668c3ab1d6b2d1= 8edd9d6e06fd = >> _______________________________________________ >> MLS mailing list >> MLS@ietf.org >> https://www.ietf.org/mailman/listinfo/mls >=20 > _______________________________________________ > MLS mailing list > MLS@ietf.org > https://www.ietf.org/mailman/listinfo/mls --Apple-Mail=_69371053-640A-4148-BEDE-FD2E765E6DC0 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8
Don't add and move make synchronization concerns worse?  = Can two clients ask for the same empty-when-they-looked node?

Russ


On Oct 22, 2018, at 2:59 PM, = Raphael Robert <raphael@wire.com> wrote:

I think these two = operations make perfect sense (had the same ones in mind). Some = comments:

Regarding = Move:
We should work on a recommendation of when to = do a Move instead of an Update, and also of when to do a Move even if no = Update was planned.
The recommendation could = initially be something naive, such as: when the ratio of blank leaves / = full leaves is greater than xxx, do a Move. 
Regarding Add-in-place:
I think this has the potential of becoming the default, as = opposed to the current Add. Maybe both operations could be one and the = same if we just add an index to the current Add. In that case the = recommendation for the index would simply be the left-most empty leaf = node.

If both = operations are correctly applied by clients, the tree should have the = optimal size.
There is however a case where trees = will not shrink, but only if the following three conditions are = met:

 - A = large number of members left the group (large is relative to the group = size)
 - A large number of the remaining = members never come online again and therefore cannot move themselves = (large is again relative to the remaining group size)
 - Only very few new members are added = subsequently

I = suspect that the above scenario is however an edge case. If it occurs = =E2=80=9Cin the wild=E2=80=9D it might eventually get solved on a social = level (when unresponsive members get removed by active ones).


On 22 = Oct 2018, at 20:34, Richard Barnes <rlb@ipv.sx> wrote:

Hey MLS folks,

tl;dr:
- Would there be = interest in a Move operation?
- How about an = operation to Add a new member in an open slot instead of the right = edge?

In looking at the "partial tree" stuff (#67), it occurred to = me that once you have partial trees with blank leaves, you can in = principle do two new operations: An existing member can move from one = leaf in the tree to another; and an existing member can add a new member = at a leaf that is currently blank.  These operations would work = roughly as follows:

- Move:
    - Blank out = old dirpath
    - = Move credential from old slot to new slow
    - Send update along new = dirpath
- Add-in-place:
    - Blank out dirpath for slot
    - Install new member's leaf key in = slot
    - Install new member's = credential in slot

For = Move, you would also want to have people step down the size of the = tree.  For example, if you go from having 10 leaves (X _ X X _ _ _ = _ _ X) to four leaves (X X X X) as the result of a move, then the = resulting tree should only have height 2, not 4 (as is required for 10 = leaves).  Fortunately, this is trivial with the tree math defined = in the document; you just truncate the node vector, and the calculated = root gets correspondingly smaller.

I've prototyped this out in my JS stack = [1][2].  Once you've built a tree, and removed a couple of members, = you can click one of the "Move" buttons to move that node to the lowest = open slot.  As you can see, it's not a ton of code.

In any case, this seems = to me to be potentially useful, since it addresses the issue that was = raised in the BoF that the size of the resources for a group increases = monotically.  Move allows you to reclaim resources that are unused = (assuming some orchestration outside of MLS), and Add-in-place allows us = to be conservative with resources that are already allocated (cf. = realloc).

If folks think these sound like useful tools, I'll write up a = PR and we can discuss in BKK.

--Richard

[1] https://ipv.sx/treekem/
[2] https://github.com/bifurcation/treekem/commit/7f470422ba61ce668= c3ab1d6b2d18edd9d6e06fd
_______________________________________________
MLS = mailing list
MLS@ietf.org
https://www.ietf.org/mailman/listinfo/mls

_______________________________________________
MLS mailing list
MLS@ietf.org
https://www.ietf.org/mailman/listinfo/mls

= --Apple-Mail=_69371053-640A-4148-BEDE-FD2E765E6DC0--