MPT 下岗？智能合约区块链的优化

作者：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 rocksdb
class DBWrap:    def __init__(self, db) -> None:        self.db = db
    def __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 += 10000    if start > 10000000:        break

test_mpt_write.py

import rocksdb

conn = 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 += 10000    if start > 10000000:        break

链接：https://gist.github.com/kernel1983/f746c1470376e422a8efe3ee6782901d

还记得我在刚学写代码的时候，老师们告诉我们一个基本原理，程序 = 算法 + 数据结构。如果我们限定数据结构，那么即使在算法上拼命优化（这往往需要数年的学术努力，很多情况下几乎无法再提高），也很难突破当前数据结构的性能限制。那么非常学术的改进方案，寻找性能更好的 MPT 代替算法，研究可能会花费数年时间。作为在这个方向努力的前辈，Verkle Tree 使用多项式的方式优化区块链数据结构，我们则会尝试一些更加独特和简单的思路。