EIP-3026: BW6-761 曲线运算

BW6-761 曲线运算的预编译

摘要

此预编译添加了 BW6-761 曲线（来自 EY/Inria 的适用于单层证明组合的优化且安全的配对友好椭圆曲线研究论文）的运算，作为高效执行单层组合 zkSNARKs 证明验证所需的一组预编译。 如果 block.number >= X，我们将引入七个独立的预编译来执行以下操作（地址待定）：

• BW6_G1_ADD - 在素数域上定义的曲线上执行点加法
• BW6_G1_MUL - 在素数域上定义的曲线上执行点乘法
• BW6_G1_MULTIEXP - 在素数域上定义的曲线上执行多重指数运算
• BW6_G2_ADD - 在底为素数域的曲线扭曲上执行点加法
• BW6_G2_MUL - 在素数域上定义的曲线扭曲上执行点乘法
• BW6_G2_MULTIEXP - 在曲线扭曲上执行多重指数运算，曲线扭曲定义在素数域上
• BW6_PAIRING - 在一组 (G1, G2) 点的对之间执行配对运算

多重指数运算是点乘法的推广，但提出了单独的预编译，因为通过 MULTIEXP 运行单个 MUL 似乎会贵 20%。

动机

这个 EIP 基于并且倾向于替换 matter-labs 的方案，因为它具有显着的性能优势。在大多数应用中，BW6-761 用作 EIP-2539 中考虑的 BLS12-377 的外曲线。 此预编译的动机是允许 SNARK 证明的有效单层组合。目前，这由 Zexe 使用 BLS12-377/CP6-782 曲线对完成。此预编译提出了用 BW6-761 替换 CP6-782，这可以实现更快的操作。例如，已经表明，使用 BW6-761 验证 Groth16 证明比使用 CP6-782 快 30 倍。

建议的地址表

规范

曲线参数：

BW6-761 y^2=x^3-1 曲线由以下参数集完全定义：

Base field modulus = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b
A coefficient = 0x0
B coefficient = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008a
Main subgroup order = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
Extension tower:
Fp3 construction: (Fp3 = Fp[u]/u^3+4)
Fp cubic non-residue = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d000000000087
Twist parameters:
Twist type: M
twist curve A coefficient c0 = 0x0
                          c1 = 0x0
twist curve B coefficient c0 = 0x4
                        c1 = 0x0
Generators:
G1:
X = 0x1075b020ea190c8b277ce98a477beaee6a0cfb7551b27f0ee05c54b85f56fc779017ffac15520ac11dbfcd294c2e746a17a54ce47729b905bd71fa0c9ea097103758f9a280ca27f6750dd0356133e82055928aca6af603f4088f3af66e5b43d
Y = 0x58b84e0a6fc574e6fd637b45cc2a420f952589884c9ec61a7348d2a2e573a3265909f1af7e0dbac5b8fa1771b5b806cc685d31717a4c55be3fb90b6fc2cdd49f9df141b3053253b2b08119cad0fb93ad1cb2be0b20d2a1bafc8f2db4e95363
G2:
X = 0x110133241d9b816c852a82e69d660f9d61053aac5a7115f4c06201013890f6d26b41c5dab3da268734ec3f1f09feb58c5bbcae9ac70e7c7963317a300e1b6bace6948cb3cd208d700e96efbc2ad54b06410cf4fe1bf995ba830c194cd025f1c
Y = 0x17c3357761369f8179eb10e4b6d2dc26b7cf9acec2181c81a78e2753ffe3160a1d86c80b95a59c94c97eb733293fef64f293dbd2c712b88906c170ffa823003ea96fcd504affc758aa2d3a3c5a02a591ec0594f9eac689eb70a16728c73b61
Pairing parameters:
e(P,Q)=(ML1(P,Q)*ML2(P,Q)^q)^FE
|loop_count_1| (first miller loop ML1 count) = 0x8508c00000000002
|loop_count_2| (second miller loop ML2 count) = 0x23ed1347970dec008a442f991fffffffffffffffffffffff
loop_count_1 is negative = false
loop_count_2 is negative = false

编码

域元素编码：

要编码操作中涉及的点，必须仅编码基域的元素。

基域元素 (Fp) 被编码为 96 字节，方法是对相应的（无符号）整数执行 BigEndian 编码。对应的整数MUST小于基域模数。

如果在预编译中的任何地方，编码在解析过程中不遵循此规范，则预编译MUST恢复并显示“endoding error”。

未压缩点的编码：

G1 和 G2 中的点都可以表示为 (x, y) 仿射坐标，其中 x 和 y 是基域的元素。 因此，G1 和 G2 中的点被编码为 x 和 y 仿射坐标的域元素编码的字节连接。因此，G1/G2 点的总编码长度为 192 字节。

无穷远点的编码：

也称为“零点”。对于 BW6-761 (y^2=x^3-1) 及其 M 扭曲曲线 (y^3=x^3+4)，坐标为 (0, 0)（Fp 中的形式零）的点不在曲线上，因此 (0, 0) 的编码用作编码无穷远点的约定。

乘法和多重指数运算的标量编码：

对于乘法和多重指数运算，标量被编码为 64 字节，方法是对相应的（无符号）整数执行 BigEndian 编码。

请注意，BW6-761 的主子群阶实际上只有 377 位（48 字节），但是已选择 64 字节的编码以具有 32 字节对齐的 ABI（可表示为例如 bytes32[2] 或 uint256[2]）。

对应的整数MAY大于主子群的阶。

操作的 ABI

G1 加法的 ABI

G1 加法调用需要 384 字节作为输入，这些字节被解释为两个 G1 点（每个点编码为 192 字节）的字节连接。输出是加法运算结果的点编码。

错误情况：

• 任何一个点都不在曲线上
• 输入长度无效
• 字段元素编码规则适用（显然）

G1 乘法的 ABI

G1 乘法调用需要 256 字节作为输入，这些字节被解释为一个 G1 点的点编码（192 字节）和一个标量值编码（64 字节）的字节连接。输出是乘法运算结果的点编码。

错误情况：

• 点不在曲线上
• 输入长度无效
• 字段元素编码规则适用（显然）
• 标量编码规则适用（显然）

G1 多重指数运算的 ABI

G1 乘法调用需要 256*k 字节作为输入，这些字节被解释为 k 个切片的字节连接，每个切片都是一个 G1 点的点编码（192 字节）和一个标量值编码（64 字节）的字节连接。输出是多重指数运算结果的编码。

错误情况：

• 任何 G1 点都不在曲线上
• 输入长度无效
• 字段元素编码规则适用（显然）
• 标量编码规则适用（显然）

G2 加法的 ABI

G2 加法调用需要 384 字节作为输入，这些字节被解释为两个 G2 点（每个点编码为 192 字节）的字节连接。输出是加法运算结果的点编码。

错误情况：

• 任何一个点都不在曲线上
• 输入长度无效
• 字段元素编码规则适用（显然）

G2 乘法的 ABI

G2 乘法调用需要 256 字节作为输入，这些字节被解释为一个 G2 点的点编码（192 字节）和一个标量值编码（64 字节）的字节连接。输出是乘法运算结果的编码。

错误情况：

• 不在曲线上的点必须导致错误
• 字段元素编码规则适用（显然）
• 输入长度无效

G2 多重指数运算的 ABI

G2 乘法调用需要 240*k 字节作为输入，这些字节被解释为 k 个切片的字节连接，每个切片都是 G2 点的编码（192 字节）和一个标量值编码（48 字节）的字节连接。输出是多重指数运算结果的编码。

错误情况：

• 任何 G2 点都不在曲线上必须导致错误
• 字段元素编码规则适用（显然）
• 输入长度无效

配对的 ABI

配对调用需要 384*k 字节作为输入，这些字节被解释为 k 个切片的字节连接。每个切片具有以下结构：

• 192 字节 G1 点编码
• 192 字节 G2 点编码

输出是 32 字节，表示一个布尔值：

• 如果配对结果等于配对目标字段中的乘法单位元，则为 0x0000000000000000000000000000000000000000000000000000000000000001；以及
• 否则为 0x0000000000000000000000000000000000000000000000000000000000000000。

错误情况：

• 任何 G1 或 G2 点都不在曲线上
• 任何 G1 或 G2 点都不在正确的子群中
• 输入长度无效
• 字段元素编码规则适用（显然）

防止错误处理中的 DDoS

此预编译执行大量的计算，并且在执行过程中发生任何错误的情况下，MUST消耗相应操作的所有 gas 计划中的 gas。

Gas 计划

G1 加法

180 gas

G1 乘法

64000 gas

G2 加法

180 gas

G2 乘法

64000 gas

G1/G2 多重指数运算

折扣表作为一对对的向量 [k, discount]：

[[1, 1266], [2, 733], [3, 561], [4, 474], [5, 422], [6, 387], [7, 362], [8, 344], [9, 329], [10, 318], [11, 308], [12, 300], [13, 296], [14, 289], [15, 283], [16, 279], [17, 275], [18, 272], [19, 269], [20, 266], [21, 265], [22, 260], [23, 259], [24, 256], [25, 255], [26, 254], [27, 252], [28, 251], [29, 250], [30, 249], [31, 249], [32, 220], [33, 228], [34, 225], [35, 223], [36, 219], [37, 216], [38, 214], [39, 212], [40, 209], [41, 209], [42, 205], [43, 203], [44, 202], [45, 200], [46, 198], [47, 196], [48, 199], [49, 195], [50, 192], [51, 192], [52, 191], [53, 190], [54, 187], [55, 186], [56, 185], [57, 184], [58, 184], [59, 181], [60, 181], [61, 181], [62, 180], [63, 178], [64, 179], [65, 176], [66, 177], [67, 176], [68, 175], [69, 174], [70, 173], [71, 171], [72, 171], [73, 170], [74, 170], [75, 169], [76, 168], [77, 168], [78, 167], [79, 167], [80, 166], [81, 165], [82, 167], [83, 166], [84, 166], [85, 165], [86, 165], [87, 164], [88, 164], [89, 163], [90, 163], [91, 162], [92, 162], [93, 160], [94, 163], [95, 159], [96, 162], [97, 159], [98, 160], [99, 159], [100, 159], [101, 158], [102, 158], [103, 158], [104, 158], [105, 157], [106, 157], [107, 156], [108, 155], [109, 155], [110, 156], [111, 155], [112, 155], [113, 154], [114, 155], [115, 154], [116, 153], [117, 153], [118, 153], [119, 152], [120, 152], [121, 152], [122, 152], [123, 151], [124, 151], [125, 151], [126, 151], [127, 151], [128, 150]]

max_discount = 150

配对操作

配对操作的基本成本为 120000*k + 320000，其中 k 是对数。

理由

Gas 成本基于 EIP-1962 估算策略（但尚未完全包括 ABI 的解析、结果的解码和编码为字节数组）。

Gas 估算策略

Gas 成本是通过对不同实现上的相同操作进行平均计时并假设常数 30 MGas/second 得出的。由于执行时间是特定于机器的，因此此常数是根据我的机器上 ECRECOVER 和 BNPAIR 预编译的执行时间及其建议的 gas 价格（ECRECOVER 为 43.5 MGas/s，BNPAIR 为 16.5 MGas/s）确定的。以下是用于定时预编译操作的建议方法：

• G1 加法：1000 个随机样本的平均计时。
• G1 乘法：对双加算法的最坏情况的 1000 个样本进行平均计时（最大位长度和最大汉明权重的标量以及 G1 中的随机基点）
• G2 加法：1000 个随机样本的平均计时
• G2 乘法：对双加算法的最坏情况的 1000 个样本进行平均计时（最大位长度和最大汉明权重的标量以及 G2 中的随机基点）
• G1 和 G2 多重指数运算：预计由 Peppinger 算法执行，在多重指数运算中有k <= 128个点的情况下，准备一个折扣表，对于 k > 128，折扣上限为 max_discount。为避免非整数算术调用成本，计算为 k * multiplication_cost * discount / multiplier，其中 multiplier = 1000，k 是调用的（标量，点）对的数量，multiplication_cost 是对应的 G1/G2 的单次乘法调用成本。
• 配对：对线性提升的不同对数的 1000 个随机样本（G1 和 G2 中的随机点）进行平均计时。

多重指数运算作为单独的调用

显式的单独多重指数运算允许通过所使用的算法（即 Peppinger 算法）以及（通常被遗忘的）以太坊中 CALL 操作昂贵的事实来节省执行时间（因此 gas）（在撰写本文时），因此如果例如对于 100 个点的多重指数运算，必须调用乘法预编译 100 次，并且添加 99 次（大约节省 138600）次，则必须支付不可忽略的开销。

显式子群检查

G2 子群检查与 G1 子群检查的成本相同。可以利用自同态来优化此操作。

向后兼容性

不存在向后兼容性问题。

测试用例

由于有大量的测试参数空间，我们首先提供各种操作必须满足的属性。我们使用加法表示法表示点运算，大写字母（P，Q）表示点，小写字母（a，b）表示标量。G1 的生成器标记为 G，G2 的生成器标记为 H，否则我们假设曲线上正确的子组中的随机点。0 表示标量零或无穷远点。1 表示标量一或乘法单位元。group_order 是主子群阶。e(P, Q) 表示配对运算，其中 P 在 G1 中，Q 在 G2 中。

基本运算（加/乘）的所需属性：

• 交换律：P + Q = Q + P
• 加法取反：P + (-P) = 0
• 倍增 P + P = 2*P
• 子群检查：group_order * P = 0
• 微不足道的乘法检查：1 * P = P
• 乘以零：0 * P = 0
• 乘以非规范化标量 (scalar + group_order) * P = scalar * P

配对操作的所需属性：

• 退化 e(P, 0*Q) = e(0*P, Q) = 1
• 双线性 e(a*P, b*Q) = e(a*b*P, Q) = e(P, a*b*Q)（内部测试，通过 ABI 不可见）

参考实现

现有各种实现选择：

库：

• Rust 实现 (EY/Zexe): github.com/yelhousni/zexe/tree/youssef/BW6-761-Fq-ABLR-2ML-M
• C++ 实现 (EY/libff): github.com/EYBlockchain/zk-swap-libff
• Golang 实现 (Consensys/gurvy): github.com/ConsenSys/gurvy

独立实现：

• 带有 Intel 汇编的 Golang 实现 (Onur Kilic): github.com/kilic/bw6

预编译：

• OpenEthereum (EY/Parity): github.com/EYBlockchain/solidity-elliptic-curves
• Frontier (Parity): github.com/paritytech/frontier/pull/1049/files

脚本：

• SageMath 和 Magma 脚本: gitlab.inria.fr/zk-curves/bw6-761/

安全注意事项

严格遵循规范将消除安全隐患或共识隐患，这与之前的 BN254 预编译形成对比。

重要的主题是执行操作的“恒定时间”属性。我们明确声明此预编译不需要使用恒定时间算法执行所有操作。

版权

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

Citation

Please cite this document as:

Youssef El Housni (@yelhousni), Michael Connor (@iAmMichaelConnor), Aurore Guillevic <aurore.guillevic@inria.fr>, hujw77 (@hujw77), "EIP-3026: BW6-761 曲线运算 [DRAFT]," Ethereum Improvement Proposals, no. 3026, October 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-3026.