Subject: [MLS] Inferring which nodes are redundant

From: Richard Barnes <[email-masked]>
Date: Fri, 11 Feb 2022 10:02:30 -0500

In yesterday's discussion of #587 yesterday [1], we noted that omitting
intermediate blank nodes from parent hash calculations could allow blank
nodes to be added or removed.  Karthik noted that if the positions of the
blank nodes could be inferred somehow, this concern could be less.

I said on the call that it seemed like you could probably infer this from
the pattern of blanks / non-blanks in the leaves.  To flesh this out:

>From the blank / non-blank pattern in leaves, you can infer the maximal set
of non-redundant nodes in the tree.  Basically, you work up from the
leaves, marking a leaf as non-redundant if it has more than one
non-redundant node in its resolution.  I mocked this up in Rust to convince
myself it works and help visualize it:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=516d82f8e8875102b066c1a0f0e5778b

With the changes in #587, if a node is marked as redundant based on the
leaves, then it MUST be blank; there is no valid way for it to be
populated.  The reverse is not true: A non-rendundant node may be blank.
The most obvious example is a freshly-created tree, which is blank except
for its leaves.

I'm not sure how much this algorithm buys us, but it seems potentially
useful as we consider redundant nodes and parent hash computations.

--Richard

[1] https://github.com/mlswg/mls-protocol/pull/587