4 ms·
Balanced binary trees usually have some kind of rotations to maintain their properties like left-leaningness. In this application this is to be avoided in order
by peterhil 7y ago
Balanced binary trees usually have some kind of rotations to maintain their properties like left-leaningness. In this application this is to be avoided in order to not not send so many messages.
I understood that all participating clients know about the structure of the tree, so could not all the clients do the rotations in this kind of mass removal without sending messages?
I mean that in the last example, the tree is not left leaning, but can be made so by promoting every Zayne to their ancestor nodes.
- doomrobo 7y agoGood point. I don't think it'd be unreasonable to promote everyone to their parent in this example. One thing that I left out of the post is that the MLS ratchet tree has something called a "tree hash". Every node carries a hash digest, which is the hash of its two children. The root node's hash is used to derive a bunch of group-specific values, so it's important to keep this hash up to date. If you promote every member to their parent, this would require about N log(N) total hash operations, since every path from a leaf to the root would have to have its hashes recalculated. N log(N) hashes seems like a small price to pay for optimizing a structure that determines how many ECDH operations you end up doing. I'll ask other MLS people about this and see if I'm missing something.