Nowadays the group key agreements are based upon tree-based ones such as Asynchronous Ratcheting tree. Especially the latter one is constructed upon left-balanced tree.

So I keep wondering what benefits has a left-balanced tree from any other binary tree structure to this application?

up vote 1 down vote accepted

In the asynchronous ratchet tree construction, intermediate group keys are constructed at each leaf of the tree. It's important that all parties agree on the exact structure of the tree so that they will all derive the same keys. An array is the canonical representation of an ordered list of items, and that array can be viewed as a binary tree. An array of length $2^n$ corresponds to a complete binary tree, while an array of any other length corresponds to a left-balanced binary tree.

You might find the Messaging Layer Security IETF working group of interest, as I believe at least one of the ART paper's authors is involved in the specification efforts. The current MLS protocol Internet-Draft restates the ART protocol from a more concrete engineering perspective, so it's very helpful for understanding how everything fits together.

New contributor
kiwidrew is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • So it does not have to me nesessarily a left balanced minary tree, as long as the tree is the same for all nodes, right? – Dimitrios Desyllas Nov 11 at 10:10
  • 1
    Correct. In this case, viewing the ordered list of participants as a left-balanced binary tree is simply the most natural method for determining the order in which to pair the parties up with each other for deriving the intermediate keys. – kiwidrew Nov 11 at 10:16

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.