Subject: [MLS] Circular dependency in node hash calculation?

From: "Hubert Chathi" <[email-masked]>
Date: Mon, 06 Jul 2020 18:04:36 +0100

I may be missing something, but it seems to me like there is a circular dependency in the definition of the hash of a parent node.  In the "Tree Hashes" section, it says that when computing the hash of a parent node, you use the ParentNodeHashInput struct, which includes an item that is a ParentNode (which I assume is the data concerning the node that you are hashing), as well as the hashes of the two children.  However, ParentNode contains an item called parent_hash, which I assume is the hash of the node's parent.  Thus to calculate the hash of a node,  you need to calculate the hash of its parent, but that requires calculating the hash of both its children, meaning that you need to calculate the hash of node that you were trying to calculate in the first place.

Am I reading it wrong (and if so, can there be more clarification added), or is there a bug in the definitions?

Also, when calculating the hash of a struct, is there a prescribed serialization format to use, or is it up to the application to define the serialization format?

Thanks

Hubert

---

From: Raphael Robert <[email-masked]>
Date: Mon, 6 Jul 2020 22:43:05 +0200

(forgot to include the list)

> On 6 Jul 2020, at 22:05, Raphael Robert <[email-masked]> wrote:
> 
> Hi Hubert,
> 
> I admit this looks a bit confusing. The parent_hash field of a ParentNode is not to be calculated at that point in time. Instead, it should already be there. It gets populated by processing a Commit message, where a LeafNode gets updated and its entire direct path is also updated. In other words, calculating the tree hash is strictly a top down operation.
> 
> Regarding the serialisation: MLS uses the TLS presentation language specified in RFC8446.
> 
> Raphael
> 
>> On 6 Jul 2020, at 19:04, Hubert Chathi <[email-masked]> wrote:
>> 
>> _______________________________________________
>> MLS mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 7 Jul 2020 11:21:26 -0400

Yeah, just to restate / reaffirm what Raphael says:

* You get parent_hash values when you get the tree initially (in Welcome)
or when you process a DirectPath
* You compute node hashes based on those hashes, plus the other contents of
the nodes

Totally agree that this is tricky to get right, though :)  If you have
suggestions for how we can make this clearer, they would be welcome.

--Richard

On Mon, Jul 6, 2020 at 4:43 PM Raphael Robert <raphael=
[email-masked]> wrote:

> > I admit this looks a bit confusing. The parent_hash field of a
> ParentNode is not to be calculated at that point in time. Instead, it
> should already be there. It gets populated by processing a Commit message,
> where a LeafNode gets updated and its entire direct path is also updated.
> In other words, calculating the tree hash is strictly a top down operation.
> >
> >> I may be missing something, but it seems to me like there is a circular
> dependency in the definition of the hash of a parent node.  In the "Tree
> Hashes" section, it says that when computing the hash of a parent node, you
> use the ParentNodeHashInput struct, which includes an item that is a
> ParentNode (which I assume is the data concerning the node that you are
> hashing), as well as the hashes of the two children.  However, ParentNode
> contains an item called parent_hash, which I assume is the hash of the
> node's parent.  Thus to calculate the hash of a node,  you need to
> calculate the hash of its parent, but that requires calculating the hash of
> both its children, meaning that you need to calculate the hash of node that
> you were trying to calculate in the first place.
> >>
> >> Am I reading it wrong (and if so, can there be more clarification
> added), or is there a bug in the definitions?
> >>
> >> Also, when calculating the hash of a struct, is there a prescribed
> serialization format to use, or is it up to the application to define the
> serialization format?
> >>
> >> Thanks
> >>
> >> Hubert
> >>

---

From: "Hubert Chathi" <[email-masked]>
Date: Tue, 07 Jul 2020 16:24:38 +0100

Thanks to both of you for the clarifications.  I'll see if I can come up with a way to make it clearer.