Re: [MLS] RT array implementation motivation

Raphael Robert <> Thu, 20 May 2021 14:33 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 87D3A3A18D8 for <>; Thu, 20 May 2021 07:33:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Status: No, score=-2.097 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, 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 (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id YlpZFrNx4Skc for <>; Thu, 20 May 2021 07:33:01 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::630]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 732663A18D6 for <>; Thu, 20 May 2021 07:33:01 -0700 (PDT)
Received: by with SMTP id et19so18596001ejc.4 for <>; Thu, 20 May 2021 07:33:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=rr; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=AaLGr9Z1fcvz3apFiJkodCxXvo1jWJTgNpSm4DrFvms=; b=O4AkeOl5nbr48gYlh95yzSRysxnFF7UqaLy7l6JzA6NtTMPiuMqzrwNw2n7+qhDbdW d63Fw0Du4bQd52rfMaptEJ8iqMYI1jw/3+GMAyu86tI3fobMLzYQYpYb8PGomV9xrWTY lzc0ZPRV4rA9ucOreOD2nhy13874KfXzG7oYE=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=AaLGr9Z1fcvz3apFiJkodCxXvo1jWJTgNpSm4DrFvms=; b=XygSNjtQdL6SkzFE1wdQ1M0jNOx0p5HcPq8rFRO44miF8BDzj85IJTm6ps+/HQOBS2 TlGgj/U1DR3m5puZ5/wOGwOrU826AbL6UExUo6TEmlsOfp+5sE7ZkUOHhn/kp8y4bv2a 14cU36NRRjU9uplycaYrclp5b9LsAUk+tp+FBl6QHgMfjsY+XglPHvfjQDg3R2kI6xjs Gg5C3rXt/KToay8RSt1W1pWmhePk6G7M822Vx80rEPRm0BfRw7Eh8w+WA2keTWpwmlKy un7ycXYs1CCAJaW69I8C3aSD3ShA+j0o18YJ74CxCj6PnJKksyKMAcDbW2drWm0hewRw KqLA==
X-Gm-Message-State: AOAM530KJo3fWxgT6JG1Gbffc2KRaSNHUeTcypJifSXCWeLHsNB4UmJ0 FU1JK/s3rUS9SRJl1xdmUsckPg==
X-Google-Smtp-Source: ABdhPJzeIzkBGEuKmNtEHEFFMKJJc+/pK5ML8fo8A2w+bNlMR53Eb8M9MILhwVT7VlICKgDcR8SK1g==
X-Received: by 2002:a17:906:c211:: with SMTP id d17mr5003453ejz.247.1621521174507; Thu, 20 May 2021 07:32:54 -0700 (PDT)
Received: from ([]) by with ESMTPSA id u14sm1664159edy.47.2021. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 20 May 2021 07:32:53 -0700 (PDT)
From: Raphael Robert <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_38AE23C4-4891-45BB-8B44-6C5EBFBE83DB"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.\))
Date: Thu, 20 May 2021 16:32:52 +0200
In-Reply-To: <>
To: Tijana Klimovic <>
References: <> <> <>
X-Mailer: Apple Mail (2.3654.
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: Thu, 20 May 2021 14:33:08 -0000

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

The signature only proves the signer is in possession of the private signature key. The membership_tag also proves that the member has access to group secrets and that means that it is a member of the group from a cryptographic standpoint.

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

The membership_key is an output of the key schedule as described in 8. It is used to compute the membership_tag as described in 9.1.

> Lastly, I wanted to ask what is the purpose of having the parent_hash extension? 
> 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.

The parent_hash is intended to be checked by new joiners. This way new joiners can come to the conclusion that existing members agreed on (some of) the public tree in the past. New joiners cannot derive that from the confirmation_tag when they process a Welcome message, because they don’t have all of the past transcript.


> Many thanks.
> Tijana
> 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
> > <>
> > <>