EIP-197: 用于在椭圆曲线 alt_bn128 上进行最佳 ate 配对检查的预编译合约

简述

需要用于椭圆曲线配对操作的预编译合约，以便在区块 gas 限制内执行 zkSNARK 验证。

摘要

此 EIP 建议为特定配对友好椭圆曲线上的配对函数添加预编译合约。 这反过来可以与 EIP-196 结合使用，以验证以太坊智能合约中的 zkSNARK。 zkSNARK 对以太坊的总体好处是，它将提高用户的隐私（由于零知识属性），也可能是一种可扩展性解决方案（由于简洁性和高效的可验证性属性）。

动机

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

请注意，固定这些参数绝不会限制 zkSNARK 的用例，它甚至允许整合 zkSNARK 研究中的一些进展，而无需进一步的硬分叉。

配对函数可用于执行有限形式的乘法同态运算，这对于当前的 zkSNARK 是必需的。 此预编译可以用于在区块 gas 限制内运行此类计算。 此预编译合约仅指定特定检查，而不指定配对函数的评估。 原因是配对函数的 codomain 是一个相当复杂的字段，可能会提供编码问题，并且 zkSNARK 中配对函数的所有已知用途仅需要指定的检查。

规范

对于 block.number >= BYZANTIUM_FORK_BLKNUM 的区块，为椭圆曲线“alt_bn128”上的组上的双线性函数添加预编译合约。 我们将根据离散对数定义预编译合约。 当然，离散对数被假定为难以计算，但我们将给出一个等效的规范，该规范利用可以有效计算的椭圆曲线配对函数。

地址：0x8

对于素数阶 q 的循环群 G（以加法形式书写），令 log_P: G -> F_q 为该群上关于生成元 P 的离散对数，即 log_P(x) 是最小的非负整数 n，使得 n * P = x。

预编译合约定义如下，其中两个群 G_1 和 G_2 由它们的生成元 P_1 和 P_2 定义如下。 两个生成元都具有相同的素数阶 q。

Input: (a1, b1, a2, b2, ..., ak, bk) from (G_1 x G_2)^k
Output: 如果输入的长度不正确或者任何输入不是各自组的元素或者未正确编码，则调用失败。
        否则，如果
        log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0
        (在 F_q 中) 则返回 1，否则返回 0。

请注意，k 由输入的长度确定。 按照下面的编码部分，k 是输入长度除以 192。 如果输入长度不是 192 的倍数，则调用失败。 空输入有效并导致返回 1。

为了检查输入是否为 G_1 的元素，验证坐标的编码并检查它们是否满足曲线方程（或者是否为无穷大的编码）就足够了。 对于 G_2，除了这些之外，还必须检查元素的阶是否等于群的阶 q = 21888242871839275222246405745257275088548364400416034343698204186575808495617。

群的定义

群 G_1 和 G_2 是素数阶 q = 21888242871839275222246405745257275088548364400416034343698204186575808495617 的循环群。

群 G_1 定义在字段 F_p 上曲线 Y^2 = X^3 + 3 上，其中 p = 21888242871839275222246405745257275088696311157297823662689037894645226208583，生成元为 P1 = (1, 2)。

群 G_2 定义在不同的字段 F_p^2 = F_p[i] / (i^2 + 1) 上曲线 Y^2 = X^3 + 3/(i+9) 上（p 与上面相同），生成元为

P2 = (
  11559732032986387107991004021392285783925812861821192530917403151452391805634 * i +
  10857046999023057135944570762232829481370756359578518086990519993285655852781,
  4082367875863433681332203403145435568316851327593401208105741076214120093531 * i +
  8495653923123431417604973247489272438418190587263600148770280649306958101930
)

请注意，G_2 是该椭圆曲线在字段 F_p^2 上唯一的阶为 q 的群。 任何其他阶为 q 的生成元而不是 P2 都将定义相同的 G_2。 但是，P2 的具体值对于怀疑存在阶为 q 的群的持怀疑态度的读者很有用。 可以指示他们比较 q * P2 和 P2 的具体值。

编码

F_p 的元素编码为 32 字节的大端数字。 大于或等于 p 的编码值无效。

F_p^2 的元素 a * i + b 编码为 F_p 的两个元素 (a, b)。

椭圆曲线点编码为雅可比对 (X, Y)，其中无穷远点编码为 (0, 0)。

请注意，数字 k 派生自输入长度。

返回数据的长度始终恰好为 32 字节，并编码为 32 字节的大端数字。

Gas 成本

预编译合约的 gas 成本为 80 000 * k + 100 000，其中 k 是点的数量，或者等效地，是输入长度除以 192。

理由

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

考虑了向输入添加曲线和字段参数的功能，但最终被拒绝，因为它使规范复杂化； gas 成本更难确定，并且可以在不是实际椭圆曲线或不允许高效配对实现的曲线上调用合约。

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

选择以 F_p^2 编码字段元素是为了与元素本身的大端编码保持一致。

向后兼容性

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

测试用例

待撰写。

实现

预编译合约可以使用椭圆曲线配对函数来实现，更具体地说是 alt_bn128 曲线上的最佳 ate 配对，可以有效地实现。 为了看到这一点，首先请注意，配对函数 e: G_1 x G_2 -> G_T 满足以下属性（G_1 和 G_2 以加法形式书写，G_T 以乘法形式书写）：

(1) e(m * P1, n * P2) = e(P1, P2)^(m * n) (2) e 是非退化的

现在观察到

log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0 (在 F_q 中)

当且仅当

e(P1, P2)^(log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk)) = 1 (在 G_T 中)

此外，该等式的左侧等于

e(log_P1(a1) * P1, log_P2(b1) * P2) * ... * e(log_P1(ak) * P1, log_P2(bk) * P2)
= e(a1, b1) * ... * e(ak, bk)

因此，可以通过验证 e(a1, b1) * ... * e(ak, bk) = 1 来实现预编译合约

实现可在此处获得：

• libff (C++)
• bn (Rust)
• Python

版权

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

Citation

Please cite this document as:

Vitalik Buterin <vitalik@ethereum.org>, Christian Reitwiessner <chris@ethereum.org>, "EIP-197: 用于在椭圆曲线 alt_bn128 上进行最佳 ate 配对检查的预编译合约," Ethereum Improvement Proposals, no. 197, February 2017. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-197.