smt
smt copied to clipboard
celestiaorg
Use raw key as path instead of hash(key)
Note: this is a backwards-incompatible change in the interface, but shouldn't change the commitment so long as the library is used the same way.
Currently (as of #37), values are stored in a map hash(key) -> value. This allows constant-time reads. However, an outstanding change is using the raw key instead of the hash of the key: https://github.com/celestiaorg/smt/issues/14#issuecomment-762895582
This is needed to allow applications to store certain entries at specific keys in the tree, which also allows for algorithms that operate over subtrees (see above-linked comment for more context). Users who do not want to use this functionality can simply hash their keys before passing them to the library, resulting in an identical tree as before the change proposed here.
I will start working on this at the end of September if no one else has picked it up before then.
Wouldn't a simpler way for an end-user to implement this than https://github.com/celestiaorg/smt/pull/64 would be to implement a treeHasher with a custom path() function that simply returns the same bytes as output? https://github.com/celestiaorg/smt/blob/dba215ccb88452c31d823bf156d8f35406c1dc04/treehasher.go#L30
Hm, that's a good suggestion. Off the top of my head I don't see why that wouldn't work. If there are no objections from @SweeXordious who worked on this most recently, we can instead just document this property and close the issue.
That's a good idea. The only thing I am thinking about is the key size, the library expects it to be constant, if I remember correctly. Thus, additional key size checks will need to be added.
Those checks should probably be required orthogonally to the issue at hand.
Sounds good :+1:.
If I remember correctly, my PR was only doing the following:
- Adding constant key size checks
- Ability to track the key size not to panic
If these are orthogonal, or can be added as preconditions, then the PR would be way smaller.
