EIP-1829: 椭圆曲线线性组合的预编译

椭圆曲线线性组合的预编译

简单总结

目前 EVM 仅通过 ecrecover 以有限的方式支持 secp256k1，并通过两个预编译支持 altbn128。有一些提案草案添加了更多的曲线。还有许多椭圆曲线具有有用的应用，可用于与现有系统集成或为零知识证明新开发的曲线。

此 EIP 添加了一个预编译，允许使用整个类别的曲线。

摘要

一个预编译，它接受一个曲线并计算曲线点的线性组合。

动机

规格

给定整数 m, α 和 β，标量 s_i，以及曲线点 A_i，构造椭圆曲线

y² = x³ + α ⋅ x + β  mod  m

并计算以下内容

C = s₀ ⋅ A₀ + s₁ ⋅ A₁ + ⋯ + s_n ⋅ A_n

又名线性组合、内积、多重乘法甚至多重指数运算。

(Cx, Cy) := ecmul(m, α, β,  s0, Ax0, As0, s1, Ax1, As1, ...)

Gas 消耗

BASE_GAS = ...
ADD_GAS  = ...
MUL_GAS  = ...

总 gas 消耗为 BASE_GAS 加上每个 s_i 为 1 的 ADD_GAS，以及每个 s_i > 1 的 MUL_GAS（s_i = 0 是免费的）。

点的编码

编码为 (x, y')，其中 s 指示是否应采用 y 或 -y。它遵循 SEC 1 v 1.9 2.3.4，只是不支持未压缩的点 (y' = 0x04)。

从仿射坐标到压缩坐标的转换很简单：y' = 0x02 | (y & 0x01)。

特殊情况

坐标恢复。 设置 s₀ = 1。输出将是 A₀ 的恢复坐标。

链上检查。 进行坐标恢复并比较 y 坐标。

加法。 设置 s₀ = s₁ = 1，输出将是 A₀ + A₁。

倍增。 设置 s₀ = 2。输出将是 2 ⋅ A₀。（注意：在当前的 gas 模型下，这可能比自加法更昂贵！）

标量乘法。 仅设置 s₀ 和 A₀。

模平方根。 设置 α = s₀ = A = 0，输出将具有 Cy² = β mod m。

边界情况

• 非素数模数或太小的模数
• 字段元素大于模数
• 曲线具有奇异点 (4 α³ + 27 β² = 0)
• 无效的符号字节
• x 坐标不在曲线上
• 返回无穷远点
• （如果您发现更多，请添加）

原理

通用字段和曲线。 许多重要的优化独立于所使用的字段和曲线。一些错过的特定优化是：

• 专门针对字段素数的二进制结构的约简。
• 蒙哥马利因子的预计算。
• 预先计算某些流行点的倍数，例如生成器。
• α = -3、α = -1、α = 0、β = 0 的特殊点加法/倍增 公式。

TODO：α 和 β 的特殊情况可能值得实现并提供 gas 折扣。

压缩坐标。 压缩坐标允许合约仅使用 x 坐标和符号字节。它还可以防止点不在曲线上的错误。转换为压缩坐标很简单。

线性组合。 我们可以改为进行简单的乘法运算 C = r ⋅ A。在这种情况下，我们需要为加法进行单独的预编译。此外，线性组合允许像 Shamir’s trick 这样的优化，这些优化在单个标量乘法中不可用。 ECDSA 需要 s₀ ⋅ A₀ + s₁ ⋅ A₁ 并且会从中受益。

EIP-196 预编译引入的 BN254（又名 alt_bn8）乘法运算仅处理单个标量乘法。错过的性能是，对于两个或更多个点，使用 EVM 更便宜，正如 Weierstrudel 实际演示的那样。

可变时间数学。 在交易期间调用时，不存在隐私假设，也不需要缓解侧信道攻击。

素数域。 此 EIP 适用于大特征的域。它不涵盖二进制域和其他非素数特征的域。

256 位模数。 此 EIP 适用于小于 2^{256} 的字段模数。这涵盖了许多流行的曲线，同时仍然使所有参数都适合单个 EVM 字。

TODO：考虑一个双字版本。 512 位将涵盖除 E-521 之外的所有已知曲线。特别是，它将涵盖爱沙尼亚 e-Identity 使用的 NIST P-384 曲线和 ZCash Sappling 使用的 BLS12-381 曲线。

Short Weierstrass 曲线。 此 EIP 适用于以 Short Weierstrass 形式指定的字段。虽然可以通过变量替换将任何曲线转换为 Short Weierstrass 形式，但这会错过那些特定形式的性能优势。

向后兼容性

测试用例

实现

将有一个基于现有库（特别是 ZCash 和 The Matter Inc. 的库）的 Rust 参考实现。

参考实现将是生产级的，并编译为具有 C api 和 webassembly 版本的本机库。 鼓励 Node 开发人员使用参考实现，并且可以使用 rust 库、本机 C 绑定或 webassembly 模块。当然，Node 开发人员可以随时决定实现自己的实现。

参考

此 EIP 的范围与以下内容重叠

• EIP-196：altbn128 的 ecadd、ecmul
• EIP issue 603：SECP256k1 的 ecadd、ecmul。
• EIP-665：ED25519 的 ECDSA 验证。
• EIP-1108：优化 altbn128 的 ecadd 和 ecmul。

版权

在 CC0 下放弃版权和相关权利。

Citation

Please cite this document as:

Remco Bloemen <Recmo@0x.org>, "EIP-1829: 椭圆曲线线性组合的预编译 [DRAFT]," Ethereum Improvement Proposals, no. 1829, March 2019. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-1829.