search

pokt-network / smt

A Go library that implements a Sparse Merkle Trie for a key-value map.
https://pkg.go.dev/github.com/pokt-network/smt
Other
16 stars 4 forks source link

Use lazy-loaded cached tree implementation #6

Closed h5law closed 1 year ago

h5law commented 1 year ago

This is a port of this PR whilst retaining the squashed commit history of @roysc

This introduces a largely rewritten implementation of the SMT which operates on a cached, lazily-loaded tree structure, as opposed to the current paradigm of reading from/writing to the DB directly for each operation. This gives a significant performance https://github.com/cosmos/cosmos-sdk/issues/11444#issuecomment-1103714044 on all operations while preserving full compatibility of the produced hashes.

This also refactors the hasher objects to allow tree paths and stored values to be hashed independently, and Options to configure them. https://github.com/celestiaorg/smt/issues/40 can be satisfied by passing an identity function as the path hasher.

As noted https://github.com/cosmos/cosmos-sdk/issues/11444#issuecomment-1112401379, the DeepSubtree code supporting state-transition fraud proofs was not compatible as-is with this implementation and so is removed; but there should be no technical block to adapting that code to this impl.; it was simply outside the scope of Cosmos-SDK ADR-40 for which this was originally built.

Although using the latest vulcanize/smt lazy_loading branch some changes had to be made:

This solves and merge conflicts and enables lazy loading to be used in the repo.

roysc commented 1 year ago

Thanks for pulling from the new branch, and pointing out the missing file - sorry about that!

h5law commented 1 year ago

Thanks for pulling from the new branch, and pointing out the missing file - sorry about that!

No worries thanks for all your hard work!