Subject: [MLS] Merging tree-hash based parent hash

From: Richard Barnes <[email-masked]>
Date: Sat, 19 Feb 2022 11:09:56 -0500

Hi all,

I think the tree-hash-based parent hash PR [1] is in a merge-able state
now.  Please respond by the end of the day on Tuesday, Feb. 22 if you have
concerns or think we should not merge.

My personal take is that we should merge.  On the benefit side: It seems
like there's broad agreement that there is no regression in security; both
old and new approaches sign the public keys to which a node's private key
was sent.  In addition, we rule out some potential hijinks with identities
(as discussed on the PR) and authenticate blanks (which makes the
no-rendundancies parent hash validation less subject to manipulation).
Overall, we get closer to the idea that the tree I get is the same one that
everyone in the group has seen [2].  I'm comfortable with the cost side of
the equation given the empirical data I posted yesterday showing a modest
constant overhead (~18%) in the hardest case.

Thanks,
--Richard

[1] https://github.com/mlswg/mls-protocol/pull/527
[2] To expand on this: The obvious assumption for a developer to have is
that the tree a joiner gets is the same one that every member in that epoch
holds; it's the job of the crypto to verify this property to the extent
possible. (The tree hash guarantees that everyone who holds the epoch
secret agrees on the tree; it doesn't guarantee that all of the members in
leaves of the tree hold the secret.)  In an ideal world, a new joiner would
get direct assurance of this property, e.g., signatures from everyone in
the group over the whole tree.  From this point of view, every parent hash
is an approximation of this ideal.  Using the tree hash as the input to the
parent hash brings us closer because it authenticates more of the tree's
structure.