search

hacl-star / merkle-tree

A verified Merkle Tree, built as a standalone project on top of EverCrypt
6 stars 6 forks source link

Merkle tree deserialize correctness check #5

Open eozturk1 opened 4 years ago

eozturk1 commented 4 years ago

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

wintersteiger commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 notifications@github.com 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 commented 4 years ago

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 commented 4 years ago

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 notifications@github.com 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.