Pairing for beginners[1]摘要
>因为篇幅有限，这里列举了on proving pairing论文中需要的知识点。

1. 群环域
* 群（G）定义了一个集合和一个群运算+，满足封闭性和结合律,存在单位元和逆元素
* 环（Z）在群的基础上多定义了一个群运算x，也满足封闭性和结合律，且存在
（乘法）单位元（不要求存在逆元素）。
* 域（F）在环的基础上，除了加法单位元之外所有元素存在（乘法）的逆元素，也就是说域同时满足加法群和乘法群
整数集构成一个环但不构成域。有理数集，实数集和复数集均构成域

群具有如下性质：
* 一个群 G 的元素个数称为群的阶，记作 $\#G$。
* 一个群元素 P 的阶为最小的整数 k 使得 $kP = O$（k 个 P 进行群运算，O 为单
位元）称为 P 的阶。
* 群内任何一个元素的阶一定整除群的阶。
* 如果一个元素 P 的阶等于群的阶，则 P 是 G 的一个生成元，且 $G = {P, 2P, ...}$
是一个 cyclic group循环群。
参考[2]
2. 循环子群和协因子
如果一个群的阶为合数，根据拉格朗日定理，一定存在多个循环子群。比如定义在有限域Fq上的椭圆曲线群的阶为$\#E(Fq)=105=3*5*7$, 一定存在阶为{1,3,5,7,15,..105}的循环子群。
如何获得这些循环子群？ 就要用到协因子cofactor的概念，cofactor $h=\#E/r$，r是目标循环子群的阶。比如获取r=3阶子群，h=105/3=35, 然后用h乘以群的生成元P=(47,12)，就得到3阶群的生成元$[35](47,12)=(28,8)$，继而得到整个3阶子群。这里群元素点的坐标(x,y)。
注意，协因子的概念非常重要。

3. r-torsion 点
r-torsion点是一类很重要的子群，$E[r]=\{P \in E: [r]P=O\}$
$$ E[r] \cong Z_r \times Z_r $$
r-torsion是定义在$E(\overline{F_q})$上的所有r阶点构成的子群，$E[r]$是两个模r剩余类环(也就是整数集合Z通过模r运算得到的商集)$Z_r$的乘积，一般来说这个群的阶为$\#E[r]=r^2$
注意，群元素是在ECC上的点，而不是有限域中的数值。这些r-torsion点有r+1个阶为r的循环子群组成，之所以是r+1,是因为每个子群都有一个共同的单位元。[Beginner Figure 4.1]

4. 如何找到所有r-torsion点
我们已经知道r-torsion点一定有$r^2$个，也知道$E[F_q]$有一个r阶子群，如果$E[F_q]$只包含一个循环子群，可以扩展到$E[F_{q^2}]$上再获取一个循环子群，要想获取到所有$r^2$个点，并不是一定要扩张r次，往往k次就够了，k<<r, 判断标准就是$q^k-1$能整除r, 而有趣的是，一旦$q^k-1$能整除r,就一下子找到了所有的r-torsion点。k就是嵌入度
* k 是使得$r|(q^k-1)$的最小正整数
* K 也是使得有限域$F_{q^k}$包含了所有r次单位根的最小正整数$(x^r=1 mod F_{q^k})$
* K 同时也是使得所有r-torsion点在$E(F_{q^k})$上能找到的最小正整数
可见r次单位根似乎和r-torsion点之间有种特殊的联系
举例说明(beginner 4.1.1)，Let $q=11，E/Fq: y^2=x^3+4, E(F_q)$有12个点也就是$\#E(F_q)=12$，想获取所有3-torsion点，即E[3]=3*3=9, 可以看到只有3个在$E(F_q)$中，同时$q-1/3 \ne 0$,但是$(q^2-1) =0\ mod\ 3$,所以嵌入度k=2，在$F_{q^2}$上就能找到所有9个点
[Beginner Figure 4.1]

这里要说明的是k=2扩域的构造，不是简单的扩展到$q^2=11*11$,而是$F_{q^2}=Fq(i), i^2+1=0$的形式来构造，类似虚数的形式。
如果q-1/r=0, 就说明所有r-torsion点在$E(F_q)$上就能找到，不需要扩域。[Beginner example 4.1.2]

5. Divisors
要理解pairing，绕不开Divisors的概念，divisor来自代数集合，比较抽象，定义：
$$ D= {\sum_{P \in {E(\overline{F}_{q})} }n_{P}(P)} $$
$n_{p}$是P点的系数也叫阶
个人理解：divisor是因子的意思，类似多项式Q=$(x-1)^{2}(x-2)$,其中x-1因子的阶是2，在椭圆曲线上，一条曲线（包括直线）和椭圆曲线的交点就构成了这些divisors，如果是切线，degree就是2
例如，y=ax+b和ECC相交于三个点P,Q,-(P+Q)，其实还有极点O,阶为-3即-3O
关于divisors还有其他一些概念和性质，比如这些degree的和一定是0，请参考Beginner。

6. Wei reciprocity(Wei 互换)
在一个Divisor $D={\sum_{P \in E}}{n_p}(P)$上计算函数$f \in F_{q}(E)$有一个自然的定义
$$f(D)={\prod_{P \in E}}f(P)^{n_p}$$
也就是将D的点代入f函数计算。
Wei reciprocity说的就是：假设两个函数f,g，在一个椭圆曲线上的Divisor为(f)和(g),那么就有：
$$ f((g) = g((f))$$
也就是各自的Divisor点代入到对方函数，结果相等
Example3.3.1, $E/F_{503}: y^2=x^3+1$, 函数$f:\frac{20y+9x+179}{199y+187x+359}=0$ and $g: y+251x^2+129x+201=0$
因子
(f)=2(433,98)+(232,199)-(432,27)-2(127,258)
(g)=(413,369)+(339,199)+(147,443)+(124,42)-4O
这样这些divisor可以代入对方函数计算。具体请参考Beginner
Wei互换就有了pairing的雏形。

7. Pairing
pairing的定义是一个双线性映射
$$e: G_1 * G_2=G_t$$
$G_1,G_2$ 定义在群 $E(F_{p^k})$ 上，而 $G_t$ 定义在乘法群$F_{p^k}^*$上。
注意：左侧是椭圆曲线上的加法群，右侧是有限域上的乘法群。G1和G2中间的乘，就是普通意义上的乘法, pairing把椭圆曲线和有限域两个世界联系在了一起，amazing!
我们时常使用的是左侧,双线性性质如下，不论左侧如何乔装改扮，右侧始终如一
$$e(aP, bQ) = e(P, bQ)^a = e(aP, Q)^b = e(P,Q)^{ab} = e(bP,aQ)$$

8. Wei pairing
根据上面Divisor知识，对于任一m属于整数集($m\in Z$),P是椭圆曲线点($P\in E$),有：
$$ (f_{m,P}) = m(P)-([m]P)-(m-1)O$$
这里系数和m-1-(m-1)=0, 也就是说,对系数和为0的divisor一定存在一个函数$f_{m,P}$
或者说就是给定divisor，我们可以构造出相关的和ECC相交的曲线函数
有一些限定条件考虑文章的可读性没有列出，感兴趣读者可以学习Beginner
如果m=r，根据r-torsion点的性质，[r]P=O,O是无穷远点或叫单位元，也就有：
$$ (f_{r,P}) = r(P)-r(O)$$
如何计算($f_{r,P}$)的值？
观察到$(f_{m+1},P ) − (f_m,P ) = (P) + ([m]P) − ([m + 1]P) − (O)$
而$f_{0,P}=1$，可以通过渐进迭代的方式从$f_{0,P}$得到$f_{1,P}$, 到$f_{2,P}$...$f_{r,P}$
而每一步都是一个斜线和一个垂直线$ℓ_{[m]P,P} /v_{[m+1]P}$的值相除的结果,
其中斜线是$(P)+([m]P)$两个点连线来构造，垂直线为过([m+1]P)点来构造。
可以看到如果r很大，计算量是非常大的，著名的miller loop就是把这个计算过程优化到生产级别。
[Beginner Figure 5.1]:

Wei Pairing:
设$P,Q\in E(F_{q^k})[r]$，即定义在有限域$F_{q^k}$上的椭圆曲线上的r-torsion点， $D_P,D_Q$是degree=0的divisors，存在函数f,g使得$(f)=rD_P, (g)=rD_Q$
定义Wei Pairing是一个映射：
$$ w_r: E(F_{q^k})[r] * E(F_{q^k})[r] \to u_r$$
$$ w_r(P,Q)=\frac{f(D_Q)}{g(D_P)}$$
$u_r$是r次单位根，注意：$f(D_Q)$不是$f(D_P)$,意思是把Q点divisor代入到$D_P$构造的f函数计算，g的参数是P点的Divisor。两者相除的结果是对应有限域$F_{q^k}$上的r次单位根
具体计算例子可以参考[Beginner Example 5.1.1]加深理解。
可以看到Wei Paring需要两个来自r-torsion点参数，计算量大，而tate pairing只需要1个

9. Tate Pairing
Tate Pairing要比Wei Pairing复杂，但是计算更加精简
Tate Pairing需要了解陪集和商群的概念，其中G2就是定义在$E(F_{q^k})$等价的商群上的

9.1 r倍点陪集
$E(F_{q^k})$上所有点的r倍构成一个陪集,不是群，它的数量是协因子$h=\#E(F_{q^k})/r^2$,定义：
$$rE(F_{q^k}) = \{[r]P: P \in E(F_{q^k}) \}$$
注意，这里跟r-torsion点的区分，r-torsion点有$r^2$个，获取r-torsion点的方法是：
$$r_{torsion} = \{[h]P: P \in E(F_{q^k}) \}$$
可以看到，任何一个r-torsion点Q, $rQ=[rh]P=O$, 任何一个r倍点Q,$hQ=[hr]P=O$
对r倍点加上任意一个其他的$E(F_{q^k})$上的不在r-torsion中的点R构成另一个陪集.
这样的陪集正好有$r^2$个(想想为什么?)，而且有趣的是，每一个陪集里都有唯一的r-torsion中的点。
这些陪集构成一个商群E/rE, 单位元是r倍点陪集rE, 而pairing中的G2就定义在这个商群上。
这个商群的每一个陪集有一个重要的性质，陪集内部的两个元素的差一定在rE中，因为每个陪集都是rE的元素加上一个随机点R构造的，两点的差就把这个R消去了，所以一定在rE中。
参考如下Biginner书中的例子:
Firgure5.3集中了所有3-torsion点，
Firgure5.2 则列出了$r^2=9$个陪集，每个陪集都包含有一个r-torsion中的点，第一个陪集是r倍点陪集，包含单位元O点

9.2 Tate Pairing Map:
设$P\in E(F_{q^k})[r]$，$Q\in E(F_{q^k})$即E/rE的等价类群，可见G2范围放宽了， $D_P,D_Q$是degree=0的divisors，存在函数f使得$(f)=rD_P$
$$ t_r: E(F_{q^k})[r] * E(F_{q^k})/rE(F_{q^k}) \to F_{q^k}^*/(F_{q^k}^*)^r$$
$$ t_r(P,Q)=f(D_Q)$$
可见，只需要计算$f(D_Q)$就可以了，但是$G_t$不再是r次单位根$u_r$而是一个有限域乘法商群，和E/rE非常相似。
$(F_{q^k}^*)^r$是$(F_{q^k}^*)$的子群，定义为：
$$(F_{q^k}^*)^r = {\{u^r: u \in F_{q^k}^*\}}$$
和rE定义何其相似，它们在映射上存在某种关系。
因此，$F_{q^k}^*/(F_{q^k}^*)^r$是$F_{q^k}^*$的等价类，等价关系是$a1/a2 \in(F_{q^k}^*)^r$, 也就是说，两个tate pairing相等，只要它们两个的商属于$(F_{q^k}^*)^r$, 换句话说，两个等价的tate pairing的结果不一定相等，但是他们一定在同一个乘法商群的陪集里，两个结果的商一定在类似r倍点的$(F_{q^k}^*)^r$中
可以参考书中Example5.2.2,
$t_r(P,Q)=4i+4, t_r(P,[2]Q)=2i+4=t_r(P,Q)^2$ 但是$t_r([2]P,Q)=3i+2$
即$t_r([2]P,Q)，t_r(P,[2]Q) \notin (F_{q^k}^*)^r$, 可以验证$(3i+2)^{3^2-1}=4$
但是$t_r([2]P,Q)/t_r(P,[2]Q) \in (F_{q^k}^*)^r$，可以验证$((3i+2)/(2i+4))^8=i^8=1$

9.3 Tate pairing final exponent
为了直接判断两个Tate pairing相等，可以提指到$(q^k-1)/r$幂次，得到r次单位根
$$ T_r: E(F_{q^k})[r] * E(F_{q^k})/rE(F_{q^k}) \to u_r$$
$$ T_r(P,Q)=t_r(P,Q)^{\#F_{q^k}/r}=f_{r,P}(D_Q)^{(q^k-1)/r}$$
原理就是，有限域商群中的陪集也是从$(F_{q^k}^*)^r=\{u^r\}$乘一个随机数s而来，即
${\{u^r\}} \to {s*\{u^r\}}$, 对陪集中元素提指后，所有的${\{u^r\}^{(q^k-1)/r}}$将变为1，而只剩下${s}^{(q^k-1)/r}$,是r次单位根。
这个提指就叫final exponent.
理论上来说没问题了，但是生产上为了保证安全r和q都非常大，都在256bit幂次级别的计算，这样几乎不可能投入使用，这样就有了miller loop算法和针对r值计算量更小的ate pairing

10. Miller Loop
在之前章节中介绍了$f_{r,P}$的计算可以通过$f_{1,P}，f_{2,P}..f_{r,P}$迭代计算而来。
考虑之前介绍过的divisor：
$$ (f_{m,P}) = m(P)-([m]P)-(m-1)O$$
miller观察到，它的平方为：
$$ (f_{m,P}^2) = 2m(P)-2([m]P)-2(m-1)O$$
同时：
$$ (f_{2m,P}) = 2m(P)-([2m]P)-(2m-1)O$$
两者很相似，差值为：
$$ (f_{2m,P})-(f_{m,P}^2) = 2([m]P)-([2m]P)-O$$
其中，$2([m]P)$，是$[m]P$点的double，$-([2m]P)$是$[2m]P$点的垂直线，差值就是两者的线性函数相除。也就是说$f_{2m,P}$可以通过$f_{m,P}^2*(line_{[m]P,[m]P}/v_{[2m]P})$计算得到。同样是迭代，这次是从1,2,4,8..m这样的double得到，如果m不能被2整除，可以用之前的迭代add即可。效率指数倍提升。
Miller Loop解决的是给定m，可以指数效率计算得到，而下面的Ate paring 解决的是让m尽量小.

11. Ate pairing
$$ a_T: G_2 * G_1 \to G_T$$
$$ a_T(Q,P) = f_{T,Q}(P)^{q^k-1/r}$$
可见，ate pairing和tate pairing类似，只是把$G_1,G_2$顺序反了一下，同时miller loop的迭代数量也从$r$改为了$T$, $T<<r$。T是什么？

11.1
根据Hasse bound定理
$$|q+1-t|=\#E(F_q), |t| \le 2\sqrt{q}$$
也就是说，ECC阶和q+1相差一个t，这个t叫做"trace of Frobenius", 椭圆曲线参数选定，t也就定了，定义T=t-1，$|q-T|=\#E(F_q)$。
$$r(x)=x^4-x^2+1, t(x)=x+1, t<<r$$
考虑$q \equiv T\ mod\ r, q^k \equiv 1\ mod\ r \to T^k \equiv 1\ mod\ r$, 有$$T^k-1=rm,m \in Z$$.

考虑$G_2$在前面的tate pairing $e(Q,P)=f_{r,Q}(P)^{(q^k-1)/r}$，那么根据双线性性质有$$e(Q,P)^m=f_{mr,Q}(P)^{(q^k-1)/r}=f_{T^k-1,Q}(P)^{(q^k-1)/r}$$
而$f_{T^k-1,Q}(P) = \prod{f_{T,[T^i]Q}(P)}$(注:根据divisor的性质)
因为$Q \in G_2$,可以很好利用Frobenius 自同态的性质${[T^i]Q=\pi^i(Q)}$
Frobenius 自同态是一个很强大技巧，可以参考[3]
这样$\prod{f_{T,[T^i]Q} \to f_{T,Q}^{q^i}(P)}$，
tate pairing 和ate pairing等价：$e(Q,P)=a_T(Q,P)^v$
我们就可以计算$a_T(Q,P)$来判断两个ate pairing是否相等,T要远远小于r。

11.2 Optimal Ate pairing
Vercauteren研究到，$T \equiv q\ mod\ r$只是一个$\lambda_i \equiv q^i\ mod\ r$的特例，因为$\lambda_i$是miller loop的循环长度，所以，我们希望它尽可能小，而最终就是要找到一个$\lambda_i = \sum_{i=0}^{l}c_iq^i$的最小的$c_i$系数，这是一个格问题，借助格数学最终可以得到一个最小系数。其中，BN曲线上我们得到:
$$\lambda = 6x+2+q-q^2+q^3$$
这也就是当前pairing使用的循环$f_{\lambda,Q}(P)^{(q^k-1)/r}$，其中$q-q^2+q^3$部分借助Frobenius map，它的计算几乎是免费的，所以真正耗时的是$6x+2$部分，而借助最小Hamming算法，它只有65次循环。

12. On proving pairing[4]
可以看到tate pairing最贵的计算一个是miller loop，另一个是final exponent提指，而On prove pairing paper创新的地方就是消除了final exponent部分，大大节省了验证时间。
>on prove pairing paper中使用了零知识证明中常用的“验证代替计算”的思想，比如代替计算$x^{-1}=y$，验证的思想就是提供$y$，验证$xy=1$.

已知miller loop结果是一个乘法群等价类$(F_{q^k}^*)/(F_{q^k}^*)^r$,在提指之前，两个等价的pairing x,y的结果的商肯定在$(F_{q^k}^*)^r$中，也就是$xc^r=y$,所以final exponent提指后一定为1.
也就是
$$y^{q^k-1/r}=(xc^r)^{q^k-1/r}=x^{q^k-1/r}c^{q^k-1}=x^{q^k-1/r}$$
定理1：
$$\prod_ie(P_i,Q_i)=1 \iff \exists c\in F_{q^k}^*: \prod_if_{r,Q_i}(P_i)=c^r $$
就是说，两个pairing提指后积(商)为1，等价于两个pairing的miler loop的积存在r次剩余。
如果我们提前计算好r次剩余c，就有$\prod_if_{r,Q_i}(P_i)*c^{-r}=1$
这样相比final exponent的提指$q^k-1/r$幂次，根据c计算$r$次幂，计算量小了2/3.
但是因为r很大，1/3的计算量仍然很大，还可以再优化。

回顾Optimal ate pairing的miller loop计算,达到最小循环次数，最小计算量
$$f_{\lambda,Q}(P)^{(q^k-1)/r}$$
> 那么更进一层，是否可以考虑两个miller loop的积和$c^{\lambda}$等价?

$\lambda=m\cdot r,m \in Z$, miller loop积的结果是否可以和$c^{\lambda}$即$(c^m)^r$等价，也就是要计算是否存在$\lambda$剩余。

定理2：
$$\prod_ie(P_i,Q_i)=1 \iff \exists c\in F_{q^k}^*: \prod_if_{r,Q_i}(P_i)=c^{\lambda/d} $$
定义：$\lambda=m\cdot r, d=gcd(m,h), \lambda=d\cdot m'\cdot r, h=(q^k-1)/r$
因为$\lambda$和h不互素$d=gcd(m,h)$，无法直接计算$\lambda$次剩余，但是$\lambda/d$和h互素，即$gcd(\lambda/d, h)=1$，如果f是miller loop输出，$f^h=1$，根据贝祖定理，一定存在$\lambda/d$次剩余,根据贝祖定理有
$$x\cdot \lambda/d + y\cdot h=1 \to f^{x\cdot \lambda/d}*f^{y\cdot h}=f \to {(f^x})^{\lambda/d} = f$$
$x是\lambda/d \ mod\ h的逆, f^x 即是f的 \lambda/d次剩余$

$\lambda=d\cdot m'\cdot r, gcd(m', h)=1,gcd(r, h)=1,gcd(d, h)\ne 1$, 因为$d|(q^k-1)$不互素, 所以f有可能不是d次剩余，作者给出的创新就是,在f是非d次剩余时候，f乘以一个非d次剩余$w$,使得$f\cdot w$是d次剩余,从而$f\cdot w$也是$\lambda$次剩余。
两点保证：
- 如果miller loop输出f不是r次剩余，$f\cdot w$也不是r次剩余
- 如果miller loop输出f不是$\lambda$次剩余，通过$f\cdot w$就可以得到$\lambda$次剩余

第一点保证了$f$不是$r$次剩余，但通过$f\cdot w$成为为$r$次剩余的可能(这样攻击者可以提供错误的f来完成证明)，可以参考作者的证明，不再赘述。
第二点作者给出引理2：
“如果b是非d次剩余，一定存在非d次剩余a，一定是r次剩余，同时$a\cdot b$是d次剩余”
证明：$h=d^s \cdot f=(p^k-1)/r, d\nmid f$, 一定可以找到a，a的阶为$d^s，ord(a)=d^s, r是素数, gcd(d^s,r)=1$,借助贝祖定理，a一定存在r次剩余，
反证法，假设a存在d次剩余，就有$b^d=a$, 因为$ord(a)=d^s, ord(b)=d^{s+1}$, 但是$d^{s+1}\nmid h, d^{s+1}\nmid q^k-1$, 也就是$b^{d^{s+1}} \ne 1$,所以a的阶为$d^s$时候，一定不存在d次剩余。
通过这个引理，可以很方便的找到一个非d次剩余，然后和b一起构造出d次剩余。
作者提出在BN curve下$d=3,s=3,d^s=27$即27-th剩余。

定理3：
$$\prod_ie(P_i,Q_i)=1 \iff \exists c，w\in F_{q^k}^*: \prod_if_{r,Q_i}(P_i)=c^{\lambda}w \land w^{d^s}=1 $$

这样可以预先根据miller loop $f\cdot w^{-1}$计算出$\lambda$剩余c，在pairing验证时候代替final exponent，使用$f\cdot (w \cdot c^{\lambda})^{-1}=1$来验证。
而$c^{\lambda}$的计算，可以嵌入到miller loop($\lambda$次循环)的计算过程中一起计算，很方便。
其中一些手推代码请参考白菜老师的文章[5]

参考:
[1] Pairing for beginners book
[2] https://download.yeez.tech/doc/ECcurve.pdf
[3] https://learnblockchain.cn/article/8052
[4] original paper: https://eprint.iacr.org/2024/640.pdf
[5] https://learnblockchain.cn/article/8150

Touch
- twitter: @muhuali956697
- email: [e-mail]