Re: [MLS] RT array implementation motivation

[Richard Barnes <[e-mail]>]

Hi Tijana,

The specification doesn't require that the tree be implemented in a given
way.  Implementations are free to arrange their memory however they like.
The array notation just gives us a simple way to assign each node in the
tree an index.

--Richard

On Wed, May 19, 2021 at 8:56 AM Tijana Klimovic <[e-mail]>
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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>