EIP-2539: BLS12-377 曲线运算

用于 BLS12-377 曲线运算的预编译合约

摘要

此预编译合约添加了 BLS12-377 曲线（来自 Zexe 论文）上的运算，作为高效执行诸如 BLS 签名验证和执行 SNARKs 验证等操作所需的一组预编译合约。BLS12-377 的独特属性也使得之后能够以高效的方式检查 BLS12-377 配对的 SNARKs，并允许例如固定大小的 BLS 签名聚合。

如果 block.number >= X，我们将引入九个单独的预编译合约来执行以下操作：

• BLS12_377_G1ADD - 用于在素数域上定义的曲线上执行点加法
• BLS12_377_G1MUL - 用于在素数域上定义的曲线上执行点乘法
• BLS12_377_G1MULTIEXP - 用于在素数域上定义的曲线上执行多重指数运算
• BLS12_377_G2ADD - 用于在基域的二次扩展上定义的曲线扭曲上执行点加法
• BLS12_377_G2MUL - 用于在基域的二次扩展上定义的曲线扭曲上执行点乘法
• BLS12_377_G2MULTIEXP - 用于在基域的二次扩展上定义的曲线扭曲上执行多重指数运算
• BLS12_377_PAIRING - 用于在 (G1, G2) 点的对集合之间执行配对运算
• BLS12_377_MAP_FP_TO_G1 - 将基域元素映射到 G1 点
• BLS12_377_MAP_FP2_TO_G2 - 将扩展域元素映射到 G2 点

包含多重指数运算是为了在 BLS 签名验证期间有效地聚合公钥或各个签名者的签名。

建议的地址表

动机

此预编译合约的动机是添加一种密码学原语，与仅提供 80 位安全性的现有 BN254 预编译合约相比，该原语允许在配对友好的曲线上为运算获得 120+ 位的安全性。此外，它还允许高效的一次性递归证明聚合，例如关于基于 BLS12-377 的签名存在的证明。

规范

曲线参数：

BLS12-377 曲线由以下参数集完全定义（所有 BLS12 曲线的系数 A=0）：

基域模数 = 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
B 系数 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
主子群阶数 = 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001
扩展塔:
Fp2 构造:
Fp 二次非剩余 = 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508bffffffffffc
Fp6/Fp12 构造:
Fp2 三次非剩余 c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Fp2 三次非剩余 c1 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
扭曲参数:
扭曲类型: D
扭曲的 B 系数 c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
扭曲的 B 系数 c1 = 0x010222f6db0fd6f343bd03737460c589dc7b4f91cd5fd889129207b63c6bf8000dd39e5c1ccccccd1c9ed9999999999a
生成器:
G1:
X = 0x008848defe740a67c8fc6225bf87ff5485951e2caa9d41bb188282c8bd37cb5cd5481512ffcd394eeab9b16eb21be9ef
Y = 0x01914a69c5102eff1f674f5d30afeec4bd7fb348ca3e52d96d182ad44fb82305c2fe3d3634a9591afd82de55559c8ea6
G2:
X c0 = 0x018480be71c785fec89630a2a3841d01c565f071203e50317ea501f557db6b9b71889f52bb53540274e3e48f7c005196
X c1 = 0x00ea6040e700403170dc5a51b1b140d5532777ee6651cecbe7223ece0799c9de5cf89984bff76fe6b26bfefa6ea16afe
Y c0 = 0x00690d665d446f7bd960736bcbb2efb4de03ed7274b49a58e458c282f832d204f2cf88886d8c7c2ef094094409fd4ddf
Y c1 = 0x00f8169fd28355189e549da3151a70aa61ef11ac3d591bf12463b01acee304c24279b83f5e52270bd9a1cdd185eb8f93
配对参数:
|x| (米勒循环标量) = 0x8508c00000000001
x 为负数 = false

基本元素的细节和编码

字段元素编码：

为了编码操作中涉及的点，必须编码基域和扩展域的元素。

基域元素 (Fp) 被编码为 64 字节，方法是对相应的（无符号）整数执行大端编码（顶部 16 字节始终为零）。选择 64 字节是为了具有 32 字节对齐的 ABI（可以表示为例如 bytes32[2] 或 uint256[2]）。相应的整数必须小于字段模数。

对于二次扩展域 (Fp2) 的元素，编码是各个系数编码的字节连接，总共为 128 字节。对于形式为 el = c0 + c1 * v 的 Fp2 元素，其中 v 是形式二次非剩余，c0 和 c1 是 Fp 元素，则相应的字节编码将为 encode(c0) || encode(c1)，其中 || 表示字节连接（或者可以使用 Solidity 类型中的 bytes32[4] 或 uint256[4]）。

如果在预编译合约中解析期间的任何地方编码不遵循此规范，则预编译合约必须返回错误。

G1/G2 中点的编码：

G1（在基域中）或 G2（在扩展域中）中的点被编码为 x 和 y 仿射坐标编码的字节连接。因此，G1 点的总编码长度为 128 字节，G2 点的总编码长度为 256 字节。

无穷远点的编码：

也称为“零点”。对于 BLS12 曲线，坐标为 (0, 0) 的点（Fp 或 Fp2 中的形式零）不在曲线上，因此点 (0, 0) 的编码用作编码无穷远点的约定。

乘法运算标量的编码：

乘法运算的标量被编码为 32 字节，方法是对相应的（无符号）整数执行大端编码。不要求相应整数小于或等于主子群大小。

操作的 ABI

G1 加法的 ABI

G1 加法调用需要 256 字节作为输入，该输入被解释为两个 G1 点的字节连接（每个 128 字节）。输出是加法运算结果的编码 - 单个 G1 点（128 字节）。

错误情况： - 任何一个点不在曲线上都必须导致错误 - 字段元素编码规则适用（显然） - 输入具有无效长度

G1 乘法的 ABI

G1 乘法调用需要 160 字节作为输入，该输入被解释为 G1 点编码（128 字节）和标量值编码（32 字节）的字节连接。输出是乘法运算结果的编码 - 单个 G1 点（128 字节）。

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

G1 多重指数的 ABI

G1 多重指数调用需要 160*k 字节作为输入，该输入被解释为 k 个切片的字节连接，每个切片都是 G1 点编码（128 字节）和标量值编码（32 字节）的字节连接。输出是多重指数运算结果的编码 - 单个 G1 点（128 字节）。

错误情况： - 任何 G1 点不在曲线上都必须导致错误 - 字段元素编码规则适用（显然） - 输入具有无效长度

G2 加法的 ABI

G2 加法调用需要 512 字节作为输入，该输入被解释为两个 G2 点的字节连接（每个 256 字节）。输出是加法运算结果的编码 - 单个 G2 点（256 字节）。

错误情况： - 任何一个点不在曲线上都必须导致错误 - 字段元素编码规则适用（显然） - 输入具有无效长度

G2 乘法的 ABI

G2 乘法调用需要 288 字节作为输入，该输入被解释为 G2 点编码（256 字节）和标量值编码（32 字节）的字节连接。输出是乘法运算结果的编码 - 单个 G2 点（256 字节）。

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

G2 多重指数的 ABI

G2 多重指数调用需要 288*k 字节作为输入，该输入被解释为 k 个切片的字节连接，每个切片都是 G2 点编码（256 字节）和标量值编码（32 字节）的字节连接。输出是多重指数运算结果的编码 - 单个 G2 点（256 字节）。

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

配对的 ABI

配对调用需要 384*k 字节作为输入，该输入被解释为 k 个切片的字节连接。每个切片具有以下结构： - 128 字节的 G1 点编码 - 256 字节的 G2 点编码

输出是 32 字节，其中前 31 字节等于 0x00，如果配对结果等于配对目标字段中的乘法恒等式，则最后一个字节为 0x01，否则为 0x00。

错误情况： - 任何布尔变量的无效编码必须导致错误 - 任何 G1 或 G2 点不在曲线上都必须导致错误 - 任何 G1 或 G2 点都不在正确的子群中 - 字段元素编码规则适用（显然） - 输入具有无效长度

将 Fp 元素映射到 G1 点的 ABI

场到曲线的调用需要 64 字节的输入，该输入被解释为基域的一个元素。此调用的输出为 128 字节，并且是遵循相应编码规则的 G1 点。

错误情况： - 输入具有无效长度 - 输入不是有效字段元素

将 Fp2 元素映射到 G2 点的 ABI

场到曲线的调用需要 128 字节的输入，该输入被解释为二次扩展域的一个元素。此调用的输出为 256 字节，并且是遵循相应编码规则的 G2 点。

错误情况： - 输入具有无效长度 - 输入不是有效字段元素

预防错误处理中的 DDoS

此预编译合约执行大量的计算，如果在执行期间发生任何错误，则它必须消耗相应操作的所有 gas 计划中的 gas。

Gas 计划

假设一个常数 30 MGas/秒，建议以下价格。

G1 加法

600 gas

G1 乘法

12000 gas

G2 加法

4500 gas

G2 乘法

55000 gas

G1/G2 多重指数

预计多重指数运算将由 Peppinger 算法执行（我们也可以说必须由 Peppinger 算法执行，才能获得加速，从而导致对朴素实现的折扣，即分别乘以每对并添加结果）。对于这种情况，准备了一个表，用于在多重指数中存在 k <= 128 个点的情况下进行折扣，对于 k > 128，折扣上限为 max_discount。

为了避免非整数算术，调用成本计算为 k * multiplication_cost * discount / multiplier，其中 multiplier = 1000，k 是调用的（标量，点）对的数量，multiplication_cost 是 G1/G2 的相应单个乘法调用成本。

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

[[1, 1200], [2, 888], [3, 764], [4, 641], [5, 594], [6, 547], [7, 500], [8, 453], [9, 438], [10, 423], [11, 408], [12, 394], [13, 379], [14, 364], [15, 349], [16, 334], [17, 330], [18, 326], [19, 322], [20, 318], [21, 314], [22, 310], [23, 306], [24, 302], [25, 298], [26, 294], [27, 289], [28, 285], [29, 281], [30, 277], [31, 273], [32, 269], [33, 268], [34, 266], [35, 265], [36, 263], [37, 262], [38, 260], [39, 259], [40, 257], [41, 256], [42, 254], [43, 253], [44, 251], [45, 250], [46, 248], [47, 247], [48, 245], [49, 244], [50, 242], [51, 241], [52, 239], [53, 238], [54, 236], [55, 235], [56, 233], [57, 232], [58, 231], [59, 229], [60, 228], [61, 226], [62, 225], [63, 223], [64, 222], [65, 221], [66, 220], [67, 219], [68, 219], [69, 218], [70, 217], [71, 216], [72, 216], [73, 215], [74, 214], [75, 213], [76, 213], [77, 212], [78, 211], [79, 211], [80, 210], [81, 209], [82, 208], [83, 208], [84, 207], [85, 206], [86, 205], [87, 205], [88, 204], [89, 203], [90, 202], [91, 202], [92, 201], [93, 200], [94, 199], [95, 199], [96, 198], [97, 197], [98, 196], [99, 196], [100, 195], [101, 194], [102, 193], [103, 193], [104, 192], [105, 191], [106, 191], [107, 190], [108, 189], [109, 188], [110, 188], [111, 187], [112, 186], [113, 185], [114, 185], [115, 184], [116, 183], [117, 182], [118, 182], [119, 181], [120, 180], [121, 179], [122, 179], [123, 178], [124, 177], [125, 176], [126, 176], [127, 175], [128, 174]]

max_discount = 174

配对操作

配对操作的成本为 55000*k + 65000，其中 k 是对的数量。

Fp 到 G1 映射操作

Fp -> G1 映射是 5500 gas。

Fp2 到 G2 映射操作

Fp2 -> G2 映射是 75000 gas

原理

动机部分涵盖了使 BLS12-377 曲线上的操作可用的全部动机。我们还扩展了移动特定细节的基本原理。

多重指数作为单独的调用

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

向后兼容性

没有向后兼容性问题。

重要提示

子群检查

子群检查在配对调用期间是强制性的。实现应该使用快速子群检查：在撰写本文时，乘法 gas 成本基于 double-and-add 乘法方法，该方法具有明显的“最坏情况”（所有位都等于 1）。对于配对操作，预计实现使用更快的子群检查，例如通过对椭圆曲线使用 wNAF 乘法方法，该方法对于窗口大小等于 4 时，便宜约 40%。（经过经验测试。节省的原因是群顺序的汉明权重较低，甚至 wNAF 的汉明权重更低。具体而言，一对中 G1 和 G2 点的子群加起来约为 35000）。

测试用例

由于测试参数空间很大，我们首先提供各种操作必须满足的属性。我们使用加法表示法进行点运算，大写字母（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 不可见）

所有操作的测试向量都在 matter-labs 的 1962 提案中的 csv 文件中展开。

参考实现

现有曲线运算的实现有多种选择。可能需要额外的工作来添加 ABI： - 具有固定参数的代码库 - Rust: matter-labs - C++: matter-labs - Zexe 论文中链接的原始 Rust 实现：github.com/scipr-lab/zexe - Go 中的独立实现：github.com/kilic/bls12-377

安全考虑

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

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

版权

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

Citation

Please cite this document as:

Alex Vlasov (@shamatar), hujw77 (@hujw77), "EIP-2539: BLS12-377 曲线运算 [DRAFT]," Ethereum Improvement Proposals, no. 2539, February 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2539.