pairing friendly 椭圆曲线 BN254 之前被 ZCash （第 5.4.9.1 节）使用，目前是以太坊上仅有的几个具有预编译合约用于椭圆曲线加法、标量乘法和 pairing 的曲线（EIP 196, 197）。由于这些预编译，BN254 是使用诸如 Groth16 和 PlonK 证明方案验证链上 zkSNARKs 的最实用选择。

尽管自从 Kim-Barbulescu 的新算法之后，BN254 的安全位数从 128 降到了 大约 100，但由于以太坊上的预编译，BN254 依然是使用 Groth16 和 PlonK 证明方案进行链上 zkSNARK 验证的最实用的 pairing friendly 曲线。

我发现关于 BN254 的信息很难找到（部分是因为多个名称，见下文），因此这份文档的目的是将所有与开发者/研究人员在实践中使用这条曲线相关的信息整理到一个地方。这份文档的灵感无疑来自于存在的 BLS12-381 For The Rest Of Us。

为了增加对 BN254 的混淆，它通常被称为 多个不同的名称，例如：

• BN128（128 曾经指的是安全位数）或
• alt_bn_128

（254 代表与基域相关的素数的位数。）

警告： 这不是这里提到的 BN254：https://neuromancer.sk/std/bn/bn254

BN254 (alt_bn_128) 是一条不同的 Barreto-Naehrig (BN) 曲线，具有 254 位素数。该曲线定义为：

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

在本文的其余部分，我们将该曲线称为 BN254。

Barreto-Naehrig 曲线

Barreto-Naehrig (BN) 曲线是形如

Y^2=X^3+b 的椭圆曲线

E，定义在素数域 F_p 上，其中素数

p 定义为

p=36x^4+36x^3+24x^2+6x+1，对于一个参数

x。

参数

x 还决定了与曲线 E 相关的其他常数：

r=36x^4+36x^3+18x^2+6x+1，t=6x^2+1，其中

x 被选为使得

r 是素数，并且

t 是该曲线的 Frobenius 构成 的迹。

BN 曲线的嵌入度总是 12，这意味着 12 是最小的整数

k，使得

E(F{p^k})[r]=E(F{-p})[r]。

BN 曲线是通过 CM 方法构造的，始终具有 CM 判别式

−3 和

j-不变量等于

0。

如何从参数 x 中找到 b

给定参数

x，使得曲线

y^2=x^3+b 在 F_p 上具有阶 r 的系数 b 是使用所谓的 CM 方法计算的（CM 代表复数乘法）。有关 CM 方法和 BN 曲线的概述，请参见 [ Shirase, 3.1]。对于 BN 曲线，

j-不变量等于

0，这大大简化了 CM 方法：

• 遍历 b，使得

b+1 是模 p 的平方剩余

• 对于这样的 b，点 G=(1,b+1) 位于 E(F_p) 上。
• 检查是否

rG=O，即点 G 的阶为 r。

• 如果

rG≠O，则迭代到下一个 b。

BN254 的参数

BN254（alt_bn128）的参数 x 为：

x = 4965661367192848881

（来源：libff）。可以检查这给出了文档顶部给出的 254 位素数 p。

对于这个特定的 x，曲线的阶 r 为：

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

恰好也是一个 254 位素数。对于 BN254，r 是 Baby Jubjub 素数。

对于 BN254，b = 3。如前文所述，如果我们尝试

b=1，则

b+1=2 是模 p 的平方剩余，但

y^2=x^3+1 并没有阶 r。因此我们继续选择

b=3，b+1=22 是一个平方剩余，可以检查点

(1,2)∈E(F_p) 确实具有阶 r。

总之，

y^2=x^3+3 是参数 x = 4965661367192848881 对应的 BN 曲线。

范围扩展塔

为了进行 pairing，我们需要选择 F{p^{12}} 的一个表示。标准方法是将 F{p^{12}} 表示为 F_p 的一个特定字段扩展塔：

F_{p^2}=Fp[u]/(u^2−β)
F{p^6}=F{p^2}[v]/(v^3−ξ)
F{p^{12}}=F_{p^6}[w]/(w^2−v)

其中

β 是 F_p 中的一个平方非剩余，且

ξ 在 F_{p^2} 中既不是平方剩余也不是立方剩余。对 ξ 的条件等价于多项式

X^6−ξ 在 F_{p^2}[X] 上是不可约的。

对于 BN254，我们使用

β=−1 和

ξ=9+u。因此使用的详细字段扩展塔为：

F_{p^2}=Fp[u]/(u^2+1)
F{p^6}=F{p^2}[v]/(v^3−(9+u))
F{p^{12}}=F_{p^6}[w]/(w^2−v)

最重要的方程是

u^2=−1 和

w^6=9+u。

我们还可以直接写成

F_{p^{12}}=F_p[w]/((w^6−9)^2+1)=F_p[w]/(w^{12}−18w^6+82)。这与 Python 实现 这里 一致。

扭曲

扭曲的工作方式几乎与 BLS12-381 相同：

回想一下，X^6−ξ 在 F_{p^2}[X] 上是不可约的，其中 ξ=9+u。根据 [第 3 节，Barreto-Naehrig]，我们可以使用 ξ 定义 BN254 曲线 E:y^2=x^3+3 的 D 类型 六次扭曲：

E′: y′^2=x′^3+3/ξ=x′^3+3/(9+u)。 （脚注：BLS12-381 有一个 M 类型六次扭曲。）曲线 E′ 在 F_{p^2} 中定义。这个定义与 EIP 197 一致。为具体起见，

E' : y^2 = x^3 + (19485874751759354771024239261021720505790618469301721065564631296452457478373 + 266929791119991161246907387137283842545076965332900288569378510910307636690 u)

我们有 w∈F_{p^{12}} 是 X^6−ξ 的根，因此

Ψ(x′,y′)=(w^2x′,w^3y′) 定义了一个群同态

Ψ:E′(F{p^2})→E(F{p^{12}})。我们有以下事实：

• Ψ:E′(F{p^2})→E(F{p^{12}}) 是单射（但不是满射）
• Ψ 扩展为一个同构

Ψ~:E′(F{p^{12}}) ≅ E(F{p^{12}})。

• 存在阶 r 的子群

G2 of E′(F{p^2}) 通过 Ψ 发送到 E(F{-p})[r] 的一个线性独立子群。

知道 E′(F_{p^2}) 和 E(F_p) 没有阶为 2 的点是有用的。

Frobenius 构成

定义 Frobenius 构成

ϕp:E(F{-p})→E(F_{-p}) 为

ϕ_p(x,y)=(x^p,y^p)。这在 E 定义于 F_p 的情况下是定义良好的。Frobenius 构成是一个度为 p 的同构，其特征多项式为

X^2−tX+p。这意味着

ϕ_p^2−[t]ϕp+[p]=[0] 在 E(F{-p}) 上。

由于 E(Fp) 是 E(F{-p}) 的 Frobenius 不动点，我们得到

G1:=E(Fp)[r]=E(F{p^−})[r]∩ker(ϕ_p−[1])。令

Ψ(G2) 表示 G2:=E′(F_{p^2})[r] 在扭曲映射 Ψ 下的像。然后我们有 Ψ(G2) 的一个替代描述为

Ψ(G2)=E(F_{-p})[r]∩ker(ϕ_p−[p])。注意“迹”的事实与 ϕ_p 的迹等于 [t] 是没有矛盾的，因为

p+1≡t(mod r)。

最优 Ate pairing

对于 BN 曲线，最优 Ate pairing

e:G1×G2→GT，其中 GT=μr⊂F{p^{12}}× 是单位根的 r 重的根，被定义为：

e(P,Q)=(f{6x+2},Q(P)⋅l{[6x+2]}Q,ϕp(Q)(P)⋅l{[6x+2]}Q+ϕ_p(Q),−ϕ_p^2(Q)(P)) p^{12−1}r

其中：

• f{i,Q} 对于 i∈N,Q∈G2 是 E 上的 F{p^{12}} 有理函数，在 Ψ(Q) 处有 i 个零，同时在 Ψ(Q) 处有一个极点 [i]，并且在原点 O 处有 i−1 个极点。
• f_{i,Q} 是使用 Miller 算法递归计算的

f{i+j,Q}=f{i,Q}⋅f{j,Q}⋅l{[i]Ψ(Q)},[j]Ψ(Q)v{[i+j]}Ψ(Q)。这里 l{P_1,P_2} 表示通过 P_1,P2 的直线的方程，而 v{P} 表示通过 P 的竖直线的方程。

• 最后指数化的优化是，最终值

e(P,Q) 在上述方程中如果省略对 v_{[i+j]}Ψ(Q) 的除法，保持不变。

• x 是曲线的参数。
• ϕ_p(x,y)=(x^p,y^p) 是 Frobenius 运算符。

子群检查

G1 的子群检查

给定一个对

(x,y)∈F_{p^2}，容易检查

(x,y) 是否是曲线 E(F_p) 上的一点。我们还需要进一步检查它是否属于子群

G1=E(F_p)[r]。幸运的是，对于 BN 曲线，我们有

G1=E(F_p)，因此不需要进一步检查。

一种查看这种情况的方法是 Weil 猜想 [定理 2.3.1，Silverman] 意味着

E(F_p)=p+1−t。我们可以检查，对于由参数 x 生成的 BN 曲线，我们有

p(x)+1−t(x)=r(x)，使用上述公式 （Barreto-Naehrig curves）。我们得出结论

E(F_p)=r。

Weil 猜想还告诉我们，如果

α,β∈C 是 Frobenius 构象的特征多项式

X^2−tX+p 的根，则

α,β 的绝对值为

p（因此 β=α^−），并且

(1) #E(F_{p^k})=p^k+1−α^k−α^−k。

G2 的子群检查

给定对

P=(x,y)∈F_{p^{2}}^2，容易检查

P 是否是扭曲曲线 E′(F_{p^2}) 上的一点。然而，我们需要进一步检查

P 是否在子群

G2=E′(F_{p^2})[r] 中。设

E′(F_{p^2})=c_2r。遗憾的是在我们的例子中

c_2≠1。这个数字

c_2 被称为

G2 的 余因子。

G2 的阶

我们可以通过 [命题 2，HSV] 进行一些修改 来计算

E′(F_{p^2})：

构造曲线的 CM 方法产生整数

D,V 使得

DV^2=4p−t^2，其中

−D 是判别式，结果曲线 E 的

End(E)⊂Q(−D)。对于 BN 曲线，

D=3，因此

End(E) 是 Q(−3) 中的一个整环。由于 E′ 是 E 的六次扭曲，我们知道六次单位根

μ_6 ⊂ Aut(E)。唯一满足这个条件的整环是

Z[ω]，其中

ω=−1+i√3/2。我们得出结论，任何 BN 曲线都有复数乘法

End(E)=Z[ω]。

X^2−tX+p 的根等于

t±√(t^2−4p^2)=t±V−√3/2 根据二次公式，所以我们可以取

α=t+V−√3/2。扭曲 E′ 在 F_{p^2} 上定义，因此我们可以考虑 Frobenius 图

ϕ{p^2}' 在 E' 的 F{-p}。设

α′ 为 Frobenius 运算符特征多项式的根之一。

由于 E 和 E′ 在 F_{p^{12}} 上同构，我们有

E(F{p^{12}})=p^{12}+1−α^{12}−α^{−12}=p^{12}+1−α′^6−α′^−6=#E′(F{p^{12}})。我们推导出直到共轭，

α′=ζα^2，其中 ζ∈μ6。此外，由于 F{p^{12}} 是上述成立的最小字段扩展，

ζ 必须是原始的六次单位根

ζ=1±i√3/2。某些计算得出

α′+α′^−=t^2∓3tV^2−p，其中

V=(4p−t^2)/3。因此：

E′(F_{p^{2}})=p^2+p+1−t^2∓3tV^2，

右手边有两种可能性，对应于 E 的两种可能的六次扭曲（类型 D 与类型 M）。

对于 BN 曲线，

V=6x^2+4+1，其中

x 是参数。插入 关于参数 的公式 后，我们发现使

E′(F_{p^{2}}) 能被 r=p−t+1 整除的正确符号是：

E′(F_{p^{2}})=p^2+p+1−t^2+3tV^2，这可简化为

E′(F_{p^{2}})=(p−t+1)(p+t−1)c_2=p+t−1。对于 BN254 的特定情况，我们得到：

#E'(F_{p^2}) = 479095176016622842441988045216678740799252316531100822436447802254070093686356349204969212544220033486413271283566945264650845755880805213916963058350733
c_2 = 21888242871839275222246405745257275088844257914179612981679871602714643921549

使用有效的自同构进行 G2 成员检查

检查 P∈E′(F_{p^2}) 是否属于 G2 的一个简单但缓慢的方法是查看

[r]P=O。这是不可取的，因为在 BN254 的情况下，r 有 254 位。

有多种方法可以加快不同曲线的 G2 成员检查，方法是找到一个有效计算的自同构。对于 BN 曲线，我们可以使用 HGP 中第 4.3 节的新方法，该方法改编自 Scott。它基于由 Galbraith-Scott 引入的非扭曲 Frobenuis 倍思自同构

ψ:E′(F{p^2})→E′(F{p^2})，它被定义为

ψ=Ψ^−1∘ϕ_p∘Ψ，其中

Ψ:E′(F{p^2})→E(F{p^{12}}) 是扭曲映射，而

ϕ_p(x,y)=(x^p,y^p) 是 Frobenius 构造。请注意，

Ψ 只是单射，但可以直接检查

ϕ_p∘Ψ 位于

Ψ 的像中。对于 BN 曲线的 D 类型六次扭曲，我们有

ψ(x′,y′)=(ξ(p−1)/3x′^p,ξ(p−1)/2y′^p) （回想一下，对于 BN254 的 ξ=9+u）。

根据 [HGP](https://eprint.iacr.org/2022/352.pdf) 的命题 3，P∈E′(F_{p^2}) 属于 G2 若且唯若 ψ(P)=[6x^2]P，其中 x 表示曲线 E 的参数。 （在 loc cit. 的表述中有一个小错误，但论据正确。）为方便起见，我们提供了一个证明：

我们有

r=p−t+1，并且给定 P∈E′(F_{p^2})，我们需要检查

[r]P=O。这等价于

[p]P=[t−1]P。另一方面，

ψ 满足 Frobenius 运算符的特征多项式，这意味着

ψ^2−[t]ψ+[p]=0。因此

[p]P=[t−1]P 等价于

ψ^2(P)−[t]ψ(P)+[t−1]P=O。

设局部 λ=t−1=6x^2。那么上述内容可因式分解为

(ψ−[1])(ψ−[λ])(P)=O。显然

ψ(P)=[λ](P) 表示该方程成立。相反，假设

[r]P=O，因此该方程成立。令 Q=(ψ−[λ])P。那么

ψ(Q)=Q 表示扭曲映射 Ψ(Q)∈E(F_p)=E(F_p)[r]。交集

Ψ(E′(F_{p^2}))∩E(F_p)[r]={O}，所以

Q=O。换句话说，

ψ(P)=[λ]P。

参考资料

• Barreto-Naehrig, Pairing-Friendly Elliptic Curves of Prime Order. https://www.cryptojedi.org/papers/pfcpo.pdf （比 https://eprint.iacr.org/2005/133.pdf 更新）
• Beuchat 等，高速软件实现最佳 Ate pairing 在 Barreto–Naehrig 曲线。 https://eprint.iacr.org/2010/354.pdf
• Silverman, 椭圆曲线的算术。 https://link.springer.com/book/10.1007/978-0-387-09494-6

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