Update in Merkle Trees

[eozturk1]

We are working on a project in which we need Merkle tree leaves to be updatable (which should propagate to the root and update the root hash). Is there support for such updates in the hacl-star implementation?

Can flush and retract functions be used to achieve this? I checked out the documentation but their use-cases were not clear to me.

[msprotz]

My understanding is that you can remove nodes from the beginning of the tree but not at arbitrary positions. Maybe @wintersteiger or @fournet could confirm.

[eozturk1]

Thanks for the response @msprotz! We are currently updating a node by

• Retracting the tree to the point before the target node is added,
• Updating the target node,
• Inserting previously removed nodes to the tree.

Unfortunately, this is hacky and more importantly not optimal. It would be nice to have this feature in future releases.

Please let me know if I need to do anything else to suggest this feature to the developers (and possibly help with development).

[wintersteiger]

Sorry for having missed this issue before. Your use of retraction is as expected; flushing is used to remove the left side of the tree, e.g. in blockchain applications you may not need to remember the entire tree, but only recent parts.

You're right, updating arbitrary nodes is not currently supported. I think that, as long as the updated nodes fit into the same memory, it shouldn't be too hard to proof preservation of the invariants. I'm not sure I'll have enough time to actually implement it anytime soon though.

[eozturk1]

We had some plans to compress the past in the tree up to a point, maybe we could use flush for that then. Thanks @wintersteiger !

We are using the hash values in the nodes -- if I understand correctly -- updates should not change the size of the nodes.

We are using the Merkle tree in another project as well -- which also requires updates. I think updates would be a nice feature to have. Static nodes seems to be a good fit for blockchain type of applications, but I believe there are many applications who would need dynamic nodes.