Alert Source Discuss
Standards Track: Core

EIP-196: alt_bn128 椭圆曲线上加法和标量乘法的预编译合约

Authors Christian Reitwiessner <chris@ethereum.org>
Created 2017-02-02

Table of Contents

简述

为了在区块 gas 限制内执行 zkSNARK 验证，需要用于椭圆曲线运算的预编译合约。

摘要

此 EIP 建议为特定配对友好椭圆曲线上的加法和标量乘法添加预编译合约。这可以与 EIP-197 结合使用，以验证 Ethereum 智能合约中的 zkSNARK。zkSNARK 对 Ethereum 的一般好处是，它将提高用户的隐私（由于零知识属性），并且也可能是一种可扩展性解决方案（由于简洁性和高效的可验证性）。

动机

目前 Ethereum 上的智能合约执行是完全透明的，这使得它们不适用于涉及私人信息（如位置、身份或过去交易历史）的几种用例。zkSNARK 技术可能是解决此问题的方法。虽然以太坊虚拟机理论上可以使用 zkSNARK，但它们目前太昂贵，无法适应区块 gas 限制。因此，此 EIP 建议为某些启用 zkSNARK 的基本原语指定某些参数，以便可以更有效地实现它们并降低 gas 成本。

请注意，虽然固定这些参数可能看起来像限制 zkSNARK 的用例，但这些原语非常基本，可以以足够灵活的方式组合，甚至可以在不需要进一步硬分叉的情况下允许 zkSNARK 研究的未来进展。

规范

如果 block.number >= BYZANTIUM_FORK_BLKNUM，则为椭圆曲线 “alt_bn128” 上的点加法 (ADD) 和标量乘法 (MUL) 添加预编译合约。

ADD 的地址：0x6 MUL 的地址：0x7

曲线定义为：

Y^2 = X^3 + 3
在域 F_p 上，其中
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

编码

字段元素和标量编码为 32 字节的大端数字。曲线点编码为两个字段元素 (x, y)，其中无穷远点编码为 (0, 0)。

对象的元组编码为它们的串联。

对于两个预编译合约，如果输入短于预期，则假定它在末尾虚拟填充零（即与 CALLDATALOAD 操作码的语义兼容）。如果输入长于预期，则忽略末尾多余的字节。

返回数据的长度始终按指定（即，它不是“未填充”）。

确切的语义

无效输入：对于两个合约，如果任何输入点不位于曲线上，或者任何字段元素（点坐标）等于或大于字段模数 p，则合约失败。标量可以是 0 和 2**256-1 之间的任何数字。

ADD

输入：两个曲线点 (x, y)。 输出：曲线点 x + y，其中 + 是上面指定的椭圆曲线 alt_bn128 上的点加法。 在无效输入时失败并消耗所有提供的 gas。

MUL

输入：曲线点和标量 (x, s)。 输出：曲线点 s * x，其中 * 是上面指定的椭圆曲线 alt_bn128 上的标量乘法。 在无效输入时失败并消耗所有 gas。

Gas 成本

  • ECADD 的 Gas 成本：500
  • ECMUL 的 Gas 成本：40000

理由

之所以选择特定的曲线 alt_bn128，是因为它特别适合 zkSNARK，或者更具体地说，是配对函数的验证构建块。此外，通过选择此曲线，我们可以利用与 ZCash 的协同效应，并重复使用它们的一些组件和工件。

添加曲线和字段参数到输入的功能已被考虑，但最终被拒绝，因为它使规范复杂化：gas 成本更难确定，并且可以在不是实际椭圆曲线的东西上调用合约。

选择非紧凑点编码是因为它仍然允许在智能合约本身中执行某些操作（包括完整的 y 坐标），并且可以比较两个编码点的相等性（没有第三个投影坐标）。

向后兼容性

与引入任何预编译合约一样，已经使用给定地址的合约将更改其语义。因此，这些地址取自 256 以下的“保留范围”。

测试用例

要测试的输入：

  • 如果数字采用 mod p，则有效的曲线点（应失败）。
  • 两个合约都应在空输入上成功。
  • 导致有效曲线点的截断输入。
  • 不在曲线上的点（但以其他方式有效）。
  • 将点乘以位于群的阶和字段之间的标量（应成功）。
  • 将点乘以大于字段阶的标量（应成功）。

实现

这些原语的实现可在此处获得：

在这两个代码库中，使用了曲线 alt_bn128 上的特定组，称为 G1。

  • Python - 可能是最独立的，也是最易读的。

版权

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

Citation

Please cite this document as:

Christian Reitwiessner <chris@ethereum.org>, "EIP-196: alt_bn128 椭圆曲线上加法和标量乘法的预编译合约," Ethereum Improvement Proposals, no. 196, February 2017. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-196.