Alert Source Discuss
🚧 Stagnant Standards Track: Core

EIP-2926: 基于块的代码 Merkle 化

Authors Sina Mahmoodi (@s1na), Alex Beregszaszi (@axic)
Created 2020-08-25
Discussion Link https://ethereum-magicians.org/t/eip-2926-chunk-based-code-merkleization/4555
Requires EIP-161, EIP-170, EIP-2584

Table of Contents

摘要

代码 Merkle 化，以及 trie 的二元化和状态访问操作码的 gas 成本增加，被认为是无状态或部分无状态 Eth1x 路线图中减少区块见证大小的主要手段。在这里，我们指定了一种固定大小的块方法来进行代码 Merkle 化，并概述了现有合约向此模型过渡的方式。

动机

字节码目前是区块见证大小的第二大贡献者，仅次于证明哈希。将 trie 从十六进制过渡到二进制可以减少见证的哈希部分 3 倍，从而使代码成为第一大贡献者。通过将合约代码分解为块并在 Merkle 树中提交这些块，无状态客户端只需要在给定交易期间涉及的块来执行它。

规范

本规范假定已部署 EIP-2584，并相应地提出了 Merkle 化规则和 gas 成本。以下内容分为两个部分：

  1. 给定合约代码如何拆分为块然后进行 Merkle 化
  2. 如何在硬分叉期间对所有现有合约代码进行 Merkle 化

常量和定义

常量

  • CHUNK_SIZE: 32 (字节)
  • KEY_LENGTH: 2 (字节)
  • MAX_CHUNK_COUNT: 0xfffc
  • VERSION_KEY: 0xfffd
  • CODELEN_KEY: 0xfffe
  • CODEHASH_KEY: 0xffff
  • VERSION: 0
  • EMPTY_CODE_ROOT: 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (==keccak256(''))
  • HF_BLOCK_NUMBER: 待定义

定义

  • BE(x, N): 将 x 强制转换为 N 字节的无符号整数，并返回其大端表示

代码 Merkle 化

对于具有代码 C 的帐户记录 A，字段 A.codeHash 将被 codeRoot 替换。如果 C 为空，则 codeRoot 为 EMPTY_CODE_ROOT。否则，它包含 codeTrie 的根，这是一个具有以下叶子节点的二叉树：

  • 键: VERSION_KEY, 值: BE(VERSION, 1)
  • 键: CODELEN_KEY, 值: BE(length(C), 4)
  • 键: CODEHASH_KEY, 值: keccak256(C)

除此之外, codeTrie 提交到一个代码列表 chunks = [(FIO_0, code_0), ..., (FIO_n, code_n)], 这些代码以如下方式从 C 中派生:

  • n < MAX_CHUNK_COUNT.
  • code_0 || ... || code_n == C.
  • length(code_i) == CHUNK_SIZE 其中 0 <= i < n.
  • length(code_n) <= CHUNK_SIZE.
  • FIO_i 是块内第一条指令的偏移量。只有当 code_i-1 中的最后一条指令是跨越块边界的多字节指令（如 PUSHN）时，它才应大于 0。如果一个块的所有字节都是数据，则将其设置为 CHUNK_SIZE。

chunks 的第 i 个元素存储在 codeTrie 中，使用：

  • 键: BE(i, KEY_LENGTH)
  • 值: BE(FIO_i, 1) || code_i, 其中 || 表示按字节连接

合约创建 gas 成本

目前，通过合约创建操作（无论是通过 CREATE、CREATE2 还是外部交易发起）存储在状态中的代码，每字节收取 200 gas 的费用。这个每字节的成本将从 200 增加到 TBD，以弥补分块和 Merkle 化的成本。

更新现有代码（过渡过程）

过渡过程包括读取状态中的所有合约并将上述过程应用于它们。显示此过程需要多长时间的基准测试仍在进行中，但直观上，它应该比两个区块之间的时间更长（按小时计算）。因此，我们建议客户端在 EIP 激活之前预处理更改。

代码具有它(大部分)是静态的良好属性. 因此，客户端可以维护一个 [accountAddress -> codeRoot] 的映射，该映射存储它们已 Merkle 化的合约的结果。在此预计算阶段，每当创建新合同时，都会计算其 codeRoot 并将其添加到映射中。每当合约自毁时，其相应的条目将被删除。

在 EIP 激活的区块 HF_BLOCK_NUMBER 处，在执行任何交易之前，客户端必须更新状态中所有具有非空代码的合约的帐户记录，以将 codeHash 字段替换为预先计算的 codeRoot。EoA 帐户将保留其 codeHash 值作为 codeRoot。具有空代码的帐户将保留其 codeHash 值作为 codeRoot。

理由

十六进制与二进制 trie

Ethereum 主网状态目前以十六进制 Merkle Patricia 树的形式编码。作为 Eth1x 路线图的一部分，已经研究了向二叉树的过渡，目的是减少见证大小。由于代码块也存储在 trie 中，因此该 EIP 将受益于二元化所提供的见证大小减少。因此，我们已决定明确声明 EIP-2584 是此更改的要求。请注意，如果在硬分叉之前包含代码 Merkle 化，则在二进制转换之后必须对所有代码进行重新 Merkle 化。

块大小

当前推荐的 32 字节块大小是基于一些观察结果选择的。较小的块更有效（即具有更高的块利用率），但由于更高的 trie 深度，会产生更大的哈希开销（即作为证明一部分的哈希数量）。较大的块效率较低，但哈希开销较小。我们计划运行一个更大的实验，比较各种块大小，以得出最终建议。

第一条指令偏移量

当客户端没有所有块时（例如，接收块见证的无状态客户端），firstInstructionOffset 字段允许安全的 jumpdest 分析。

注意：在计算块的 FIO 时，可能会出现一种极端情况，即字节码末尾（最后一个块）的数据字节类似于多字节指令。这种情况可以安全地忽略。

代码访问操作码的 Gas 成本

Merkle 化代码如何在客户端数据库中存储会影响代码访问操作码的性能，即：CALL，CALLCODE，DELEGATECALL，STATICCALL，EXTCODESIZE，EXTCODEHASH 和 EXTCODECOPY。将代码 trie 与数据库中的所有中间节点一起存储意味着需要多次查找以获取被调用者的代码，这比当前所需的一次查找（不包括用于获取帐户的 trie 遍历）要多。请注意，CODECOPY 和 CODESIZE 不受影响，因为当前合约的代码已经加载到内存中。

本节中的 Gas 成本分析假设了一种特定的存储方式。在这种方法中，客户端仅在创建期间对代码进行一次 Merkle 化以计算 codeRoot，然后丢弃这些块。相反，它们将完整的字节码以及元数据字段存储在数据库中。我们认为，通过无状态模型中的见证计量，可以更轻松地解决每次调用的分块计量问题。

不同的分块逻辑

我们考虑了另一种打包块的选项，其中每个块都以其 chunkLength 开头，并且仅包含完整的操作码（即，任何不适合 CHUNK_SIZE 的多字节操作码都将推迟到下一个块）。

与指定的块相比，此方法具有缺点： 1) 需要更大的 CHUNK_SIZE – 至少 33 个字节才能容纳 PUSH32 指令。 2) 它更浪费。例如，DUP1 PUSH32 <32-byte payload> 将被编码为两个块，第一个块仅包含 DUP1，第二个块仅包含带有其有效负载的 PUSH32 指令。 3) 计算块的数量并非易事，必须将其显式存储在元数据中。

此外，我们还审查了许多其他选项（基于基本块、Solidity 子程序（需要确定控制流）、EIP-2315 子程序）。但是，此 EIP 仅关注基于块的选项。

RLP 和 SSZ

为了与二进制转换提案保持一致，我们避免使用 RLP 来序列化叶子值。此外，我们还考虑了使用 SSZ 进行数据序列化和 Merkle 化，并对采用它持开放态度，但为了简单起见，决定使用二叉树格式。

元数据字段

添加元数据字段 version、codeLen 和 codeHash 主要是为了在无状态范例中更经济地实现 EXTCODESIZE 和 EXTCODEHASH。版本字段允许区分未来字节码类型（例如，EVM1.5/EIP-615，EIP-2315 等）或代码 Merkle 化方案（或 Merkle 化设置，例如更大的 CHUNK_SIZE）。

可以将 codeHash 和 codeSize 编码在元数据中，也可以将它们作为帐户的一部分。我们认为，元数据是一个更简明的选择，因为 EoA 不需要这些字段，从而导致额外的逻辑（在帐户中省略这些字段）或计算（将它们包含在 Merkle 化帐户中）。

版本字段的替代选项是添加帐户级别字段：要么遵循 EIP-1702，要么添加 accountKind 字段（具有潜在选项：eoa、merkleized_evm_chunk32、merkleized_eip2315_chunk64 等）作为帐户的第一个成员。这样做的一个好处是可以省略 EoA 的 codeHash。

代码 trie 中的键（和 KEY_LENGTH）

如上面的规范中所述，代码 trie 中的键是 chunks 数组的索引。键长度为 2 字节意味着 trie 可以寻址 65536 - 3（减去元数据字段）个块，这对应于 ~2Mb 代码大小。这允许将来大致增加 ~85 倍的代码大小限制，而无需更改 Merkle 化。

EoA 的 codeRoot 的替代值

此提案更改了帐户的第四个字段（codeHash）的含义。在此更改之前，该字段表示字节码的 Keccak-256 哈希，对于 EoA 来说，逻辑上是空输入的哈希。

由于 codeHash 被 codeRoot 替换，即代码 trie 的根哈希，因此对于 EoA，该值在新规则下会有所不同：codeTrie(metadata=[codeHash=keccak256(''), codeSize=0]) 的根。另一种方法是简单地使用空 trie 的哈希。或者，为了避免引入另一个常量（上述结果），也可以考虑为 EoA 使用 codeRoot = 0。

但是，我们希望保持与 EIP-1052 的兼容性，并决定通过为 EoA 使用空输入的哈希（c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470）来简化问题。

向后兼容性

从合约的角度来看，该设计旨在是透明的，除了 gas 成本的变化。

除了为合约提供的接口之外，该提案还对合约代码的存储方式进行了重大更改，并且需要对 Ethereum 状态进行大量修改。因此，它只能通过硬分叉引入。

测试用例

待定

显示以下情况的 codeRoot：

  1. code=''
  2. code='PUSH1(0) DUP1 REVERT'
  3. code='PUSH32(-1)'（数据通过块边界传递）

实现

Typescript 中分块和 Merkle 化逻辑的实现可以在此处找到，Python 中的实现可以在此处找到。请注意，这两个示例目前都不使用二叉树。

安全注意事项

待定

版权

版权和相关权利通过 CC0 放弃。

Citation

Please cite this document as:

Sina Mahmoodi (@s1na), Alex Beregszaszi (@axic), "EIP-2926: 基于块的代码 Merkle 化 [DRAFT]," Ethereum Improvement Proposals, no. 2926, August 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2926.