[Persistence] Evaluate Celestia's Sparse Map Tree implementation

[Olshansk]

Objective

Determine if we can leverage an open source Sparse Merkle Tree implementation or if we need to implement our own.

Origin Document

The implementation of Pocket Network's V1 state hash can be done independently of #147 by leveraging an existing library, but its correctness is dependent on that of the underlying library.

With cosmos leaving IAVL, there are lots of other options available in the industry. cosmos/cosmos-sdk#7100. Per the research done in this deck, Libra's Jellyfish Merkle Tree seems to be the best path forward.

One of the best open source, fully in Go, implementations we've found online is from Celestia: https://github.com/celestiaorg/smt. I've reached out to see if this is being used in production via a Tweet but have not heard back.

Goals

• Review, evaluate & understand Celestia's open source SMT implementation
• Stretch goal: merge changes/ improvements upstream; opportunity to contribute back and work more closely together

Deliverable

• A determination of the correction of Celestia's implementation
• A decision if this codebase could / should be used as our SMT implementation
• Optional: changes / improvements to Celestia's SMT

Non-goals / Non-deliverables

• Implement any part of the Pocket Network V1 state hash

---

Creator: @Olshansk

[Olshansk]

Update. I sent out an initial PR with some questions related to their implementation & edits here: celestiaorg/smt#74

I have a call with someone from their team this week as well

[Olshansk]

tl;dr We will be using this Celestia's Merkle Tree for the time being, whichis being implemented in #285.

Future Work

Based on the research in [1] and [2], this fits our use case so far. Follow-up work (to be tracked in future tickets) to explain and verify this will include:

1. Present: Summarizing [1] and [2] and presenting it to the team (and community?) to provide a clear picture of the landscape of trees and why this was selected.
2. Benchmark: Using the tool in [Persistence] First Implementation of the StateHash (#284) #285 to benchmark different KV stores when performance optimizations matter.
3. Visualize: Producitonizing the tools presented in [Exploration] Using Celestia's SMT for Pocket Network V1? celestiaorg/smt#74 to improve observability & debugging in the tree.
4. Export: Building a tree export tool scoped in [Persistence] Export Trees Tool #340
5. Re-evaluate & verify this in Milestone M5 depending on how things and any new information that becomes available.

Key Reasons - Technical

1. Best available: In short, to avoid IAVL (old, slow, complex), and while we're awaiting Verkle trees (too early), Sparse Merkle Tree implementations are the most efficient approach to generating a state hash today.
2. State of Industry: This implementation is a simplification of Libra's JMT, which is used by Aptos (formally Libra, formally Diem), optimized for high throughput and performance.
3. Maintanble: This implementation is done completely in Go and can therefore be forked, extended and maintained by the team.
4. Configurable: It is configurable for any key-value store rather than being tied to a specific one keeping forward-looking optionality.
5. Swappable: The interface is composed of 3 simple functions, allowing us to swap this out for other tree implementations in the future with minor "proxy interface" wrapper if need be also maintaining forward-looking optionality.

Key Reasons - Technical Reassurance

These reassurances took place after the original decision as a result from [1] and [2] which is a big ➕ .

1. Cosmos: In Cosmos' ADR 40, they were planning to migrate to using this SMT due to, in part, some of the technical reasons listed above.

2. Free upgrade: A large refactor & performance improvement is currently being reviewed to further improve this implementation, providing us with a "free lunch".

3. Avoiding tech debt: Seems like [1] is no longer going to be the case (at the time of writing) because Cosmos is too complex to adopt something anything other than IAVL (though that is the long-term goal given the discussion here), so instead, IAVL had to be forked and modified: feat: Support Adds in a Deep Subtree rollkit/iavl#8

References

[1] All the rough research notes on Trees & KV stores can be found here
[2] The WIP presentation (at the time of writing) is available here

Note: If you are an external contributor trying to access [1] or [2], reach out to the team on discord!