ADR-040 Implementation

[roysc]

We'd like to start a conversation on how to implement ADR-040, present an overview of our current plans, and resolve some design questions. Here we cover:

• Versioning and state-sync snapshots using BadgerDB (and RocksDB?) as backends
• Updates to LL-SMT and its MapStore
• How to decouple state commitment and storage concerns in KV stores

Interface for historical versions

The backend DB will need to expose an interface for accessing and viewing historical versions of records. The simplest way to do this may be to supply a new interface type representing a read-only DB, and a new method like DB.AtVersion(uint64) (ReadOnlyDB, error). It may also be convenient to provide a DB.GetAt([]byte, uint64) method to access a single record.

This can implemented like so:

• BadgerDB in managed mode allows arbitrary integers to be used as "timestamp" versions. DB.NewTransactionAt() is used to view DB state at a version.
• For RocksDB, a Checkpoint can be created for each commit in a path corresponding to the version integer, and then opened as a read-only copy of the DB.

ABCI state-sync snapshots

Approach

We will attempt to make all needed changes conform to the same interface used in the Snapshot/Restore methods implemented by rootmulti.Store. This is the only type that will need to be serialized for snapshots, hence the only type to implement the Snapshotter interface. Adapting this pattern for the new backends will mostly be a matter of defining the serialization units for export/import.

The most straightforward way to do this is to just define a new SnapshotItem message type encapsulating a KV-pair, and stream all entries from a store in this format. This will allow the SDK stores to be completely agnostic to the backend used, while the existing export/import procedure will remain mostly the same.

• Both new backends also provide native export (or "backup") features. These could potentially be used in implementing ABCI snapshots for some performance benefit, but this would force the boostrapping node to use the same backend for the same stores as every peer node, since the data would be in a backend-specific format. So, this option can probably be ruled out.

Interface

We can define new generic interface types to export and import encoded messages, and implement these for all relevant persistent stores. These will mimic the current export interface for IAVL, but deal directly with SnapshotItems (or another generic type). The existing logic can then be refactored easily.

type PortableStore interface {
    Export(uint64) (Exporter, error)
    Import(uint64) (Importer, error)
}

type Exporter interface {
    Next() (SnapshotItem, error)
    Close()
}

type Importer interface {
    Add(SnapshotItem)
    Commit() error
    Close()
}

Implementation

BadgerDB

As described above, he DB.NewTransactionAt method provides a view of the DB at a specific version. In "managed" mode, the version (timestamp) can be an arbitrary integer.

• CommitAt also allows restoring state at a past version, although we seem to have no use case for this as of yet.

RocksDB

RocksDB Snapshots are an ephemeral view of the DB at a specific point in time. This is enough to create a snapshot directly after a commit.

• If we want to support creation from a past block height, that can be implemented with persistent copy-on-write Checkpoints as described above.

Encoding

We define the following new protobuf message and add it as a subtype of SnapshotItem:

message SnapshotKVItem {
    bytes key = 1;
    bytes value = 2;
}

message SnapshotItem {
  oneof item {
    ...
    SnapshotKVItem kv = 3;
  }
}

The Exporter/Importer implementations for BadgerDB and RocksDB both stream instances of SnapshotKVItem. The IAVL handling code can also be wrapped so that the rootmulti code only has to deal with this generic interface.

SMT/MapStore updates

We will need to add some functionality to the LazyLedger SMT and the MapStore interface it uses, to expose needed features from the backing DB.

Batch support

If we want to implement efficient batched writes to the SMT, that could be supported in the following way. The tree will need to be able to read as well as write to the batch itself while building it, using something closer to a transaction object.

• RocksDB has a Write Batch With Index utility which allows this.
• BadgerDB's WriteBatch does not support Gets, but, as it is a relatively simple wrapper around a transaction, we could just use Txn.

These writable batch types would be wrapped in the MapStore interface. The SMT would need a new interface type to represent the batch (e.g. WriteBatch). This would wrap a derived SparseMerkleTree object using the transaction object as its MapStore. All normal SMT operations would then be available on the batch.

Versioning and snapshots

Creating state sync snapshots is not required for SMT data.

Versioning may not be needed either (?); however, if it is desired, it could be implemented with a MapStore.GetAt([]byte, uint64) method, which forwards to a DB.GetAt() method as described above.

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 no. 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 (no. 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 (no. 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 no. 1 above, the primary issue is not being able to wrap the underlying stores. With no. 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).

cc/ @robert-zaremba @marbar3778 @i-norden

[alexanderbez]

Thanks for creating this thread @roysc.

• Why does Tendermint need to be involved here? The interface should be defined in the SDK. Tendermint should only concern itself with the block storage which is separate from the application storage and interfaces.
• I would highly consider sticking with BadgerDB as that is what Tendermint will probably end up using very soon.
• We should use Badger's Tx as much as possible.
• The multi-store should be removed.

[i-norden]

Thanks for the feedback @alexanderbez!

Tendermint DB here refers to tm-db which at this time is not merged into cosmos-sdk but once it is that is the context in which we would be adjusting it.

Previously we had discussed supporting both BaderDS and RocksDB for ADR-040, do we want to shift focus solely on BaderDB?

Removing the multistore was not part of the scope originally discussed for ADR-040, it's not requisite to the decoupling and is a significant refactor affecting pieces of the SDK that ADR-040 otherwise has no concern for, so I think it potentially deserves its own scope/ADR rather than being tagged onto ADR-040.

[alexanderbez]

Just want to re-iterate, I do NOT think tm-db should continue to be supported and certainly not rolled into the SDK.

[i-norden]

Just want to re-iterate, I do NOT think tm-db should continue to be supported and certainly not rolled into the SDK.

My mistake, I think I see what you mean now. We are not proposing to merge tm-db into the SDK but rather a successor interface that will be used to support state commitment and storage using either BadgerDB or RocksDB. I'm not sure yet how we want to refer to it's successor, we have been calling it tm-dbv2 but that is obviously a misnomer since it will be inside and used by the SDK.

[aaronc]

Removing the multistore was not part of the scope originally discussed for ADR-040, it's not requisite to the decoupling and is a significant refactor affecting pieces of the SDK that ADR-040 otherwise has no concern for, so I think it potentially deserves its own scope/ADR rather than being tagged onto ADR-040.

I believe removing the multi-store affects the proof format as I have outlined elsewhere. Also, we are talking about new versioning mechanisms with ADR 040 which as far as I understand it would need to be coordinated with the multi-store across separate atomic stores. Anyway, maybe there's a sequential way to add SMT first and then remove the multi-store. But the multi-store (i.e. separate atomic stores) needs to go and it all at once.

[roysc]

Thanks @alexanderbez and @i-norden - I removed the references to "Tendermint DB"/tm-db to avoid confusion.

Badger will definitely be supported, and the Transaction is a fundamental part of its interface, so it will definitely be widely used. As for the multi-store, as Ian said we aren't planning to scope that into this work, but will factor its future deprecation into the plan.

[robert-zaremba]

Interface for historical versions

This section is correct - it's exactly what we were testing. See here for example: #8297 (comment), and other threads and tests in this discussion.

[aaronc]

I have not seen any justification nor use cases for why we should be storing SS-B2. In what scenarios would one have hash(key,value) but not key and need some mechanism to retrieve the key? That seems unlikely and we should identify a need before including it.

[roysc]

I can't speak to the use case, but it does seem like something that could be easily added later if deemed useful.

[aaronc]

I have expressed this elsewhere, but I believe we should allow direct access to both SC and SS for modules that want to use a higher level wrapper layer (such as that described in #9156) which would have a custom SC format and not map secondary indexes in SS to SC.

For existing modules, I think we should expose a KVStore wrapper with the same StoreKey mechanism that we do now which wraps both SS and SC so that backwards compatibility is easier.

[roysc]

Sounds good, we will aim for this, it should minimize the friction of moving to the new store scheme while not hiding too much from users.

[robert-zaremba]

Right. The ADR doesn't propose SDK API change for using the store. By default, modules will see only one store, which will compose both SS and SC.
The direct access is a low level API.

[ethanfrey]

Correct me if I am wrong, but currently, we only expose access to SS operations to the modules.
The SC operations are handled by some core SDK logic to generate proofs on queries, but never exposed to the modules. (See the KVStore interface).

Now these will be decoupled, I would propose only sharing the SS store to the modules, rather than providing SS + SC and then passing it through a wrapper that only allows SS access. This could allow future sdk-internal optimizations that will not affect the module interface.

[roysc]

According to the ADR, the SC layer will not need historical versions, and the SMT will be pruned of orphaned nodes, leaving only the current version of the tree. However, if a query of past state requests a proof, it seems that we will need the old version to generate the proof. Am I misunderstanding @robert-zaremba?

[ethanfrey]

As for accessing old versions: we remove the updated nodes immediately, but they will be removed from DB only when we remove the DB snapshot (version). So it's safe to remove tree nodes even if we want to have historical proofs. We just need to use past version. Here is how to do it with Badger; #8297 (comment). RocksDB was presented in the tests.

I think making use of DB-internal CoW semantics is a good idea. I do believe much of this will be cleared on restart, but that shouldn't be a critical issue (correct me if I am wrong, IBC team - will you even need a pre-upgrade proof after an x/upgrade restart?)

However, replicating current sdk functionality would imply constantly using CoW snapshots for each of the last 1000 blocks, releasing 1 of them each time. I am not sure how efficiently Badger or RocksDB supports such a huge number of snapshots, and if they can properly cleanup if there are other outstanding snapshots. This depends a lot how the logic is implemented internally in each DB, and can and should be tested independent of the SMT implementation.

I would love to see a benchmark of performance of the DBs under batch write operations with eg. no snapshots, 10 snapshots, 100 snapshots, 1000 snapshots.

[cwgoes]

IBC does currently rely on proofs for past heights - a consensus state for a particular height is verified by the on-chain light client and stored; relayers then will need to query proofs for that height since it is the state which the client has verified. This is not unique to IBC: light clients in general need to do this. Of course, they can update to the latest consensus state, but we only want to require that of light clients when they actually need updated state (e.g. a packet since received), not just because we can no longer create proofs for some other reason, that would be a considerable efficiency loss.

For this reason, I would encourage this ADR to retain historical proof creation ability for past heights. It may be optional, but the restrictions imposed by not supporting it (e.g. breaking IBC relayers) should be clearly noted.

[aaronc]

Yes please let’s use the same DB instance for SS and SC

[roysc]

I do think trying to use separate DB instances for SS and SC complicates things some and the benefit is unclear. Both instance versions will need to be kept in sync and similarly configured. That said, if there is a proven performance benefit it may be worth it. It would be useful to see an IBC use case and benchmarks to understand this better.

[ethanfrey]

It would be useful to see an IBC use case and benchmarks to understand this bette

Do we have any realistic benchmarks for the sdk and iavl? With real-world database sizes (think Cosmos Hub or Terra) and using on-disk (leveldb?) storage rather than memdb.

It would be good to have such real-world benchmarks before working on optimizing paths that add extra complexity

[robert-zaremba]

@roysc , I created a PR to update ADR-40 with regards to Multistore and database setup for SS and SC. I couldn't add you as a reviewer but it will be great for have your review as well: #9355

[roysc]

To support this implementation, I've drafted a new interface for the backing key-value DB. Please see the new synopsis here (for simplicity this is currently within the tm-db repo, though we understand that the code will eventually be part of cosmos-sdk). In summary, this refactors the current DB and Batch into types that map closely to the BadgerDB interface:

• A DB type representing a database connection
  • This exposes all methods for version access and control (current version, save version, etc.)
  • Transaction objects are branched off of this object
• A DBReader for read-only transactions
  • This can be acquired for past and current DB versions
• A DBWriter for read-write transactions
  • Only available on the current version
  • Must be flushed to DB

There are some design questions still to resolve; chiefly, how should DB.SaveVersion() behave when there are unfinished, possibly concurrent transactions? Some options:

• Discard all pending transactions (or, all read-write transactions)
• Wait for them to be discarded, maybe with a configurable timeout
• Raise an error

I arrived at this design after reviewing tendermint/tendermint#6425 and tendermint/tendermint#6032, and it may rightly belong to another ADR, but as this work depends on it I wanted to propose it here and get any feedback before moving forward.

[ethanfrey]

There are some design questions still to resolve; chiefly, how should DB.SaveVersion() behave when there are unfinished, possibly concurrent transactions? Some options:

What about the DB only allowing one DBWriter at a time? And if the SDK wishes to use some concurrency, it can handle it by wrapping multiple DBWriter on top of the one from the DB and implement custom logic to merge it.

Unless we want to implement a full-blown database versioning system and transaction isolation levels, it makes most sense to not do this and just let the sdk implement the very small subset needed for a concrete use case (only supporting just those cases)

[roysc]

What about the DB only allowing one DBWriter at a time?

We could do this, but the DB still needs a policy on what to do when the single writer hasn't finished. Unless we move the "save version" logic into the writer's Commit method.

Badger is already capable of running concurrent transactions and will handle merge conflicts on flush, so we will want to take advantage of that. It also provides versioning, so all we need in terms of additional abstractions is a way to specify the boundaries of a "saved" version. Handling this could also be pushed up a layer in the SDK, but this interface will ultimately be part of the SDK anyway.

[robert-zaremba]

@roysc , @i-norden Let's have a sync about the ADR-40 implementation. Do you need anything from the SDK team? In particular, I would like to check on and consult with you:

• adr-40: use prefix store instead of multistore docs: adr-40: reduce multistore and make it atomic #9355
• docs(adr): update ADR-40 by adding low level access to SC docs(adr): update ADR-40 by adding low level access to SC #9451
• Incorporate tm-db Incorporate tm-db #9092
  • feat: ADR 040: New DB interface #9573

[robert-zaremba]

thank you @AdityaSripal for an excellent response in the #8297 (reply in thread) thread.

TL;DR - @roysc multistore removal is not blocked by IBC.

[roysc]

Sounds good. Any ETA on the final decision & new design? The remaining features should only take a few weeks to implement once that's established.

[okwme]

I think that the TL;DR is more complicated. @AdityaSripal wrote up more details here: cosmos/ibc-go#256

It seems that it would require at least a couple months of work from the IBC team who is atm pretty under-resourced. I've been trying to collect information about why it's important to replace the multistore but it's still unclear to me which users are asking for the change. If it's just a nice to have I think it's hard to justify.

My understanding of the race condition issue that @robert-zaremba mentioned earlier was an IAVL issue and not directly related to multistore.

@roysc stated that “It seems there is a consensus from the team that it's desired?” but I like to better understand if that's the case.

I saw @alexanderbez write last May that multi-store should be removed and in the discussion he summarized that "Smells like over-engineering to me and we're paying the cost for it.". I'd love to know where that cost is being paid and hear about in comprison to other priorities how does the cost compare?

@cwgoes asked a good question:

What was the original design rationale for the multi-store? Presumably there was one, e.g. allowing different store types to be mounted to sub-paths. Is anyone using that, or is there any reason we might want to? If not, I agree that the abstraction is superfluous and adds unnecessary friction - although we need to be careful not to break IBC, as discussed above.

@ethanfrey provided a good summary of the system as "allows multiple backing stores in one theoretical storage interface and hide the mapping from the modules." as well as some good background and context that Jae wanted it for Ethermint (@fedekunze should be asked if this is still relevant). It may also be good for "transient stores". Ethan also stated being in "favor of on Merkle Tree using key prefixes to separate different modules, not one merkle tree with the root hashes of dozens of sub-merkle trees, which just makes it all much more complex to reason about. And many assumptions break as soon as you add non-iavl data in there"

These all seem like valid concerns and desires, however I'm not convinced that Interchain Accounts, Interchain Staking, or IBC Fees should be delayed 2+ months as well as years of complicated backwards compatibility work to ensure the changes propagate across the ecosystem smoothly. Especially when there's a version of ADR-40 that doesn't include replacing the multistore with minimal disruption and the majority of the benefits outlined in the proposal. As @zmanian stated "The Hub would like to switch from IAVL to SMT before then but if the only version of SMT doesn't contain the multistore then the Hub has to wait."

Would love to hear more opinions with regard to prioritization. Is this in fact a "nice to have" or more critical to the success of users of the Cosmos SDK, IBC and the Cosmos Hub?

[ethanfrey]

Thanks for this write up @okwme

It seems that it would require at least a couple months of work from the IBC team who is atm pretty under-resourced. I've been trying to collect information about why it's important to replace the multistore but it's still unclear to me which users are asking for the change. If it's just a nice to have I think it's hard to justify.

While I generally support removing the MultiStore interface and simplifying storage, I also feel it is just a "nice to have" and the main correctness issue is only when there are different backing stores (not all one shared leveldb), which doesn't show up in the standard use case.

I would have loved to have seen this replace before ibc rolled out, and that was my concern about all the multi paths and hashes when I was building out ics23 support 2 years ago. It works, and while it does have a smell, it definitely does not justify any delays to other work.

I would love to see SMT working with the multistore, to have a non-IBC breaking change with the performance improvements. SMT work should just focus on performance. MultiStore changes are orthogonal to that.

And ICS27, fees, staking, etc should all work with existing IBC connections / chains. Either still using IAVL/MultiStore, or using SMT/MultiStore. The "remove MultiStore" migration will likely take 1+ year as @zmanian commented (in Discord) and does not deserve to block any other projects.

[robert-zaremba]

We don't want to be significantly delayed by IBC updates and we don't want to significantly delay IBC.

We are discussing also a solution, where everything, except the IBC will be in a single, "general" store: cosmos/ibc-go#256 (comment)

[roysc]

@i-norden and I want to propose storing just hash(value), rather than hash(key, value) in the SC store. Doing it in this fashion:

• The SMT leaf node will contain: hash(key) || hash(value)
• In the inverted index we store hash(key) => key, instead of hash(key, value) => key
  • This maintains the uniqueness of keys for inverse lookup
  • This index can still be used from the context of iterating the trie without knowing the raw key, since the trie node has the hash(key) (path) stored in it

One motivation is that this would work much better with IPLD, as it requires storing just the proper content hash for a value. It would also avoid ambiguity in the case where a stored key + value is identical to another (e.g. "a" => "bc" and "ab" => "c").

I'll open a PR for this as well. (edit: PR #9680)

[robert-zaremba]

@roysc , ah, I thought the SMT we concatenate bytes before hashing, rather than concatenate hashes. So what you propose makes sense.

But we aren't sure what this means and how it impacts the decision to combine the key and value.

My intention was to follow the SMT behavior.

[i-norden]

@robert-zaremba yeah prefix || hash(key) || hash(v) is the leaf node. But the way the SMT is currently implemented we need to provide- from the SDK level- a v == hash(key || value) so that when we Get from the SMT we are retrieving hash(key || value) which is what we need as the key in the inverse index. So the content of a leaf node in the SMT, in current practice, is prefix || hash(key) || hash(hash(key, value)).

Related, this hashing of the v that is being performed is currently redundant. The SMT hashes the provided v, stores the hash in the SMT, and stores the raw v provided to it in a separate bucket it manages internally. It as if it is managing a state store bucket of its own.

To be explicit here: v == value provided to the SMT, value == the value actually stored in the separate state store.

[robert-zaremba]

yeah, let's keep prefix || hash(key) || hash(v) in the leaf.

[adlerjohn]

The value of a leaf node is computed as

node.v = h(0x00, k, h(serialize(d)))

aka

prefix || key || hash(value)

See: https://github.com/celestiaorg/celestia-specs/blob/ec98170398dfc6394423ee79b00b71038879e211/src/specs/data_structures.md#sparse-merkle-tree

Of note is that the SMT accepts a key (more specifically, a path), and does not hash it when computing the leaf node value. The current implementation hashes the key, but this will be changed with celestiaorg/smt#40.

[ethanfrey]

As Robert asked a lot about the design in DMs, I will capture it here for others who are interested.

The leaf hash algorithm is documented in the proto file (which is the living spec):

output = hash(prefix || length(hkey) || hkey || length(hvalue) || hvalue)

length prefixing and prehashes are all optional, and can be no-ops.

Test cases show how you can define sha256(key || value) as the leaf hash function. But I do not recommend that as you can easily make preimage collisions. Both key and value should either be prehashed, or be length prefixed (or both).

If you are designing something, you have lots of options that can still fit in the spec.

You can define prefix || hash(key) || hash(v) with ics23 (just define the outer hash as a no-op). But you cannot define prefix || hash(key) || hash(hash(key, value)). It seems there is no reason for such a complex structure in practice.

[roysc]

The work is being pushed in a sequence of PRs, most of which are ready for review. The dependency looks something like:

• feat: ADR 040: New DB interface #9573 - introduces a new KV DB interface which supports versioning. This should be merged first as other code depends on it.
• feat: ADR 040: Implement in-memory DB backend #9952 - in-memory DB and test cases. This should be merged next, as it is used in test cases for the store and contains utils used by other implementations.
  • feat: ADR-040: Implement BadgerDB backend #9848 - Badger KVDB
  • feat: ADR-040: Implement RocksDB backend #9851 - RocksDB KVDB
  • feat: ADR-040: Implement KV Store with decoupled storage and SMT #9892 - KV Store using the above interface
    • Future PR to refactor the Base app to use a prefix-based root store built on the above, whether by replacing the Multistore or using it as an alternative.
      • Future PR to implement ABCI state snapshots
• Future PR to implement ICS-23 format SMT proofs

[ethanfrey]

Nice work