Update in Merkle Trees - Githubissues

hacl-star / merkle-tree

A verified Merkle Tree, built as a standalone project on top of EverCrypt

6 stars 6 forks source link

Update in Merkle Trees #7

Open eozturk1 opened 4 years ago

eozturk1 commented 4 years ago

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

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

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

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

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.