EIP-198: 大整数模幂运算

参数

• GQUADDIVISOR: 20

规范

在地址 0x00……05 处，添加一个预编译合约，它期望以下格式的输入：

<length_of_BASE> <length_of_EXPONENT> <length_of_MODULUS> <BASE> <EXPONENT> <MODULUS>

其中每个 length 都是一个 32 字节的左侧填充整数，表示下一个值占用的字节数。假设调用数据无限地在右侧填充零字节，并忽略多余的数据。消耗 floor(mult_complexity(max(length_of_MODULUS, length_of_BASE)) * max(ADJUSTED_EXPONENT_LENGTH, 1) / GQUADDIVISOR) gas，并且如果有足够的 gas，则返回一个输出 (BASE**EXPONENT) % MODULUS，作为一个字节数组，其长度与模数相同。

ADJUSTED_EXPONENT_LENGTH 定义如下。

• 如果 length_of_EXPONENT <= 32，并且 EXPONENT 中的所有位均为 0，则返回 0
• 如果 length_of_EXPONENT <= 32，则返回 EXPONENT 中最高位的索引（例如，1 -> 0，2 -> 1，3 -> 1，255 -> 7，256 -> 8）。
• 如果 length_of_EXPONENT > 32，则返回 8 * (length_of_EXPONENT - 32) 加上 EXPONENT 的前 32 个字节中最高位的索引（例如，如果 EXPONENT = \x00\x00\x01\x00.....\x00，有一百个字节，那么结果是 8 * (100 - 32) + 253 = 797）。如果 EXPONENT 的前 32 个字节全部为零，则精确返回 8 * (length_of_EXPONENT - 32)。

mult_complexity 是一个旨在近似 Karatsuba 乘法（用于所有主要的 bigint 库）难度的函数，定义如下。

def mult_complexity(x):
    if x <= 64: return x ** 2
    elif x <= 1024: return x ** 2 // 4 + 96 * x - 3072
    else: return x ** 2 // 16 + 480 * x - 199680

例如，输入数据：

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000020
0000000000000000000000000000000000000000000000000000000000000020
03
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

表示指数 3**(2**256 - 2**32 - 978) % (2**256 - 2**32 - 977)。根据费马小定理，这等于 1，所以结果是：

0000000000000000000000000000000000000000000000000000000000000001

作为 32 字节返回，因为模数长度为 32 字节。ADJUSTED_EXPONENT_LENGTH 将为 255，gas 成本将为 mult_complexity(32) * 255 / 20 = 13056 gas（请注意，这大约是使用 EXP 操作码计算 32 字节指数的成本的 8 倍）。在最坏的情况下，一个 4096 位的 RSA 指数运算将花费 mult_complexity(512) * 4095 / 100 = 22853376 gas，尽管实际上 RSA 验证通常使用 3 或 65537 的指数，这将 gas 消耗分别降低到 5580 或 89292。

这个输入数据：

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000020
0000000000000000000000000000000000000000000000000000000000000020
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

将被解析为底数为 0，指数为 2**256 - 2**32 - 978，模数为 2**256 - 2**32 - 977，因此将返回 0。注意，如果 length_of_BASE 为 0，那么它不会将_任何_数据解释为底数，而是立即将接下来的 32 个字节解释为 EXPONENT。

这个输入数据：

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000020
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd

将解析为长度为 0 的底数，长度为 32 的指数，以及长度为 2**256 - 1 的模数，其中底数为空，指数为 2**256 - 2，模数为 (2**256 - 3) * 256**(2**256 - 33) (是的，这是一个非常大的数字)。然后它会立即失败，因为它不可能提供足够的 gas 来进行计算。

这个输入数据：

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000020
03
ffff
8000000000000000000000000000000000000000000000000000000000000000
07

将被解析为底数为 3，指数为 65535，模数为 2**255，并且会忽略剩余的 0x07 字节。

这个输入数据：

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000020
03
ffff
80

也将被解析为底数为 3，指数为 65535，模数为 2**255，因为它尝试从 0x80 开始获取 32 个字节作为模数 - 但没有更多的数据，所以它用 31 个零字节在右侧填充。

理由

这允许在 EVM 内部进行高效的 RSA 验证，以及其他形式的基于数论的密码学。请注意，不需要为加法和减法添加预编译，因为 EVM 内算法已经足够高效，并且可以通过此预编译通过 a * b = ((a + b)**2 - (a - b)**2) / 4 完成乘法。

基于位的指数计算专门用于公平地收取常用指数 2（用于乘法）和 3 和 65537（用于 RSA 验证）的费用。

版权

版权及相关权利通过 CC0 豁免。

Citation

Please cite this document as:

Vitalik Buterin (@vbuterin), "EIP-198: 大整数模幂运算," Ethereum Improvement Proposals, no. 198, January 2017. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-198.