Use lazy-loaded cached tree implementation

[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 improvement 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 here, 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.

[codecov-commenter]

Codecov Report

Merging #73 (676615b) into master (5f13c0f) will increase coverage by 0.83%. The diff coverage is 86.15%.

@@            Coverage Diff             @@
##           master      #73      +/-   ##
==========================================
+ Coverage   85.62%   86.46%   +0.83%     
==========================================
  Files           6        8       +2     
  Lines         466      650     +184     
==========================================
+ Hits          399      562     +163     
- Misses         39       53      +14     
- Partials       28       35       +7     

Impacted Files	Coverage Δ
options.go	50.00% <50.00%> (ø)
smt_testutil.go	69.23% <69.23%> (ø)
smt.go	83.33% <84.31%> (+2.54%)	:arrow_up:
types.go	88.37% <88.37%> (ø)
proofs.go	93.61% <97.05%> (-6.39%)	:arrow_down:
hasher.go	100.00% <100.00%> (ø)
utils.go	100.00% <100.00%> (ø)

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

[musalbas]

Thanks @roysc! I've pulled the changes from the vulcanize repo a few weeks into the "lazy" branch here (https://github.com/celestiaorg/smt/tree/lazy), as we need to implement the things in https://github.com/celestiaorg/smt/issues/72 first before merging to master. Is our lazy branch already up to date or does this PR introduce anything new not in the lazy branch (if so can this PR be against the lazy branch rather than master)?

For context though, we've currently decided to put the SMT work on hold too, as we're currently implementing deep trees for IAVL instead (https://github.com/celestiaorg/iavl/issues/1). This is because due to the assumptions made by store V1 including range queries and versioning etc, making store V1 work well with SMT is more work than expected so we've decided to pursue IAVL for now.

[roysc]

(if so can this PR be against the lazy branch rather than master)?

Sorry, I didn't see that branch - this branch is just somewhat cleaned up, I removed a caching MapStore which isn't quite relevant, renamed some minor things and added some comments. This is a rebase, so targeting the original head might be a mess, but I will check.

[musalbas]

@roysc does this PR remove value storage? I recall in the original lazy implementation in vulcanize, value storage was removed. But it looks like you added back in this PR, if I understand correctly (from a cursory look)? Would the code in the README still work?

[roysc]

Sorry for the delay on this, it was sidelined by prioritization and time off. I'd like to wrap it up if possible, and to that end I've pushed an additional cleanup/refactor with a README update.

@roysc does this PR remove value storage?

Yes it does, but we can easily add a type that wraps value storage with the tree. (Alternatively, the raw value can be stored directly in the leaf by using an identity function as the value hasher.)

What's the likelihood of this being reviewed in the near future? If no movement is likely for now (or you just plan to use your own branch), I will probably just close this PR.

[musalbas]

Thanks for this @roysc. Given we're not currently using SMT at Celestia, there's no one really currently maintaining this repo.

My suggestion is that given that your PR breaks the current interface, that you merge this into vulcanize/smt, and then perhaps I can add to the README of this repo that this repo isn't currently being maintained, and point them to vulcanize/smt as a more recently maintained version. Is vulcanize currently using and maintaining vulcanize/smt? Alternatively, I think it's fine to just leave this PR open in case we start maintaining this repo again, and for future users to see.

[roysc]

Thanks @musalbas. I think the SMT is basically shelved for vulcanize for now as well, but could possibly be experimented with in the future, so pointing to that fork makes sense. I'll close this PR though, just for tidiness purposes.

[Olshansk]

@musalbas @roysc We're using this library at Pocket and plan on taking it to production as well. It probably won't be for a month or two, but what I was thinking was:

1. We can fork this library
2. Use this PR (update docs, test, etc...)
3. Optionally merged it back here to avoid maintaining a fork

[roysc]

@Olshansk That works, we will maintain our fork at Vulcanize and I can take up your PR once it's ready.

[musalbas]

We intend to deprecate/archive this repo as we don't have bandwidth to review PRs and maintain this repo. So @Olshansk if you plan to actively use and maintain SMT, I suggest maintaining your own fork for now.

[Olshansk]

We intend to deprecate/archive this repo as we don't have bandwidth to review PRs and maintain this repo. So @Olshansk if you plan to actively use and maintain SMT, I suggest maintaining your own fork for now.

👍 I've created https://github.com/pokt-network/smt.

Will revisit potential collaboration opportunities when our fork is more mature & battle-tested.