readme.md

title	tags
38. Tate 配对	zk abstract algebra elliptic curve group theory finite field pairing

WTF zk 教程第 38 讲：Tate 配对

这一讲，我们介绍 Tate 配对和它的变种 Ate 配对，它们改进了 Weil 配对，增加了计算效率。

1. Tate 配对

Tate 配对是一种定义在有限域上的椭圆曲线 $E(F_Q)$的双线性配对，其中 $q = p^n$。

定义： $m$ 是与 $q$ 互质的质数 $q \equiv 1 \pmod{m}$，且 $E[m] \cong \mathbb{Z}/m\mathbb{Z}$，Tate 配对将椭圆曲线 $m$-挠群 $E[m]$ 上的两点 $P, Q$ 映射到有限域 $F_q$ 中：

$$ \hat{\tau}(P, Q) = (\frac{f_P(Q+X)}{f_P(X)})^{(q-1)/m} $$

其中 $X$ 是椭圆曲线上的任意点，满足 $f_P(Q+X)$ 和 $f_P(X)$ 非零。而 $f_P$ 是定义在椭圆曲线 $E(F_Q)$ 上的有理函数，它的除子满足：

$$ \text{div}(f_P) = m[P] - m[O] $$

Tate 配对具有以下性质：

性质1. 双线性： Tate 配对满足 $\hat{\tau}(P + R, Q) = \hat{\tau}_m(P, Q) \hat{\tau}_m(R, Q)$ 和 $\hat{\tau}_m(P, Q + R) = \hat{\tau}_m(P, Q) \hat{\tau}_m(P, Q)$。

性质2. 非退化性： 若对于非零的点 $P \in E[m]$，有 $\hat{\tau}_m(P,P) \in \mu_m$ 成立，即 $\hat{\tau}_m(P,P) ^m = 1$ 且 $\hat{\tau}_m(P,P) ^m \neq 1$

性质3. 计算高效： Weil 配对需要我们计算 $f_P$ 和 $f_Q$，但 Tate 配对只需要我们计算 $f_P$，可以用 Miller 算法更加高效的计算。

2. Ate 配对

Ate 配对是 Tate 配对的一个变种，优化了计算过程。Ate 配对使用了 Frobenius 映射和一个较小的循环长度来减少计算中的迭代次数，从而加速配对的计算。以太坊上的配对都是基于 Ate 配对实现的，详见 EIP-197。

下面我们使用以太坊的 py_ecc 库写一个配对示例。在这个示例中，我们取了椭圆曲线上的两个生成元 $G_1$ 和 $G_2$，其中 $G_2$ 是每个坐标用复数 $a+bi$ 表示，看起来会复杂一些，但是性质和之前是一样的。

然后，我们取了三个数 $a = 69, b = 420, c = ab = 28980$，然后计算了三个点 $A= aG_2, B = bG_1, C = cG_2$，然后用配对验证 $e(A, B)$ 和 $e(G_2, C)$ 是否相等。

因为 $ab = c$，所以 $e(A, B) = e(aG_2, bG_1) = abe(G_2, G_1) = ce(G_2, G_1) = e(G_2, cG_1) = e(G_2, C)$，所以两个配对相等。这样，我们可以在不知道 $a, b$ 的情况下，通过 $A, B, C, G_2$ 的配对来验证 $ab = 28980$，非常神奇。

from py_ecc.bn128 import G1, G2, pairing, add, multiply, eq

print(G1)
print(G2)
print("\n")

a = 69
b = 420
c = a * b
A = multiply(G2, a)
B = multiply(G1, b)
pair_A_B = pairing(A, B)
print("Pairing of points A and B: ",pair_A_B)
print("\n")

C = multiply(G2, c)
pair_G2_C = pairing(C, G1)
print("Pairing of points G2 and C: ",pair_G2_C)
print("\n")

print("Is pair_A_B == pair_G2_C? ", pair_A_B == pair_G2_C)

# 输出
# (1, 2)
# ((10857046999023057135944570762232829481370756359578518086990519993285655852781, 11559732032986387107991004021392285783925812861821192530917403151452391805634), (8495653923123431417604973247489272438418190587263600148770280649306958101930, 4082367875863433681332203403145435568316851327593401208105741076214120093531))


# Pairing of points A and B:  (19735667940922659777402175920395455799125563888708961631093487249968872129612, 1976543863057094994989237517814173599120655827589866703826517845909315612857, 19686523416572620016989349096902944934819162198495809257491045534399198954254, 5826646852844954420149583478015267673527445979905768896060072350584178989060, 2064185964405234542610947637037132798744921024553195185441592358018988389207, 8341934863294343910133492936755210611939463215146220944606211376003151106114, 12807669762027938768857302676393862225355612177677457846751491105239425227277, 5741126950795831539169012545403256931813076395529913201048083937620822856065, 11074901068523180915867722424807487877141140784438044188857570704539589417315, 19327019285776193278582429402961044775129507055467003359023290900912857119476, 17306986078986604236447922180440988200852103029519452658980599808670992125088, 13188937242065601189938233945175869194113210620973903647453917247887073581439)


# Pairing of points G2 and C:  (19735667940922659777402175920395455799125563888708961631093487249968872129612, 1976543863057094994989237517814173599120655827589866703826517845909315612857, 19686523416572620016989349096902944934819162198495809257491045534399198954254, 5826646852844954420149583478015267673527445979905768896060072350584178989060, 2064185964405234542610947637037132798744921024553195185441592358018988389207, 8341934863294343910133492936755210611939463215146220944606211376003151106114, 12807669762027938768857302676393862225355612177677457846751491105239425227277, 5741126950795831539169012545403256931813076395529913201048083937620822856065, 11074901068523180915867722424807487877141140784438044188857570704539589417315, 19327019285776193278582429402961044775129507055467003359023290900912857119476, 17306986078986604236447922180440988200852103029519452658980599808670992125088, 13188937242065601189938233945175869194113210620973903647453917247887073581439)


# Is pair_A_B == pair_G2_C?  True

3. 总结

这一讲，我们介绍了 Tate 配对和它的变种 Ate 配对，它们在计算上都比 Weil 要高效。其中，Ate 配对被以太坊采纳并用于计算配对。