Re: [MLS] RT array implementation motivation

Raphael Robert <ietf@raphaelrobert.com> Wed, 19 May 2021 13:25 UTC

Return-Path: <ietf@raphaelrobert.com>
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 8829B3A0E7C for <mls@ietfa.amsl.com>; Wed, 19 May 2021 06:25:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=raphaelrobert.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 8MMs10YSXOcO for <mls@ietfa.amsl.com>; Wed, 19 May 2021 06:25:44 -0700 (PDT)
Received: from mail-ed1-x533.google.com (mail-ed1-x533.google.com [IPv6:2a00:1450:4864:20::533]) (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 A6F8F3A0E79 for <mls@ietf.org>; Wed, 19 May 2021 06:25:44 -0700 (PDT)
Received: by mail-ed1-x533.google.com with SMTP id b17so15379037ede.0 for <mls@ietf.org>; Wed, 19 May 2021 06:25:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=raphaelrobert.com; s=rr; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=tpAuOZLZJhcOaWsGI3tjj+ZC9hKgwdqSli+nwx9XHJA=; b=aNYi9N+51XihMA1+fqAWfZdHB4IG15OPMoaeaZgnOl4eGVv2H0Un/06vcKUtk6ewGd PrPTKpzl32Bt3/77/dDw07O5UcE/wqaS4IGlAqQfh9qwBQy/ZnNnig55nfmkpaSO9RSl FTlL0Be7NN9kbS+64bUiTDEwQi25p7pYPFEV0=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=tpAuOZLZJhcOaWsGI3tjj+ZC9hKgwdqSli+nwx9XHJA=; b=bQdWAOo0//zqjdaL5Sw5XmIMm2a0wlTNqxcTDVxh5hDKirUtdPBflZ5W9zB2zfEnCX fIvaQezbp4YkJwxlmhI2/Z7buqIx+gygCSSflMRG7E6VmPSfNovNYUs2IDBPxpyQo1mr ypVZzXvKYye1iycSLeaFMxeXMAttNgCwsX3j9CtkUvwLfV+LKY+ESGAqyGADsc7QvP6Y 0NHY1apbowuPLKQWTYOLNyUAXk+JZP4XJTolALVou9fweWe6XydcjE6vZtxZNyXoVnJc Q+A5d1halfuy1a+OxdtN1xp8+vVDqBTj3bb92yNkuzIesbNu/r1tjhRTRX1+89wdFq/A dWqQ==
X-Gm-Message-State: AOAM533/8v9G1c2kD/I27o6fsv0gHbbeEK53pHflvKMLD3Q0EabLs4b2 F8CDpcV4hwXEPdT8M4gG/GMUrg==
X-Google-Smtp-Source: ABdhPJxGw9IlUDdYXhJKZoynrUczMCmvsFXONjMl22V0r+W0yKvz/WiqcfrhPqt6oX6U8sCi882P6Q==
X-Received: by 2002:a05:6402:50cd:: with SMTP id h13mr13179779edb.111.1621430742279; Wed, 19 May 2021 06:25:42 -0700 (PDT)
Received: from smtpclient.apple ([37.49.18.137]) by smtp.gmail.com with ESMTPSA id c10sm8936797eds.90.2021.05.19.06.25.41 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 19 May 2021 06:25:41 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.80.0.2.43\))
From: Raphael Robert <ietf@raphaelrobert.com>
In-Reply-To: <CAHvbzjKTFFAp-V_o_Gs-vqiT=6Zh1qXim6E0096t3or8UcrJ-g@mail.gmail.com>
Date: Wed, 19 May 2021 15:25:40 +0200
Cc: mls@ietf.org
Content-Transfer-Encoding: quoted-printable
Message-Id: <F0D85996-7BD6-4DAF-A40F-8C9501A8E3EE@raphaelrobert.com>
References: <CAHvbzjKTFFAp-V_o_Gs-vqiT=6Zh1qXim6E0096t3or8UcrJ-g@mail.gmail.com>
To: Tijana Klimovic <tijana.klimovic97@gmail.com>
X-Mailer: Apple Mail (2.3654.80.0.2.43)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/VMobQawVFnASWKddQHNBG6zYBSg>
Subject: Re: [MLS] RT array implementation motivation
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 19 May 2021 13:25:50 -0000

Hi Tijana,

At the end of the day you can use whatever implementation works best of course. The array approach has a few benefits though:
 - it’s language agnostic, something that’s important for IETF
 - it gives you a serialisation format for free (quite practical for the ratchet tree extension)
 - it let’s you use references to nodes in the tree that are used in the Secret Tree to derive secrets for example
 - it makes it easy to add and remove nodes without having to change anything in neighbouring nodes

From a performance standpoint, using the tree math provided should also be reasonably fast. If you have some benchmarks to share that prove otherwise, it would be interesting to look into it.

Lastly, pointers can be great, but they can also be quite dangerous if implemented wrongly.

Hope this helps,

Raphael

> On 19. May 2021, at 14:55, Tijana Klimovic <tijana.klimovic97@gmail.com> wrote:
> 
> Hello,
> 
> I have only recently started to look into the MLS specification, and was wondering why the ratchet tree (RT) structure is chosen to be implemented with an array. From what I understand, the pointer-based tree where each node would contain the following information: 
> 
>         struct {
>         Node* sibling;
>         Node* parent;
>         Node* left_child;
>         Node* right_child;
>         Optional<HPKEPublicEncKey> hpke_enc_pk;
>         Optional<HPKESecretEncKey> hpke_enc_sk;
>         Optional<Credential> credential;
>         Optional<vector<byte>> parent_hash;
>         Optional<vector<Node*>> unmerged_leaves;
>         } Node 
> 
> would be more efficient than an array w.r.t. all operations supported by the RT. 
> 
> Many thanks.
> Tijana
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls