以太坊的世界树
- 2 minsMPT 数据结构
merkle partricia trie
以太坊客户端使用
为什么 Merkle Patricia trie 的根节点不依赖于数据的顺序。
因为 Merkle Patricia Trie 使用了基于前缀的压缩技术，它将具有相同前缀的节点合并成一个节点，并存储一个指向下一个节点的链接。这种压缩技术使得节点的顺序不再影响根节点的计算。
换句话说，即使数据项的顺序不同，只要它们具有相同的键值对，最终生成的 Merkle Patricia Trie 结构将是相同的，因此根节点的哈希值也会相同。
状态树
小树: 储存树
之所以将存储树称为一棵小树，是因为该树每个账户都有，记录该账户的存储区，它是状态树的一个组成部分。
交易树
交易树用来记录每个区块中所有交易的哈希值，并最终生成一个根哈希值，这个根哈希值被记录在区块头中。
储存交易树是为了：
- 验证区块的完整性： 通过验证交易树的根哈希值是否与区块头中记录的值一致，可以确保区块中的交易信息没有被篡改。
- 快速查找交易： 交易树是一种高效的数据结构，可以快速定位到某个特定的交易。
- 防止双重支付： 交易树可以确保每个交易只被执行一次，防止恶意用户重复提交相同的交易。
收据树
收据树是为了方便查询和验证交易信息而储存的。
收据树包含了每笔交易的收据，收据中记录了交易执行后的状态、交易费用、产生的日志等信息。这些信息可以用来：
- 验证交易是否成功执行： 通过查看收据中的状态信息，可以判断交易是否成功执行。
- 查询交易的详细信息： 收据中包含了交易的各种信息，例如交易费用、产生的日志等，方便用户查询交易的详细信息。
- 追踪智能合约的执行过程： 收据中的日志信息可以用来追踪智能合约的执行过程，帮助开发者调试和分析智能合约。
总而言之，收据树是区块链中重要的数据结构，它记录了交易的执行结果，方便用户查询和验证交易信息。
区块
以太坊客户端用什么数据库?
Geth (Go-Ethereum):
- LevelDB: Geth 默认使用 LevelDB，这是一个高性能的键-值存储库，非常适合嵌入式数据库应用。
cosmos-sdk默认使用什么数据库?
GoLevelDB: a pure Go implementation of LevelDB (see below). Currently the default on-disk database used in the Cosmos SDK.
SMT
Sparse Merkle Tree
Plasma Cash: 用于存储有关已存资产的信息，并通过包含（或不包含！）证明来验证交易历史记录。
稀疏 Merkle 树是一种数据结构，它类似于标准的 Merkle 树，但它允许你存储大量数据，而无需为每个数据点都创建一个节点。它通过将数据索引并放置在与索引相对应的叶子上，并使用特殊值（如 null）来填充空叶子来实现这一点。
稀疏 Merkle 树的主要优点是：
- 有效地证明非包含性: 它可以有效地证明一个数据点是否不在树中。
- 键值存储: 它可以作为键值存储使用，其中键是索引，值是存储在叶子中的数据。
稀疏 Merkle 树的主要缺点是：
- 树的大小: 由于它存储了大量数据，因此树的大小可能会非常大。
总的来说，稀疏 Merkle 树是一种强大的数据结构，它可以有效地存储和验证大量数据，并为非包含性证明提供了一种有效的方法。
Sparse Merkle Tree和merkle partricia trie有什么不一样, 为什么以太坊使用MPT, cosmos使用SMT?
Sparse Merkle Tree (SMT) 和 Merkle Patricia Trie (MPT) 是两种不同类型的加密数据结构，用于高效地存储和验证数据的完整性。它们在架构、性能以及应用场景上各有优劣。以下是它们的主要区别：
Sparse Merkle Tree (SMT) 杀马特
-
结构: Sparse Merkle Tree 是一种带有稀疏特性的 Merkle 树，其中每一个可能的哈希值对应一个叶子节点，即使那些哈希值没有实际对应的值。
-
路径长度: 在SMT中，任何一个键的路径长度是固定的，这是因为每一个可能的哈希值都有一个路径到根。
-
存储效率: 由于是稀疏的，这种树会消耗较多存储空间，但可以通过一些技巧（如使用哈希表或紧凑数据结构）来优化。
-
更新效率: 更新操作可以是高效的，因为仅需要修改相关路径上的哈希值。
Merkle Patricia Trie (MPT) 孟婆汤
-
结构: MPT 是一种结合了前缀树和 Merkle 树的数据结构。它通过压缩路径来减少树的高度，对稀疏区域进行了优化。
-
路径长度: MPT 的路径长度不是固定的，因而在某些情况下可以更加紧凑。
-
存储效率: 由于可以压缩路径，MPT 的存储效率通常较高，尤其是在键值数据稀疏分布的情况下。
-
更新效率: 更新操作相对复杂，因为需要处理路径压缩和重新计算哈希。但由于以太坊设计了一些优化机制，这些操作在大多数情况下仍然高效可接受。
为什么 SMT 比 MPT 验证一个数据的完整性更加高效
SMT 使用了 Sparse Merkle Tree 的数据结构，该结构允许跳过不必要的空间，因此有助于减少计算量和存储开销。
而 MPT 使用了 Merkle Patricia Trie 的数据结构，该结构适用于以太坊等区块链网络中，能够有效地处理存储和验证大量数据。但在某些情况下，MPT 验证数据的完整性可能需要更多的计算步骤和存储空间，因此相比之下，SMT 可能更高效一些。
为什么以太坊使用MPT，Cosmos使用SMT？
以太坊选择MPT的理由：
-
灵活性和存储效率: 以太坊作为一个通用的智能合约平台，需要高效地存储和检索大量的键值对数据，包括账户状态、合约存储等。MPT 的路径压缩和适应性使其成为了一个适合这种需求的选择。
-
复杂交易处理: 以太坊交易涉及多种不同数据结构的访问和修改，比如账户余额、nonce、智能合约存储等。这要求基础数据结构不仅要高效，还需要有很好的灵活性以满足这些复杂的需求。
Cosmos选择SMT的理由：
-
简化的结构和高效验证: Cosmos更多关注跨链通信和模块化区块链的构建，这要求轻量级、高效的数据验证机制。SMT 提供了比 MPT 更为简单高效的可验证数据结构。
-
固定路径和一致性: 在一些应用场景下，固定路径长度的优点是显而易见的，特别是当数据键分布较为均匀或者可以预见时。SMT在这种情况下能够提供较高的性能和一致性。
总结
以太坊主要关注复杂智能合约平台的高效性和灵活性，因此选择了结构较为复杂但存储和处理效率较高的MPT。Cosmos专注于跨链通信和快速状态验证，选用了结构相对简单却高效的SMT。这两种数据结构虽然都有自己的优势，但它们各自适用于不同的应用场景。
cosmos为什么从IAVL转换成SMT?
Cosmos 从 IAVL 转换成 SMT 是因为 IAVL 在状态承诺方面存在一些效率问题，例如：
- 每个对象查询都需要从根遍历树，导致效率低下。
- 每个边缘遍历都需要一个数据库查询，增加了查询时间。
- 创建快照成本很高，导出少于 100 MB 的状态大约需要 30 秒。
- IAVL 中的更新可能会触发树重组和可能的 O（log（n）） 哈希重新计算，这可能会成为 CPU 瓶颈。
- IAVL 节点结构非常昂贵，包含标准的树节点元素和其他元数据，导致存储空间浪费。
此外，IAVL 项目缺乏支持和维护者，而 SMT 已经成为一个更成熟和广泛采用的解决方案，例如 Ethereum2、Diem (Libra)、Trillian、Tezos 和 Celestia 都选择了 SMT。
因此，Cosmos 决定用 Celestia 的 SMT 替换 IAVL，以提高状态承诺的效率和性能。
cosmos如何使用SMT结构储存什么东西?
Cosmos 使用 SMT 结构来存储 状态承诺。
具体来说，Cosmos SDK 中的 SMT 用于：
- 存储状态机中所有数据的哈希值。 这些哈希值构成一个 Merkle 树，树的根哈希值代表整个状态的承诺。
- 生成 Merkle 证明。 当需要验证某个数据是否在状态中存在时，可以使用 SMT 生成 Merkle 证明，证明该数据对应的哈希值确实存在于 Merkle 树中。
SMT 存储的不是数据本身，而是数据的哈希值。 这样做的优点是：
- 提高效率： 由于只存储哈希值，而不是完整的数据，因此可以节省存储空间，并提高查询速度。
- 增强安全性： 由于哈希值是不可逆的，因此可以防止数据被篡改。
Cosmos SDK 中的 SMT 存储模型：
- 状态存储 (SS)： 存储实际的数据，使用 Key-Value 数据库实现。使用Key-Value database，可以是RocksDB、Badger或Pebble等支持快照机制的数据库。
- 状态承诺 (SC)： 存储数据的哈希值，使用 SMT 实现。使用Celestia的SMT，它基于Diem (Jellyfish)的设计，并使用SHA-2-256作为哈希函数。
数据存储流程：
- 当数据被写入状态存储 (SS) 时，会计算数据的哈希值。
- 数据的哈希值被写入状态承诺 (SC) 中的 SMT。
- SMT 会更新其 Merkle 树，并生成新的根哈希值。
数据验证流程：
- 当需要验证某个数据是否在状态中存在时，会使用数据的 Key 查询状态存储 (SS)。
- 从状态存储 (SS) 中获取数据，并计算数据的哈希值。
- 使用数据的 Key 查询状态承诺 (SC) 中的 SMT，并生成 Merkle 证明。
- 使用 Merkle 证明验证数据的哈希值是否与状态承诺 (SC) 中的哈希值一致。
总结：
SC和SS可以使用同一个数据库，也可以使用不同的数据库。使用同一个数据库可以简化操作，而使用不同的数据库可以提高性能和灵活性。
cosmos state storage
某账户是否存在，该账户对应的余额。
想要检查帐户是否有效？询问状态tree
想知道您的账户余额吗？询问收据tree
如何根据交易哈希, 查询某交易是否存在，若存在，是否包含在特定的区块中。
交易是否包含在区块中？询问交易tree