title: 38. Tate 配对
tags:
  - 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 中：

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

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 配对被以太坊采纳并用于计算配对。