Re: [MLS] RT array implementation motivation

Hi Tijana,

At the end of the day you can use whatever implementation works best of course. The array approach has a few benefits though:
 - it’s language agnostic, something that’s important for IETF
 - it gives you a serialisation format for free (quite practical for the ratchet tree extension)
 - it let’s you use references to nodes in the tree that are used in the Secret Tree to derive secrets for example
 - it makes it easy to add and remove nodes without having to change anything in neighbouring nodes

From a performance standpoint, using the tree math provided should also be reasonably fast. If you have some benchmarks to share that prove otherwise, it would be interesting to look into it.

Lastly, pointers can be great, but they can also be quite dangerous if implemented wrongly.

Hope this helps,

Raphael

> On 19. May 2021, at 14:55, Tijana Klimovic <tijana.klimovic97@gmail.com> wrote:
> 
> Hello,
> 
> I have only recently started to look into the MLS specification, and was wondering why the ratchet tree (RT) structure is chosen to be implemented with an array. From what I understand, the pointer-based tree where each node would contain the following information: 
> 
>         struct {
>         Node* sibling;
>         Node* parent;
>         Node* left_child;
>         Node* right_child;
>         Optional<HPKEPublicEncKey> hpke_enc_pk;
>         Optional<HPKESecretEncKey> hpke_enc_sk;
>         Optional<Credential> credential;
>         Optional<vector<byte>> parent_hash;
>         Optional<vector<Node*>> unmerged_leaves;
>         } Node 
> 
> would be more efficient than an array w.r.t. all operations supported by the RT. 
> 
> Many thanks.
> Tijana
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls