Re: [MLS] RT array implementation motivation

Tijana Klimovic <> Wed, 19 May 2021 15:11 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 885C43A13D5 for <>; Wed, 19 May 2021 08:11:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.846
X-Spam-Status: No, score=-1.846 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, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id SMG78FDI2Sne for <>; Wed, 19 May 2021 08:11:54 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::b31]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 3C1193A13D3 for <>; Wed, 19 May 2021 08:11:49 -0700 (PDT)
Received: by with SMTP id b13so17153657ybk.4 for <>; Wed, 19 May 2021 08:11:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=vUGwzibPodRrLRLDYB2YSSc3CoqmcIwQ3kjfn1TO/Xg=; b=ijQXIMJumcNS4262u3eXq4wPTwWq9DUh2XJDiot3AogDbZu5uOzgSowrE8wssy/7J6 zVe0f1kV6R6sYyh4pJ+u9KPK6wocbj53iJsrD6crXTv5pTrGaCx/0JjzE6Q5Wk9/tttL iu0h02lENoVyytw26DU9IS0ZyGGV75of/0GLHZOxw6Jiy0ms5feOwa2Pa0hydHzPQYI9 mTWjpLIuu83hoeNDNac0HHWPOLZPdfHv4BjOxzONHnOKcTBym+hQN90F+lm7UcMJOfUw 0rYv4h1Psi16ZDMW+DK55lsD1pmRg42DPFYH5gHlvzDgt9NPUGpzh2qJex4wmyz/4pvO CO4g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=vUGwzibPodRrLRLDYB2YSSc3CoqmcIwQ3kjfn1TO/Xg=; b=Ig2SElAw4E8tQD9MFCALJqajFj4fs6ozVXAEbkLcUEupucRHufH/tYKPZYuHB5Gewv Y9fxwi0RC8NObrjZHA2+TMujc1PZ9fHAIahxY8eS07ig7wsLtv3kcNizKRxOSQQd6wRI xZDtymd9BgL0FnSjZFMSKQFQVQU3m9+RsrLLd6koenHTW3tsvLh5M/u2wEN1fPFpXmV1 k9trEwsJOsVBibaQg78qnFmvxS4eCfcynTFtDAvUbbLVPfPcpU+szAscP7B5PSVCvfWd Ad1yjjNsh8hNqCVJAv4KEq8TahzAWec6tzhd6H6IHl5ES19gPiserd2WocZXIgXYszBy ArDw==
X-Gm-Message-State: AOAM53267OcqNxcMBFHe31j8Xln+vp13cZfaCAzRrCMaiuAXXin7xeUR WYWndPvfM2DU36X4dBaKqa9LUYs8RuBc7/AeKyg=
X-Google-Smtp-Source: ABdhPJy3TA+OAo+Tko7xdSBVXCSvgpxWPnxHyszwoHbTwbV5lqaJPYKzbFxA8fj3pb/jRyVwO40m+oPwLxwrTe494Tg=
X-Received: by 2002:a25:5d0b:: with SMTP id r11mr15728997ybb.380.1621437107812; Wed, 19 May 2021 08:11:47 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Tijana Klimovic <>
Date: Wed, 19 May 2021 17:11:37 +0200
Message-ID: <>
To: Raphael Robert <>
Content-Type: multipart/alternative; boundary="000000000000d63c5d05c2b03eb1"
Archived-At: <>
Subject: Re: [MLS] RT array implementation motivation
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: Wed, 19 May 2021 15:12:00 -0000


Thank you for your answers to the question about RT. I do have some more
questions about the choice of framing if you don't mind me asking. I tried
to find answers to them in the group but didn't have much luck.

Namely, in the MLSPlaintext structure, you have the membership_tag included
that MACs everything above it in the MLSPlaintext structure with the
membership_key. I don't see how the framing is any less secure without it
being there, since the signature covers everything above itself, hence only
not including the two mac tags.

Furthermore, it's not clear to me which membership_key is used to construct
it in case of commit messages. I would think that it would be the
membership_key deduced from the GroupContext for the new epoch, after the
proposals and UpdatePath have been applied so that joiners can compute the
epoch_secret. Is this correct?

Lastly, I wanted to ask what is the purpose of having the parent_hash

As far as I understand, it only must be included in the leafKeyPackage of
the UpdatePath structure and it serves to bind the new HPKE public keys of
all nodes on the path from the leaf(committer) with the leafKeyPackage to
the root and the set of HPKE public keys to which PK's secret key was
encrypted. But the commit contains the confirmation_tag that confirms that
the members of the group have arrived at the same state of the group. So
the confirmation_tag would bind the same as the parent_hash and even more.

Many thanks.

On Wed, 19 May 2021 at 15:25, Raphael Robert <> wrote:

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