Subject: [MLS] Overly aggressive tree trimming can break parent hashes

From: Konrad Kohbrok <[email-masked]>
Date: Fri, 10 Dec 2021 13:17:16 +0100

Hi everyone,

while testing changes to our tree implementation, we found what we 
believe is a bug in the specification. More concretely, the tree 
truncation mandated by the spec is too aggressive and can destroy parent 
hashes in an otherwise valid tree.

For debugging purposes, we had a check that would validate parent hashes 
of every node every time a commit is processed, which is how we found 
the bug.

Currently, the spec mandates that upon a remove operation, the leaves 
are removed until the right-most leaf in non-blank. However, this can 
lead to a situation, where non-blank parent nodes of a non-blank leaf 
are removed. This removal potentially interrupts valid 
"parent-hash-chains". More concretely, if the affected leaf node was the 
last node to commit a path in its subtree, then overly aggressive 
truncation can lead to the removal of parent nodes in that path. This in 
turn leads to an error when the parent hash of the parent of the removed 
parent node is verified. Note that if the parent hash chain is 
interrupted in this way, the situation is indistinguishable from one 
where the parent hash of a node is simply invalid.

Consider the following example:

                               15

                 _______________|

                /                |

               7                 |

         ______|______           |

        /             \          |

       3              11         |

     __|__           __|__       |

    /     \         /     \      |

   1       5       9      13     |

  / \     / \     / \     / \    |

A   B   C   D   E   F   G   -   I

                     1 1 1 1 1 1 1

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

- G performs an update, leading to a valid parent hash chain along its 
direct path (13, 11, 7, 15).

- A removes I, leading to the following state, since G is the right-most 
non-blank leaf.

               7

         ______|______

        /             \

       3              11

     __|__           __|

    /     \         /   \

   1       5       9     |

  / \     / \     / \    |

A   B   C   D   E   F   G

                     1 1 1

0 1 2 3 4 5 6 7 8 9 0 1 2

- Since we have removed 13 in the process of removing (leaf) node 14, 
verification of the parent hash of node 11 will now fail, since none of 
its children carries its hash in its parent hash field.

- This will become apparent if a new member is added, either by one of 
the nodes A-D or by any node without a path.

As solution, we propose that the right-most leaf is only removed in the 
process of truncation if both it _and its parent_ are blank.

Raphael pointed out that this "careful" truncation leads to sparser 
trees and thus makes the protocol overall less efficient (larger tree 
structures need to be stored, longer direct paths with more secrets and 
key pairs to derive, etc.).

We can fix this by having two forms of truncation: A "careful" one, as 
described above and the one that is already in the spec right now with 
one caveat.

The careful one replaces the one that is currently described in the spec 
and is thus performed with each removal operation.

The one that we have right now is performed before a committer (or the 
receiver of a commit) applies a direct path, except that it can only 
remove nodes that are in the direct path of the committer.

This should allow us to get the smallest tree that we can without 
compromising valid parent hash chains.

Cheers,

Konrad

---

From: Richard Barnes <[email-masked]>
Date: Fri, 10 Dec 2021 11:29:35 -0500

Hi Konrad,

Thanks for thinking through this.  I mocked this up as a test case in
mlspp, and I can confirm that it breaks there too.

https://github.com/cisco/mlspp/compare/truncate-parent?expand=1

A couple of thoughts here...

# Putting blanks in update paths

It occurs to me that there is a different solution approach available here,
which preserves the sparsity of the tree, and even makes commits a little
more
efficient in some cases.

The starting point here is to observe that the current update path algorithm
adds useless intermediate nodes.  The reason the parent hash fails in your
example is that G added a useless intermediate node.  Since G is the only
child
of 13, that node could just as well have been left blank.  The resolution
algorithm would then result in the same number of encryptions when someone
elsewhere in the tree updated.

This is a small fix to the update path generation / processing algorithms.
When
the resolution of the copath node is empty, you simply set the parent node
to a
blank node instead of a populated parent node.

For the parent hash computation: Since blank nodes are all the same for
parent
hash, if the receiver of a tree knows where to put the blanks, then it can
add
them into the parent hash computation.  So the main work here would be to
(1)
update the parent hash algorithm so that it can cover blank nodes, and (2)
add
some syntax to the ParentHash extension that describes where the blanks
go.  If
we still had a notion of node indices, you could state it that way; less
clear
how to do it otherwise.

To work through an example: Suppose we have the following tree, in which G
has
just sent a commit to remove H.  The direct path sent by G resets nodes 12,
13,
11, 7, and 15, but sets node 13 to a blank because its copath resolution is
blank.

                                15
                 _______________|
                /                \
               7                 |
         ______|______           |
        /             \          |
       3              11         |
     __|__           __|__       |
    /     \         /     \      |
   1       5       9       _     |
  / \     / \     / \     / \    |
 A   B   C   D   E   F   G   _   I

                     1 1 1 1 1 1 1

The parent hash at G is thus over the path (12, _, 11, 7, 15).  We will
assume
that G's parent hash extension indicates that there is a blank in its direct
path between 12 and 11.

Now suppose as in your example that A removes I, so that you end up with the
same tree as in your example.

               7
         ______|______
        /             \
       3              11
     __|__           __|
    /     \         /   \
   1       5       9     |
  / \     / \     / \    |
 A   B   C   D   E   F   G

                     1 1 1

A recipient seeing this tree can recognize that node 11 is covered by G's
parent
hash, because it will add a virtual blank node when computing the parent
hash
from 11 to G.

Now, that's pretty complicated, especially when you work out the details.
So
I'm not sure it's the right answer.  Just wanted to put it out there in the
interest of completeness.

# Exponential delete

I don't think your proposed careful delete solution actually works.  You
need
not only the parent node to be blank, but the whole path to the root.  I'll
assert that without proof for now, because the counterexample requires an
inconveniently large tree :)

Fortunately, that idea turns into an algorithm that's even simpler: Only
truncate the tree by removing the whole right side of it.  In the example
above,
after I gets removed, you would keep the blank leaf at node 14, and move the
root of the tree to node 7.  In an even sparser example:

                                15
                 _______________|
                /                \
               7                 |
         ______|______           |
        /             \          |
       3               _         |
     __|__           __|__       |
    /     \         /     \      |
   1       _       _       _     |
  / \     / \     / \     / \    |
 A   B   _   _   _   _   _   _   I

                     1 1 1 1 1 1 1

... after removing I you would first chop down to 0..14, then 0..6, then
0..2.
While root.right.empty(), root = root.left.

The overall semantic would then be that the tree grows linearly, but shrinks
exponentially.  (Like TCP!)  That obviously keeps bigger trees around for
longer, but it ultimately gets the job done.  And an implementation that
really
cares can use Remove+Add move operations to compact the tree.

# ...

Overall, I think my preference here would be to go with the exponential
delete
option. Adding blanks in the parent hash is nice in that it saves some
work, but
the details seem intimidatingly complicated. Exponential delete is a simple,
easy-to-understand solution that still GC's the tree, just more slowly.

--Richard

On Fri, Dec 10, 2021 at 7:18 AM Konrad Kohbrok <[email-masked]>
wrote:

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Raphael Robert <[email-masked]>
Date: Fri, 10 Dec 2021 18:55:19 +0100

Thanks for verifying it Richard!

Since things get confusing quickly given the complexity of the subject, I want to summarise the different mechanisms discussed so far:

M1: Trimming carefully upon removing members
I think we essentially talk about the same thing here (what you call exponential delete). It can be expressed quite simply in the array representation. We inspect the rightmost tuple of nodes (parent_node, leaf_node) in the array. Previously – with the aggressive trimming – we would remove the tuple if leaf_node was blank. What we propose is to only remove the tuple when both parent_node and leaf_node are blank.

M2: Trim the direct path of committers by omitting blank nodes
This is what you proposed in your previous email. I agree that it sounds quite involved at first and could have some unforeseen effects elsewhere. This approach however seems to have the highest gain of efficiency, because unnecessary parent nodes are removed even before the original trimming would occur.

M3: Trim the tree before computing the update path of a commit
This what Konrad additionally described in his email. In essence, another trimming pass starting from the right side of the tree takes place before the committer computes the update path. The effect is similar to M2, but it occurs later in time (namely only once the leaves rough to the committer have been removed). This approach does not require to have blanks in the direct path, it just potentially shortens the direct path (and therefore the update path). The complexity seems moderate and so far I don’t this could have nasty side effects.

Now, the question is which on of those we would like to mandate in the spec. It seems we agree that M1 is uncontroversial as such, we just need to agree on the details of the algorithm.
M2 and M3 are mutually exclusive, in that M3 becomes unnecessary if we also have M2.

Assuming we don’t come up with more mechanisms, I currently see 3 approaches:

M1 + M2: Highest efficiency, but also highest complexity
M1 + M3: Balance between efficiency and complexity
M1: Conservative choice, slowest shrinking of trees

My take on it is that we should go with M1 for now because it seems to be orthogonal to M2/M3 anyway. We can still ponder a bit more about M2/M3 in the meantime.

Raphael

> On 10. Dec 2021, at 17:29, Richard Barnes <[email-masked]> wrote:
> 
> Hi Konrad,
> 
> Thanks for thinking through this.  I mocked this up as a test case in mlspp, and I can confirm that it breaks there too.
> 
> https://github.com/cisco/mlspp/compare/truncate-parent?expand=1 <https://github.com/cisco/mlspp/compare/truncate-parent?expand=1>
> 
> which preserves the sparsity of the tree, and even makes commits a little more
> efficient in some cases.
> 
> example is that G added a useless intermediate node.  Since G is the only child
> This is a small fix to the update path generation / processing algorithms.  When
> the resolution of the copath node is empty, you simply set the parent node to a
> For the parent hash computation: Since blank nodes are all the same for parent
> hash, if the receiver of a tree knows where to put the blanks, then it can add
> them into the parent hash computation.  So the main work here would be to (1)
> update the parent hash algorithm so that it can cover blank nodes, and (2) add
> some syntax to the ParentHash extension that describes where the blanks go.  If
> we still had a notion of node indices, you could state it that way; less clear
> how to do it otherwise.
> 
> To work through an example: Suppose we have the following tree, in which G has
> just sent a commit to remove H.  The direct path sent by G resets nodes 12, 13,
> The parent hash at G is thus over the path (12, _, 11, 7, 15).  We will assume
> A recipient seeing this tree can recognize that node 11 is covered by G's parent
> hash, because it will add a virtual blank node when computing the parent hash
> from 11 to G.
> 
> Now, that's pretty complicated, especially when you work out the details.  So
> I don't think your proposed careful delete solution actually works.  You need
> truncate the tree by removing the whole right side of it.  In the example above,
> ... after removing I you would first chop down to 0..14, then 0..6, then 0..2.
> longer, but it ultimately gets the job done.  And an implementation that really
> Overall, I think my preference here would be to go with the exponential delete
> option. Adding blanks in the parent hash is nice in that it saves some work, but
> On Fri, Dec 10, 2021 at 7:18 AM Konrad Kohbrok <[email-masked] <mailto:[email-masked]>> wrote:
> Hi everyone,
> 
> 
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Konrad Kohbrok <[email-masked]>
Date: Fri, 10 Dec 2021 19:14:58 +0100

Hi Richard,

replies inline below.

On 10/12/2021 17:29, Richard Barnes wrote:
> <https://github.com/cisco/mlspp/compare/truncate-parent?expand=1>
> 

This seems like a good idea beyond solving the problem of trimming. Do 
we really need that explicit description in the ParentHashExtension? I 
haven't worked out the algorithm, but I would think that the verifier 
could work out that from the verification perspective in a similar way 
that it can work out where blank nodes have been added to accommodate 
new nodes. More concretely, if a child is blank, it could either be 
because a new node was added, or because the whole subtree under that 
child has only one occupant, which should have the right value in its 
extension.

> 11, 7, and 15, but sets node 13 to a blank because its copath resolution is

Can you describe abstractly in what situation this approach would fail? 
I don't see it immediately and I'm curious where this method falls 
short. Although now that I think about it, the "careful" algorithm 
should remove a leaf if it is blank and its parent is either blank or 
the root node.

I believe that should give you pretty much the same result as the 
exponential delete method you're sketching here. But I'd be happy to be 
proven wrong.

> root of the tree to node 7.  In an even sparser example:

Do you mean that one would perform one step per commit? Why not just 
shrink the tree down to 0..6 in one go?

> On Fri, Dec 10, 2021 at 7:18 AM Konrad Kohbrok 
> <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     Hi everyone,
> 
> 
> 
>     <https://www.ietf.org/mailman/listinfo/mls>
> 
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 14 Dec 2021 09:48:03 -0500

Thanks, this taxonomy is helpful.  And I think I agree with you on the way
forward.

Just to confirm that I understand your M3, is the following an accurate
restatement of the proposal?

* Define two types of truncation:
  * Aggressive: Remove a leaf if it is blank (what we currently do)
  * Careful: Only remove a leaf if both the leaf and its parent are blank
* Do careful truncation after applying Remove proposals
* Do aggressive truncation after applying all proposals, but before
computing the update path

I think that only works (i.e., doesn't break parent hash) when the
committer is the rightmost leaf in the truncated tree.  Otherwise, you have
parent nodes on the right whose parent hash is getting broken, and the
parent node is not being reset by the update.  You could of course write a
provision that says "if the committer is the rightmost non-blank leaf, then
strip the leaves to the right", but I don't really think the extra branch
in the code (heh) is worth the savings.

So my proposal here would be to do M1 and not M2 or M3.  As a bonus, it's a
short PR!

https://github.com/mlswg/mls-protocol/pull/524

I could be persuaded to do M3 (with the above caveats) if people are keen.
It would basically be another step in the Commit generation / processing
that says "If there are no non-blank leaves to the right of the committer,
truncate the tree so that the committer is the rightmost leaf."

--RLB

On Fri, Dec 10, 2021 at 12:55 PM Raphael Robert <[email-masked]>
wrote:

> Since things get confusing quickly given the complexity of the subject, I
> want to summarise the different mechanisms discussed so far:
>
> I think we essentially talk about the same thing here (what you call
> exponential delete). It can be expressed quite simply in the array
> representation. We inspect the rightmost tuple of nodes (parent_node,
> leaf_node) in the array. Previously – with the aggressive trimming – we
> would remove the tuple if leaf_node was blank. What we propose is to only
> remove the tuple when both parent_node and leaf_node are blank.
>
> This is what you proposed in your previous email. I agree that it sounds
> quite involved at first and could have some unforeseen effects elsewhere.
> This approach however seems to have the highest gain of efficiency, because
> unnecessary parent nodes are removed even before the original trimming
> would occur.
>
> This what Konrad additionally described in his email. In essence, another
> trimming pass starting from the right side of the tree takes place before
> the committer computes the update path. The effect is similar to M2, but it
> occurs later in time (namely only once the leaves rough to the committer
> have been removed). This approach does not require to have blanks in the
> direct path, it just potentially shortens the direct path (and therefore
> the update path). The complexity seems moderate and so far I don’t this
> could have nasty side effects.
>
> Now, the question is which on of those we would like to mandate in the
> spec. It seems we agree that M1 is uncontroversial as such, we just need to
> agree on the details of the algorithm.
> My take on it is that we should go with M1 for now because it seems to be
> orthogonal to M2/M3 anyway. We can still ponder a bit more about M2/M3 in
> the meantime.
>
> Raphael
>
>
> On Fri, Dec 10, 2021 at 7:18 AM Konrad Kohbrok <
> [email-masked]> wrote:
>
>> Hi everyone,
>>
>>
>>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 14 Dec 2021 09:48:09 -0500

Inline, with some trimming...

> child has only one occupant, which should have the right value in its

You might be able to get away with something like describing the pattern of
blank leaves in the tree when this node was last updated, if you also
enforced the invariant that a node was blank unless it has two non-blank
children.  But that would still require a whole bunch of algorithms, so I'm
inclined not to do it for now.

> exponential delete method you're sketching here. But I'd be happy to be

I tried to construct an example, and I think you're actually right.  Proof
sketch:

* The algorithm to remove the rightmost leaf (see PR#522) always removes
exactly two nodes, the rightmost leaf R and its parent P.  Let L be the
other child of P and Q be the parent of P.
* There are two parent-hash "links" destroyed here, L->P and P->Q.  In the
case that P is the root, Q doesn't exist, and so we can ignore P->Q.
* Removing the L->P link is not harmful, since a link is only needed to
verify a non-blank parent node, and we are removing P.  So L will continue
to have P's parent hash in it, which will be meaningless, but that's
harmless.
* Removing the P->Q link is harmful if Q is non-blank and P was the last
updated child of Q, since then the L->P->Q path is the path that verifies
Q.  However, if P is blank, then it can't be the last updated child.  So if
P is blank, then the P->Q link is not required for parent hash verification
(regardless of whether Q is blank).
* So removing the rightmost leaf doesn't break the parent hash as long as
the parent of the rightmost leaf is either blank or the root.

> shrink the tree down to 0..6 in one go?

That would be fine, I was just showing the steps :)

I have some thoughts on the way forward here, but I like Raphael's
taxonomy, so I will put them in reply to his message.

--RLB