通过 EVM 代码默克尔化缩减见证数据大小

本文着重讨论如何默克尔化 EVM 字节码,但总体思路并不局限于 EVM 。

作者: Sina Mahmoodi

翻译&校对: IAN LIU & 阿剑

来源:以太坊爱好者

摘要:区块中每发生一次合约调用,无状态客户端都需要完整的合约代码作为区块见证(witnesss)的一部分,而传输合约代码占用无状态客户端带宽的比例,高居其带宽开销的第二位。

人们认为,代码默克尔化方法(Merklization)能够优化带宽开销。本文解释了如何将代码拆分为 “块( chunk ) ”,默克尔化这些 chunk,并只在交易需要的情况下传递这些 chunk 。实验证明,基于目前的主网情况,我们能看到合约代码传输的开销节省了 40%~60% 。

巨大的无状态区块

代码默克尔化的概念已经被提出好一阵子了,一开始主要用于代码去重,但其他用途还未被很好地探索。现在它重新进入大众视线,却是因为另一个目的 —— 用于降低无状态客户端所需要的带宽开销(e.g. 详见此处)。如果你想知道无状态客户端为什么出现,我推荐这篇总结,或是 Alexey Akhunov 的推文(编者注:中译本见文末《以太坊无状态客户端初探》),里面还附上了他的实验数据。为求简短扼要,我不会深入整个无状态客户端模型的细节,仅提供相关细节的简要总结(如果你早已了解相关的背景,可以跳过下一段的内容)。

在无状态模式下,(至少有部分)节点可以依赖其他节点(例如矿工节点)来取得区块内容(包含合约代码)并使用相关默克尔证明加以验证,而不必自己存储所有区块状态 —— 这会给网络带宽带来巨大的性能提升。Alexey Akhunov 和 turbo-geth 团队一直在研究,希望能确定已经产出的主网区块的区块见证大小。下图是对最近 50000 个区块的测量结果:红线追踪每个无状态区块需要发送的合约代码量(合约代码目前占见证大小的第二大头)。如果以太坊从当前的 hexary 字典树结构转为二进制 trie,则见证数据所包含的哈希值数据大小约能减小 3 倍(编者注:中译本见文末《二进制状态树实验》),这时候合约代码量就成为构成见证大小的第一大头了。

通过 EVM 代码默克尔化缩减见证数据大小

- 图表显示最近 50000 个主网区块的无状态区块见证大小变化,经过窗口 = 128个区块的移动平均计算 (数据来自 https://github.com/mandrigin/ethereum-mainnet-bin-tries-data)-

不要发送整段代码

我们假设,其实每笔交易只会调用部分的合约代码(例如只调用 4 个函数中的 2 个),所以我们的目标就是拆分这些代码块(chunk),每次交易只发送需要的 chunk(以及相应的有效性证明)的区块见证。如果这种假设合理,而且每笔交易真的只用到一小部分字节码(剧透:历史数据表示的确这样),那么区块见证的合约代码部分就能大大的减小。

为了更好地理解,想象我们正在部署一份新的合约,我们需要传递代码和并确定 basic block (详见此处算法)。请注意,为了进行 JUMPDEST 分析,客户端已经传递过一次代码,因此这次传递不会增加开销。这些 basic block(译者注:指只有一个入口且只有一个出口的代码块,没有跳转进入,也没有跳转退出)有两种特性:

通过 EVM 代码默克尔化缩减见证数据大小

- 字节码的 basic blocks(假想的)-

  • Basic block 要么从索引 0 开始,要么从 JUMPDEST 开始 —— 这么做能保证每个无状态客户端都能安全地进行 JUMPDEST 分析(不只如此)。
  • 每个 basic block 都无法更改控制流(例如没有 jump 操作码)。因此,我们可以确定一旦开始执行代码,只会存在两种情况:正确执行结束,或是 gas 耗尽。虽然还没有和其他方案进行比较,我们先假设这么执行是相对更有效率的。

出于效率考量,我们合并相邻块,直到每个代码块都至少有 128 字节(可自行设置)为止。接着以第一个字节作为 key,将这些合并后的代码块插进 Trie(树状数据结构)。最后,客户端将此 Trie 的根作为该合约账户的新记录存储下来。如下图所示,记录代码的 Trie 会成为状态树的子树(类似于 “存储树”)。

通过 EVM 代码默克尔化缩减见证数据大小

- 代码默克尔化之后,会成为状态树(state trie)的子树( sub-tree )。为了简化,上图我用了二进制树 (而非以太坊使用的默克尔-帕特里夏树),同时树的路径也不准确,不能完整表示真实的 key -

为了测试部署的合约,我们试着发起一笔调用该合约的交易。矿工会执行这笔交易,并标记执行过程中触及的每个 chunk(例子里假设触及 chunk#1 和 chunk#3 )。当要发布区块的时候,矿工会将合约状态的证明,以及触及哪些代码 chunk 的 turboproof 证明,一起打包在区块内。

通过 EVM 代码默克尔化缩减见证数据大小

- 交易所触及的所有 chunk 和验证 codeRoot 所需的哈希值,都会以 turboproof 证明的形式发送出去-

收到这个区块后,无状态客户端就能验证合约是否属于区块状态的一部分,也能验证合约的余额、nonce 、状态根、 codeRoot 等其他参数。这些信息足以让客户端从 chunk 中重构部分字节码,同时清空其他不需要的 chunk 。因为 chunk 算法的设计,所以客户端知道所有的 chunk(除了首个 chunk )都是从 JUMPDEST 开始,因此能够安全地进行jump操作。

通过 EVM 代码默克尔化缩减见证数据大小

- 我们可以通过 turboproof 重构字节码;对于交易不需要的 chunk 则设为 0 -

实验

为了验证,我们编写了一份测试原型,该原型可以从 Geth 客户端的 RPC 端口获取主网的区块和过去的状态,然后模拟执行交易。每当执行过程中遇到新的合约,就将合约拆分为多个 chunk,并标记执行交易时触及的 chunk 。当区块中的交易全部执行完毕后,会为所触及的 chunk 生成证明 —— turboproof 。

接着重置状态,用 turboproof 重构出来的代码,替换掉原本的合约代码,然后再次执行刚才的交易。为了检查执行的正确性,我们比较前后两次消耗的 gas 量和区块的 bloom 过滤器。

对最近的 50 个区块执行此过程,我们可以看到合约代码量减少了40% ~ 60%

通过 EVM 代码默克尔化缩减见证数据大小

提醒:上图的数据结果似乎令人充满希望,但请记住,我们还需要成千上万个区块中的数据,才能得出令人信服的实验结论;目前原型处于早期阶段,一切结论都还为时尚早!

后续发展

你应该还记得,每个代码块的最小长度是可设置的参数(文中取的是 128 字节),修改这个参数会在截然不同的两个方面影响见证的大小。假设我们将参数设为 32 字节,则 chunk 的粒度变得更小,要传递的代码量也就变得更少。但是这样一来, Trie 的深度就必须增加;换句话说,为了生成 chunks 的证明,我们需要进行更多次哈希运算。

所以下一步,我们将会深入分析——究竟要将区块最小长度设为多少,才能获得最优解。当然不论如何,只要将 hexary 字典树结构二进制 Trie ,我们就能减少 3/4 的哈希运算(详见此处),从而降低见证数据的大小。

在测试原型中,我们将合约代码拆分为 basic block;而可选的代码拆分算法当然有很多,有的简单有的复杂。最简单的一种就是拆分为固定大小的 chunk(比如,32 bytes/chunk),从目前来看,这种方法只会有 push 和 jumpdest 分析的问题。

更进一步地说,如果我们任意设置字节码的最小值,则客户端在收到 chunk 之后,可能会因为 PUSH 操作或任何多字节码的操作,而碰上 JUMPDEST ( 0x5b ) 报错的情况。如下图所示,有完整代码的客户端会发现这里的 jump 操作是非法的,因为 0x5b 属于 PUSH1 的操作数,执行到这里应该终止。但如果客户端只收到 chunks #6 和 #8,而没有收到 #7 ,则他会跳到位置 41 继续执行,就产生了对同一份合约代码的不同解释。后面我们会扼要地说明怎么在任意设置字节码的情况下,避免这种错误。

通过 EVM 代码默克尔化缩减见证数据大小

为了解决这个问题,Martin Holst Swende 建议向每个 chunk 添加一个元数据,该元数据记录了有多少个 chunk 的首字节是 push 操作;然后,验证者就能在 jumpdest 分析过程中跳过那些字节。Alexey 正在探索的另一种方法是 “不允许在 EVM 中进行动态跳转操作”(至少,不允许使用代码默克尔化的合约进行跳转操作),这使我们只需在部署合约时做一次静态的跳转分析,而不需要在每次执行代码时进行。Alex Beregszaszi建议使用合约控制流程图,以更好地规范默克尔化流程;与之类似,Christian Reitweissner 提出了一种执行证明方法,从合约的控制流程图创建默克尔 DAG(有向无环图)。我不会在本文中评价这些想法,希望之后能披露更多信息。

最终结果可能表明,不同的 chunk 拆分算法之间的效率提升可以忽略不计,这么一来选择的算法就越简单越好。而好消息是,基于早期数据实验,我们至少有一种算法可以显著减少无状态区块中需要传输的代码量。

本文着重讨论如何默克尔化 EVM 字节码,但总体思路并不局限于 EVM 。实际上, Ewasm 团队的其他成员也在尝试默克尔化 Wasm 代码,也遇到了相应的挑战。这些挑战主要是因为 Wasm 代码由多个部分组成,并且在执行之前需要经过严格的验证——这意味着重构的字节码也必须通过验证。

敬请期待后续更多信息!

原文链接: https://medium.com/ewasm/evm-bytecode-merklization-2a8366ab0c90

本文来自,仅作分享,存在异议请联系平台删除。本文观点不代表刺猬财经 - 刺猬区块链资讯站立场。

(0)
上一篇 2020年5月5日 下午2:39
下一篇 2020年5月5日

相关推荐