Alert Source Discuss
🚧 Stagnant Standards Track: Core

EIP-6690: EVM 模块化算术扩展

EVM 的扩展宽度、高效模块化算术运算

Authors Jared Wasinger (@jwasinger), Alex Beregszaszi (@axic), Vitalik Buterin (@vbuterin), Radosław Zagórowicz (@rodiazet), Paweł Bylica (@chfast)
Created 2023-03-15
Discussion Link https://ethereum-magicians.org/t/eip-6690-evm-modular-arithmetic-extensions/13322

摘要

本 EIP 提议新的 EVM 模块化算术操作码,它支持对介于 3 和 2**768-1 之间的奇数或二的幂模数进行运算。

动机

当前的模块化算术操作码仅支持最大 256 位宽的值。此外,它们是允许型的,并且接受输入端的任何可表示值。

许多加密操作都受到模块化算术的严重瓶颈。为了扩展可以作为 EVM 合约有效实现的加密原语的范围,我们提出了新的为效率而设计的模块化算术操作码。

规范

常量

名称 描述
COST_SETMODX_BASE 1 SETMODX 操作码的静态成本组成部分
COST_STOREX_BASE 1 STOREX 操作码的静态成本
COST_LOADX_BASE 1 LOADX 操作码的静态成本

约定

  1. assert 的使用意味着如果断言失败,则当前调用帧将消耗所有调用 gas 并在异常状态下终止调用执行。
  2. 除非另有说明,否则大小的隐含单位是字节。

概述

EVM 调用帧的执行状态被修改为包括 id(一个 0-256 的数字)到字段上下文的映射。字段上下文包括一个模数和一个已分配的虚拟寄存器空间,用于在其上执行模块化算术运算。

正在执行的合约使用新的指令 SETMODX 来设置活动字段上下文,如果在映射中 id 尚不存在该上下文,则分配一个新的上下文。

新的算术操作码使用来自活动字段上下文的虚拟寄存器的输入/输出执行模块化加法、减法和乘法。

新的加载/存储操作码将值复制到 EVM 内存和活动字段上下文分配的虚拟寄存器,以及从其中复制值。

新的操作码

SETMODX(0xc0)

输入<堆栈顶部> id modulus_offset modulus_size alloc_count

输出:无

执行

收取 COST_SETMODX_BASE

断言 0 <= id <= 256

如果 id 的某个字段上下文存在于此调用范围内:

  • 将其设置为活动上下文。

否则:

  • 断言 modulus_size <= 96
  • 断言字节范围 [modulus_offset, modulus_offset+modulus_size] 位于 EVM 内存中。
  • 从 EVM 内存加载字节范围,将其解释为大端 modulus
  • 断言 modulus 是奇数或为二的幂。
  • 断言 3 <= modulus <= 2**768 - 1
  • 断言 0 < alloc_count <= 256
  • 定义存储在虚拟寄存器中的元素的大小:element_size 作为表示模数所需的大小,并填充为 64 位的倍数。实现将沿系统字线对齐虚拟寄存器值。
  • 断言当前调用上下文中分配的所有虚拟寄存器的新大小不超过 24576 字节。
  • 收取 EVM 内存扩展成本,以将内存扩展 alloc_count * element_size 字节:。
  • 如果模数是奇数,则收取动态成本组成部分(如下定义)
  • 分配带有 alloc_count 个初始归零寄存器的新字段上下文。在映射中将其与 id 关联。
  • 现在,新的字段上下文被设置为活动上下文。
奇数模数的动态成本组成部分
模数大小(填充到最接近的 64 位) 成本
64 位 23
128 位 26
192 位 29
256 位 32
320 位 36
384 位 39
448 位 42
512 位 45
576 位 48
640 位 51
704 位 54
768 位 58

此表中的值基于以下线性成本模型:

def cost_setmodx_dynamic(modulus_size: int) -> int:
    limb_count = (modulus_size + 7) / 8
    return round(limb_count * 3.13 + 19.94)

算术操作码

操作码 ADDMODX(0xc3)SUBMODX(0xc4)MULMODX(0xc5) 采用 7 字节立即数,解释为字节值 out_idxout_stridex_idxx_stridey_idxy_stridecount

基于模数为每个算术运算定义成本表:

模数大小(填充到最接近的 64 位) 每次加/减的成本 每次乘的成本
64 1 1
128 1 1
192 1 1
256 1 2
320 1 2
384 1 3
448 1 4
512 2 5
576 2 7
640 2 8
704 2 10
768 2 12

此表中的值对应于以下成本模型:

def cost_add_or_sub(modulus_size: int) -> int:
    limb_count = (modulus_size + 7) // 8
    return round(limb_count * 0.12 + 0.58)
    
def cost_mul(modulus_size: int) -> int:
    limb_count = (modulus_size + 7) // 8
    return round((0.08 * limb_count**2) + (-0.06 * limb_count) + 0.75)

执行断言:

  • 所有访问的值都在范围内:max([out_idx + (out_stride * count), x_idx + (x_stride * count), y_idx + (y_stride * count)]) < len(field_context.registers)
  • out_stride != 0
  • count != 0
  • 活动字段上下文 active_ctx 已设置。

然后,收取 count * operation_cost,其中 operation_cost 从成本表中提取。计算:

for i in range(count):
    active_ctx.registers[out_idx+i*out_stride] = operation(active_ctx.registers[x_idx+i*x_stride], active_ctx.registers[y_idx+i*y_stride])

其中 operation 根据操作码计算模块化加法、减法或乘法。

注意:输入/输出可以重叠。在循环中的所有操作都完成之前,不会修改 active_ctx.registers

数据传输操作码

注意:EVM 内存中值的序列化格式:大端,填充为 active_ctx.element_size 字节。

LOADX(0xc1)

堆栈输入(堆栈顶部) dest source count

堆栈输出:无

描述:将值从当前活动字段上下文中的寄存器复制到 EVM 内存。

执行
  • 断言在当前调用帧中已将字段上下文设置为活动状态。
  • 断言范围 [source, source + count] 落在活动字段上下文的从零开始的值空间内。
  • 断言范围 [dest, dest + count * active_ctx.element_size] 完全落在 EVM 内存中。
  • 如果模数为二的幂:
    • 收取 (active_ctxt.element_size + 31) // 32 * 3 gas(与 MCOPY 操作码的内存复制组件相同)。
  • 如果模数为奇数:
    • 收取 count * operation_cost gas,其中 operation_cost 从乘法成本表中查找,给定 active_ctxt.element_size
  • 将虚拟寄存器值 [source, source + count] 复制到内存 [dest, dest + count * active_ctx.element_size]
STOREX(0xc2)

堆栈输入dest source count

堆栈输出:无

描述:将值从 EVM 内存复制到当前活动字段上下文的寄存器中。

执行
  • 断言在当前调用帧中已将字段上下文设置为活动状态。
  • 断言 dest + count 小于或等于活动字段上下文的虚拟寄存器的数量。
  • 如果活动上下文的模数为二的幂:
    • 收取 cost_mem_copy(count * active_ctx.element_size)(待定:故意未选择 mcopy gas 模型,以查看是否可以考虑更便宜的模型)。
  • 否则,如果活动上下文的模数为奇数:
    • 收取 count * operation_cost gas,其中 operation_cost 从乘法成本表中查找,给定 active_ctxt.element_size
  • 断言 [source, source + count * active_context.element_size] 完全落在 EVM 内存中。将其解释为 count 个值,断言每个值都小于模数,并将其存储在寄存器 [dest, dest + count] 中。

EVM 内存扩展成本修改

当通过 SETMODX 扩展 EVM 内存或分配新的字段上下文时,扩展成本现在将考虑当前调用帧中所有已分配的虚拟寄存器的大小。

基本原理

分离 EVM 内存和 EVMMAX 虚拟寄存器空间

假设优化后的实现不会以 EVM 兼容的大端序列化格式存储值,而是将其转换为内部工作表示形式。规范中的成本明确反映了选择 Montgomery 形式作为最佳内部表示形式。

以 Montgomery 形式表示的值可以利用优化的模块化归约进行乘法运算。有关更多详细信息,请参阅基本原理中有关 Montgomery 乘法的专用部分。

虚拟寄存器分配总上限

选择 24576 字节作为每次调用上下文的分配限制,目的是确保虚拟寄存器空间可以包含在大多数机器的 L1 CPU 数据缓存中(并留有余地),以便算术运算成本不必考虑内存访问延迟。

SETMODX 成本

对于奇数模数,SETMODX 预先计算用于通过 Montgomery 归约进行优化模块化乘法的两个值。这主要由模数的模块化归约决定,因此成本模型被假定为线性的。

二的幂模数不需要预先计算即可进行优化的模块化算术。

LOADX/STOREX 成本

对于二的幂模数,假定 LOADX/STOREX 在 EVM/EVMMAX 内存之间直接复制值,而无需可测量的转换成本,即可在 EVM 大端序列化和使用的任何内部表示形式之间进行转换。

对于奇数模数,规范假定内部表示形式为 Montgomery 形式。规范/Montgomery 形式之间的转换每个方向上每个值需要一次模块化乘法。内存复制的成本已纳入乘法价格模型中。

算术成本

假定加法/减法/乘法具有恒定时间的实现。加法/减法可以使用线性复杂度来实现,而乘法在模数大小上是二次方的。

二的幂模块化乘法的成本是暂定的,并且可能会在推出并对优化的算术实现进行基准测试时降低。

Montgomery 模块化乘法

对于值 A、奇数模数 M 和值 R(必须与 M 互质且大于 M,选择作为二的幂以提高效率的目的),Montgomery 表示形式为 A * R % M

定义两个值 AB 的 Montgomery 模块化乘法:mulmont(A, B, M): A * B * R**-1 % M,其中 R**-1 % MR 相对于 M 的模块化逆。自 1985 年以来,已经发表了各种用于计算 mulmont 的文献和算法,并且该操作普遍用于执行受到奇数模数运算瓶颈的地方。

请注意,普通的模块化加法和减法算法适用于 Montgomery 形式的值。

规范表示形式到 Montgomery 表示形式的转换

mulmont(canon_val, R**2 % M, M) = mont_val

从 Montgomery 表示形式到规范表示形式的转换

mulmont(mont_val, 1, M) = canon_val

实现

# Basic Montgomery Multiplication
# 基础蒙哥马利乘法
#   x, y, mod (int) - x < mod and y < mod
#   mod (int) - an odd modulus
#   mod (int) - 一个奇数模数
#   R (int) -  a power of two, and greater than mod
#   R (int) - 2 的幂,且大于 mod
#   mont_const (int) - pow(-mod, -1, R), precomputed
#   mont_const (int) - pow(-mod, -1, R), 预先计算
# output:
# 输出:
#  (x * y * pow(R, -1, mod)) % mod
#  (x * y * pow(R, -1, mod)) % mod
#
def mulmont(x: int, y: int, mod: int, monst_const: int, R: int) -> int:
    t = x * y
    m = ((t % R) * mont_const) % R
    t = t + m * mod
    t /= R
    if t >= mod:
        t -= mod
    return t

有用于计算表示为系统字数组的 bigint 数字的Montgomery乘法的各种优化算法。

这些都使用不同的预计算常量 mont_const = pow(-mod, -1, 2**SYSTEM_WORD_SIZE_BITS)

测试用例

Geth 实现中包含一些测试。但是,目前还没有跨客户端测试。

参考实现

在给 Go Ethereum 的一个开放 PR 中,有这个 EIP 的实现。

安全注意事项

版权

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

Citation

Please cite this document as:

Jared Wasinger (@jwasinger), Alex Beregszaszi (@axic), Vitalik Buterin (@vbuterin), Radosław Zagórowicz (@rodiazet), Paweł Bylica (@chfast), "EIP-6690: EVM 模块化算术扩展 [DRAFT]," Ethereum Improvement Proposals, no. 6690, March 2023. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-6690.