Subject: [MLS] Simplifying the key schedule

From: Richard Barnes <[email-masked]>
Date: Fri, 22 Feb 2019 22:27:56 -0500

At the last interim, we filed an issue to discuss simplifying the key
schedule.  In particular, folks were unhappy that the whole, possibly
gigantic GroupState object has to be hashed on every epoch change.  When I
sat down to think about how to simplify, though, it wasn't clear what
direction to go in, because it wasn't clear exactly what people were
finding painful.

I'll posit from the start that I'm pretty sure that we need to somehow
include the tree, the roster, and the message transcript into the key
schedule.  The transcript inclusion follows from the same reasons as it
does in TLS; the roster and tree are needed because the whole transcript
isn't accessible to a new joiner (so the new joiner can't infer those
values from the transcript).

With that said, there are multiple ways to represent those values for
inclusion the key schedule:

1. Directly (as now)
2. As hashes
3. As structured hashes, e.g., a Merkle or "ampelmann" tree

People are clearly unhappy with (1).  The difference between 2 and 3 (and
between variants of 3) is what value we're trying to achieve.  (2) reduces
the amount of hashing somewhat, but it doesn't change the amount of state
you have to keep -- each member has to keep the full roster and tree, and
hash the whole thing when it changes.

For (3), it seems like there are weak and strong forms.  In the weak form,
we make it so that the member has to hash a sub-linear-size amount of data
to update its representation of the tree/roster when it changes (e.g., in a
Merkle tree, you have to recompute log(N) nodes).  But each member still
has to have the whole structure.  In the strong form, we arrange the
protocol so that a member can operate while holding a sub-linear amount of
state (e.g., just a copath/frontier in some tree).  Note that the strong
form would entail pretty major protocol changes, e.g., bringing back the
Merkle membership proofs that were in earlier versions of the protocol.
For similar reasons, this would also entail larger messages.

So basically, the mapping of options to values is:

1. Overall simplicity
2. A smaller coefficient on the linear amount of data hashed
3(weak). Sub-linear amount of data hashed
3(strong). Sub-linear amount of state

In my personal value judgement, I would probably end up somewhere between
(2) and (3,weak).  It seems pretty unavoidable to me that members will have
*some* linear-size state for the group, even if it's only a names for the
members; adding say a key and a roster entry for each of those doesn't seem
like a huge increment.  So appealing though the state savings would be,
they're not compelling enough to merit the protocol complexity and overhead.

All that said, I would be interested in other folks' thoughts on which
options are to be preferred here, or if there are other options that come
to mind.

Thanks,
--Richard

---

From: Joel Alwen <[email-masked]>
Date: Sun, 24 Feb 2019 12:17:16 +0700

Hi Richard,

Sandro Corretti and I just discussed the questions you brought up in
your email about the key schedule and we've come round to the opinion
that of the options you present we prefer:

- for the roster a merkle tree seems to be a good solution
- for the ratchet tree an ampelmann hashing scheme should work well

In our opinion linear state size (with reasonably small constants) is
the lesser of the three evils when compared to needing extensive hashing
for each tree update and needing larger packet sizes for the protocol
(e.g. due to membership proofs).

Having said that I wanted to suggest an alternative. Namely, including
the ID's of leaves as part of what gets hashed for the ratchet tree.
This makes including the roster redundant which means we would save on
all the merkle tree storage as well as the hashing during join/leave
ops. The only cost I see is that we might want to include the *hash* of
ID's as part of the state to avoid having to recompute when that party
updates their PK. (But that still needs less storage than a full merkle
tree on the roster so its also an improvement.)

While we are on the subject of amplemann tree's I wanted to make a
suggestion for how to deal with blank nodes. I think its conceptually
simpler (and thus hopefully also less error prone / easier to code) then
using the resolution of blank nodes to define their values in the
ampelmann hash. We let the value of each node begin with an indicator
bit b (or octet if thats more practical). So node values are strings of
the form b || PK. (Alternatively for leaves it would be b || PK ||
H(ID).) When b indicates the node is blank (b=1) we simply define PK
(and H(ID)) to be all 0s.

I'm also in favour of Raphael's suggestion to define the hash of a node
to be H(L || R || V) where L and R are the hash of the left and right
child while V denotes the value of the current node. It seems simpler
than H(H(L || R) || V).

- Joel

On 2/23/19 10:27 AM, Richard Barnes wrote:
> gigantic GroupState object has to be hashed on every epoch change.  When
> I sat down to think about how to simplify, though, it wasn't clear what
> People are clearly unhappy with (1).  The difference between 2 and 3
> (and between variants of 3) is what value we're trying to achieve.  (2)
> reduces the amount of hashing somewhat, but it doesn't change the amount
> of state you have to keep -- each member has to keep the full roster and
> tree, and hash the whole thing when it changes.
> 
> For (3), it seems like there are weak and strong forms..  In the weak
> form, we make it so that the member has to hash a sub-linear-size amount
> of data to update its representation of the tree/roster when it changes
> (e.g., in a Merkle tree, you have to recompute log(N) nodes)..  But each
> member still has to have the whole structure.  In the strong form, we
> arrange the protocol so that a member can operate while holding a
> sub-linear amount of state (e.g., just a copath/frontier in some tree). 
> Note that the strong form would entail pretty major protocol changes,
> e.g., bringing back the Merkle membership proofs that were in earlier
> versions of the protocol.  For similar reasons, this would also entail
> larger messages.
> 
> In my personal value judgement, I would probably end up somewhere
> between (2) and (3,weak).  It seems pretty unavoidable to me that
> members will have *some* linear-size state for the group, even if it's
> only a names for the members; adding say a key and a roster entry for
> each of those doesn't seem like a huge increment.  So appealing though
> the state savings would be, they're not compelling enough to merit the
> protocol complexity and overhead.
> 
> options are to be preferred here, or if there are other options that
> come to mind.
> 
> Thanks,
> --Richard
> 
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Benjamin Beurdouche <[email-masked]>
Date: Sun, 24 Feb 2019 11:15:41 +0100

Hi Joel,

> On Feb 24, 2019, at 6:17 AM, Joel Alwen <[email-masked]> wrote:
> 
> Hi Richard,
> 

I am not sure to understand what you mean here :)  while it might be poorly
documented all the user init keys in TreeKEM are already mixed in the
epoch secret because the Group AKE mandates to agree on whom is in
the group at all times. Our issue is that a newcomer cannot use that
information to explicitly check the identities.

In general, I agree that the TreeKEM section of the draft lacks clarity on
what it provides, and I believe it will be helpful to improve upon it so
I will take a pass on it with Karthik before the interim.

Cheers,
B.

---

From: Richard Barnes <[email-masked]>
Date: Mon, 25 Feb 2019 10:32:00 -0500

Hi Joel,

Some notes inline:

> (e.g. due to membership proofs).

Thanks for the clear priorities!

> tree on the roster so its also an improvement.)

This seems sensible to me.  So you would basically end up with a unified
tree with the following shape:

- Leaves hold (DHPublicKey, Credential, NodeHash)
- Intermediate nodes hold (DHPublicKey, LeftHash, RightHash, NodeHash)

It actually looks to me like this is a wash from a storage POV -- in each
case, you have 2n-1 DH keys, n credentials, and n-1 hashes.  But it
probably saves you some hashing in some cases.

> (and H(ID)) to be all 0s.

This is actually already kind of covered in the current spec.  The nodes in
the ratchet tree are of type optional<DHPublicKey>, which is 0x01 || PK
when populated and 0x00 when blank.  So if we just use that same struct for
the V input to the ampelmann hashing, things should be pretty
straightforward to code.

> child while V denotes the value of the current node. It seems simpler

The only difference that occurs to me here is that there's a factor of 2 in
proof size to be had: If you don't care about the children, you can just
send H(L || R) instead of sending (L, R).  Of course, there's a
corresponding factor of two in hashing, so there's another trade-off space
to select from.

--Richard