密码学 - BLS12-381 - Zcash

BLS12-381

这是 BLS12-381 配对友好椭圆曲线构造的实现。

BLS12 参数化

BLS12 曲线由一个值 x 参数化，以便可以计算基域模数 q 和子群 r：

• q = (x - 1)² ((x⁴ - x² + 1) / 3) + x
• r = (x⁴ - x² + 1)

给定如上参数化的素数 q 和 r，我们可以很容易地构造出一个在素数域 F_q 上的椭圆曲线，该曲线包含一个订单为 r 的子群，使得 r | (q¹² - 1)，赋予它 12 的嵌入度。在扩展域 F_q² 上实例化其六次扩展会产生一种高效的双线配对函数，将任意曲线的订单为 r 的子群内的元素映射到 F_q¹² 的一个订单为 r 的乘法子群。

在 zk-SNARK 方案中，我们需要 F_r 具有大的 2ⁿ 级单位根以便进行高效的快速傅里叶变换。因此，确保大的 2ⁿ | (r - 1)，或者等价地 x 具有一个大的 2ⁿ 因子，产生适合 zk-SNARK 的 BLS12 曲线。

由于近期的研究，许多人估计 q 应该大约为 384 位，以瞄准 128 位安全性。方便的是，当 q 大约为 384 位时，r 约为 256 位，使得 BLS12 曲线成为理想的 128 位安全性选择。这也使它们非常适合许多 zk-SNARK 应用，因为标量域可以用于密钥材料，例如嵌入曲线构造。

许多曲线符合我们的描述，但出于效率考虑，我们需要一些额外的属性：

• q 应该小于 2³⁸³，并且 r 应该小于 2²⁵⁵，以便在使用 64 位或 32 位获取时，最高有效位未设定。这允许进行廉价的约简。
• F_q¹² 通常是使用扩展域塔构建的。作为对 研究 BLS 曲线嵌入度为 24 的副产品，我们可以识别出 BLS12 曲线的子家族（为我们的目的，x mod 72 = {16, 64}），它们生成高效的扩展域塔和扭转同构。
• 我们希望 x 具有小的汉明权重，以提高配对函数的性能。

BLS12-381 实例化

BLS12-381 构造通过 x = -0xd201000000010000 被实例化，这产生了满足上述要求的最大 q 和最小汉明权重的 x。结果为：

• q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab（381 位）
• r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001（255 位）

我们的扩展域塔构造如下：

1. F_q² 被构造为 F_q(u) / (u² - β)，其中 β = -1。
2. F_q⁶ 被构造为 F_q²(v) / (v³ - ξ)，其中 ξ = u + 1。
3. F_q¹² 被构造为 F_q⁶(w) / (w² - γ)，其中 γ = v。

现在，我们实例化椭圆曲线 E(F_q) : y² = x³ + 4，以及椭圆曲线 E'(F_q²) : y² = x³ + 4(u + 1)。

group G₁ 是 E 的 r 阶子群，其余量为 (x - 1)² / 3。 group G₂ 是 E' 的 r 阶子群，其余量为 (x⁸ - 4x⁷ + 5x⁶ - 4x⁴ + 6x³ - 4x² - 4x + 13) / 9。

生成器

G₁ 和 G₂ 的生成器通过寻找字典顺序最小的有效 x 坐标，以及其字典顺序最小的 y 坐标计算，并按余量对其进行缩放，使结果不是无穷远点。

G1

x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569

G2

x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*u + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*u + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905

序列化

• Fq 元素以大端形式编码。这种形式占用 48 字节。
• Fq2 元素以大端形式编码，意味着 Fq 元素 c0 + c1 * u 由 Fq 元素 c1 后跟 Fq 元素 c0 表示。这意味着 Fq2 元素在这种形式中占据 96 字节。
• group G1 使用 Fq 元素作为坐标。group G2 使用 Fq2 元素作为坐标。
• G1 和 G2 元素可以以未压缩形式（x 坐标后跟 y 坐标）或压缩形式（仅 x 坐标）进行编码。G1 元素在未压缩形式中占用 96 字节，在压缩形式中占用 48 字节。G2 元素在未压缩形式中占用 192 字节，在压缩形式中占用 96 字节。

G1 或 G2 编码的最高三位应在解释坐标之前屏蔽掉。这些位用于明确定义底层元素：

• 当最高有效位设定时，指示该点为压缩形式。否则，该点为未压缩形式。
• 第二位最高有效位指示该点为无穷远点。如果该位被设定，组元素编码的其余位应设为零。
• 如果该点为压缩形式 且 不是无穷远点 且 其 y 坐标是与编码 x 坐标相关的两个坐标中字典顺序最大的，则第三位最高有效位被设定。

• 原文链接： github.com/zcash/librust...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～