Merkle tree deserialize correctness check

[eozturk1]

Does mt_deserialize check for correctness of the tree, i.e., root is correct given the nodes in the tree?

[wintersteiger]

No it doesn't. It performs some lower level checks, but it doesn't recompute the hashes. I'm planning to change the serialization so as not to save internal hashes at all (to save space), but as a side-effect it would also recompute the internal hashes. So far, I haven't had time to actually do that though.

[eozturk1]

Then, does it make sense to rebuild the tree from the leaves instead of serializing/deserializing if deserializing side does not trust the correctness of the tree it receives? Is there a better/cheaper way to ensure correctness in this case?

[wintersteiger]

I don't think there's anything cheaper because you have to check every single hash computation since you can't invert them. Maybe we could save some extra information during serialization that allows us to cut some paths during deserialization, but I'm not convinced it would pay off.

[eozturk1]

I understand, thank you!

For correctness, after deserialization, would it be enough to get the root with mt_get_root and compare the received root to the expected value? From the code, it seems to me mt_get_root calculates the root starting with the leaves and going up. Therefore, the root returned from this function should be the correct root of the deserialized tree.

[prosecco]

I am curious: is there a public RFC or other standard for merkle trees that the code is trying to meet?

…

On 30 Apr 2020, at 12:01, Christoph M. Wintersteiger ***@***.***> wrote: I don't think there's anything cheaper because you have to check every single hash computation since you can't invert them. Maybe we could save some extra information during serialization that allows us to cut some paths during deserialization, but I'm not convinced it would pay off. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://github.com/project-everest/hacl-star/issues/293#issuecomment-621736397>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABDABHTBHPW4I4BLOSELYNTRPFD7ZANCNFSM4MTK2KJA>.

[wintersteiger]

If I remember correctly, deseralization does set the rhs_ok flag to false, so that it triggers a recalculation, but that's only for the right-most hashes on every level of the tree, so I don't think that would be enough.

@prosecco: I don't know the answer, but if you find it, please forward it to me!

[prosecco]

This is the only public spec I see: https://tools.ietf.org/html/rfc6962#section-2.1 <https://tools.ietf.org/html/rfc6962#section-2.1> I don’t expect the F* code follows this though.

…

On 6 May 2020, at 11:03, Christoph M. Wintersteiger ***@***.***> wrote: If I remember correctly, deseralization does set the rhs_ok flag to false, so that it triggers a recalculation, but that's only for the right-most hashes on every level of the tree, so I don't think that would be enough. @prosecco <https://github.com/prosecco>: I don't know the answer, but if you find it, please forward it to me! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://github.com/project-everest/hacl-star/issues/293#issuecomment-624528242>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABDABHUL22OG6YQFO4S22TTRQERU7ANCNFSM4MTK2KJA>.