Always operate on a full tree

[bifurcation]

In order to use tree hashes to represent siblings in parent hashes, we had to compute a different tree hash on the right edge of the tree, pretending that the tree is full, in the sense of having 2^n leaves. Thus we actually have two tree hashes in play, one used for group agreement on the tree and one used for parent hash inputs.

We should consider specifying that the logical tree used by MLS is always full. This change to the specification would not change the computations done by the protocol much, if at all. Thanks to the fact that we no longer generate redundant nodes (#587), there is never anything non-blank to the right of the rightmost non-blank leaf anyway. So the main impact is to insert some blank nodes between a parent node on the right edge of the tree and its right child -- and all of the algorithms in the specification already skip over such nodes.

Likewise, implementations' internal represntations of the tree wouldn't have to change much, since the extra nodes could be "virtual". The only time they would be noticed is when computing tree hashes. We would have to update the description of the ratchet_tree extension to say that it only covers the tree up to the rightmost non-blank leaf.

It would simplify the specification in a few ways, for example:

• The "original sibling tree hash" would just entail blanking unmerged leaves, not structure changes.
• The description of extending and truncating the tree would be much simpler.

The main cost would be extra hashes when joining, or when updating a member close to the right edge of the tree. If you have a tree with 2^n + 1 leaves, then you have to compute tree hashes over 2^n - 1 blank leaves and their 2^n - 2 blank parents.

[bifurcation]

Thanks to @mulmarta and @TWal for helping inspire and develop this idea in discussions around #635

[bifurcation]

Virtual interim 2022-05-19

• @mulmarta notes that the current tree hash is quite tricky to implement, so this would be a useful simplification
• Doubling the hashes on a fresh tree doesn't sound too intimidating
• Folks would find more concreteness useful here, interested in PR
• Could we phrase this as only a change to TreeKEM?
  • Would be premised on the equivalence of the hashed tree an the tree you operate on

[seanturner]

Discussed at 19 May interim: @bifurcation to draft a PR.

[bifurcation]

Holding a PR until after #689 lands.

Some notes on what would need to change:

• {{ratchet-tree-terminology}} would change from "the unique left-balanced tree with N leaves" to "the unique balanced binary tree with depth d, where d is the smallest number such that N <= 2^d".
• {{adding-and-removing-leaves}} would either be removed, or updated so that it talks about increasing or decreasing the depth of the tree (equivalently, doubling or halving the number of leaves).
• {{add}} would talk about increasing depth instead of adding leaves.
• {{remove}} would talk about decreasing depth instead of removing leaves.
• {{ratchet-tree-extension}} would be explicit that it only carries nodes up to the rightmost non-blank leaf. The encoding/decoding algorithms would have to be updated.
• {{array-based-trees}} and {{link-based-trees}} could probably be simplified.
• We would need to make sure all figures showed full trees.

[bifurcation]

I went ahead and filed #694 for this, based on top of #689. Once that merges, we can update the PR to be a little easier to read. The changes are basically as described above.

One additional note: We have actually already incurred the cost to a new joiner of hashing all the extra nodes, because they have to do it for parent hash verification anyway. So this approach is actually a net reduction in the amount of hashing that has to be done, since they don't have to also compute the non-full-tree hashes.