背景和动机
在开始讲对 MPT 的改进之前，我们先谈一谈进行这项研究的背景。
本人在读博并且做公链设计。这条公链除了核心的共识升级：有用的工作量证明以外，另一个重要的任务是实现兼容 ETH 的智能合约系统。我们目前已经实现了一个基于 Python 字节码的虚拟机，并整合到一条区块链的合约系统中，并且非常意外的做到了以太坊 RPC 兼容。我们使用 Python 构建了一个符合 ERC20 标准的智能合约进行测试，很自然的我们要在合约执行的下层，实现能承载千万级别用户的 KV 数据机构（类似于 Solidity 中的 Mapping，用来存储每个账号下的代币数量，这样的账号可能有上亿个）。
接下来，公链设计的工作内容很自然的触达到了 MPT，trie 等概念。我们参考了以太坊的设计，三棵树，trie，MPT 等。
发现瓶颈
幸运的是，在我们准备动手实现智能合约调用 MPT 之前，我们突发奇想的在 AWS 的服务器上运行了一个简单的 MPT 树 Benchmark 程序。当尝试用 Trie 和 MPT 插入一亿 KV 的数据量后，我们非常惊讶的得到了结果：MPT 树的性能居然是这样的低。
运行以下代码，我们观察到：向 Rocksdb 插入一千万 KV 键值对，Trie 需要几分钟，MPT 需要几小时。当我们把测试数据数量级增加到 1 亿，MPT 插入程序需要运行数天。这意味着，区块链使用 MPT 数据结构运行智能合约的时候，速度也会受到较大限制。
实验证明，使用 MPT 数据结构带来的开销，既会拖慢智能合约的执行速度，也会降低区块链节点的同步速度（即使在带宽非常充足的时候，从其他节点下载数据并且重建节点，也必须花费数天时间）。然而，由于以太坊的数据结构设计很难被修改，即使我们用“更快”的编程语言重写或者优化，如果不做底层数据结构上的更新，区块链将很难突破性能的限制。
test_mpt_write.py
test_mpt_write.py
还记得我在刚学写代码的时候，老师们告诉我们一个基本原理，程序 = 算法 + 数据结构。如果我们限定数据结构，那么即使在算法上拼命优化（这往往需要数年的学术努力，很多情况下几乎无法再提高），也很难突破当前数据结构的性能限制。那么非常学术的改进方案，寻找性能更好的 MPT 代替算法，研究可能会花费数年时间。作为在这个方向努力的前辈，Verkle Tree 使用多项式的方式优化区块链数据结构，我们则会尝试一些更加独特和简单的思路。
我们采用第一性原理思考方式，能不能不用 MPT ？如果我们可以绕开 MPT 直接在 Trie 之上实现智能合约，就不再有 MPT 带来的开销 （马一龙的第一性原理，一个不存在的东西是不会有性能开销的）。
作为代价，我们新设计的方案可能无法与现有 MPT 直接兼容，但是由于不修改以太坊RPC接口，所以可以重用很多现有以太坊基础设施：比如 Etherjs 和 MetaMask。绕开 MPT 属于内部数据结构优化，这是对区块链性能的自由探索。
前置知识
Rocksdb 和 Trie
Trie 字典树，是一种大学课本中提及高级的树数据结构，在肖老师的视频中 MPT 就是基于 Trie 字典树构建的。我们可以认为 Trie 的实现环境是在内存当中。
但是我们工程上，是无法直接使用 Trie 直接实现产品，因为我们还需要让数据在硬盘上持久化，这一步骤又有很多工程上的优化，所以我们一般基于 Rocksdb 来实现 MPT 树。
Rocksdb 是 FB 基于 leveldb 的开源 Fork，底层使用了 LSMT（参考论文 The log-structured merge-tree）。从抽象的角度，我们可以把 Rocksdb 认为是一个优化过的，可以持久化的字典树。
Rocksdb 的基本使用非常简单，主要用到的是 Get put 和按前缀 Iterate 查询三种基本操作。
状态机
状态机是经常被人们用来建模区块链的工具，它非常简单：给一个原有状态加上一个输入, 得到一个新状态。
以太坊的全局状态可以理解成状态机的状态，比如在区块 1 的时候, 所有智能合约的 KV 值就是一个全局状态，一个区块中所有的交易，被 EVM 执行，可以理解成状态机的输入，比如一个 Mint 合约调用，使得一个用户的 Balance 和合约的 Total 变量在区块 2 变为 1000。
一个容易被人们忽视的状态机概念，叫状态转换函数，它定义了输入的规则，当输入不合理的时候，会拒绝输入信息。比如，我们尝试转账给别人一个负数金额的时候，这样的交易就不会被执行 (当然，有 Bug 的智能合约可以接受这样的交易，在 ETH 中，状态转换函数可以通过图灵完备的语言自定义)。
MPT 介绍
有可能你已经听说过以太坊三棵树，分别叫交易树，状态树，和回执树。他们都是 MPT 树，全称是 Merkle Patricia Tries 。其中，状态树可能是最适合使用 MPT 数据结构的用例。具体可以参考肖老师的视频讲解。
MPT 树基于 Trie 数据结构之上，能够像默克尔树一样把所有状态数据，计算成一个根哈希，放到以太坊的区块头。以太坊区块头里有三颗 MPT 树的根哈希，我们通常叫做三棵树。
区块头中是否可以不放置全局状态的树根呢？可以的，比特币区块中放置的就是交易，并把交易的默克尔根放进了区块头（使用了默克尔树，但没有使用 MPT）。但是比特币没有以太那样的智能合约，也没有全局状态的概念。以太坊在最初设计带智能合约的区块链的时候，抛弃了比特币的 1 M 区块设计和 UTXO，选择 MPT 数据结构和账户模型，以及用 Gas 来解决停机问题，满足了智能合约运行中对于全局状态的需求。
那么，以太坊中使用 MPT 的目标是什么呢?
通过区块头中的默克尔根，查找区块链对应的状态。
节省重复数据占用的空间。
可以通过根哈希验证状态是否正确。
其中第 1 点是刚需，执行 EVM 的同时需要读取各种状态，如果使用类似比特币 UTXO 的设计模式，需要回溯很多区块才能得到某个用户的账户余额状态。使用 MPT 则很好的满足需求。
第 2 点，MPT 节省空间，区块链状态可以看成是一个巨大的字典。每个区块，仅仅有一小部分 Key 被更新，大部分 Key 还是保持原有值。使用 MPT 树可以仅仅更新需要更新的键值，无需在每个区块将未改动的状态复制一遍。
第 3 点，MPT 的优势是，使用根哈希访问到的状态键值，已经完成了全局状态的验证。这也是在写入 MPT 树时候，比较耗时的主要原因。如果不使用 MPT，节点依然可以在同步区块期间，验证数据的一致性。
不使用 MPT 完成第 1 和第 2 点，我们就可以绕开 MPT 的开销。所以我们要基于 Trie（可以理解为 Rocksdb）设计一个方案，存储区块链的状态数据。
设计
我们主要设计一个基于 Trie 的方案来存储链上状态，根据第一性原理，不存在 MPT 数据结构，就没有运行 MPT 所需要的系统开销。只要基于 Trie 的智能合约系统可以被实现并正确运行，就意味着优化已经完成。实践中我们可以把 Rocksdb 看成是一个 Trie，更简单的理解，就是一个高性能的 KV 数据库。
使用 [globalstate 为前缀_合约地址_变量名_区块高度_区块哈希] 作为 KV 数据库的键值，比如以下格式。其中 0x1 是合约地址，Total 是变量名，1 是区块高度，ABC1234 是区块哈希值（后面会省略）
globalstate_0x1_total_1_abc1234
在以太坊 Solidity 中，变量可以定义为 Memory、Storage 和 Calldata，我们主要关注 Storage 类型，因为它会被存储在全局状态中。除了简单变量外，我们还考虑 Mapping，因为区块链上用户的数量级是全球级别的，所以会出现超大的 KV mapping。除此以外，Array 等数据类型，我们会当成简单数据结构处理，直接 Json 后存入 Rocksdb。我们在编码的时候，应当很自然的估算 KV 数据结构中的 Value 数据数量级，以选择适当的存储方式。
合约存储状态变量
如果不使用 MPT，我们如何实现 MPT 的第一点和第二点设计目标呢？
假设我们在 ERC20 合约中有一个变量 Total，这个变量只有在 Token 数量总量增加（Mint）或者减少（Burn）的时候才会改变，但是用户 A 向用户 B 转账（Transfer）的时候 Total 的值保持不变。
为了简单，假设合约地址是 0x1，在区块高度为 1 的时候，合约的 Owner 进行了一次 Mint 2000，在高度为 2－8 区块上，用户进行了多次转账，现在区块高度是 9。
此时，我们只需要向数据库查询以 [globalstate_0x1_total_] 前缀的 Key。虽然我们的当前最新区块是 9，但是由于 Total 变量在 2-8 区块都没有发生变化，所以以上查询的第一个结果将是 [globalstate_0x1_total_1] 的值，所以我们找到了 Total 变量的最新值，在区块 1 的时候发生过改变的 Total 变量。
此时，新区块又产生，假设用户在第 9 区块和第 11 区块又做了两次 Mint。这里我们发现 Rocksdb 的一个特性，如果我们有以下 Key
globalstate_0x1_total_1 : 2000
globalstate_0x1_total_9 : 4000
globalstate_0x1_total_11 : 6000
那么搜索的第一个结果总是区块 1，而不是最新区块 11。因为我们暂时没有从 Rocksdb 文档中找到改变搜索结果顺序的参数，所以我们用了一个小技巧，使用一个较大的数字比如 100 去减区块高度（实际会大得多），并且补零，所以最新区块会排在搜索结果最前面。
globalstate_0x1_total_089 : 6000
globalstate_0x1_total_091 : 4000
globalstate_0x1_total_099 : 2000
存储 Mapping 类型
前面我们提到了，Mapping 数据结构的 Key 量级有可能是海量的，所以我们不可能将 Mapping 中上万个 Key 的字典 Json 成一个字符串，否则添加删除 Key，或者修改 Value 的代价会是非常可怕的。
假设用户的地址是 0x2，我们稍稍扩展一下之前的存储 Key 格式：
[globalstate_0x1_[balance_0x2]_2] : 2000
这里之前的 [变量名]，扩展成了[变量名 + Mapping 字典的 Key]
以上数据代表用户 0x2 在区块高度 2 的 Balance 余额是 2000，如果没有更新的数据覆盖当前的余额，那么用户在区块 2 的数据就代表着最新状态。
globalstate_0x1_balance_0x2_098 : 2000
globalstate_0x1_total_0x1_099 : 2000
验证区块
和默克尔树根一样，MPT 树根也代表着对全局状态的一种验证。只要我们可以保证区块数据一致性，是否一定要用 MPT 并且把 Root 写进区块头，是可以在设计上取舍的。
我们在区块设计上做了一些改进，让区块头包含了两个 Body，一个是交易数据块，另外一个是状态更新数据块。
交易数据块包含所有交易的哈希，矿工或者节点可以某个区块高度的全局状态开始，按照交易数据块中的给出的顺序执行完所有交易，得到下一个区块的全局状态。如果交易量很大，执行又不太可能并行（因为会打乱交易顺序），所以如果要求全世界的节点都执行一遍所有交易，是比较费时间的。
为此，我们设计了状态更新数据块，其中包括了运行完所有交易以后，被更新过的全局状态键值。如果是一个落后很多区块的节点，那么在选择运行虚拟机执行所有交易以外，它也可以根据状态更新 Body 的内容，直接向数据库插入键值，以节约运算量，缩短同步时间。
当然，执行所有交易更新的键值，和状态更新区块包含的 Diff，必须完全一致，否则这个新区块是不合法的。
假设全世界有 10000 个节点，当我们掷色子设定百分之一的概率去执行交易，大约 100 个节点会执行交块交易，其他节点则信任接状态更新数据块的内容，那么这个区块链系统中很多节点将能节省大量重复运算。
实现
在完成了之前的设计之后，我们马上着手实现这一想法。
首先，我们将 Python VM 整合进了区块链系统。这是一个由 Python 实现的 Python 虚拟机，目前它兼容 PY 3.10 的字节码。我们希望智能合约可以使用 Python 的部分语法，比如我们只需要函数，并不希望开发者使用 Class，所以我们目前并没有完全支持所有的 PY 字节码。
关于编译器，Solidity 需要开发专用的编译器，将源代码转换成 EVM 字节码。使用 Python 可以借助这个有三十年历史的优秀基础设施语言，轻松的将 Python 源码转换成 PY 字节码，用户几乎感觉不到编译时间。
我们的 VM 代码仓库如下，欢迎大家给我们提意见，修复潜在安全问题：
链接：https://github.com/EcoPoW/python_stf_vm 第二步，我们开发了一个 Python 版本的 ERC20，代码一直在更新。不同于 Solidity，我们并没有使用关键字来标识变量的存储方式，所有的局部变量都在内存中，我们使用 _get 和 _put 全局函数来读取和写入状态。 
链接：https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py 
https://github.com/EcoPoW/BitPoW/blob/master/state.py
落地和改进
对于从提出问题，到设计，以及编码实现，我们大约花了两个月时间。
通过整个夏天的设计 + 实际的编码，新的智能合约系统，仅仅使用字典树 Trie 而不依赖 MPT 数据结构，已经可以落地运行（大家可以通过 Github clone 来尝试本地运行测试节点）。绕过基于 MPT 的智能合约存储，意味着在带宽充分的条件下，一亿 KV 大小的节点的同步时间，可以从好几天，降低到几分钟。智能合约的执行效率也将变快，CPU 所消耗的计算量，会更多的用在执行字节码，而不是构建默克尔树所需要的哈希运算。我们很幸运，在工程实现智能合约的时候，没有直接沿用“工业标准”的设计，而是先尝试优化和减法，得到了一个“数据结构”正确的智能合约区块链。因为不同于 Web2 产品，我们比喻成一边开汽车一边换轮胎，Web3 区块链更像是火箭发射。一个运行中的区块链，是很难进行大结构改进的，所以我们只能改进“下一个”系统，在上线前做好充分准备。
目前，我们设计的 BitPoW 区块链的 Testnet2 号测试网已经部署，大家都可以通过 RPC 使用 MetaMask 连接到这条区块链上进行测试，尝试基于 Python VM 的 ERC20 转账。同时，我们还有很多工作尚未完成，我们仍然需要依靠社区来推动这一新型区块链基础设施。
我们欢迎大家来了解和实际上手测试这些新概念驱动的技术实现，包括对于移除 MPT 后的性能测试，对于新智能合约和新链的安全测试。
总结
至此，我们绕开了 MPT 设计了直接基于 Trie 的智能合约存储方案。目前，我们在基于 Python vm 的区块链上实现了这一改进，作为可行性证明。从发现问题到提出方案，到从代码实现，我们大约花了三个月时间，但是这次研究的更重要之处在于，我们在此之前和许多普通人一样，从课堂学习到 MPT 知识后，并未进一步思考去改进它。解决方案并不复杂，但是需要实践和行动。解决方案并不复杂，但是需要实践和行动。在实践中积极思考，才能找到灵感，进一步的创新。非常感谢 LXDAO 对本次研究的支持，也希望在社区中能认识更多对区块链底层感兴趣的朋友们。这个行业还非常早期，基础设施远未成熟。我们希望推动区块链底层知识的普及，让更多人可以一起参与到技术革新的最前沿。
