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


摘要:

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

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

巨大的无状态区块

代码默克尔化的概念已经被提出好一阵子了,一开始主要用于代码去重,但其他用途还未被很好地探索。现在它重新进入大众视线,却是因为另一个目的 —— 用于降低无状态客户端所需要的带宽开销。为求简短扼要,我不会深入整个无状态客户端模型的细节,仅提供相关细节的简要总结(如果你早已了解相关的背景,可以跳过下一段的内容)。

在无状态模式下,(至少有部分)节点可以依赖其他节点(例如矿工节点)来取得区块内容(包含合约代码)并使用相关默克尔证明加以验证,而不必自己存储所有区块状态 —— 这会给网络带宽带来巨大的性能提升。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

作者: Sina Mahmoodi

翻译&校对: IAN LIU & 阿剑

本文来自网络,不代表吾所求区块链新闻网立场,转载请注明出处:http://www.wusuoqiu.cn/character/10225.html
分享到