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 |
Table of Contents
摘要
本 EIP 提议新的 EVM 模块化算术操作码,它支持对介于 3 和 2**768-1 之间的奇数或二的幂模数进行运算。
动机
当前的模块化算术操作码仅支持最大 256 位宽的值。此外,它们是允许型的,并且接受输入端的任何可表示值。
许多加密操作都受到模块化算术的严重瓶颈。为了扩展可以作为 EVM 合约有效实现的加密原语的范围,我们提出了新的为效率而设计的模块化算术操作码。
规范
常量
名称 | 值 | 描述 |
---|---|---|
COST_SETMODX_BASE |
1 | SETMODX 操作码的静态成本组成部分 |
COST_STOREX_BASE |
1 | STOREX 操作码的静态成本 |
COST_LOADX_BASE |
1 | LOADX 操作码的静态成本 |
约定
assert
的使用意味着如果断言失败,则当前调用帧将消耗所有调用 gas 并在异常状态下终止调用执行。- 除非另有说明,否则大小的隐含单位是字节。
概述
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_idx
、out_stride
、x_idx
、x_stride
、y_idx
、y_stride
、count
。
基于模数为每个算术运算定义成本表:
模数大小(填充到最接近的 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
。
定义两个值 A
和 B
的 Montgomery 模块化乘法:mulmont(A, B, M): A * B * R**-1 % M
,其中 R**-1 % M
是 R
相对于 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.