Subject: [MLS] Syntax and mechanics for external commit

From: Richard Barnes <[email-masked]>
Date: Tue, 6 Oct 2020 21:20:10 -0400

Hey all,

I wanted to send some thoughts on how to implement external commit, as a
prelude to a PR.  This is a little bit of an essay, so tl;dr, the proposal
is:

- Rather than re-using Proposal/Commit, we should make a new ExternalCommit
message, parallel to Proposal/Commit
- We should also define a syntax for telling the joiner the requisite
information about the group

# HPKE-based init secret

The concept here is as follows:

- An HPKE/KEM key pair `(skG, pkG)` is derived off of the key schedule for
each epoch
- The public key `pkG` of that key pair is published along with with other
group metadata
- The joiner calls SetupBaseS(pkG, some_public_group_context) to get an
encapsulated key `enc` and an HPKE context `ctx`
- The joiner sends the encapsulated key to the group with their external
commit
- The members of the group call SetupBaseS(enc, skG,
some_public_group_context) to get an equivalent HPKE context `ctx`
- Everyone calls `ctx.export(MLS_export_label, init_secret_size)` to derive
the init secret

So there are two syntactic requirements:

1. Publishing the group’s public key `pkG`
2. Sending the encapsulated key `enc` to the group

# What Proposals?

The current PR correctly requires that the external Commit MUST cover an
Add proposal for the new member.   It does not forbid the Commit covering
*other* proposals.  It seems like it might be useful in a couple of cases
to keep that option open:
* Including PSK proposals for additional authentication when joining
* Including a Remove proposal for your prior appearance when re-joining

The only current proposal that would be nonsensical is an Update.

Whether we do this has some impact on the syntax, as discussed below.

# External commit syntax: Separate or Together

Assume for the moment that we are not going to do the above asymmetric
calculation for every commit.  Then we need some extra, optional syntax  to
carry `enc`, either as an optional field on Commit or as a new Proposal,
which is the agreed mechanism for extending Commits.  (If we do it every
time, we can just make this part of Commit.)  In the below, I’ll assume a
new Proposal, say ExternalInitSecret.

struct {
  opaque kem_output<0..2^16-1>;
} ExternalInitSecret;

Given the requirement for an Add proposal, the joiner now has to send a
“flight of messages”:

- Proposal(Add)
- Proposal(ExternalInitSecret)
- Commit

Let’s call this the Separate Option.  It’s a bit heavyweight, since each of
these is signed separately.  It’s duplicative, since the KeyPackage in the
Add is immediately overwritten by the (necessarily different) KP in the
Commit.  And you have potential fate-sharing issues, since all three need
to succeed or fail.

You could also envision a Together Option, where we define another
top-level content type (parallel to Proposal and Commit) for this purpose:

struct {
  opaque kem_output<0..2^16-1>;
  UpdatePath path;
} ExternalCommit;

That would avoid all of the challenges above, but it optimizes out all of
the flexibility to include other proposals.  So maybe it’s worth
considering an Extensible Together Option, where we can put extra proposals
into an ExternalCommit

struct {
  Proposal proposals<0..2^32-1>;
  opaque kem_output<0..2^16-1>;
  UpdatePath path;
} ExternalCommit;

Personally, I kind of like the Flexible Together Option, since it provides
simplicity and extensibility.  And to be honest, I’ve been wondering if we
should allow inline proposals in Commit for a while, along just these
lines.  If we do this option, we should probably back-port it to Commit as
well.

# Syntax for what the Joiner Needs

The PR notes that the joiner needs to know a bunch of information about the
group in order to make a well-formed ExternalCommit.  In earlier iterations
of this style of join, we had a GroupInitKey that carried the right
information. Following that pattern here, we get something like the
following:

struct {
  CipherSuite cipher_suite;
  opaque group_id<0..255>;
  uint64 epoch;
  opaque tree_hash<0..255>;
  opaque confirmed_transcript_hash<0..255>;
  Extension extensions<0..2^32-1>;
} GroupKeyPackage;

Note that this object is essentially the same as a GroupInfo object.  The
only things it is missing are interim_transcript_hash and signature, both
of which might be useful.  So maybe all we need to do here is say that
clients can publish GroupInfo unencrypted if they want to enable self-adds,
in addition to distributing it in encrypted form in Welcome.

In any case, it seems like it would be useful to have some syntax for this.

Hope this helps,
—RLB

---

From: Raphael Robert <[email-masked]>
Date: Wed, 7 Oct 2020 12:36:21 +0200

Thanks Richard for looking at all aspects in detail!

I thought about these things as well and will comment inline:

> On 7 Oct 2020, at 03:20, Richard Barnes <[email-masked]> wrote:
> 
> Hey all,
> 
> I wanted to send some thoughts on how to implement external commit, as a prelude to a PR.  This is a little bit of an essay, so tl;dr, the proposal is:
> 
> - Rather than re-using Proposal/Commit, we should make a new ExternalCommit message, parallel to Proposal/Commit

I think we are better off with re-using the current Commit syntax and I’ll explain why further below.

> - We should also define a syntax for telling the joiner the requisite information about the group
> 
> # HPKE-based init secret
> 
> - An HPKE/KEM key pair `(skG, pkG)` is derived off of the key schedule for each epoch
> - The public key `pkG` of that key pair is published along with with other group metadata
> - The joiner calls SetupBaseS(pkG, some_public_group_context) to get an encapsulated key `enc` and an HPKE context `ctx`
> - The joiner sends the encapsulated key to the group with their external commit
> - The members of the group call SetupBaseS(enc, skG, some_public_group_context) to get an equivalent HPKE context `ctx`
> - Everyone calls `ctx.export(MLS_export_label, init_secret_size)` to derive the init secret
> 

From the discussion at the interim, I think there is consensus about this part, we just need to add that to the PR.

> 
> 
> # What Proposals?
> 
> The current PR correctly requires that the external Commit MUST cover an Add proposal for the new member.   It does not forbid the Commit covering *other* proposals.  It seems like it might be useful in a couple of cases to keep that option open: > 

While that is not very explicit in the current PR, my approach was the following:

All Proposals should be allowed in an external Commit:

 - Adds: The joiner (new member) could right away add more members, or Commit to already existing Add Proposals if those are accessible. 
 - Removes: The joiner can remove prior appearances of itself (like you pointed out) or Commit to already existing Remove Proposals.
 - Updates: The joiner should of course not issue own Updates and Commit to them, but that is already the case for internal Commits. The joiner can Commit to already existing Update Proposals from other members.

Whether all of the above is allowed should only be governed by the policy for a group, nothing else. As a reminder: all clients MUST have the same policy for a certain group in order ta validate/refute Proposals and Commits.

This pretty much motivates my idea for fully re-using the existing Commit syntax and only introduce the new ExternalInitSecret Proposal.

> Assume for the moment that we are not going to do the above asymmetric calculation for every commit.  Then we need some extra, optional syntax  to carry `enc`, either as an optional field on Commit or as a new Proposal, which is the agreed mechanism for extending Commits.  (If we do it every time, we can just make this part of Commit.)  In the below, I’ll assume a new Proposal, say ExternalInitSecret.
> 
> struct {

This is exactly the Proposal we need.

> 
> Given the requirement for an Add proposal, the joiner now has to send a “flight of messages”:
> 
> - Proposal(Add)

I see some more nuance here. The first Add Proposal does not have to be issued by the new joiner, it could very well be an external Proposal. The scenario I had in mind here is the following:

A server issues an external Add Proposal for a group. The following things can happen:

a) Ideal scenario:

 - A member of the group comes online, validates the Add Proposal according to the policy and references it in an internal Commit (no External Commit needed) and sends a Welcome message to the new member

b) Equally ideal scenario:

 - The new joiner comes online before anyone else, has access to the public group data but does not need to communicate with the group. Nothing happens.

c) Emergency scenario:

 - The new joiner comes online before anyone else and needs to urgently send a message to the group. The new joiner creates the ExternalInitSecret Proposal and the Commit and sends both to group.

> 
> Let’s call this the Separate Option.  It’s a bit heavyweight, since each of these is signed separately.  It’s duplicative, since the KeyPackage in the Add is immediately overwritten by the (necessarily different) KP in the Commit.  And you have potential fate-sharing issues, since all three need to succeed or fail.
> 
> You could also envision a Together Option, where we define another top-level content type (parallel to Proposal and Commit) for this purpose:
> 
> struct {
> That would avoid all of the challenges above, but it optimizes out all of the flexibility to include other proposals.  So maybe it’s worth considering an Extensible Together Option, where we can put extra proposals into an ExternalCommit
> 
> struct {
> Personally, I kind of like the Flexible Together Option, since it provides simplicity and extensibility.  And to be honest, I’ve been wondering if we should allow inline proposals in Commit for a while, along just these lines.  If we do this option, we should probably back-port it to Commit as well.
> 

As mentioned above, I’m all for re-using the existing Commit syntax because of clarity, simplicity and flexibility. 

I do agree that the amount of signatures is sub-optimal, and this is something that also occurs in other situations. For example, when a member wants to add n new members at once to the group, it needs to compute n+1 signatures for that.
You mention the idea of inline proposals: Would that be a proposal that doesn’t have a signature, but still all other information? If so, I think it would be worthwhile looking at that separately, because as you say, it could be back-ported to internal Commits as well. I’m all for exploring that idea further.

> The PR notes that the joiner needs to know a bunch of information about the group in order to make a well-formed ExternalCommit.  In earlier iterations of this style of join, we had a GroupInitKey that carried the right information. Following that pattern here, we get something like the following:
> 
> struct {

This is what the PR currently says, except that the PR used GroupContext and has the full public tree. I agree that the tree hash should be enough and I’ll change the PR accordingly.

> 
> Note that this object is essentially the same as a GroupInfo object.  The only things it is missing are interim_transcript_hash and signature, both of which might be useful.  So maybe all we need to do here is say that clients can publish GroupInfo unencrypted if they want to enable self-adds, in addition to distributing it in encrypted form in Welcome.

While the two are awfully similar, the signature on GroupInfo is not required here and might have undesired effects w.r.t deniability if this is publicly accessible. The other reason for not wanting the signature is that it would be an additional signature to compute with every Commit, making them even more expensive. I propose to keep the struct as-is.

> In any case, it seems like it would be useful to have some syntax for this.

TL;DR:

I propose the following:

 - Keep the current Commit syntax 
 - Allow all kinds of Proposals for External Commits, same as with internal Commits
 - Do the HPKE-based init secret for External Commits
 - Introduce the ExternalInitSecret Proposal and make it mandatory for External Commits
 - Explore the idea of inline proposals separately
 - Do not re-use signed GroupInfo struct and keep the adjusted ExternalCommitInfo instead

Raphael

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Joel Alwen <[email-masked]>
Date: Wed, 7 Oct 2020 13:27:04 +0200

> new Proposal, say ExternalInitSecret.
Isn't it a bit redundant to have the External party prepare a full
(ExternInitSecret) proposal packet only to then immediately commit to it? That
means a full extra frame of bandwidth, an extra signature for the external party
and an extra sig verification for group members.

I'm wondering what the motivation is for making this an explicit proposal
instead of, say, a second mode for commits. (E.g. a commit uses init_secret[n]
iff no kem_output field is included in the commit packet. Otherwise it uses the
"external_init_secret" computed as Richard described.)

ATM I can't think of a scenario where we wouldnt want the external committer to
also be the one creating the ExternalInitSecret proposal and immediatly
committing to it...

- Joël

On 07/10/2020 12:36, Raphael Robert wrote:
>> each epoch - The public key `pkG` of that key pair is published along with
>> with other group metadata - The joiner calls SetupBaseS(pkG,
>> some_public_group_context) to get an encapsulated key `enc` and an HPKE
>> context `ctx` - The joiner sends the encapsulated key to the group with
>> their external commit - The members of the group call SetupBaseS(enc, skG,
>> some_public_group_context) to get an equivalent HPKE context `ctx` -
>> Everyone calls `ctx.export(MLS_export_label, init_secret_size)` to derive
>> the init secret
>> 
>> 1. Publishing the group’s public key `pkG` 2. Sending the encapsulated key
>> `enc` to the group
> 
> From the discussion at the interim, I think there is consensus about this
> part, we just need to add that to the PR.
> 
>> 
>> 
>> # What Proposals?
>> 
>> to keep that option open: > * Including PSK proposals for additional
>> authentication when joining * Including a Remove proposal for your prior
>> appearance when re-joining
>> 
> - Adds: The joiner (new member) could right away add more members, or Commit
> to already existing Add Proposals if those are accessible. - Removes: The
> joiner can remove prior appearances of itself (like you pointed out) or
> Commit to already existing Remove Proposals. - Updates: The joiner should of
> course not issue own Updates and Commit to them, but that is already the case
> for internal Commits. The joiner can Commit to already existing Update
> Proposals from other members.
> 
> Whether all of the above is allowed should only be governed by the policy for
> a group, nothing else. As a reminder: all clients MUST have the same policy
> for a certain group in order ta validate/refute Proposals and Commits.
> 
> This pretty much motivates my idea for fully re-using the existing Commit
> syntax and only introduce the new ExternalInitSecret Proposal.
> 
>> 
>> 
>> struct { opaque kem_output<0..2^16-1>; } ExternalInitSecret;
> 
>> - Proposal(Add) - Proposal(ExternalInitSecret) - Commit
> 
> I see some more nuance here. The first Add Proposal does not have to be
> issued by the new joiner, it could very well be an external Proposal. The
> scenario I had in mind here is the following:
> 
> - A member of the group comes online, validates the Add Proposal according to
> the policy and references it in an internal Commit (no External Commit
> needed) and sends a Welcome message to the new member
> 
> - The new joiner comes online before anyone else, has access to the public
> group data but does not need to communicate with the group. Nothing happens.
> 
> c) Emergency scenario:
> 
> - The new joiner comes online before anyone else and needs to urgently send a
> message to the group. The new joiner creates the ExternalInitSecret Proposal
> and the Commit and sends both to group.
> 
>> 
>> struct { opaque kem_output<0..2^16-1>; UpdatePath path; } ExternalCommit;
>> 
>> struct { Proposal proposals<0..2^32-1>; opaque kem_output<0..2^16-1>; 
>> UpdatePath path; } ExternalCommit;
>> 
> I do agree that the amount of signatures is sub-optimal, and this is
> something that also occurs in other situations. For example, when a member
> wants to add n new members at once to the group, it needs to compute n+1
> signatures for that. You mention the idea of inline proposals: Would that be
> a proposal that doesn’t have a signature, but still all other information? If
> so, I think it would be worthwhile looking at that separately, because as you
> say, it could be back-ported to internal Commits as well. I’m all for
> exploring that idea further.
> 
>> 
>> struct { CipherSuite cipher_suite; opaque group_id<0..255>; uint64 epoch; 
>> opaque tree_hash<0..255>; opaque confirmed_transcript_hash<0..255>; 
>> Extension extensions<0..2^32-1>; } GroupKeyPackage;
> 
> This is what the PR currently says, except that the PR used GroupContext and
> has the full public tree. I agree that the tree hash should be enough and
> I’ll change the PR accordingly.
> 
>> 
> While the two are awfully similar, the signature on GroupInfo is not required
> here and might have undesired effects w.r.t deniability if this is publicly
> accessible. The other reason for not wanting the signature is that it would
> be an additional signature to compute with every Commit, making them even
> more expensive. I propose to keep the struct as-is.
> 
>> 
>> Hope this helps, —RLB
> - Keep the current Commit syntax - Allow all kinds of Proposals for External
> Commits, same as with internal Commits - Do the HPKE-based init secret for
> External Commits - Introduce the ExternalInitSecret Proposal and make it
> mandatory for External Commits - Explore the idea of inline proposals
> separately - Do not re-use signed GroupInfo struct and keep the adjusted
> ExternalCommitInfo instead
> 
> Raphael
> 
>> _______________________________________________ MLS mailing list 
>> [email-masked] https://www.ietf.org/mailman/listinfo/mls
> 
> _______________________________________________ MLS mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/mls
>

---

From: Raphael Robert <[email-masked]>
Date: Wed, 7 Oct 2020 14:57:26 +0200

I think that’s exactly the motivation we need for inline proposals, this surplus of signatures is not specific to this use case!

Raphael

> On 7 Oct 2020, at 13:27, Joel Alwen <[email-masked]> wrote:
> 
>> * Including PSK proposals for additional

---

From: Richard Barnes <[email-masked]>
Date: Wed, 7 Oct 2020 11:38:26 -0400

OK, how about the following proposal (heh):

- Add ExternalInitSecret proposal
- Add an "inline proposals" field to Commit that lets the committer send
proposals with a commit

Two remaining worries here:

- Validation: You want it to be the case that an ExternalInitSecret is only
present for a Commit signed by a new joiner.  So some that information will
have to be passed from MLSPlaintext validation to Commit processing.  Or
maybe we don't care about that restriction?  It seems like a member sending
ExternalInitSecret should at least be SHOULD NOT, but maybe it's not bad
enough to absolutely forbid / have hard checks against.

- Complexity: MLSPlaintext signature validation has to find a key to verify
the signature.  I guess in this case, it should take the one for the
Committer (Commit.update_path.leaf_key_package.public_key), but it should
also be the case that that key was added to the group with this Commit.  In
any case, this probably calls for a new sender type.

Maybe these can both be solved with a flag passed into Commit processing:

if (external_commit) {
  // verify that there is an Add corresponding to
update_path.leaf_key_package
} else {
  // verify that ExternalInitSecret is not present
}

Even if so, that logic should get specified in the commit processing
section of the spec.

--RLB

On Wed, Oct 7, 2020 at 8:57 AM Raphael Robert <raphael=
[email-masked]> wrote:

> I think that’s exactly the motivation we need for inline proposals, this
> surplus of signatures is not specific to this use case!
>
> Raphael
>
> >> I think we are better off with re-using the current Commit syntax and
> I’ll
> >> explain why further below.
> >>
> >> A server issues an external Add Proposal for a group. The following
> things
> >> can happen:
> >>
> >> a) Ideal scenario:
> >>
> >> As mentioned above, I’m all for re-using the existing Commit syntax
> because
> >> of clarity, simplicity and flexibility.
> >>

---

From: Raphael Robert <[email-masked]>
Date: Wed, 7 Oct 2020 22:23:48 +0200

Good points again!

> On 7 Oct 2020, at 17:38, Richard Barnes <[email-masked]> wrote:
> 
> - Add an "inline proposals" field to Commit that lets the committer send proposals with a commit
> 
> - Validation: You want it to be the case that an ExternalInitSecret is only present for a Commit signed by a new joiner.  So some that information will have to be passed from MLSPlaintext validation to Commit processing.  Or maybe we don't care about that restriction?  It seems like a member sending ExternalInitSecret should at least be SHOULD NOT, but maybe it's not bad enough to absolutely forbid / have hard checks against.

Good question. I guess you want to detect early on if it is an External Commit or an internal one, perhaps also to block External Commits by policy. Indeed only the signature and sender type would reveal that. 
Should internal Commits be allowed to have a ExternalInitSecret proposal that then just gets ignored? I don’t have strong feelings about it, but I’m leaning towards the safe approach of saying it MUST not.

> 
> - Complexity: MLSPlaintext signature validation has to find a key to verify the signature.  I guess in this case, it should take the one for the Committer (Commit.update_path.leaf_key_package.public_key), but it should also be the case that that key was added to the group with this Commit.  In any case, this probably calls for a new sender type.
> 
>   // verify that there is an Add corresponding to update_path.leaf_key_package
> } else {

I’m thinking that the MLSPlaintext framing the External Commit will reference a previously empty leave (namely the left most empty leave in the tree). Normally clients would look up the leave to verify a signature, but in this case it’s an indication that it is an External Commit. Instead, clients have to parse the list of Add Proposal the precede the Commit to determine who the signer/sender is. Lastly the ExternalInitSecret Proposal MUST also be there.

As for the sender type, couldn’t we use new_member here? Both for the Add Proposal and the Commit?

> 
> Even if so, that logic should get specified in the commit processing section of the spec.

I agree that this should be written up in detailed steps to avoid any confusion.

Raphael

> 
> --RLB
> 
> 
> On Wed, Oct 7, 2020 at 8:57 AM Raphael Robert <raphael=[email-masked] <mailto:[email-masked]>> wrote:
> > On 7 Oct 2020, at 13:27, Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
> > 
> > On 7 Oct 2020, at 03:20, Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
> >>> On 7 Oct 2020, at 03:20, Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
> >>> 
> >>> Hey all,
> >>> 
> >>> [email-masked] <mailto:[email-masked]> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> >> 
> >> [email-masked] <mailto:[email-masked]> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> >> 
> > 
> > [email-masked] <mailto:[email-masked]>
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Brendan McMillion <[email-masked]>
Date: Wed, 7 Oct 2020 17:45:48 -0700

I know you're all tired of hearing me say this, but I still feel strongly
we should always use asymmetric Commits. If MLS is otherwise secure, then
there's simply no reason not to, and it simplifies implementations. There
wouldn't have to be a new ExternalInitSecret proposal, validation logic
wouldn't get substantially more complicated, and there wouldn't be this
worry about bundling several proposals. Otoh, I think allowing inline
proposals in Commits is a good idea but it's orthogonal to asymmetric
Commits.

On Wed, Oct 7, 2020 at 1:24 PM Raphael Robert <raphael=
[email-masked]> wrote:

> - Validation: You want it to be the case that an ExternalInitSecret is
> only present for a Commit signed by a new joiner.  So some that information
> will have to be passed from MLSPlaintext validation to Commit processing.
> Or maybe we don't care about that restriction?  It seems like a member
> sending ExternalInitSecret should at least be SHOULD NOT, but maybe it's
> not bad enough to absolutely forbid / have hard checks against.
>
>
> Good question. I guess you want to detect early on if it is an External
> Commit or an internal one, perhaps also to block External Commits by
> policy. Indeed only the signature and sender type would reveal that.
> Should internal Commits be allowed to have a ExternalInitSecret proposal
> that then just gets ignored? I don’t have strong feelings about it, but I’m
> leaning towards the safe approach of saying it MUST not.
>
>
> - Complexity: MLSPlaintext signature validation has to find a key to
> verify the signature.  I guess in this case, it should take the one for the
> I’m thinking that the MLSPlaintext framing the External Commit will
> reference a previously empty leave (namely the left most empty leave in the
> tree). Normally clients would look up the leave to verify a signature, but
> in this case it’s an indication that it is an External Commit. Instead,
> clients have to parse the list of Add Proposal the precede the Commit to
> determine who the signer/sender is. Lastly the ExternalInitSecret Proposal
> MUST also be there.
>

---

From: Richard Barnes <[email-masked]>
Date: Thu, 8 Oct 2020 11:47:21 -0400

(Changing subject line because changing subject)

Since there seems to be some energy around inline proposals regardless of
ExternalCommit, I made a quick PR:

https://github.com/mlswg/mls-protocol/pull/414

The interesting nuance here is that the Commit specifies an order in which
Proposals are applied.  So there are basically two design options here:

1. Include proposals by value, and reference them by hash in the order
specification
2. Allow the order specification to reference proposals by value or by hash

I went with the latter approach, because it seemed slightly simpler to me.
But if folks feel strongly, we could go the other way as well.

--Richard

---

From: Raphael Robert <[email-masked]>
Date: Fri, 9 Oct 2020 07:25:51 +0200

I think this is a good start and a useful feature in general!

I think there is is one more nuance when it comes to processing and validating Commits:

In the current state of the draft clients send Proposals followed by one Commit. Proposals might be valid or not and clients have to validate them at the latest when they process the Commit. At that point they will reject the Commit if it contains any invalid Proposal. They will however still keep the Proposals as such around and wait for the next Commit or issue a Commit themselves.

With inline Proposals this is no longer true. When clients reject a Commit because of an invalid inline proposal, that proposal is effectively lost. Clients could of course extract the inline proposals and either re-use them in their own Commit or frame them as standalone proposals. We should think about whether we want that and what we should specify here.

> On 8 Oct 2020, at 17:47, Richard Barnes <[email-masked]> wrote:
> 
> Since there seems to be some energy around inline proposals regardless of ExternalCommit, I made a quick PR:
> 
> https://github.com/mlswg/mls-protocol/pull/414 <https://github.com/mlswg/mls-protocol/pull/414>
> 
> The interesting nuance here is that the Commit specifies an order in which Proposals are applied.  So there are basically two design options here:
> 
> 1. Include proposals by value, and reference them by hash in the order specification
> I went with the latter approach, because it seemed slightly simpler to me.  But if folks feel strongly, we could go the other way as well.

I’m not sure I understand how that’s reflected in the current PR. Regardless, I think that inline and standalone proposals should be treated equally from a semantic point of view.

> 
> --Richard
> 
> 
> On Wed, Oct 7, 2020 at 8:45 PM Brendan McMillion <[email-masked] <mailto:[email-masked]>> wrote:
> I know you're all tired of hearing me say this, but I still feel strongly we should always use asymmetric Commits. If MLS is otherwise secure, then there's simply no reason not to, and it simplifies implementations. There wouldn't have to be a new ExternalInitSecret proposal, validation logic wouldn't get substantially more complicated, and there wouldn't be this worry about bundling several proposals. Otoh, I think allowing inline proposals in Commits is a good idea but it's orthogonal to asymmetric Commits.
> 
> On Wed, Oct 7, 2020 at 1:24 PM Raphael Robert <raphael=[email-masked] <mailto:[email-masked]>> wrote:
> Good points again!
> 
>> On 7 Oct 2020, at 17:38, Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: Richard Barnes <[email-masked]>
Date: Sun, 11 Oct 2020 14:58:38 -0400

In case it helps folks grok this change: I implemented this PR in the C++
stack that Suhas and I have been working on, as part of prototyping out
external Commit:

https://github.com/cisco/mlspp/pull/118/commits/a52018c1ed44224fe5b616b7ef824b74a791d1f7

Raphael: To your equivalence point, the above code does what I think is the
opposite of what you propose -- inline proposals fate share with the Commit
they're attached to.  If the Commit fails, then the proposals inlined in it
are not cached.  Personally, I think that's probably the right outcome,
since otherwise you end up with a Commit that can partly fail, in the sense
that it was not applied, but still left some proposals cached.  Cleaner to
have the Commit and all inline proposals discarded if the Commit or any
inline proposal is invalid.

--Richard

On Fri, Oct 9, 2020 at 1:25 AM Raphael Robert <[email-masked]> wrote:

> In the current state of the draft clients send Proposals followed by one
> Commit. Proposals might be valid or not and clients have to validate them
> at the latest when they process the Commit. At that point they will reject
> the Commit if it contains any invalid Proposal. They will however still
> keep the Proposals as such around and wait for the next Commit or issue a
> Commit themselves.
>
> With inline Proposals this is no longer true. When clients reject a Commit
> because of an invalid inline proposal, that proposal is effectively lost.
> Clients could of course extract the inline proposals and either re-use them
> in their own Commit or frame them as standalone proposals. We should think
> about whether we want that and what we should specify here.
>
> I went with the latter approach, because it seemed slightly simpler to
> me.  But if folks feel strongly, we could go the other way as well.
>
>
> I’m not sure I understand how that’s reflected in the current PR.
> Regardless, I think that inline and standalone proposals should be treated
> equally from a semantic point of view.
>
>
> --Richard
>
>
>>>> I think that’s exactly the motivation we need for inline proposals,
>>>> this surplus of signatures is not specific to this use case!
>>>>
>>>> Raphael
>>>>
>>>> >> I think we are better off with re-using the current Commit syntax
>>>> and I’ll
>>>> >> While that is not very explicit in the current PR, my approach was
>>>> the
>>>> >> following:
>>>> >>
>>>> >>> In any case, it seems like it would be useful to have some syntax
>>>> for
>>>> >>> this.
>>>> >>>
>>>> >>> Hope this helps, —RLB
>>>> >>
>>>> >>
>>>> >> TL;DR:
>>>> >>
>>>> >> I propose the following:
>>>> >>

---

From: Richard Barnes <[email-masked]>
Date: Sun, 11 Oct 2020 15:09:02 -0400

To help flush out additional details needed here, I went ahead and
prototyped out external commits in mlspp:

https://github.com/cisco/mlspp/pull/118

As outlined in the PR, there are few additional things we need in the spec
PR:

1. The ExternalInit proposal type and its handling
This is largely just what was sketched up-thread.

2. Defining the minimal requirements for an external Commit
We probably need a section describing some special additional constraints
that apply to external Commits, beyond general Commits:
- It MUST cover an Add proposal for the committer
- It MUST include an inline an ExternalInit proposal
- It MAY cover other proposals
- Commit.path MUST be populated

3. A new SenderType value for external commits and signature validation
logic
The above PR defines a new SenderType value "external_joiner", and when an
MLSPlaintext with that sender type is encountered, uses the public key from
Commit.path.leaf_key_package.  (The latter so that it doesn't have to look
up an Add proposal within the Commit.)  I think that validation strategy is
probably the right balance of simplicity and correctness.  As far as the
SenderType, we could probably re-use the "new_member" type, with the
understanding that:
- new_member + Proposal => Proposal MUST be an Add, and the signature must
validate with the public key from Add.key_package
- new_member + Commit => Commit MUST be an external Commit (with Add and
ExternalInit proposals), and the signature must validate with the public
key from Commit.path.leaf_key_package

But if we can nail those down, I think we have a tool here that's pretty
powerful, and not all that complicated to implement.

--Richard

---

From: Raphael Robert <[email-masked]>
Date: Sun, 11 Oct 2020 21:19:16 +0200

Thanks for implementing it! That’s always good for validation.

> On 11 Oct 2020, at 21:09, Richard Barnes <[email-masked]> wrote:
> 
> To help flush out additional details needed here, I went ahead and prototyped out external commits in mlspp:
> 
> https://github.com/cisco/mlspp/pull/118 <https://github.com/cisco/mlspp/pull/118>
> 
> As outlined in the PR, there are few additional things we need in the spec PR:
> 
> We probably need a section describing some special additional constraints that apply to external Commits, beyond general Commits:

This is what we currently already have in the PR:

- External Commits MUST reference the Add Proposal that adds the issuing new member to the group      
- External Commits MUST be signed by the new member      
- External Commits MUST contain a `path` field (and is therefore a "full" Commit)      
[ - When processing a Commit, both existing and new members MUST use an empty init secret (all-zero vector of size Hash.length) ] (outdated)
- If the Add Proposal is also issued by the new member, its member SenderType MUST be `new_member`

> 
> 3. A new SenderType value for external commits and signature validation logic
> The above PR defines a new SenderType value "external_joiner", and when an MLSPlaintext with that sender type is encountered, uses the public key from Commit.path.leaf_key_package.  (The latter so that it doesn't have to look up an Add proposal within the Commit.)  I think that validation strategy is probably the right balance of simplicity and correctness.  As far as the SenderType, we could probably re-use the "new_member" type, with the understanding that:
> - new_member + Proposal => Proposal MUST be an Add, and the signature must validate with the public key from Add.key_package
> - new_member + Commit => Commit MUST be an external Commit (with Add and ExternalInit proposals), and the signature must validate with the public key from Commit.path.leaf_key_package
> 
> But if we can nail those down, I think we have a tool here that's pretty powerful, and not all that complicated to implement.

Thanks for confirming my intuition!

Raphael

---

From: Joel Alwen <[email-masked]>
Date: Wed, 14 Oct 2020 11:35:19 +0200

Quick question: is an *explicit* add proposal for the external commitor needed?
Or can we leave that implicit since an external commitor is always being added
and their new leaf key package is already specified as part of the path field in
the commit.

- Joël

---

From: Raphael Robert <[email-masked]>
Date: Wed, 14 Oct 2020 12:43:02 +0200

That’s a good question. I can definitely think of cases where the explicit Add Proposal is desired, for example when an external party (like a server) issues that Add Proposal. In the scenario where the new member issues the Add Proposal, it does seem a bit redundant, like you say. Because an Add Proposal for the new member might already exist, this mechanism has to be optional, otherwise we would have to force drop proposals.

I see two options:

a) We keep it as is. In the case the new member issues the Add Proposal, it could be an inline proposal (once we have that mechanism) and therefore the only overhead would be increased payload size, since the KeyPackage is repeated, but there is no overhead coming from additional signatures.

Pros:
 - Clarity and simplicity when parsing Commit messages

Cons:
 - Increased payload size

b) We infer the Add Proposal from the External Commit if it didn’t exist so far. Internally clients would have create the Add Proposal and add it to the beginning of the list. This complicates the parsing logic a bit, but saves the repetition of the KeyPackage. The complication comes from the fact that this can really only be optional (as mentioned above).

Pros:
 - Optimal payload

Cons:
 - More complicated logic

I don’t see any negative impact on security just yet, to me it just looks like a tradeoff between logic simplicity and payload size. I don’t have a strong opinion on this either way, maybe Richard can comment on the potential increase in complexity?

Raphael

> On 14 Oct 2020, at 11:35, Joel Alwen <[email-masked]> wrote:
>

---

From: Joel Alwen <[email-masked]>
Date: Wed, 14 Oct 2020 12:52:36 +0200

On 14/10/2020 12:43, Raphael Robert wrote:
> I can definitely think of cases where the explicit Add Proposal is desired,
> for example when an external party (like a server) issues that Add Proposal.

OK, I think I get it. To make sure: Is the use case for explicitly including the
Add proposal in an ext. comm. for the commitor to prove to the group that the
server (or whoever else made the proposal) OKed the commitor joining the group?

- Joël

---

From: Raphael Robert <[email-masked]>
Date: Wed, 14 Oct 2020 13:15:13 +0200

Yes, that’s how you derive who added someone to the group. If Alice creates and Add Proposal to add Bob, the semantic interpretation would be “Alice added Bob”, regardless of who committed in the end.

Obviously this has to do quite a bit with the application logic and some applications might not care at all about it. But we should be clear on what information is conveyed where.

Raphael

> On 14 Oct 2020, at 12:52, Joel Alwen <[email-masked]> wrote:
>