Subject: [MLS] Switch to signing strategy using one signature per leaf.

From: Brendan McMillion <[email-masked]>
Date: Thu, 30 Jan 2020 11:45:18 -0800

Hello mls@

As per the minutes from the last virtual interim, it looks like there's
consensus around merging PR #287, "Switch to signing strategy using one
signature per leaf." Before that happens, I wanted to write a message to
the list formally introducing the change.

A while ago, we started having the members of a group sign the nodes in the
ratchet tree, along with a hash of the node's subtree, as the nodes were
changed (through Update/Commit messages). The purpose of this was to
authenticate the tree when it's sent in a Welcome message.

Without authentication, the member that sends the Welcome message could
falsify the tree and add themselves in subtrees they don't appear to be in.
This attack makes it impossible for the new member to reasonably remove the
welcomer from the group.

The proposed change in my PR switches from a scheme where every node and a
subtree hash is signed, to a scheme where each leaf and a "path hash" is
signed. The path hash of a node is defined as the hash of all the node's
ancestors. Path hashes work differently from the tree hashes we currently
have in the spec, in that they go up instead of down.

There are two main benefits of this scheme:

1. It reduces the number of signatures that need to be verified by a factor
of 2.

2. It's compatible with approaches for deniability, since the information
that each member is signing doesn't bind them to the other members of the
group.