BN128曲线
1. 引言
BN系列椭圆曲线E(Fp):y2=x3+b，其中b≠0E(\mathbb{F}_p):y^2=x^3+b，其中b\neq 0E(Fp):y2=x3+b，其中b=0，由Paulo S. L. M. Barreto1 和 Michael Naehrig 在2005年论文 Pairing-Friendly Elliptic Curves of Prime Order中首次提出，在该论文中，提出了构建embedding degree为k=12k=12k=12的BN系列椭圆曲线的有效算法：
- 基域：素数 p=36x4+36x3+24x2+6x+1p=36x^4+36x^3+24x^2+6x+1p=36x4+36x3+24x2+6x+1
- scalar域：order （即椭圆曲线上的点的个数）n=36x4+36x3+18x2+6x+1n=36x^4+36x^3+18x^2+6x+1n=36x4+36x3+18x2+6x+1
- trace：t=6x2+1t=6x^2+1t=6x2+1（trace of Frobenius）
- n=p+1−tn=p+1-tn=p+1−t
以太坊的alt_bn128曲线，取：
x=4965661367192848881x=4965661367192848881x=4965661367192848881
从而有：
- p=21888242871839275222246405745257275088696311157297823662689037894645226208583p=21888242871839275222246405745257275088696311157297823662689037894645226208583p=21888242871839275222246405745257275088696311157297823662689037894645226208583
- n=21888242871839275222246405745257275088548364400416034343698204186575808495617n=21888242871839275222246405745257275088548364400416034343698204186575808495617n=21888242871839275222246405745257275088548364400416034343698204186575808495617
- t=147946756881789318990833708069417712967t=147946756881789318990833708069417712967t=147946756881789318990833708069417712967
根据herumi/ate-pairing可知，相应的extension field为：
- Fp2=Fp[u]/(u2+1)\mathbb{F}_{p^2}=\mathbb{F}_p[u]/(u^2+1)Fp2=Fp[u]/(u2+1)，其中u2=1u^2=1u2=1
- Fp6=Fp2[v]/(v3−ξ)\mathbb{F}_{p^6}=\mathbb{F}_{p^2}[v]/(v^3-\xi)Fp6=Fp2[v]/(v3−ξ)，其中v3=ξ，ξ=u+9v^3=\xi，\xi=u+9v3=ξ，ξ=u+9
- Fp12=Fp6[w]/(w2−v)\mathbb{F}_{p^{12}}=\mathbb{F}_{p^6}[w]/(w^2-v)Fp12=Fp6[w]/(w2−v)，其中w2=vw^2=vw2=v
相应的sage脚本为：
# GF(p) p的質數體，x為generator
sage: P. = PolynomialRing(GF(p))
# 用GF(p) extension 建構Fp2，u為generator
sage: F2. = GF(p).extension(x^2 + 1)# Fp2的Polynomial ring P，t為generator
sage: P. = F2[]
# 用Fp2 extension 建構Fp6，v為generator
sage: F6. = F2.extension(t^3 - u-9)# 若可以則執行下列：
# Fp6的Polynomial Ring P，y為generator
sage: P. = F6[]
# 用Fp6 extension 建構Fp12，w為generator
sage: F12. = F6.extension(y^2 - v)
Pairing-Friendly Elliptic Curves of Prime Order论文中有：
以太坊黄皮书中与zkSNARK相关的预编译合约使用的是BN128曲线对：
- 曲线C1（基于Fp\mathbb{F}_pFp）为：
- 曲线C2（基于Fp2\mathbb{F}_{p^2}Fp2）为：
相应的sage脚本为：
# G1
sage: F1 = GF(21888242871839275222246405745257275088696311157297823662689037894645226208583)
sage: G1 = EllipticCurve(F1,[0,3])sage: P1 = G1(1,2)# G2
sage: F2 = GF(21888242871839275222246405745257275088696311157297823662689037894645226208583^2,"i",modulus=x^2 + 1)
sage: TwistB = 3*F2("9+i")^(-1)
sage: G2 = EllipticCurve(F2,[0,TwistB])sage: P2x = F2("11559732032986387107991004021392285783925812861821192530917403151452391805634*i + 10857046999023057135944570762232829481370756359578518086990519993285655852781")
sage: P2y = F2("4082367875863433681332203403145435568316851327593401208105741076214120093531*i + 8495653923123431417604973247489272438418190587263600148770280649306958101930")
sage: P2 = G2(P2x,P2y)
基于以上BN128曲线对 构建的pairing计算结果对应 Fp12\mathbb{F}_{p^{12}}Fp12，即有：
以太坊EIP-197：Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128，以太坊的预编译合约采用以上（公式253）来替代（公式254），从而验证pairing运算结果是否一致。
参考资料
[1] BN128曲线
[2] Paulo S. L. M. Barreto1 和 Michael Naehrig 2005年论文 Pairing-Friendly Elliptic Curves of Prime Order
[3] 以太坊黄皮书