Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create an error if we try to collapse E --> H #237

Closed
BGluth opened this issue May 21, 2024 · 0 comments · Fixed by #455
Closed

Create an error if we try to collapse E --> H #237

BGluth opened this issue May 21, 2024 · 0 comments · Fixed by #455
Assignees
Labels
crate: mpt_trie Anything related to the mpt_trie crate.
Milestone

Comments

@BGluth
Copy link
Contributor

BGluth commented May 21, 2024

As from the discussion in #202, if we ever have a branch where:

  • It has exactly two children
  • One child is a hash node
  • One child is a leaf node
  • The leaf node gets deleted

Then this is a bit of a problem as we can not collapse the remaining E --> H node if needed (because a branch with a single child collapses into an extension node). If the hash node was a leaf, then the leaf should "absorb" the extension node's key. However, we can not do this with a hashed leaf node.

It was discussed in Slack that if mpt_trie ever encounters an E --> H after a delete, then it should return an error. I don't think we should extend this to raise an error whenever we encounter one of these during traversal (eg. the pre-image that we were given contains a E --> H), as it's not a problem unless it's involved in a collapse. If we only return an error whenever we attempt to collapse an E --> H, then I think this should be sufficient. Does this sound right @Nashtare @frisitano?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
crate: mpt_trie Anything related to the mpt_trie crate.
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

2 participants