search

celestiaorg / smt

A Go library that implements a Sparse Merkle tree for a key-value map.
https://godoc.org/github.com/celestiaorg/smt
MIT License
138 stars 53 forks source link

Use raw key as path instead of hash(key) #40

Open adlerjohn opened 3 years ago

adlerjohn commented 3 years ago

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.

roysc commented 3 years ago

Is there an ETA or general priority set for this?

adlerjohn commented 3 years ago

I will start working on this at the end of September if no one else has picked it up before then.

musalbas commented 2 years ago

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

adlerjohn commented 2 years ago

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.

rach-id commented 2 years ago

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.

adlerjohn commented 2 years ago

Those checks should probably be required orthogonally to the issue at hand.

rach-id commented 2 years ago

Sounds good :+1:.

If I remember correctly, my PR was only doing the following:

If these are orthogonal, or can be added as preconditions, then the PR would be way smaller.

universe2439 commented 2 years ago

Agreed