如果你是一个SNARKER，你一定听说过KZG Commitment，如果你听说过KZG Commitment，那你一定知道Pairing。这就是我们接下来要讨论的，大家如果想了解Pairing 的底层逻辑(pairing primitives)，或者对它的应用感兴趣都可以留言，或者添加文末的联系方式。

至今距离pairing 的“尘埃落定”其实已经大概有6、7年的时间了，网上的资料很完整，但关于它的讨论(工程上)仍未止步，比如On Proving Pairings.

本文所有内容源自hackmd上的note，欢迎follow.

这里没有的

• group theory, field theory and homomorphism

  相关基本概念在这里不会涵盖，详情请查阅任何abstract algebraic 相关的书籍

• divisors

  相关基本概念在这里不会涵盖，对于了解Pairing 来说 Pairing for Beginners 已足够，如果你还想深入理解最好翻阅一下 algebraic geometry 相关的书籍

• structure of elliptic curve over finite field and its arithmetics (scalar multiplication)

  理论和算法部分这里不会涵盖，详情可以查阅 Guide to Elliptic Curve Cryptography

• hash to curve

  bytes string 映射到${\mathbb{G}}_1$或者${\mathbb{G}}_2$ 上的点，简单说就是hash，是pairing 应用层面必备的一大模块，后续会详细补充这块内容

• non-affine coordinate

  affine coordinate 其实只是椭圆曲线元素表达的需要，它的scalar multiplication 并不经济，所以实际计算上都会用non-affine coordinate 来替代，后续会补上这块内容

• advanced scalar multiplication algorithms GLV/GLS

  特定的曲线上充分利用同态映射来加速scalar multiplication，同时还能(GPU)并行化处理也是当下硬件加速卖点，后续也会再补上

这里有的

本篇文章集中讨论了各种Pairing 变体:

• Weil Pairing
• Tate Pairing
• Ate Pairing
• Optimal Pairing

和它们的具体实现。除此之外，我们还包含了一些重要的实现层面的tricks，尤其是:

• Tower Fields
• Frobenius Map
• Twist
• Cyclotomic Group
• …

关于代码

• python implementation

  主要集中在Pairing的计算逻辑上，包括Miller Loop 和 Final Exponentiation。目前已经完成验证。

  Finite Field 和 Elliptic Curves的算术运算并没有逐一实现，用的是Sagemath库自带的 Galois Field and Elliptic Curve.

• rust implementation

  从零着手，从 Bigint 算术运算到 Finite Field 算术运算到 Elliptic Curve 算术运算，再到 Pairings Primitives。底层的逻辑已经验证完毕，目前在Pairings验证过程中 …

公共信息

• Modulus of base prime field (characteristic) $F_p$ with 381-bits: $$p=4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787$$

• Embedding degree, or the degree of full extension field $F_{p^k}$: $$k=12$$

• Elliptic Curve (additive group) over base prime field $F_p$: $${\mathbb{G}}_1/E(F_p):y^2=x^3+4$$

• Elliptic Curve (additive group) over extension field $F_{p^k}$: $${\mathbb{G}}_2/E(F_{p^k}):y^2=x^3+4$$

• Largest prime factor of $|E(F_p)|$ with 255-bits: $$r=52435875175126190479447740508185965837690552500527637822603658699938581184513$$

• Trace of Frobenius: $$t=p+1-|E(F_p)|=-15132376222941642751$$

• Parameter for BLS12 Pairing-family: $$x=-15132376222941642752$$ for: $$\begin{array}{rl}r(x)& =x^4-x^2+1\\ p(x)& =(x-1{)}^2\cdot r(x)\cdot \frac{1}{3}+x\\ t(x)& =x+1\end{array}$$

• Target (multiplicative) group with order $r$ defined over $F_{p^k}$: $${\mathbb{G}}_T:F_{p^k}^{\times }[r]$$

Pairing 的演进

Weil Reciprocity

$g$ and $f$ 是两个定义在椭圆曲线上的divisor function, $f,g\in K(E)$，它们的divisor support 不存在交集, $supp((f))\wedge supp((g))=\varnothing$。然后我们就有:

$$g((f))\equiv f((g))$$

其中 $(f)$ 表示函数 $f$的divisor, $g((f))$ 表示divisor $(g)$ 在函数$g$ 上的evaluation。 $f((g))$ 也类似.

如果我们放松上面的约束条件, 如果 $supp((f))\wedge supp((g))\ne \varnothing$, 然后就有一个更general 的 Weil Reciprocity 公式: $$g((f))\equiv ϵ((f),(g))\cdot f((g))$$ 其中 $ϵ((f),(g))=1$，当两个divisor $(f)$ and $(g)$ 的support 存在交集, 否则 $ϵ((f),(g))=-1$.

Details of general definition of Weil Reciprocity, you can refer THEOREM 3.9 of Guide to Pairing-based Cryptography.

那么Weil Reciprocity 究竟有什么意义呢? 它直接诞生了 Weil Pairing.

Weil Pairing

定义

假定在 $r$-torsion subgroup 中有两个线性不相交的点, $P,Q\in E[r],P\ne \lambda Q$. 基于此，假定 $(f)=r\cdot D_P$, and $D_P\equiv (P)-(\mathcal{O})$, 同样 $(g)=r\cdot D_Q,D_Q\equiv (Q)-(\mathcal{O})$. 它们同样满足 $Supp(D_P)\wedge Supp(D_Q)=\varnothing$.

然后我们就有: $$\begin{array}{rl}{g}_{r{D}_Q}(r\cdot D_P)& \equiv f_{r{D}_P}(r\cdot D_Q)\\ & \Downarrow \\ g_{r{D}_Q}(D_P{)}^r& \equiv f_{r{D}_P}(D_Q{)}^r\\ & \Downarrow \\ (\frac{g_{r{D}_Q}(D_P)}{f_{r{D}_P}(D_Q)}{)}^r& \equiv 1\end{array}$$

这样，Weil Pairing 就出现了: $$\frac{f_{r{D}_Q}(D_P)}{f_{r{D}_P}(D_Q)}={\mu }_r\in F_{p^k}^{\times }[r]$$ 其中 $(f_{r{D}_Q})=r{D}_Q,(f_{r{D}_P})=r{D}_P$, ${\mu }_r$ 是乘法group $F_{p^k}^{\times }$ 上的$r$-次单位元根 , 也就是说 ${\mu }_r^r\equiv 1\mathrm{mod}{p}^k-1$.

如何选择合适的divisor $D_P$ and $D_Q$

理论上我们需要选择合适的 divisors $D_P$ and $D_Q$，让它们的support 不相交, 你可能会奇怪，这应该有很多种选择，那么$D_P$ and $D_Q$不同的选择会导致最终pairing的结果 ${\mu }_r$ 不一样吗？

事实上 Weil Pairing 的结果 ${\mu }_r$ 它是与 $D_P$ and $D_Q$ 的选择无关的。下面简单证明一下：

假定 $D_{P1}$ and $D_{P2}$ 都是与divisor $(P)-(\mathcal{O})$ 等效的divisor, 那么一定存在另外一个中间divisor $(t)$ 使得 $D_{P1}=D_{P2}+(t)$, 然后: $$\frac{f_{r{D}_Q}(D_{P1})}{f_{r{D}_{P1}}(D_Q)}=\frac{f_{r{D}_Q}(D_{P2})\cdot f_{r{D}_Q}((t))}{f_{r{D}_{P2}}(D_Q)\cdot f_{(t)}(D_Q{)}^r}$$

根据 Weil Reciprocity 定理, 由于 $supp((t))\wedge supp(r{D}_Q)=\varnothing$, 所以 $f_{r{D}_Q}((t))\equiv f_{(t)}(r{D}_Q)=f_{(t)}(D_Q{)}^r$. 因此: $$\frac{f_{r{D}_Q}(D_{P1})}{f_{r{D}_{P1}}(D_Q)}=\frac{f_{r{D}_Q}(D_{P2})}{f_{r{D}_{P2}}(D_Q)}$$

既然跟divisor 具体的选择无关，那我们就选择最简单的 divisors： $D_P=(P)-(\mathcal{O}),D_Q=(Q)-(\mathcal{O})$. 这时，它们的support 是存在交集的，根据上面那个general Weil Reciprocity公式，我们就有Weil Pairing的正式定义: $$(-1{)}^r\cdot \frac{f_{r((Q)-(\mathcal{O}))}((P)-(\mathcal{O}))}{f_{r((P)-(\mathcal{O}))}((Q)-(\mathcal{O}))}={\mu }_r\in F_{p^k}^{\times }[r]$$

如何对divisor $D_P$ and $D_Q$ 进行evaluate

divisor $D_P=(P)-(\mathcal{O})$ 的evaluation 可以被进行一步简化:

$$f_{r{D}_Q}(D_P)\equiv f_{r{D}_Q}(P)$$

只要$P$ and $Q$ 是线性不相关的，即 $P\ne \lambda Q,\lambda \le r$.

注意上面的符号是 $\equiv$ 不是 $=$，也就是说它们evaluation的值可能不同，但并不会对Weil Pairing 最终的结果${\mu }_r$ 有影响，即： $$\frac{f_{r{D}_Q}(P)}{f_{r{D}_P}(Q)}=\frac{f_{r{D}_Q}(D_P)}{f_{r{D}_P}(D_Q)}={\mu }_r$$

因此 Weil Pairing 简化为: $$(-1{)}^r\cdot \frac{f_{r((Q)-(\mathcal{O}))}(P)}{f_{r((P)-(\mathcal{O}))}(Q)}={\mu }_r\in F_{p^k}^{\times }[r]$$

Miller Loop 使得divisor function的evaluation $f_{r((Q)-(\mathcal{O}))}(P)$ 变得更容易实现，是工程上的一大步。很明显 Weil Pairing 是几何上对称的, 它实际上需要运行两次 Miller Loop. 看起来并不太经济? 实际上单次就够了，这就是 Tate Pairing 要做的事情.

算法

直接参考Guide to Pairing-based Cryptography 中的Algorithm 3.2:

Tate Pairing

你可能会奇怪divisor function的evaluation $f_{r((P)-(\mathcal{O}))}(Q)$ 长什么样子? 由于 $P,Q\in E_{F_{p^k}}[r]$, 然后 $P_x,P_y,Q_x,Q_y\in F_{p^k}$, 所以 $f_{r((P)-(\mathcal{O}))}(Q)\in F_{p^k}$. 运用coset 的特性, Tate Pairing 就出现了: $$f_{r((P)-(\mathcal{O}))}(Q{)}^{\frac{p^k-1}{r}}\equiv {\mu }_r\in F_{p^k}^{\times }[r]$$

它分两步走, Miller Loop 和 Final Exponentiation. 这也是我们所说的 Final Exponentiation 的由来。

定义

其实 Tate Pairing 有一个更正式的定义: $$e_{T,r}(P,Q):E[r](F_{p^k})\times E(F_{p^k})/rE(F_{p^k})\to {\mu }_r$$ 其中 $P\in E[r](F_{p^k}),Q\in E(F_{p^k})/rE(F_{p^k})$, $Q$ 并不是$r$-torsion subgroup 中的元素, 它不再跟$P$一样被定义在group $E(F_{p^k})[r]上$。而是商群的某个元素, 确切的说就是group $E(F_{p^k})$ 上的任意一个与$P$ 线性不相关的元素. 看起来似乎是把约束条件放得更宽了。

既然这样，那么divisor function的evaluation值 $f_{r,P}(Q)$ (result of Miller Loop)会变成什么样子呢? 同样，它一定也是商群的某个元素，确切的说就是group $F_{p^k}^{\times }$上的任意一个元素，这也更加坚定了后续提指Final Expoentiation的必要性:

$$f_{r,P}(Q)\in F_{p^k}^{\times }/r{F}_{p^k}^{\times }$$

似乎Tate Pairing 要比Weil Pairing更通用 (more relaxed constraints) ，是吧?

Since $P\ne \lambda Q,\lambda \le r$, usually for the convenience of computation(utilization of Frobenius Automorphism) we let $P\in {\mathbb{G}}_1=\pi [1]$, namely $\pi (P)=1\cdot P$, ${\mathbb{G}}_1$ is so-called Base Group. While $Q\in {\mathbb{G}}_2=\pi [p]$, namely $\pi (Q)=[p]Q$, ${\mathbb{G}}_2$ is so-called Trace-zero Group. :::

算法

同样直接参考 Guide to Pairing-based Cryptography 的Algorithm 3.3:

Miller Loop

你可能已经注意到， Weil Pairing 中Miller Loop 的长度 and Tate Pairing 的都是 $\log (r)$ (bit length of $r$).

理论上 Tate Pairing 已经够实用了，至少实现起来是没有任何阻碍的了，所以后续的research 其实主要是针对工程实现上的优化，基本框架并没有改变。 基本集中在缩短 Miller Loop 的长度，以及更高效的提指 Final Expoentiation运算.

还有Miller Loop 更短的算法? 是的，但是我们需要深入挖掘一下乘法group $F_{p^k}^{\times }$ 的结构.

Ate Pairing

在Ate Pairing中, 点 $Q$ 被严格约束在 ${\mathbb{G}}_2=\pi [p]$中，同时点$P$ 也被约束在 ${\mathbb{G}}_1=\pi [1]$中，即Frobenius Map： $$\pi (Q)=[p]Q,\pi (P)=[1]P$$ 充分利用Frobenius Map的特性，将大大降低pairing的计算成本。

Miller 算法的两个重要特性

$$\begin{array}{rl}{f}_{a+b},Q(P)& =f_{a,Q}(P)\cdot f_{b,Q}(P)\cdot \frac{l_{[a]Q,[b]Q}}{v_{[a+b]Q}}\\ f_{a\cdot b,Q}(P)& =f_{b,Q}^a(P)\cdot f_{a,[b]Q}(P)\end{array}$$ 关于这两个特性的proof，这里不再推演，熟悉divisor function 后很容易推导出来。

更短的 Miller Loop

由于$r|p^k-1$, 假定 $u=(p^k-1)//r$，因此我们就有: $$f_{p^k,Q}(P)=f_{p^k-1,Q}(P)\cdot f_{1,Q}(P)\cdot \frac{l_{[p^k-1]Q,[1]Q}(P)}{v_{[p^k-1+1]Q}(P)}$$

由于 $Q\in {\mathbb{G}}_2$, 然后 $[r]Q=\mathcal{O},[p^k-1]Q=\mathcal{O}$, 我们就有 $l_{[p^k-1]Q,[1]Q}=v_{[p^k-1+1]Q}=(Q)+(-Q)-2(\mathcal{O})$, 因此: $$f_{p^k,Q}(P)=f_{p^k-1,Q}(P)=f_{r,Q}(P{)}^u$$

看起来我们似乎可以用$p$ 替代 $r$了, 但是这完全没有必要，因为 $p>r$，反而让Miller Loop 变得更长了。

如果 $\lambda \equiv p\mathrm{mod}r$ and $r|p^k-1$, 然后 $r|{\lambda }^k-1$, 假定 $m=({\lambda }^k-1)//r$, 类似地我们有: $$f_{{\lambda }^k,Q}(P)=f_{{\lambda }^k-1,Q}(P)=f_{r,Q}(P{)}^m$$

根据上面的两个 Miller 算法的特性， 可以继续推导: $$\begin{array}{rl}{f}_{{\lambda }^k,Q}& =f_{\lambda ,Q}^{{\lambda }^{k-1}}\cdot f_{{\lambda }^{k-1},[\lambda ]Q}\\ & =f_{\lambda ,Q}^{{\lambda }^{k-1}}\cdot f_{\lambda ,[\lambda ]Q}^{{\lambda }^{k-2}}\cdot f_{{\lambda }^{k-2},[{\lambda }^2]Q}\\ & =f_{\lambda ,Q}^{{\lambda }^{k-1}}\cdot f_{\lambda ,[\lambda ]Q}^{{\lambda }^{k-2}}\cdot f_{\lambda ,[{\lambda }^2]Q}^{{\lambda }^{k-3}}\cdot f_{{\lambda }^{k-3},[{\lambda }^3]Q}\\ & =\dots \\ & =f_{\lambda ,Q}^{{\lambda }^{k-1}}\cdot f_{\lambda ,Q}^{{\lambda }^{k-2}\cdot p}\cdot f_{\lambda ,Q}^{{\lambda }^{k-3}\cdot p^2}\cdot \dots \cdot f_{\lambda ,Q}^{1\cdot p^{k-1}}\\ & =f_{\lambda ,Q}^{{\sum }_{i=0}^{k-1}(k-1-i)\cdot p^i}\end{array}$$ 令 $c={\sum }_{i=0}^{k-1}(k-1-i)\cdot p^i$, 我们有: $$f_{{\lambda }^k,Q}(P)=f_{\lambda ,Q}(P{)}^c=f_{r,Q}(P{)}^m$$

由于 $\lambda <r$, 我们完全可以用 $\lambda$替换 $r$, 但是如何找到这个 $\lambda$ 值呢?

Trace of Frobenius

根据 Hesse Bound 定理， 我们有: $$|p+1-t|=\#E(F_p)$$ 令 $T=t-1$ 其中 $t$ 就是我们据说的Trace of Frobenius, 由于 $r|\#E(F_p)$, 然后 $\lambda =T\equiv p\mathrm{mod}r$.

最后我们得到: $$\begin{array}{rl}{a}_T(P,Q)& =f_{T,Q}(P{)}^{\frac{p^k-1}{r}}\\ (f_{T,Q}(P{)}^c{)}^{\frac{p^k-1}{r}}& =(f_{r,Q}(P{)}^m{)}^{\frac{p^k-1}{r}}\\ \Downarrow & \\ a_T(P,Q{)}^c& =e_{T,r}(P,Q{)}^m\end{array}$$

很明显 Tate Pairing $e_{T,r}(P,Q)$ 和 Ate Pairing $a_T(P,Q)$有着非常紧密的关系。 你可能已经注意到，这两个pairing的计算结果${\mu }_r$ 很可能不相等，不用紧张，只是pairing策略的差异而已，并不影响它在乘法group $F_{p^{12}}^{\times }[r]$ 中的唯一性，这才是pairing 的最终目的。

事实上Ate Pairing 在做的就是找到与 $r$ 的某个倍乘相关的数, $T$ 就是我们要找的,它满足 $r|T^k-1$. 但是，$\log T$ 一定是最短的 Miller Loop吗? 可能是（也可能不是），下面写几行代码反证一下：

p = 103
r = 7
k = 6

for i in range(1, k):
    print('lambda[{0}] = {1}'.format(i, (p ** i) % r))

运行结果：

lambda[1] = 5
lambda[2] = 4
lambda[3] = 6
lambda[4] = 2
lambda[5] = 3

很明显${\lambda }_1\equiv p^1\mathrm{mod}r$，并不是最小的，${\lambda }_4\equiv p^4\mathrm{mod}r$ 才是。

Optimal Ate Pairing

在上面的 Ate Pairing 中, 我们直接地用$p$ 替换 $T$ 后得到: $$f_{p,Q}^{x2}=f_{r,Q}^u$$ 其中 $u=(p^k-1)//r$, and $x2=k\cdot p^{k-1}$.

在 Ate Pairing 中，我们有: $$f_{\lambda ,Q}^{x1}=f_{r,Q}^m$$ 其中 $m=({\lambda }^k-1)//r$, and $x1={\sum }_{i=0}^{k-1}(k-1-i)\cdot p^i$.

基于此，我们可以找到二者之间的联系: $$\begin{array}{rl}{f}_{p,Q}^{x2\cdot m}& =f_{T,Q}^{x1\cdot u}\\ ⟹f_{\lambda ,Q}^{x1}& =f_{p,Q}^{\frac{x2\cdot m}{u}}\\ & =f_{p,Q}^{\frac{k\cdot p^{k-1}\cdot m}{(p^k-1)//r}}\end{array}$$

因此，Ate Pairing 经过 $x1$ 次方提指后变成: $$a_{\lambda }(P,Q{)}^{x1}=(f_{\lambda ,Q}(P{)}^{x1}{)}^{\frac{p^k-1}{r}}=(f_{p,Q}(P{)}^{\frac{k\cdot p^{k-1}\cdot m}{(p^k-1)//r}}{)}^{\frac{p^k-1}{r}}$$ 暂时先把结论放这儿.

在Optimal Ate Pairing中把$\lambda$进行了更通用的定义：$\lambda ={\sum }_{i=0}^l{c}_i\cdot p^i,l<k$, and $\lambda =m\cdot r$. 同样运用上面的 Miller 算法的特性, 我们把它的divisor function 进行展开:

$$\begin{array}{rl}{f}_{\lambda ,Q}& =f_{{\sum }_{i=0}^l{c}_i\cdot p^i,Q}\\ & =\prod _{i=0}^l{f}_{c_i\cdot p^i,Q}\cdot \prod _{j=0}^{l-1}\frac{l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}}{v_{[s_j]Q}}\\ & =\prod _{i=0}^l{f}_{p^i,Q}^{c_i}\cdot (\prod _{i=0}^l{f}_{c_i,Q}^{p^i}\cdot \prod _{j=0}^{l-1}\frac{l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}}{v_{[s_j]Q}})\end{array}$$ 其中: $$\prod _{i=0}^l{f}_{p^i,Q}^{c_i}=\prod _{i=0}^l{f}_{p,Q}^{i\cdot c_i\cdot p^{i-1}}=f_{p,Q}^{{\sum }_{i=0}^{l}i\cdot c_i\cdot p^{i-1}}$$

然后 Ate Pairing 就被转换成了: $$\begin{array}{rl}{a}_{\lambda }(P,Q)& =f_{\lambda ,Q}(P{)}^{\frac{p^k-1}{r}}\\ & =(f_{p,Q}(P{)}^{{\sum }_{i=0}^{l}i\cdot c_i\cdot p^{i-1}}{)}^{\frac{p^k-1}{r}}\cdot (\prod _{i=0}^l{f}_{c_i,Q}(P{)}^{p^i}\cdot \prod _{j=0}^{l-1}\frac{l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}(P)}{v_{[s_j]Q}(P)}{)}^{\frac{p^k-1}{r}}\\ & =(f_{p,Q}(P{)}^{\frac{k\cdot p^{k-1}\cdot m}{(p^k-1)//r}}{)}^{\frac{p^k-1}{r}}\end{array}$$

很明显 Ate Pairing $a_{\lambda }(P,Q)$ 被划分成了两部分, 左边部分 $(f_{p,Q}^{{\sum }_{i=0}^{l}i\cdot c_i\cdot p^{i-1}}{)}^{\frac{p^k-1}{r}}$ 是基于$p$的 Ate Pairing (length of Miller Loop is $\log p$)。

既然左边已经是一个Ate Pairing 了，那么右边部分 $({\prod }_{i=0}^l{f}_{c_i,Q}^{p^i}\cdot {\prod }_{j=0}^{l-1}\frac{l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}}{v_{[s_j]Q}}{)}^{\frac{p^k-1}{r}}$ 肯定也是一个Ate Pairing，只要 $\frac{k\cdot p^{k-1}\cdot m}{(p^k-1)//r}\ne {\sum }_{i=0}^{l}i\cdot c_i\cdot p^{i-1}$**。

所以Optimal Ate Pairing 正式定义就来了: $$a_{[c_0,c_1,\dots ,c_l]}(P,Q)=(\prod _{i=0}^l{f}_{c_i,Q}(P{)}^{p^i}\cdot \prod _{j=0}^{l-1}\frac{l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}(P)}{v_{[s_j]Q}(P)}{)}^{\frac{p^k-1}{r}}$$ 其中系数 $c_i$ 都是尽可能小的数.

不用担心指数运算 $p^i$, 它几乎是免费的，在充分运用 Frobenius Map后. Optimal Ate Pairing 要做的就是并行计算 $f_{c_i,Q}(P)$ and $l_{[s_{j+1}]Q,[c_j\cdot q^j]Q}(P)$, 此时Miller Loop 的长度可能就是 $max(\log c_i)$.

可以如何找到这么一组系数 $c_i$ 呢? 实际上它是一个关于 Lattice 的问题，感兴趣可以继续研究 Optimal Pairings.

有限域上的算术运算

BLS12-381 曲线的定义是这样的: $$E(F_{p^{12}}):y^2=x^3+4$$ 其中 $F_{p^{12}}=F_p[v]/X^{12}-2X^6+2$。但是这个extension field 是如何构建的呢？

Pairing 中域的切换

为了对Pairing 底层的算术运算有个更直观的sense，下面简单介绍一下Tate/Ate pairings中域的切换。

假定定义在域 $F_p$ 上的点$P\in {\mathbb{G}}_1$，同时点 $Q\in {\mathbb{G}}_2$ 定义在域 $F_{p^{12}}$上，实际上点 $Q$ 的坐标必须定义在域 $F_{p^{12}}$的某个子域上 (先给出结论，后续有推理过程)，比如说 $x_Q\in F_{p^6},x_P\in F_p$。整个过程，可以切分为4个部分：

• Miller Loop

  • Double-Add

    line function $f_{r,P}$ 不会改变所在的域，$P$在哪个域，这个函数仍然在那个域，比如 $F_p$:

    

  • Evaluation Line Function

    比如，单个line function的evaluation： $$l_{r,P}(Q)=y_Q-y_T-\alpha \cdot (x_Q-x_T)$$

    最终evaluation 的结果， $f_{r,P}(Q)$ 不再定义在$Q$原本的域 $[r]F_{p^{12}}^{\times }$ 上了.

    

• Final Exponentiation

  • Easy Part

    通过提指把Mill Loop 的结果$f_{r,P}(Q)$ 推进一个特殊的乘法group，这就是我们所说的 Cyclotomic Group， $F_{{\Phi }_{12}}$:

    

  • Hard Part

    再次通过提指从Cyclotomic Group 拉到目标乘法group $F_{p^{12}}^{\times }[r]$:

    

域塔 Tower Fields

定义

大家知道BLS12-381 Pairing中的目标group $G_T$ 是一个定义在$F_{p^{12}}$上的$r$-torsion multiplicative subgroup，我们经常表示为$F_{p^{12}}^{\times }[r]$。

那么$F_{p^{12}}$ 是如何被构造出来的呢? 这就是tower fields 的由来：

$$F_p[u]\stackrel{X^2-\alpha }{\to }{F}_{p^2}[v]\stackrel{X^3-\beta }{\to }{F}_{p^6}[w]\stackrel{X^2-\gamma }{\to }{F}_{p^{12}}$$

在BLS12-381曲线上，extension field modulus的常量分别为: $$\begin{array}{rl}\alpha & =-1\in F_p\\ \beta & =u+1=\sqrt{\alpha }+1=\sqrt{-1}+1\in F_{p^2}\\ \gamma & =v=\sqrt[3]{\beta }=\sqrt[3]{u+1}=\sqrt[3]{\sqrt{\alpha }+1}=\sqrt[3]{\sqrt{-1}+1}\in F_{p^6}\end{array}$$

$F_{p^{12}}$模的由来：

• $X^2-\gamma =X^2-v$ is irreducible in $F_{p^6}$

• since $v$ is one root of $X^3-\beta$, then we have $X^6-\beta$ is irreducible in $F_{p^2}$

• since $\beta -1$ is one root of $X^2-\alpha$, then we have $(X^6-1{)}^2-\alpha =X^{12}-2X^6+2$ is irreducible in $F_p$

• therefore we have $F_{p^{12}}=F_p[v]/X^{12}-2X^6+2$

也就是说，域$F_{p^{12}}$ 上的算术运算可以通过域 $F_{p^6}$ 上的算术运算来完成，同时域 $F_{p^6}$ 的算术运算可以通过域 $F_{p^2}$ 上的算术运算来完成，同样域$F_{p^2}$ 的算术运算可以通过base prime field $F_p$ 上的算术运算来完成。这就是我们据说的域塔 tower fields。

你可能已经注意到域的拓展 $F_p⟶F_{p^2}$ 和 $F_{p^6}⟶F_{p^{12}}$ 都是二次拓展 quadratic extension, 而$F_{p^2}⟶F_{p^6}$ 是三次拓展 cubic extension。所以 quadratic extension 和 cubic extension 在高阶extension field （比如$F_{p^{12}},F_{p^{24}}$）的算术运算中扮演着非常重要的角色。

Quadratic Extension 上的算术运算

这部分属于常规的计算逻辑，可以直接参考 Guide to Pairing-based Cryptography 5.2.1 章节。

Cubic Extension 上的算术运算

同样，这部分也可以直接参考 Guide to Pairing-based Cryptography 5.2.2 章节。

Cyclotomic Group 上的算术运算

分圆群 Cyclotomic group 在Pairing 的提指运算 Final Expoentiation 扮演着最核心的角色，特别是在 Tate/Ate Pairings中。既然是提指，那么主要就是平方 squaring 和指数 exponentiation 这两个算子。下面主要推演一下squaring 的全过程。

假定 $\alpha \in F_{p^3},p=q^2$，$F_q$表示base prime field，那么如何计算 ${\alpha }^2$?

首先，我们需要利用tower fields来表示 $\alpha$，比如： $$\begin{array}{rl}{F}_{p^3}& =F_{(q^2{)}^3}=F_{q^2}[v]/v^3-u\\ F_{q^2}& =F_q[u]/u^2-\xi \end{array}$$

假定 : $$\alpha =a+b\cdot v+c\cdot v^2$$ 则: $$\begin{array}{rl}{\alpha }^2& =(a+bv+c{v}^2{)}^2\\ & =a^2+b^2{v}^2+c^2{v}^4+2(a\cdot bv+a\cdot c{v}^2+bv\cdot c{v}^2)\end{array}$$

由于 $v^3-u=0$， 我们继续推进: $$\begin{array}{rl}{\alpha }^2& =(a^2+2bc\cdot u)+(c^2\cdot u+2ab)\cdot v+(b^2+2ac)\cdot v^2\\ & =A+B\cdot v+C\cdot v^2\end{array}$$

所以最终我们会有3次域 $F_{q^2}$ 上的squaring (分别是 $a^2,b^2,c^2$ )， 和5次域 $F_{q^2}$ 上的multiplication (分别是 $a\cdot b,b\cdot c,a\cdot c,bc\cdot u,c^2\cdot u$)。

域 $F_{q^2}$ 上的乘法运算可能会比较昂贵，那么有没有改进的方法呢? YES

Squaring Friendly Field

如果 $6|n$, 而且 $p$ 是一个非常大的素数characteristic，乘法group $F_{p^n}^{\times }$ 的阶$p^n-1$可以用多个cyclotomic polymomials ${\Phi }_i$的连乘来表示: $$p^n-1=\prod _{i=1}^{i|n}{\Phi }_i(p)$$

这里我们称 $F_{p^n}$ 为 Squaring Friendly Field.

举个例子乘法group $F_{p^{12}}^{\times }$: $$p^{12}-1={\Phi }_1(p)\cdot {\Phi }_2(p)\cdot {\Phi }_3(p)\cdot {\Phi }_4(p)\cdot {\Phi }_6(p)\cdot {\Phi }_{12}(p)$$

其中: $$\begin{array}{rl}{\Phi }_1(p)& =p-1\\ {\Phi }_2(p)& =p+1\\ {\Phi }_3(p)& =(p-{\zeta }_3^1)\cdot (p-{\zeta }_3^2)=p^2+p+1,{\zeta }_3^3=1\\ {\Phi }_4(p)& =(p-{\zeta }_4^1)\cdot (p-{\zeta }_4^3)=p^2+1,{\zeta }_4^4=1\\ {\Phi }_6(p)& =(p-{\zeta }_6^1)\cdot (p-{\zeta }_6^5)=p^2-p+1,{\zeta }_6^6=1\\ {\Phi }_{12}(p)& =(p-{\zeta }_{12}^1)\cdot (p-{\zeta }_{12}^5)\cdot (p-{\zeta }_{12}^7)\cdot (p-{\zeta }_{12}^{11})=p^4-p^2+1,{\zeta }_{12}^{12}=1\end{array}$$

换句话说，乘法group $F_{p^{12}}^{\times }$ 的阶可以被因子分解成： $$|F_{p^{12}}^{\times }|=p^{12}-1=(p-1)\cdot (p+1)\cdot (p^2+p+1)\cdot (p^2+1)\cdot (p^2-p+1)\cdot (p^4-p^2+1)$$

所以乘法group $F_{p^{12}}^{\times }$ 中一定存在一个阶为$r=p^4-p^2+1$ 的subgroup ${\mathbb{G}}_{{\Phi }_{12}(p)}$。

因此，我们得到一个非常重要的结论: $$\begin{array}{rl}& \alpha \in {\mathbb{G}}_{{\Phi }_{12}(p)}\subset F_{p^{12}}^{\times }\\ & \Downarrow \\ & {\alpha }^{{\Phi }_{12}(p)}={\alpha }^{p^4-p^2+1}=1\end{array}$$

更快的 Squaring 算子

回到上面的Squaring 运算，有 $\alpha \in F_{(q^2{)}^3}=F_{q^2}[v]/v^3-u$: $$\begin{array}{r}\alpha =a+b\cdot v+c\cdot v^2,\{a,b,c\}\in F_{q^2}\end{array}$$

Squaring 之后: $$\begin{array}{rl}{\alpha }^2& =(a^2+2bc\cdot u)+(c^2\cdot u+2ab)\cdot v+(b^2+2ac)\cdot v^2\\ & =A+B\cdot v+C\cdot v^2\end{array}$$

现在的问题是如何有效地计算 $\{a\cdot b,b\cdot c,a\cdot c\}$ ?

在Tate/Ate Pairing的Final Exponentiation中 $\alpha \in {\mathbb{G}}_{{\Phi }_6(q)}$，根据上面刚刚推演出的结论: $$\begin{array}{r}{\alpha }^{{\Phi }_6(q)}={\alpha }^{q^2-q+1}=1\\ ⟹{\alpha }^{q^2}\cdot \alpha ={\alpha }^q\end{array}$$

其中: $$\begin{array}{rl}{\alpha }^q& =(a+b\cdot v+c\cdot v^2{)}^q\\ & =a^q+b^q\cdot v^q+c^q\cdot (v^q{)}^2\end{array}$$

但是如何有效地计算诸如 $a^q,b^q,c^q,v^q,v^{2q}$? 我们拆开来看:

• $a^q,b^q,c^q=?$

  根据Frobenius Map 的特性，我们很容易得到：$a^q=\bar{a},b^q=\bar{b},c^q=\bar{c}$ (先给出结论，在后面Frobenius Map 部分会进行推理)。因此上面的式子简化成: $$\begin{array}{r}{\alpha }^q=\bar{a}+\bar{b}\cdot v^q+\bar{c}\cdot (v^q{)}^2\end{array}$$

• $v^q=?$

  由于 $v^3=u,u^2=\xi ,u\in F_{q^2},\xi \in F_q$，因此： $$v^q=v^{3\cdot (q-1)/3}\cdot v=u^{\frac{q-1}{3}}\cdot v={\xi }^{\frac{q-1}{6}}\cdot v={\zeta }_6\cdot v$$ 其中 ${\zeta }_6$ 是域$F_q$上的 primitive 6-th root of unity，也就是说${\xi }_6^6\equiv 1\mathrm{mod}q$ .

  More properties of primitive 6-th root of unity in $F_q$: $1+{\zeta }_6^2={\zeta }_6$ ${\zeta }_6^2+{\zeta }_6^4=-1$ ${\zeta }_6^4+{\zeta }_6=0$

综合在一起，我们得到: $${\alpha }^q=\bar{a}+(\bar{b}\cdot {\zeta }_6)\cdot v+(\bar{c}\cdot {\zeta }_6^2)\cdot v^2$$

应用Frobenius map 后: $$\begin{array}{rl}{\alpha }^{q^2}& ={\bar{a}}^q+({\bar{b}}^q\cdot {\zeta }_6^q)\cdot v^q+({\bar{c}}^q\cdot {\zeta }_6^{2q})\cdot v^{2q}\\ & =a+(b\cdot {\zeta }_6^{q+1})\cdot v+(c\cdot {\zeta }_6^{2q+2})\cdot v^2\\ & =a+(b\cdot {\zeta }_6^2)\cdot v+(c\cdot {\zeta }_6^4)\cdot v^2\end{array}$$

应用Squaring Friendly Field的特性，我们得到： $$\begin{array}{rl}& {\alpha }^{q^2}\cdot \alpha ={\alpha }^q\\ & \Updownarrow \\ & (a+(b\cdot {\zeta }_6^2)\cdot v+(c\cdot {\zeta }_6^4)\cdot v^2)\cdot (a+b\cdot v+c\cdot v^2)=\bar{a}+(\bar{b}\cdot {\zeta }_6)\cdot v+(\bar{c}\cdot {\zeta }_6^2)\cdot v^2\end{array}$$

展开后，得到: $$\begin{array}{rl}\bar{a}& =(a^2+bc{\zeta }_6^2\cdot u+bc{\zeta }_6^4\cdot u)\\ \bar{b}\cdot {\zeta }_6& =(ab+ab{\zeta }_6^2+c^2{\zeta }_6^4\cdot u)\\ \bar{c}\cdot {\zeta }_6^2& =(ac+ac{\zeta }_6^4+b^2{\zeta }_6^2)\end{array}$$

所以上面的三个乘法运算被转换成: $$\begin{array}{rl}b\cdot c& =\frac{\bar{a}-a^2}{({\zeta }_6^2+{\zeta }_6^4)\cdot u}=\frac{\bar{a}-a^2}{-u}\\ a\cdot b& =\frac{(\bar{b}+c^2\cdot u)\cdot {\zeta }_6}{1+{\zeta }_6^2}=\frac{(\bar{b}+c^2\cdot u)\cdot {\zeta }_6}{{\zeta }_6}=c^2\cdot u+\bar{b}\\ a\cdot c& =\frac{(\bar{c}-b^2)\cdot {\zeta }_6^2}{1+{\zeta }_6^4}=\frac{(\bar{c}-b^2)\cdot {\zeta }_6^2}{-{\zeta }_6^2}=b^2-\bar{c}\end{array}$$