作者：KJ， LXDAO
背景和动机
在开端讲对 MPT 的改善之前，咱们先谈一谈进行这项研讨的背景。
本人在读博并且做公链规划。这条公链除了核心的共识晋级：有用的工作量证明以外，另一个重要的任务是完结兼容 ETH 的智能合约体系。咱们现在现已完结了一个依据 Python 字节码的虚拟机，并整合到一条区块链的合约体系中，并且十分意外的做到了以太坊 RPC 兼容。咱们运用 Python 构建了一个契合 ERC20 规范的智能合约进行测验，很自然的咱们要在合约履行的基层，完结能承载千万等级用户的 KV 数据机构（类似于 Solidity 中的 Mapping，用来存储每个账号下的代币数量，这样的账号或许有上亿个）。
接下来，公链规划的工作内容很自然的触达到了 MPT、Trie 等概念。咱们参考了以太坊的规划，三棵树，Trie，MPT 等。在此，我要感谢北大肖教师的区块链视频，（16-ETH-状况树_哔哩哔哩_bilibili 第 16 讲），让咱们快速的了解了这一部分常识。
视频链接：https://www.bilibili.com/video/BV1Vt411X7JF?t=11.0
发现瓶颈
走运的是，在咱们预备着手完结智能合约调用 MPT 之前，咱们突发奇想的在 AWS 的服务器上运转了一个简略的 MPT 树 Benchmark 程序。当测验用 Trie 和 MPT 刺进一亿 KV 的数据量后，咱们十分惊讶的得到了成果：MPT 树的功用居然是这样的低。
运转以下代码，咱们观察到：向 Rocksdb 刺进一千万 KV 键值对，Trie 需求几分钟，MPT 需求几小时。当咱们把测验数据数量级增加到 1 亿，MPT 刺进程序需求运转数天。这意味着，区块链运用 MPT 数据结构运转智能合约的时分，速度也会遭到较大约束。
试验证明，运用 MPT 数据结构带来的开支，既会拖慢智能合约的履行速度，也会降低区块链节点的同步速度（即便在带宽十分充足的时分，从其他节点下载数据并且重建节点，也有必要花费数天时刻）。然而，由于以太坊的数据结构规划很难被修正，即便咱们用“更快”的编程言语重写或许优化，假如不做底层数据结构上的更新，区块链将很难突破功用的约束。
test_mpt_write.py
import mptimport rocksdbclass DBWrap:def __init__(self, db) -> None:self.db = dbdef __setitem__(self, key, value):self.db.put(key, value)def __getitem__(self, key):return self.db.get(key)conn = rocksdb.DB('mpt.db', rocksdb.Options(create_if_missing=True))storage = DBWrap(conn)root_hash = conn.get(b'root_hash')print('Prev root_hash', root_hash)trie = mpt.MerklePatriciaTrie(storage, root_hash)start = 0while True:for i in range(start, start+10000):k = str(i).zfill(32).encode('utf8')trie.update(k, k)root_hash = trie.root_hash()print(f"root_hash hex {root_hash.hex()}")print(start)start += 10000if start > 10000000:break
test_mpt_write.py
import rocksdbconn = rocksdb.DB('trie.db', rocksdb.Options(create_if_missing=True))start = 0while True:print(start)for i in range(start, start+10000):k = str(i).zfill(32).encode('utf8')conn.put(k, k)start += 10000if start > 10000000:break
链接：https://gist.github.com/kernel1983/f746c1470376e422a8efe3ee6782901d
还记得我在刚学写代码的时分，教师们告诉咱们一个根本原理，程序 = 算法 + 数据结构。假如咱们约束数据结构，那么即便在算法上拼命优化（这往往需求数年的学术努力，许多情况下几乎无法再进步），也很难突破当时数据结构的功用约束。那么十分学术的改善计划，寻觅功用更好的 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.经过区块头中的默克尔根，查找区块链对应的状况。
2.节约重复数据占用的空间。
3.能够经过根哈希验证状况是否正确。
其间第 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
感谢 Python 3 供给的 Annotation 功用，咱们能够从 RPC 中把原本调用 EVM 的买卖数据，转化成 Python 能够承受的类型，比方 Uint256、Uint8 直接转化成 Python int。函数输出的值也能够主动转化成 RPC 承受的 ABI 类型。
第三步，咱们完结 _get 和 _put 函数，选用本文规划的计划来在区块链运转过程中，存储 Python VM 履行中读取和写入的区块链状况数据。状况数据的读取和写入都会先经过内存，只要当买卖成功履行，一切对状况的修正才会被汇总成状况更新数据块，连同买卖数据块和经过共识算法区块头一起广播到整个区块链网络当中。
链接：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 对本次研讨的支撑，也期望在社区中能知道更多对区块链底层感兴趣的朋友们。这个职业还十分早期，基础设施远未老练。咱们期望推进区块链底层常识的遍及，让更多人能够一起参与到技能革新的最前沿。
此时快讯
【Lido社区新提案拟关停在Polygon上的质押服务】10月19日消息，Lido社区发布讨论提案，拟把MATIC上的质押协议Lido on Polygon启动类似于Polkadot和Kusama上的sunset流程。其中该提案表示，Lido在过去一年在Polygon上花费的奖励为1,538,500枚LDO，而每1%的MATIC质押可获得的年收入为41991美元，Shard Labs的一次性补偿是15万枚LDO，这是糟糕的投资回报率。
