​
变更记录

  • 2020-01-15：草案

​
状态

草案，尚未实现

​
摘要

稀疏默克尔树（Sparse Merkle Tree， SMT）是默克尔树的一种，具备多种存储和性能优化。本文 ADR 定义了状态承诺与数据存储的分离，以及 Cosmos SDK 从 IAVL 迁移到 SMT 的方案。

​
背景

当前，Cosmos SDK 同时使用 IAVL 来处理状态承诺和数据存储。 IAVL 在 Cosmos 生态中实际上已经成为一个缺乏延续维护的项目，并且已被证明不是高效的状态承诺数据结构。 在当前设计中，IAVL 既用于数据存储，也作为状态承诺的默克尔树使用。IAVL 本意是作为一个独立的默克尔化键值数据库，不过它使用 KV DB 引擎来存储所有树节点。因此，KV DB 中的每个节点都以单独记录的形式存储。这会导致许多低效和问题：
  • 每次对象查询都需要从根开始遍历整棵树。对同一对象的后续查询会在 Cosmos SDK 层进行缓存。
  • 每次边遍历都需要一次 DB 查询。
  • 创建快照的开销很大。导出不到 100 MB 的状态大约需要 30 秒（截至 2020 年 3 月）。
  • IAVL 中的更新可能触发树重组，并可能导致 O(log(n)) 次哈希重计算，这会成为 CPU 瓶颈。
  • 节点结构本身开销较高，它不仅包含标准树节点元素（key、value、left 和 right element），还包含额外元数据，如 height、version（Cosmos SDK 实际并不需要）。整个节点会被哈希，该哈希再被用作底层数据库中的键，参见 ref。
此外，IAVL 项目缺乏支持和维护者，而我们已经看到了更好且更成熟的替代方案。因此，我们不再继续优化 IAVL，而是考察其他同时适用于存储和状态承诺的方案。

​
决策

我们提议将共识所需的状态承诺（SC）与状态机所需的状态存储（SS）这两个关注点分离。最终，我们将用 Celestia 的 SMT 替换 IAVL。Celestia SMT 基于 Diem（称为 jellyfish）的设计 \[*]，它通过将仅包含默认值的子树替换为单个节点来实现面向计算优化的 SMT（Ethereum2 也采用了相同方法），并实现了紧凑证明。 这里给出的存储模型不涉及数据结构和序列化。它是一个键值数据库，其中键和值都是二进制数据。存储使用者负责数据序列化。

​
将状态承诺与存储解耦

将存储与承诺（由 SMT 实现）分离后，可以根据不同组件的使用方式和访问模式分别进行优化。 SC（SMT）用于对数据进行承诺并计算默克尔证明。SS 用于直接访问数据。为避免冲突，SS 和 SC 将使用独立的存储命名空间（它们底层也可以使用同一个数据库）。SS 将直接存储每条记录（即将 (key, value) 映射为 key → value）。 SMT 是一种默克尔树结构：我们不会直接存储键。对于每个 (key, value) 对，使用 hash(key) 作为叶子路径（对键做哈希以便将叶子均匀分布到树中），使用 hash(value) 作为叶子内容。树结构的更详细说明见下文。 对于数据访问，我们提议增加 2 个 KV bucket（实现为键值对的命名空间，有时称为 column family）：
  1. B1：key → value：主对象存储，由状态机通过 Cosmos SDK 的 KVStore 接口使用；它提供按键直接访问，并允许前缀迭代（KV DB 后端必须支持）。
  2. B2：hash(key) → key：用于根据 SMT 路径反查 key 的反向索引。SMT 内部会将 (key, value) 存储为 prefix || hash(key) || hash(value)。因此，我们可以通过组合 hash(key) → B2 → B1 获取对象值。
  3. 如有需要，我们还可以使用更多 bucket 来优化应用使用方式。
我们提议对 SS 和 SC 都使用 KV 数据库。存储接口将允许 SS 和 SC 共享同一个物理 DB 后端，也允许使用两个独立的 DB。后者可以将 SS 和 SC 分离到不同的硬件单元中，从而支持更复杂的部署场景并提升整体性能：可以使用不同后端（如 RocksDB 和 Badger），也可以分别调优底层 DB 配置。

​
要求

状态存储要求：
  • 范围查询
  • 快速的 (key, value) 访问
  • 创建快照
  • 历史版本管理
  • 剪枝（垃圾回收）
状态承诺要求：
  • 快速更新
  • 树路径应尽可能短
  • 使用 ICS-23 标准查询历史承诺证明
  • 剪枝（垃圾回收）

​
用于状态承诺的 SMT

稀疏默克尔树基于这样一个思想：构造一棵大小难以处理的完整默克尔树。这里的假设是，由于树的规模难以处理，相对于整棵树的大小而言，只会有少量叶节点包含有效数据块，因此这是一棵稀疏树。 完整规范见 Celestia。简要总结如下：
  • SMT 由一棵二叉默克尔树组成，构造方式与 Certificate Transparency (RFC-6962) 中描述的相同，但哈希函数使用 FIPS 180-4 中定义的 SHA-2-256。
  • 叶节点和内部节点的哈希方式不同：叶节点前会加上 1 字节的 0x00，内部节点前会加上 0x01。
  • 为空叶节点指定默认值。
  • 虽然上述规则足以预计算作为空子树根节点的中间节点值，但还可以进一步简化：将该默认值扩展到所有作为空子树根的节点。默认值使用 32 字节的零值。该规则优先于上一条规则。
  • 若某个内部节点所对应子树中恰好只包含一个非空叶节点，则该内部节点会被该叶子的叶节点替换。

​
用于存储同步和状态版本管理的快照

下文中，简单说的 snapshot 指的是数据库快照机制，而不是 ABCI snapshot sync。后者将被称为 snapshot sync（它会直接使用下文描述的 DB 快照）。 数据库快照是在某一时刻或某个事务上的 DB 状态视图。它不是数据库的完整副本（那样会过大）。通常，快照机制基于 copy on write，可以高效地提供某一阶段的 DB 状态。 某些 DB 引擎支持快照。因此，我们提议复用这一能力来实现状态同步和版本管理（如下所述）。我们将支持的 DB 引擎限制为那些能够高效实现快照的引擎。本文最后一节会讨论评估过的 DB。 Stargate 的核心特性之一是 /snapshot 包提供的 snapshot sync。它提供了一种无需从创世块开始重放所有交易、即可无信任同步区块链的方式。该特性已在 Cosmos SDK 中实现，并需要存储层支持。目前 IAVL 是唯一受支持的后端。它的工作方式是向客户端流式传输某一版本下 SS 的快照以及对应的 header chain。 每个 EndBlocker 都会创建一个新的数据库快照，并用区块高度标识。root store 会跟踪可用快照，以便提供某一特定版本的 SS。root store 实现了下文描述的 RootStore 接口。实质上，RootStore 封装了一个 Committer 接口。Committer 包含 Commit、SetPruning、GetPruning 函数，这些函数将用于创建和删除快照。rootStore.Commit 函数会在每次调用时创建一个新快照并递增版本号，同时检查是否需要删除旧版本。我们需要更新 SMT 接口以实现 Committer 接口。 注意：每个区块必须且只能调用一次 Commit。否则版本号和区块高度可能会失去同步。 注意：对于 Cosmos SDK 存储，我们可以考虑将该接口拆分为 Committer 和 PruningCommitter，只有 multiroot 需要实现 PruningCommitter（cache 和 prefix store 不需要剪枝）。 用于 abci.RequestQuery 和状态同步快照的历史版本数量属于节点配置，而不是链配置（链配置由区块链共识隐含决定）。配置应允许指定保留多少过去区块，以及按某个间隔保留过去区块的快照数量（例如：保留最近 100 个区块，以及过去 2000 个区块中每 100 个区块保留一个快照）。归档节点可以保留所有历史版本。 旧快照的剪枝实际上由数据库完成。每当我们更新 SC 中的一条记录时，SMT 不会更新原有节点，而是会在更新路径上创建新节点，同时不删除旧节点。由于我们会在每个区块做快照，因此需要调整这一机制，使其立即从数据库中删除孤儿节点。这是安全的，因为快照会跟踪这些记录，并在访问历史版本时使其可用。 为了管理活跃快照，我们可以使用 DB 的 max number of snapshots 选项（如果有），或者在 EndBlocker 中删除 DB 快照。后一种方式也可以高效实现，只需用区块高度标识快照，并调用存储函数删除旧版本。

​
访问旧状态版本

功能要求之一是访问旧状态。这通过 abci.RequestQuery 结构完成。版本由区块高度指定（因此我们是在区块高度 H 查询键 K 对应的对象）。abci.RequestQuery 支持的旧版本数量可配置。访问旧状态通过使用现有快照来实现。 仅当设置 prove=true 参数时，abci.RequestQuery 才需要 SC 的旧状态。只有当 SC 和 SS 都存在所请求版本的快照时，SMT 默克尔证明才必须包含在 abci.ResponseQuery 中。 此外，Cosmos SDK 也可以提供一种直接访问历史状态的方式。不过状态机不应这样做，因为快照数量是可配置的，这会导致非确定性执行。 关于我们评估的数据库，我们已经针对用于查询旧状态的版本管理和快照机制进行了积极的验证。

​
状态证明

对于存储在状态存储（SS）中的任意对象，在 SC 中都有对应对象。由键 K 标识的对象 V 的证明，是 SC 中的一条分支，其中路径对应于键 hash(K)，叶子为 hash(K, V)。

​
回滚

我们需要能够处理交易，并在交易失败时回滚状态更新。可以按如下方式实现：在交易处理期间，我们将所有状态变更请求（写操作）保存在 CacheWrapper 抽象中（当前就是这样做的）。当我们完成区块处理后，在 Endblocker 中提交 root store；此时，所有变更都会写入 SMT 和 SS，并创建一个快照。

​
在不保存对象的情况下对其进行承诺

我们识别出一些用例：模块需要保存某个对象的承诺，但不存储对象本身。有时客户端会接收到复杂对象，而如果不了解存储布局，他们就无法证明该对象的正确性。对于这些用例，不直接存储对象、而只对其进行承诺会更容易。

​
重构 MultiStore

Stargate 的 /store 实现（store/v1）在 SDK store 的构造中增加了一个额外层级，即 MultiStore 结构。multistore 的存在是为了支持 Cosmos SDK 的模块化：每个模块都使用自己的 IAVL 实例，但在当前实现中，所有实例共享同一个数据库。不过，这恰恰说明该实现并没有提供真正的模块化。相反，它会导致与竞态条件和 DB 原子提交相关的问题（见：#6370 以及讨论）。 我们提议在 SDK 中削弱 multistore 这一概念，并在 RootStore 对象中使用单个 SC 和 SS 实例。为避免混淆，我们应将 MultiStore 接口重命名为 RootStore。RootStore 将具有如下接口；与 tracing 和 listeners 配置相关的方法为简洁起见被省略。 
// Used where read-only access to versions is needed.
type BasicRootStore interface {
    Store
    GetKVStore(StoreKey)

KVStore
    CacheRootStore()

CacheRootStore
}

// Used as the main app state, replacing CommitMultiStore.
type CommitRootStore interface {
    BasicRootStore
    Committer
    Snapshotter

    GetVersion(uint64) (BasicRootStore, error)

SetInitialVersion(uint64)

error

    ... // Trace and Listen methods
}

// Replaces CacheMultiStore for branched state.
type CacheRootStore interface {
    BasicRootStore
    Write()

    ... // Trace and Listen methods
}

// Example of constructor parameters for the concrete type.
type RootStoreConfig struct {
    Upgrades        *StoreUpgrades
    InitialVersion  uint64

    ReservePrefix(StoreKey, StoreType)
}
与 MultiStore 不同，RootStore 不允许动态挂载子存储，也不为单个子存储提供任意的底层 DB。 注意：模块将能够使用特殊承诺以及它们自己的 DB。例如：某个使用 ZK 证明来表示状态的模块，可以将这个证明存储并提交到 RootStore 中（通常作为单条记录），并私下管理专用存储，或通过 SC 的底层接口进行管理。

​
兼容性支持

为了让用户更容易过渡到这个新接口，我们可以创建一个 shim，它包装 CommitMultiStore，但提供 CommitRootStore 接口，并暴露用于安全创建和访问底层 CommitMultiStore 的函数。 新的 RootStore 及其配套类型可以在 store/v2alpha1 包中实现，以避免破坏现有代码。

​
Merkle 证明与 IBC

当前，IBC（v1.0）的 Merkle 证明路径由两个元素组成（["<store-key>", "<record-key>"]），其中每个键都对应一个单独的证明。每个证明都会按照各自的 ICS-23 规范 进行验证，每一步的结果哈希都会作为下一步的已承诺值，直到得到根承诺哈希。 "<record-key>" 证明的根哈希会与 "<store-key>" 一起哈希，以针对 App Hash 进行验证。 这与 RootStore 不兼容，因为它在单一 Merkle 树结构中存储所有记录，不会分别为 store-key 和 record-key 生成独立证明。理想情况下，证明中的 store-key 部分应该可以直接省略，并更新为使用 "no-op" 规范，这样只使用 record-key 即可。然而，由于 IBC 验证代码硬编码了 "ibc" 前缀，并将其作为证明路径中的独立元素应用到 SDK 证明上，因此如果不进行破坏性变更，这一点无法实现。打破这一行为会严重影响已经广泛采用 IBC 模块的 Cosmos 生态。要求各条链同步升级 IBC 模块既耗时，也很难落地。 作为变通方案，RootStore 将不得不使用两棵独立的 SMT（它们可以使用同一个底层 DB）：一棵用于 IBC 状态，另一棵用于其他所有内容。一个引用这两棵 SMT 的简单 Merkle map 将充当 Merkle Tree，以生成最终的 App hash。Merkle map 不会存储在 DB 中，而是在运行时构造。IBC 子存储键必须是 "ibc"。 该变通方案仍然可以保证原子同步：提议的 DB 后端 支持原子事务和高效回滚，这些能力将在提交阶段使用。 上述变通方案可以一直使用，直到 IBC 模块完全升级为支持单元素承诺证明。

​
优化：压缩模块键前缀

我们考虑通过建立从模块键到整数的映射，并使用 varint 编码对该整数进行序列化，来压缩前缀键。Varint 编码可以确保不同的值不会拥有共同的字节前缀。对于 Merkle 证明，我们不能使用前缀压缩，因此它应只应用于 SS 键。此外，前缀压缩应仅应用于模块命名空间。更准确地说：
  • 每个模块都有自己的命名空间；
  • 在访问模块命名空间时，我们创建一个带有内嵌前缀的 KVStore；
  • 只有在访问和管理 SS 时，这个前缀才会被压缩。
我们需要确保这些编码不会变化。我们可以将映射固定在一个静态变量中（由应用提供），或者固定在 SS 状态中的某个特殊键下。 TODO：需要就键压缩作出决定。

​
优化：SS 键压缩

某些对象可能会使用包含 Protobuf 消息类型的键进行保存。这类键很长。如果我们能够将 Protobuf 消息类型映射为 varint，就可以节省大量空间。 TODO：完成这一项，或将其移到另一份 ADR。

​
迁移

使用新的 store 将需要迁移。这里提出两种迁移方式：
  1. 导出创世状态，这会重置区块链历史。
  2. 原地迁移：我们可以复用 UpgradeKeeper.SetUpgradeHandler 来提供迁移逻辑：
app.UpgradeKeeper.SetUpgradeHandler("adr-40", func(ctx sdk.Context, plan upgradetypes.Plan, vm module.VersionMap) (module.VersionMap, error) {
    storev2.Migrate(iavlstore, v2.store)

    // RunMigrations returns the VersionMap
    // with the updated module ConsensusVersions
    return app.mm.RunMigrations(ctx, vm)
})
Migrate 函数会从 store/v1 的 DB 中读取所有条目，并将其保存到 AD-40 的组合 KV store 中。 不应使用缓存层，并且该操作必须以一次 Commit 调用结束。 向 SC（SMT）组件插入记录是瓶颈。不幸的是，SMT 不支持批量事务。 在 SC 层增加批量事务被视为主版本发布后的一个特性。

​
影响

​
向后兼容性

这个 ADR 不会引入 Cosmos SDK 层面的 API 变更。 我们更改了状态机的存储布局，因此需要一次存储硬分叉和网络升级才能纳入这些变更。SMT 提供了 Merkle 证明功能，但它与 ICS23 不兼容。因此，需要更新证明以兼容 ICS23。

​
正面

  • 将状态与状态承诺解耦，为进一步优化和更好的存储模式带来了更好的工程机会。
  • 性能提升。
  • 加入基于 SMT 的阵营。相较 IAVL，它拥有更广泛且经验证的采用。选择 SMT 的项目示例包括：Ethereum2、Diem (Libra)、Trillan、Tezos、Celestia。
  • 移除 Multistore 修复了当前 MultiStore 设计中的一个长期问题。
  • 简化了 Merkle 证明：除 IBC 外，所有模块的 Merkle 证明都只需一次路径遍历。

​
负面

  • 存储迁移
  • LL SMT 不支持裁剪（pruning）——我们需要添加并测试这一功能。
  • SS 键会有一个键前缀的额外开销。这不会影响 SC，因为 SC 中的所有键大小都相同（它们都经过哈希）。

​
中性

  • 弃用 IAVL，而这正是 Cosmos 白皮书的核心提案之一。

​
备选设计

大多数备选设计都已在先前关于状态承诺与存储的报告中评估过。 Ethereum research 发布了 Verkle Trie——其思想是将多项式承诺与 Merkle 树结合，以降低树高。这个概念很有潜力，但我们认为现在实现它还为时过早。当前基于 SMT 的设计一旦其他研究实现了所有必要库，就可以很容易升级到 Verkle Trie。这个 ADR 所描述设计的主要优势，在于将状态承诺与数据存储分离，并设计出更强大的接口。

​
进一步讨论

​
已评估的 KV 数据库

我们验证了现有的 KV 数据库，以评估其快照支持。以下数据库提供高效的快照机制：Badger、RocksDB、Pebble。不提供此类支持或尚未达到生产就绪的数据库包括：boltdb、leveldb、goleveldb、membdb、lmdb。

​
RDBMS

使用 RDBMS 而不是简单的 KV store 来保存状态。使用 RDBMS 将需要对 Cosmos SDK API（KVStore 接口）进行破坏性变更，同时会带来更好的数据提取和索引方案。我们不必把对象保存为单个字节 blob，而是可以将其保存为状态存储层中表里的一条记录，并按上文所述将其作为 hash(key, protobuf(object)) 保存到 SMT 中。要验证注册在 RDBMS 中的对象与提交到 SMT 中的对象相同，需要先从 RDBMS 加载它，使用 protobuf 编组，进行哈希，然后执行 SMT 查询。

​
链下存储

我们讨论过这样一种用例：模块可以使用一个辅助数据库，它不会被自动提交。模块将负责确保其存储模型是健全的，并且可以选择使用在 _在不保存对象的情况下对其进行承诺 一节中讨论的功能。

​
参考资料

​
Changelog

  • 2020-01-15: Draft

​
Status

DRAFT Not Implemented

​
Abstract

Sparse Merkle Tree (SMT) is a version of a Merkle Tree with various storage and performance optimizations. This ADR defines a separation of state commitments from data storage and the Cosmos SDK transition from IAVL to SMT.

​
Context

Currently, Cosmos SDK uses IAVL for both state commitments and data storage. IAVL has effectively become an orphaned project within the Cosmos ecosystem and it’s proven to be an inefficient state commitment data structure. In the current design, IAVL is used for both data storage and as a Merkle Tree for state commitments. IAVL is meant to be a standalone Merkelized key/value database, however it’s using a KV DB engine to store all tree nodes. So, each node is stored in a separate record in the KV DB. This causes many inefficiencies and problems:
  • Each object query requires a tree traversal from the root. Subsequent queries for the same object are cached on the Cosmos SDK level.
  • Each edge traversal requires a DB query.
  • Creating snapshots is expensive. It takes about 30 seconds to export less than 100 MB of state (as of March 2020).
  • Updates in IAVL may trigger tree reorganization and possible O(log(n)) hashes re-computation, which can become a CPU bottleneck.
  • The node structure is pretty expensive - it contains a standard tree node elements (key, value, left and right element) and additional metadata such as height, version (which is not required by the Cosmos SDK). The entire node is hashed, and that hash is used as the key in the underlying database, ref.
Moreover, the IAVL project lacks support and a maintainer and we already see better and well-established alternatives. Instead of optimizing the IAVL, we are looking into other solutions for both storage and state commitments.

​
Decision

We propose to separate the concerns of state commitment (SC), needed for consensus, and state storage (SS), needed for state machine. Finally we replace IAVL with Celestia’s SMT. Celestia SMT is based on Diem (called jellyfish) design [*] - it uses a compute-optimized SMT by replacing subtrees with only default values with a single node (same approach is used by Ethereum2) and implements compact proofs. The storage model presented here doesn’t deal with data structure nor serialization. It’s a Key-Value database, where both key and value are binaries. The storage user is responsible for data serialization.

​
Decouple state commitment from storage

Separation of storage and commitment (by the SMT) will allow the optimization of different components according to their usage and access patterns. SC (SMT) is used to commit to a data and compute Merkle proofs. SS is used to directly access data. To avoid collisions, both SS and SC will use a separate storage namespace (they could use the same database underneath). SS will store each record directly (mapping (key, value) as key → value). SMT is a merkle tree structure: we don’t store keys directly. For every (key, value) pair, hash(key) is used as leaf path (we hash a key to uniformly distribute leaves in the tree) and hash(value) as the leaf contents. The tree structure is specified in more depth below. For data access we propose 2 additional KV buckets (implemented as namespaces for the key-value pairs, sometimes called column family):
  1. B1: key → value: the principal object storage, used by a state machine, behind the Cosmos SDK KVStore interface: provides direct access by key and allows prefix iteration (KV DB backend must support it).
  2. B2: hash(key) → key: a reverse index to get a key from an SMT path. Internally the SMT will store (key, value) as prefix || hash(key) || hash(value). So, we can get an object value by composing hash(key) → B2 → B1.
  3. We could use more buckets to optimize the app usage if needed.
We propose to use a KV database for both SS and SC. The store interface will allow to use the same physical DB backend for both SS and SC as well two separate DBs. The latter option allows for the separation of SS and SC into different hardware units, providing support for more complex setup scenarios and improving overall performance: one can use different backends (eg RocksDB and Badger) as well as independently tuning the underlying DB configuration.

​
Requirements

State Storage requirements:
  • range queries
  • quick (key, value) access
  • creating a snapshot
  • historical versioning
  • pruning (garbage collection)
State Commitment requirements:
  • fast updates
  • tree path should be short
  • query historical commitment proofs using ICS-23 standard
  • pruning (garbage collection)

​
SMT for State Commitment

A Sparse Merkle tree is based on the idea of a complete Merkle tree of an intractable size. The assumption here is that as the size of the tree is intractable, there would only be a few leaf nodes with valid data blocks relative to the tree size, rendering a sparse tree. The full specification can be found at Celestia. In summary:
  • The SMT consists of a binary Merkle tree, constructed in the same fashion as described in Certificate Transparency (RFC-6962), but using as the hashing function SHA-2-256 as defined in FIPS 180-4.
  • Leaves and internal nodes are hashed differently: the one-byte 0x00 is prepended for leaf nodes while 0x01 is prepended for internal nodes.
  • Default values are given to leaf nodes with empty leaves.
  • While the above rule is sufficient to pre-compute the values of intermediate nodes that are roots of empty subtrees, a further simplification is to extend this default value to all nodes that are roots of empty subtrees. The 32-byte zero is used as the default value. This rule takes precedence over the above one.
  • An internal node that is the root of a subtree that contains exactly one non-empty leaf is replaced by that leaf’s leaf node.

​
Snapshots for storage sync and state versioning

Below, with simple snapshot we refer to a database snapshot mechanism, not to a ABCI snapshot sync. The latter will be referred as snapshot sync (which will directly use DB snapshot as described below). Database snapshot is a view of DB state at a certain time or transaction. It’s not a full copy of a database (it would be too big). Usually a snapshot mechanism is based on a copy on write and it allows DB state to be efficiently delivered at a certain stage. Some DB engines support snapshotting. Hence, we propose to reuse that functionality for the state sync and versioning (described below). We limit the supported DB engines to ones which efficiently implement snapshots. In a final section we discuss the evaluated DBs. One of the Stargate core features is a snapshot sync delivered in the /snapshot package. It provides a way to trustlessly sync a blockchain without repeating all transactions from the genesis. This feature is implemented in Cosmos SDK and requires storage support. Currently IAVL is the only supported backend. It works by streaming to a client a snapshot of a SS at a certain version together with a header chain. A new database snapshot will be created in every EndBlocker and identified by a block height. The root store keeps track of the available snapshots to offer SS at a certain version. The root store implements the RootStore interface described below. In essence, RootStore encapsulates a Committer interface. Committer has a Commit, SetPruning, GetPruning functions which will be used for creating and removing snapshots. The rootStore.Commit function creates a new snapshot and increments the version on each call, and checks if it needs to remove old versions. We will need to update the SMT interface to implement the Committer interface. NOTE: Commit must be called exactly once per block. Otherwise we risk going out of sync for the version number and block height. NOTE: For the Cosmos SDK storage, we may consider splitting that interface into Committer and PruningCommitter - only the multiroot should implement PruningCommitter (cache and prefix store don’t need pruning). Number of historical versions for abci.RequestQuery and state sync snapshots is part of a node configuration, not a chain configuration (configuration implied by the blockchain consensus). A configuration should allow to specify number of past blocks and number of past blocks modulo some number (eg: 100 past blocks and one snapshot every 100 blocks for past 2000 blocks). Archival nodes can keep all past versions. Pruning old snapshots is effectively done by a database. Whenever we update a record in SC, SMT won’t update nodes - instead it creates new nodes on the update path, without removing the old one. Since we are snapshotting each block, we need to change that mechanism to immediately remove orphaned nodes from the database. This is a safe operation - snapshots will keep track of the records and make it available when accessing past versions. To manage the active snapshots we will either use a DB max number of snapshots option (if available), or we will remove DB snapshots in the EndBlocker. The latter option can be done efficiently by identifying snapshots with block height and calling a store function to remove past versions.

​
Accessing old state versions

One of the functional requirements is to access old state. This is done through abci.RequestQuery structure. The version is specified by a block height (so we query for an object by a key K at block height H). The number of old versions supported for abci.RequestQuery is configurable. Accessing an old state is done by using available snapshots. abci.RequestQuery doesn’t need old state of SC unless the prove=true parameter is set. The SMT merkle proof must be included in the abci.ResponseQuery only if both SC and SS have a snapshot for requested version. Moreover, Cosmos SDK could provide a way to directly access a historical state. However, a state machine shouldn’t do that - since the number of snapshots is configurable, it would lead to nondeterministic execution. We positively validated a versioning and snapshot mechanism for querying old state with regards to the database we evaluated.

​
State Proofs

For any object stored in State Store (SS), we have corresponding object in SC. A proof for object V identified by a key K is a branch of SC, where the path corresponds to the key hash(K), and the leaf is hash(K, V).

​
Rollbacks

We need to be able to process transactions and roll-back state updates if a transaction fails. This can be done in the following way: during transaction processing, we keep all state change requests (writes) in a CacheWrapper abstraction (as it’s done today). Once we finish the block processing, in the Endblocker, we commit a root store - at that time, all changes are written to the SMT and to the SS and a snapshot is created.

​
Committing to an object without saving it

We identified use-cases, where modules will need to save an object commitment without storing an object itself. Sometimes clients are receiving complex objects, and they have no way to prove a correctness of that object without knowing the storage layout. For those use cases it would be easier to commit to the object without storing it directly.

​
Refactor MultiStore

The Stargate /store implementation (store/v1) adds an additional layer in the SDK store construction - the MultiStore structure. The multistore exists to support the modularity of the Cosmos SDK - each module is using its own instance of IAVL, but in the current implementation, all instances share the same database. The latter indicates, however, that the implementation doesn’t provide true modularity. Instead it causes problems related to race condition and atomic DB commits (see: #6370 and discussion). We propose to reduce the multistore concept from the SDK, and to use a single instance of SC and SS in a RootStore object. To avoid confusion, we should rename the MultiStore interface to RootStore. The RootStore will have the following interface; the methods for configuring tracing and listeners are omitted for brevity. 
// Used where read-only access to versions is needed.
type BasicRootStore interface {
    Store
    GetKVStore(StoreKey)

KVStore
    CacheRootStore()

CacheRootStore
}

// Used as the main app state, replacing CommitMultiStore.
type CommitRootStore interface {
    BasicRootStore
    Committer
    Snapshotter

    GetVersion(uint64) (BasicRootStore, error)

SetInitialVersion(uint64)

error

    ... // Trace and Listen methods
}

// Replaces CacheMultiStore for branched state.
type CacheRootStore interface {
    BasicRootStore
    Write()

    ... // Trace and Listen methods
}

// Example of constructor parameters for the concrete type.
type RootStoreConfig struct {
    Upgrades        *StoreUpgrades
    InitialVersion  uint64

    ReservePrefix(StoreKey, StoreType)
}
In contrast to MultiStore, RootStore doesn’t allow to dynamically mount sub-stores or provide an arbitrary backing DB for individual sub-stores. NOTE: modules will be able to use a special commitment and their own DBs. For example: a module which will use ZK proofs for state can store and commit this proof in the RootStore (usually as a single record) and manage the specialized store privately or using the SC low level interface.

​
Compatibility support

To ease the transition to this new interface for users, we can create a shim which wraps a CommitMultiStore but provides a CommitRootStore interface, and expose functions to safely create and access the underlying CommitMultiStore. The new RootStore and supporting types can be implemented in a store/v2alpha1 package to avoid breaking existing code.

​
Merkle Proofs and IBC

Currently, an IBC (v1.0) Merkle proof path consists of two elements (["<store-key>", "<record-key>"]), with each key corresponding to a separate proof. These are each verified according to individual ICS-23 specs, and the result hash of each step is used as the committed value of the next step, until a root commitment hash is obtained. The root hash of the proof for "<record-key>" is hashed with the "<store-key>" to validate against the App Hash. This is not compatible with the RootStore, which stores all records in a single Merkle tree structure, and won’t produce separate proofs for the store- and record-key. Ideally, the store-key component of the proof could just be omitted, and updated to use a “no-op” spec, so only the record-key is used. However, because the IBC verification code hardcodes the "ibc" prefix and applies it to the SDK proof as a separate element of the proof path, this isn’t possible without a breaking change. Breaking this behavior would severely impact the Cosmos ecosystem which already widely adopts the IBC module. Requesting an update of the IBC module across the chains is a time consuming effort and not easily feasible. As a workaround, the RootStore will have to use two separate SMTs (they could use the same underlying DB): one for IBC state and one for everything else. A simple Merkle map that reference these SMTs will act as a Merkle Tree to create a final App hash. The Merkle map is not stored in a DBs - it’s constructed in the runtime. The IBC substore key must be "ibc". The workaround can still guarantee atomic syncs: the proposed DB backends support atomic transactions and efficient rollbacks, which will be used in the commit phase. The presented workaround can be used until the IBC module is fully upgraded to supports single-element commitment proofs.

​
Optimization: compress module key prefixes

We consider a compression of prefix keys by creating a mapping from module key to an integer, and serializing the integer using varint coding. Varint coding assures that different values don’t have common byte prefix. For Merkle Proofs we can’t use prefix compression - so it should only apply for the SS keys. Moreover, the prefix compression should be only applied for the module namespace. More precisely:
  • each module has its own namespace;
  • when accessing a module namespace we create a KVStore with embedded prefix;
  • that prefix will be compressed only when accessing and managing SS.
We need to assure that the codes won’t change. We can fix the mapping in a static variable (provided by an app) or SS state under a special key. TODO: need to make decision about the key compression.

​
Optimization: SS key compression

Some objects may be saved with key, which contains a Protobuf message type. Such keys are long. We could save a lot of space if we can map Protobuf message types in varints. TODO: finalize this or move to another ADR.

​
Migration

Using the new store will require a migration. 2 Migrations are proposed:
  1. Genesis export — it will reset the blockchain history.
  2. In place migration: we can reuse UpgradeKeeper.SetUpgradeHandler to provide the migration logic:
app.UpgradeKeeper.SetUpgradeHandler("adr-40", func(ctx sdk.Context, plan upgradetypes.Plan, vm module.VersionMap) (module.VersionMap, error) {
    storev2.Migrate(iavlstore, v2.store)

    // RunMigrations returns the VersionMap
    // with the updated module ConsensusVersions
    return app.mm.RunMigrations(ctx, vm)
})
The Migrate function will read all entries from a store/v1 DB and save them to the AD-40 combined KV store. Cache layer should not be used and the operation must finish with a single Commit call. Inserting records to the SC (SMT) component is the bottleneck. Unfortunately SMT doesn’t support batch transactions. Adding batch transactions to SC layer is considered as a feature after the main release.

​
Consequences

​
Backwards Compatibility

This ADR doesn’t introduce any Cosmos SDK level API changes. We change the storage layout of the state machine, a storage hard fork and network upgrade is required to incorporate these changes. SMT provides a merkle proof functionality, however it is not compatible with ICS23. Updating the proofs for ICS23 compatibility is required.

​
Positive

  • Decoupling state from state commitment introduce better engineering opportunities for further optimizations and better storage patterns.
  • Performance improvements.
  • Joining SMT based camp which has wider and proven adoption than IAVL. Example projects which decided on SMT: Ethereum2, Diem (Libra), Trillan, Tezos, Celestia.
  • Multistore removal fixes a longstanding issue with the current MultiStore design.
  • Simplifies merkle proofs - all modules, except IBC, have only one pass for merkle proof.

​
Negative

  • Storage migration
  • LL SMT doesn’t support pruning - we will need to add and test that functionality.
  • SS keys will have an overhead of a key prefix. This doesn’t impact SC because all keys in SC have same size (they are hashed).

​
Neutral

  • Deprecating IAVL, which is one of the core proposals of Cosmos Whitepaper.

​
Alternative designs

Most of the alternative designs were evaluated in a prior state commitments and storage report. Ethereum research published Verkle Trie - an idea of combining polynomial commitments with merkle tree in order to reduce the tree height. This concept has a very good potential, but we think it’s too early to implement it. The current, SMT based design could be easily updated to the Verkle Trie once other research implement all necessary libraries. The main advantage of the design described in this ADR is the separation of state commitments from the data storage and designing a more powerful interface.

​
Further Discussions

​
Evaluated KV Databases

We verified existing databases KV databases for evaluating snapshot support. The following databases provide efficient snapshot mechanism: Badger, RocksDB, Pebble. Databases which don’t provide such support or are not production ready: boltdb, leveldb, goleveldb, membdb, lmdb.

​
RDBMS

Use of RDBMS instead of simple KV store for state. Use of RDBMS will require a Cosmos SDK API breaking change (KVStore interface) and will allow better data extraction and indexing solutions. Instead of saving an object as a single blob of bytes, we could save it as record in a table in the state storage layer, and as a hash(key, protobuf(object)) in the SMT as outlined above. To verify that an object registered in RDBMS is same as the one committed to SMT, one will need to load it from RDBMS, marshal using protobuf, hash and do SMT search.

​
Off Chain Store

We were discussing use case where modules can use a support database, which is not automatically committed. Module will responsible for having a sound storage model and can optionally use the feature discussed in _Committing to an object without saving it section.

​
References