Subject: [MLS] Using tree hash for parent hash calculations

From: Richard Barnes <[email-masked]>
Date: Sat, 12 Feb 2022 17:07:58 -0500

Hi all,

I worked through implementing PR #527 to try to understand it better, and
came away with an apparently working implementation [1] and a better
understanding.  So I thought I would share my notes with the group in the
interest of finding some agreement here.

A couple of insights were key for me:

* There are three places where parent hashes are computed:
    1. Sending a commit
    2. Receiving a commit
    3. Validating a tree on join
* When sending/receiving a commit, you can just use the tree hash directly,
since you're always talking about the tree as it exists right now.  (This
is `compute_sibling_data` in Théo's notation)
* When validating a tree, you need to do a completely different operation
(`compute_original_sibling_data`)
* Because the list of excluded unmerged leaves changes at different levels
of the tree, there's no real memoization to be done, so you basically need
to do a full tree hash computation for each non-blank parent.

With those insights in hand, it was a simple matter of changing the code
used for sending/receiving commits to use the sibling tree hash, and
writing new original sibling hash code that is used when validating a tree
[2].  It almost worked the first time! (I reversed the polarity on one
`if`.)

I was also able to implement the version where you rewind the tree
structure so that you don't need full trees.  The key insight here is that
unmerged extra leaves don't add any non-blank nodes, so if you just act as
if the right edge of the tree doesn't exist when computing parent/child
relationships [3], everything just works.  So at least in the array-based
tree representation, it's not difficult to do the structure rewinding to
work with non-full trees.

For Joël's benefit, here's the pseudocode:

- When computing parent hashes while sending/receiving a commit, replace
the original child resolution with the tree hash of the child
- When computing parent hashes while validating a tree, replace the
original child resolution with the original child tree hash:
   - This is a normal tree hash calculation with the parent node's
unmerged_leaves removed
   - If the righmost leaves of the tree are unmerged, compute parent/child
relationships as if they did not exist
   - If an unmerged leaf is included in the subtree, include a blank leaf
node at that position instead

All that said, I don't entirely agree with Théo's performance analysis.
Clearly parent hashes for Commits are very fast, O(1) per UpdatePath node
instead of O(N) since the tree-hashes are already there for other reasons.
But I don't think tree validation gets to O(N log log N); since you're
doing a full tree hash calculation under each non-blank parent, it looks
more like O(N log N) or maybe even O(N^2).  Maybe I'm miscounting, or
there's some caching optimization here I missed.

All *that* said, I find myself more inclined to make this change than
before.  There will be some non-trivial complexity in writing this up
clearly, and the cost of tree validation is not great.  But I like the
clear semantic one gets by having the leaf node signatures vouch for whole
subtrees instead of just resolutions.  For example, with regard to #587
(Stop generating redundant PKE key pairs), if we were worried about
uncertainty around blank nodes, signing the whole subtree would mean
signing the blank nodes as well.

Hope that helps,
--Richard

[1] https://github.com/cisco/mlspp/compare/tree-hash-parent-hash
[2]
https://github.com/cisco/mlspp/compare/tree-hash-parent-hash#diff-e0f47462d3a3371ea1d9893b85819a562c8f801c2c9b2fa01d449ef0e5def589R545
[3]
https://github.com/cisco/mlspp/compare/tree-hash-parent-hash#diff-e0f47462d3a3371ea1d9893b85819a562c8f801c2c9b2fa01d449ef0e5def589R615

---

From: Théophile Wallez <[email-masked]>
Date: Mon, 14 Feb 2022 15:14:59 +0100

Hi,

This algorithm was not the one I proposed, but it works: in my proof 
[1], you can actually replace "full_extension" by any reasonable 
canonicalization of the tree that is immune to extension / truncation. 
The canonicalization I proposed was to fully extend the tree, the one 
you propose is to truncate the tree, either option work. However, I 
think you also need to truncate the tree when sending / receiving a Commit!

About the O(n log n) complexity: this is the complexity that the naïve 
algorithm has. Here is a less formal and more visual way to see this: 
the complexity to check the parent hash of N is O(number of leaves in 
N's subtree).
We can then see visually what happens, if I write on # for each leaf 
that is in the subtree for each node, and separate each node by a |:

|# # # # # # # #| (1 node at level 0, the root)
|# # # #|# # # #| (2 nodes at level 1)
|# #|# #|# #|# #| (4 nodes at level 2)
|#|#|#|#|#|#|#|#| (8 nodes at level 3)

You can see that on each level, we process n leaves (here n = 8) and 
there are O(log n) levels, giving a total complexity of O(n log n).

For the O(n log log n) bound, you need a fancy algorithm that relies on 
the following fact:
during the same epoch, the function 
TreeKEMPublicKey::original_tree_hash(index, except, original_size) 
returns the same value if we call it several times with the same arguments.
This function is therefore "pure" in the functional programmers language 
(or "const" for c++ programmers), and this means that we can do 
memoization on it. I calculated that with memoization, the complexity 
was lowered to O(n log log n) [2].
However I'm not sure about what will happen in your case, since for a 
fixed `index`, there will be calls to `original_tree_hash` for different 
values for `except` and `original_size`, my analysis only works when 
`original_size` don't change.
This means we have two solution to allow this faster algorithm:
- either truncate every subtree, and not only the tree at the root,
- or do the full extension approach, which corresponds to have 
`original_size = next_power_of_2(size)`.
One argument against this analysis might be to say that memoization 
isn't O(1), you need some sort of dictionary that comes with some cost, 
however an analysis shows that if you compute the parent hash either 
bottom-up or top-bottom, then the only memoization you need is to check 
if `except` is the same as the previous call, in fact you only need to 
check the length of it! Memoization is therefore O(1) with a crazy-low 
constant.

Now that you have an actual implementation, I would be curious to have 
an actual benchmark test between the resolution-based parent hash and 
the tree-based parent hash! The O gives intuition about the performance 
for large group size, but hide the constant.

Cheers,
Théophile.

[1] https://github.com/mlswg/mls-protocol/pull/527#issuecomment-1035122916
[2] https://github.com/mlswg/mls-protocol/pull/527#issue-1082163460

On 12/02/2022 23:07, Richard Barnes wrote:
> Hi all,
>
> I worked through implementing PR #527 to try to understand it better, 
> and came away with an apparently working implementation [1] and a 
> better understanding.  So I thought I would share my notes with the 
> group in the interest of finding some agreement here.
>
> * When sending/receiving a commit, you can just use the tree hash 
> directly, since you're always talking about the tree as it exists 
> right now.  (This is `compute_sibling_data` in Théo's notation)
> * When validating a tree, you need to do a completely different 
> operation (`compute_original_sibling_data`)
> * Because the list of excluded unmerged leaves changes at different 
> levels of the tree, there's no real memoization to be done, so you 
> basically need to do a full tree hash computation for each non-blank 
> parent.
>
> With those insights in hand, it was a simple matter of changing the 
> code used for sending/receiving commits to use the sibling tree hash, 
> and writing new original sibling hash code that is used when 
> validating a tree [2].  It almost worked the first time! (I reversed 
> the polarity on one `if`.)
>
> structure so that you don't need full trees.  The key insight here is 
> that unmerged extra leaves don't add any non-blank nodes, so if you 
> just act as if the right edge of the tree doesn't exist when computing 
> parent/child relationships [3], everything just works.  So at least in 
> the array-based tree representation, it's not difficult to do the 
> structure rewinding to work with non-full trees.
>
> - When computing parent hashes while sending/receiving a commit, 
> replace the original child resolution with the tree hash of the child
>    - If the righmost leaves of the tree are unmerged, compute 
> parent/child relationships as if they did not exist
>    - If an unmerged leaf is included in the subtree, include a blank 
> leaf node at that position instead
>
> All that said, I don't entirely agree with Théo's performance 
> analysis.  Clearly parent hashes for Commits are very fast, O(1) per 
> UpdatePath node instead of O(N) since the tree-hashes are already 
> there for other reasons.  But I don't think tree validation gets to 
> O(N log log N); since you're doing a full tree hash calculation under 
> each non-blank parent, it looks more like O(N log N) or maybe even 
> O(N^2). Maybe I'm miscounting, or there's some caching optimization 
> here I missed.
>
> clear semantic one gets by having the leaf node signatures vouch for 
> whole subtrees instead of just resolutions.  For example, with regard 
> to #587 (Stop generating redundant PKE key pairs), if we were worried 
> about uncertainty around blank nodes, signing the whole subtree would 
> mean signing the blank nodes as well.
>
> Hope that helps,
> --Richard
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Mon, 14 Feb 2022 09:54:03 -0500

Thanks, Théophile.  I agree with your analysis re: O(n log n).  My O(n^2)
guess was too pessimistic; I was over-counting the number of layers.

I'm happy to run some benchmarks here, but TBH I'm not sure the differences
between O(n), O(n log n), and O(n log log n) are going to be that huge
here.  We'll probably have to go after some pathological cases to show
differences.  I'll ping you offline to dive into details.

In the meantime, interested if other folks have thoughts on whether the
algorithms here are clear, and whether these performance differences are
salient.

Thanks,
--Richard

---

From: Richard Barnes <[email-masked]>
Date: Tue, 15 Feb 2022 16:05:02 -0500

OK, I did some basic benchmarking, and the results seem supportive of
making this change.  The details get a little involved, so here's an
executive summary:

* I implemented and benchmarked the naïve algorithm described up-thread,
and a lightly memoized version that should be easy to write spec text for
* The naïve algorithm performs poorly.  Commits are no worse than before,
but validating a tree is about an order of magnitude slower with hundreds
of participants.
* The lightly memoized version is competitive.  Commits are slightly faster
than before, and validating a tree takes 20-50% more time.

Full details below.

# Methodology

I looked at three algorithms:

1. "Resolution": Parent hash based on sibling resolution
2. "Tree Hash": Parent hash based on sibling tree hash, recomputing tree
hashes on validation
3. "Tree Hash + Reuse": "Tree Hash", but re-using the existing tree hash
when nothing has changed

I implemented these in branches of mlspp [1][2][3], and made a performance
measurement branch [4] that could be rebased on any of these and linked
against the library implementing the appropriate algorithm.  The
measurements just use std::chrono time measurements before and after the
operations being timed.

The basic framework is to build a group of a certain form, then measure how
long it takes to do a commit and parent-hash-validate the tree.  In other
words, the measurement program builds a group of N participants, one at a
time, and at each epoch, measures how long it took to generate the commit
to add the latest commit and how long it takes to validate the parent
hashes of the resulting tree.  Commits are always done by the leftmost
member of the tree.

Within that framework, I looked at a few scenarios:

1. "empty" - Add+commits are done without sending an UpdatePath, so only
the leaves of the tree are populated
2. "path" - Each add+commit includes an UpdatePath, so only the path from
the leftmost leaf to the root is populated
3. "fill=k" - After every k-th addition, the newly added node removes the
(k-1) nodes to its left (populating its direct path).  The leftmost member
adds them back, adding unmerged leaves.
    * fill=1 - Every member updates and none are removed.  The tree is
full, and has no unmerged leaves
    * fill=2 - Every other member is removed and readded.  The tree is
full, and every parent node has unmerged leaves
    * fill=4 - Three of every 4 members are removed and readded.  The
bottom two tiers of the tree are sparse, and there are a lot of unmerged
leaves (3/4 of all leaves).

For each of these, five scenarios and each algorithm, I collected data up
to 256 participants, timing performance on my 2018-vintage MacBook Pro.

# Results

I've attached a PDF that shows performance curves for all the cases, and
posted the raw data in CSV form at [5].  A few features of this stand out
to me:

* There's basically no variation on the commit side of things.
    * In the "path" case, encrypting to all the participants dominates
    * In all the other cases, there's not a noticeable difference between
the three
    * With TH+R, sending a commit is a couple of percentage points faster
on average

* In all three cases, the "empty" scenario is invisible because it's on the
bottom axis.

* The naïve "Tree Hash" algorithm is awful!
    * It slows things down by about an order of magnitude over the
resolution case
    * You can clearly see things getting worse at the log transitions
    * This algorithm does better with fill=2/4 because there are fewer
nodes to verify

* The "Tree Hash + Reuse" algorithm is not dramatically worse than baseline
    * At the outside, about 50% worse than Resolution
    * Instead of performance hits at log boundaries, things get a little
better
    * Unmerged leaves hurt with fill=2, but with fill=4, this is
counteracted by having fewer nodes to check
    * The "path" case almost disappears along the bottom axis; it is more
efficient than Resolution

* Extrapolating via linear regression on the "fill=1" case:
    * At 1024 members, validating a tree takes: Resolution=83ms, TH=974ms,
TH+R=128ms
    * R^2 is pretty good in all cases, Resolution=0.988, TH=0.995,
TH+R=0.977
    * The TH+R case looks to have a bit more curve, so the above might be
an underestimate
    * ... but maybe not by much.  Higher-order polynomial fits are better,
but the linear term still dominates.
    * Excel doesn't have an "n log log n" fit function :)

# Conclusions

Together with the clarified algorithm at the top of the thread, this
experiment gives me pretty good confidence in adopting this algorithm.  It
clearly has a non-trivial performance hit, but:

a. It doesn't seem all that bad a cost for the improved validation and
clearer semantics
b. Implementations might be able to better with better memoization
c. Validation is only done once, on joining, and even with this it is
unlikely to be the dominant cost, compared to computing the tree hashes and
even just downloading the tree
d. Thereafter, things are marginally faster

My biggest remaining worry is making sure the algorithms are clear.  The
details of memoization should probably go into an implementation
considerations document, but it would be good for the protocol spec to at
least guide folks in that direction.

Overall, I'm inclined to do this.

--RLB

[1] https://github.com/cisco/mlspp/tree/main/
[2] https://github.com/cisco/mlspp/compare/tree-hash-parent-hash
[3] https://github.com/cisco/mlspp/compare/memoize
[4] https://github.com/cisco/mlspp/compare/ph-perf
[5] https://gist.github.com/bifurcation/e330ee484e53ad95453c451c12e026af

On Mon, Feb 14, 2022 at 9:54 AM Richard Barnes <[email-masked]> wrote:

> I'm happy to run some benchmarks here, but TBH I'm not sure the
> differences between O(n), O(n log n), and O(n log log n) are going to be
> that huge here.  We'll probably have to go after some pathological cases to
> show differences.  I'll ping you offline to dive into details.
>
> On Mon, Feb 14, 2022 at 9:15 AM Théophile Wallez <
> [email-masked]> wrote:
>
>> Hi,
>>
>> [1]
>> https://github.com/mlswg/mls-protocol/pull/527#issuecomment-1035122916

---

From: Richard Barnes <[email-masked]>
Date: Fri, 18 Feb 2022 09:42:17 -0500

One more update here: Théophile implemented more complete memoization and
we collected new data.  Top-level finding is that on a full tree, the
overhead is a flat 18% (no dependency on size).

I have updated the gist with the raw data for the memoized case.  The
attached PDF shows validation times for the various algorithms, both as
absolute times and as ratios over the resolution case.  As you can see, the
memoized tree hash algorithm has a performance ratio that does not depend
on N for a given tree structure.  For a full tree, using the tree hash
costs an extra 18%, or 4ms in absolute terms.  Things get a little worse if
there are lots of unmerged leaves, but the scaling is still linear (R^2 =
0.9929).  In the case where only the committer's path is populated, the
tree-hash-based algorithms scale as O(log n) instead of O(n), so there's a
performance benefit.

Interpolating between these absolute cases, it seems like the dynamics here
are:

* For trees with no unmerged leaves, the tree-hash-based parent hash scales
as the number of non-blank parent nodes
    * ... instead of scaling as the size of the tree, as for
resolution-based parent hash
    * The cost per node is ~18% higher than for resolution-based parent hash
    * But the tree-hash-based parent hash benefits more from sparsity
* Unmerged leaves force recomputations that drive up cost per node, but
this is partly offset by the sparsity that comes along with most unmerged
leaf scenarios

Personally, my expectation is that in many cases, unmerged leaves will be
relatively rare, so the expected performance here would be equal to
slightly better than resolution hash.

All in all, no major change to the performance picture, just a clearer
picture of the dynamics.

--Richard

On Tue, Feb 15, 2022 at 4:05 PM Richard Barnes <[email-masked]> wrote:

> * The lightly memoized version is competitive.  Commits are slightly
> faster than before, and validating a tree takes 20-50% more time.
>
> Full details below.
>
> # Methodology
>
> The basic framework is to build a group of a certain form, then measure
> how long it takes to do a commit and parent-hash-validate the tree.  In
> other words, the measurement program builds a group of N participants, one
> at a time, and at each epoch, measures how long it took to generate the
> commit to add the latest commit and how long it takes to validate the
> parent hashes of the resulting tree.  Commits are always done by the
> leftmost member of the tree.
>
> * In all three cases, the "empty" scenario is invisible because it's on
> the bottom axis.
>