Epic 3: Replace IAVL with SMT state commitment

[i-norden]

In #1 we introduce the new SS and write (commit) to both IAVL and the SS, at this stage we remove the IAVL KVStore and replace with the SMT KVStore as the new, decoupled, state commitment (SC).

For state commitment we store only the hash(key, value) as the value in the leafs of the SMT. Thereby, the leaf nodes are of the form: 0x01 || sha256(key) || sha256(key, value), where || is byte concatenation.

• Adjust reads to go through datastore directly
• Writes to both SMT and datastore
• Only the hash(key => value) is stored in SMT, buckets introduced in Epic 2: Replace tm-db database interface with new cosmos-db #2 remain for state storage
• Remove query lock, we will query KVStores in parallel
• Update MapStore to be backed by new tm-dbv2

[i-norden]

Decoupling SC and SS KVStores

In the state machine, we need to settle on the pattern used to decouple the state commitment and storage concerns. From the ADR-040 proposal, the store buckets consist of:

1. SC: key -> hash(key, value): for state commitment we store only the hash(key, value) as the value in the leafs of the state commitment tree.
2. SS-B1: key → value: the principal object storage, used by a state machine, behind the SDK KVStore interface: provides direct access by key and allows prefix iteration (KV DB backend must support it).
3. SS-B2: hash(key, value) → key: an index needed to extract a value (through: B2 -> B1) having a only a Merkle Path.

A few options for how implement this are outlined below. The best course of action will depend on the order of priorities.

If we want to prioritize SDK user experience, we should wrap this logic in a single KVStore interface which exposes storage data as KV pairs and only exposes SC data as Merkle root hashes (option #1 below). This only makes sense if users are not expected to need to access or iterate over hashes of individual records or the inverted index mappings. (This is the approach taken in the open SMT store PR.)

If the higher priority is to provide SDK users full visibility and control of all component KV buckets, these should be left as loosely coupled as possible (#2). The SC, SS, and index buckets will only be used in tandem at the multi-store level. The multi-store will then expose these as separate CommitKVStores, so that the user is still able to unambiguously access all underlying data, including data and hashed records, and wrap each store in a tracekv.Store, gaskv.Store or another layer. However, if the multi-store is planned to be removed in the future, users will then be responsible for managing the new state machine semantics unless a new wrapper type is created.

We suggest a third option if all of the above are considered high priorities: introduce a new interface which expands on KVStore (#3). Ideally, this will make as much as possible of the underlying store structure available for tooling, while still presenting an SDK interface that is friendly to users.

1. Write a unified KVStore that generates bucket entries and directs writes/reads to both SS and SC.

Pros:

1. Fewer changes required at the multistore level and above to support the decoupling
2. Unified store interface that can map to a StoreKey
   • Multistore exposes a single CommitKVStore for each substore
   • Presents a single Merklized store interface for SDK users

Cons:

1. Can't individually wrap (gas meter, prefix, listen, trace) each of the underlying stores
2. Set and Delete have side effects, rather than simply setting or deleting the provide KV pair they generate two other KV pairs to set/delete
3. Return value for some methods is ambiguous, e.g. which of the buckets is the returned iterator iterating over

2. Maintain separate KVStores for SC and SS

Pros:

1. Can individually wrap (gas meter/listen to/trace) each bucket
2. Set and Delete operations remain pure
3. No method result ambiguity

Cons:

1. Can't map to/differentiate differentiate the KVStores with a single StoreKey
   • Multistore needs a way to expose each decoupled component of its substores
2. We need logic at a higher level (i.e. multistore) for generating entries and directing reads/writes to the separate SC and SS KVStores.
   • Will require more changes at the multistore level and above to accommodate
3. There is talk about deprecating the multistore - if the multistore is deprecated, SDK users would be responsible for managing each store

3. Create a new KVStore subtype

With option #1 above, the primary issue is not being able to wrap the underlying stores. With #2, the primary issue is that we disrupt the current 1-to-1 mapping of StoreKey to a KVStore. We can avoid both by defining a new interface and some supporting types:

Pros:

• Unified KVStore interface that maintains 1-to-1 mapping with StoreKey
• Enables wrapping of underlying KVStores
• More explicity types the new behavior of the unified store

Cons:

• Requires refactoring of wrapping code in multistore and above
• New StoreKind enum
• Possibly confusing to module developers?

Example synopsis:

// Wrapper wraps the receiver's underlying KVStores of the specified kind with the provided KVStore
type Wrapper interface {
    Wrap(k KVStoreKind, w KVStore)
}

// StateStore is a KVStore that directs reads/write from/to an underlying state commitment, state storage, and state index KVStores
type StateStore interface {
    KVStore
    Wrapper
}

// Store is an example StateStore, each bucket is a KVStore that can be independently wrapped
type Store struct {
    // Direct KV mapping (SS)
    ss types.KVStore
    // Inverted index of SC values to SS keys
    ii types.KVStore
    // State commitments layer, LL-SMT KVStore
    sc types.CommitKVStore
}

// KVStoreKind enum used to differentiate between the different kinds KVStores underlying a StateStore
// StoreKey remains mapped 1-to-1 with a StateStore, these distinguish between the different substores.
type KVStoreKind int

const (
    StateCommitment KVStoreKind = iota
    StateStorage
    InvertedIndex
)

For all purposes other than wrapping, we can use the StateStore as any other KVStore. Methods that need to wrap an underlying store after loading it into the StateStore will need to use the new methods (e.g. MultiStore.GetKVStore when tracing or listening is enabled).

[i-norden]

Closed in #12

[i-norden]

Falls under the new Epic 2 (this is satisfied in the draft PR).

We aren't actually replacing until the Multistore is replaced, but the SMT will be fully introduced.

[i-norden]

Closing, see cosmos#9816 and child issues, tracking on zenhub