配对技术入门（一）：寻找 G1 和 G2

为吾等提供的配对

第一部分：寻找 G1 和 G2

椭圆曲线 (EC) 配对广泛应用于零知识证明 (ZKP) 以及更广泛的密码学领域。 大多数 ZK 学习资源建议将其内部运作视为一个黑盒，并专注于它们在不同证明系统中的应用。 这种方法通常足以满足初学者和大多数 ZK 从业者的需求。 一般来说，如果人们想快速地学习，用“黑盒”方法来处理复杂的主题是一个不错的策略。 配对通常在常用的库中实现，因此对配对应用的基本理解通常就足够了。

然而，对于那些真正好奇底层机制的人来说，深入研究可能具有挑战性。 大部分资源倾向于数学密集型，引入了大量的新概念和符号。

我以个人经验说话。 我从智能合约开发背景出身，没有任何数学专业知识，参加了一个 ZK 训练营 (RareSkills) 并完成了“月球数学手册”。 尽管我努力更深入地理解配对，但我始终受到缺乏入门级资源的阻碍。 在一个简单的搜索中找到的第一本书是 Craig Castello 的“Pairings for Beginners”。 标题听起来很有希望，对吧？ 它包含丰富的示例并简化了许多复杂的主题。 然而，大多数人会认为它根本不适合初学者。 这种易于理解的资源的缺乏促使我进一步探索该主题并撰写本文，希望帮助面临类似挑战的开发人员。

我用来学习 EC 配对并从中获得极大启发的资源：

• "MoonMath Manual" by "Least Authority"
• "Pairings for Beginners" by Craig Castello
• "Compute the Tate Pairing" by Michael Scott
• "An Introduction to Mathematical Cryptography" by J. Hoffstein, J. Pipher and J. Silverman

本文档记录了我的学习历程。 作为一名新手，我可能犯了一些错误和不准确之处，因此我欢迎你的反馈。

目标和先决条件

本文的目标是从基本原理开始逐步执行大多数计算，从而实现两个 EC 点的 Tate 配对，

$P$ 和

$Q$。 我们专注于 Tate 配对而非 Weil 配对，因为在实践中，Tate 配对的计算效率更高。 此外，我检查的大多数库（例如 py_ecc、substrate-bn 和 arkworks）都实现了 Tate 配对或其变体。

请注意，本文不涵盖配对的特征或其在 ZKP 中的应用。 相反，它的目的是帮助那些已经对配对有大致了解并且理想情况下以前使用过配对的人。 因此，我假设你事先了解模运算、有限域、椭圆曲线以及 EC 点的加法和乘法。 对于那些需要复习的人，我推荐 OpenZeppelin 的 这个视频 作为配对的一个很好的入门读物。

迷你 JubJub

为了方便表示和手动计算，我们将使用一个点数有限的椭圆曲线，称为“迷你 JubJub”曲线，该曲线也出现在“MoonMath Manual”中。

该曲线的方程是

$y^2 = x^3 + 8x + 8 \mod 13$。 椭圆曲线由素域中的所有对

$(x, y)$ 组成

$F_{13}$，满足此方程。 在

169 个可能的对中

$(13 \times 13)$，只有

20 种组合

$(x, y)$ 满足标准，使我们的曲线的阶数（基数）为 20

$(n = 20)$：

{O,(1,2),(1,11),(4,0),(5,2),(5,11),(6,5),(6,8),(7,2),(7,11),(8,5),(8,8),(9,4),

(9,9),(10,3),(10,10),(11,6),(11,7),(12,5),(12,8)}

根据定义，

$P$ 和

$Q$ 必须来自两个不同的、具有相同素数阶的循环子群，称为

$G_1$ 和

$G_2$。 虽然我们可以试验上面的点来形成不同的子群，但我们最终发现

$F_{13}$ 中“迷你 JubJub”中没有两个具有相同素数阶的子群。

为了解决这个问题，我们扩展素域

$q$ 并在一个更大的点群中运算，其中包括最初的

20 个点。

域扩展

域扩展上的 EC 是我花了一段时间才理解并为之建立清晰的思维模型的主题。 当我第一次遇到 EC 时，它们看起来很全面而且不太难。 是的，点加法和乘法与通常的算术不同，但你很快就能理解它们。 展望未来，我意识到大部分魔法都发生在域扩展中。 这就是为什么对域扩展有扎实的理解至关重要。

我们之前定义了域

$F_{13}$，其元素为

${0, 1, \dots, 12}$，模数为

$q = 13$。 现在，二次扩展的元素和模数 (

$F_{13^2}$) 会是什么样子？ 在这里，一个小小的精确：

$13^2$ 并不意味着我们将模数提高到 2 的幂，而是表明新域包含

169 个元素。 为了表示来自二次扩展的元素，我们将一个新的维度添加到初始元素中

$F_{13}$：

${(0, 0), (0, 1), \dots, (1, 0), (1, 2), (1, 3), \dots, (12, 11), (12, 12)}$

现在，来自

$F_{13^2}$ 的每个元素都由来自

$F_{13}$ 的两个元素表示。 加法是直观的：

$(1, 2) + (2, 5) = (3, 7)$ 或

$(7, 9) + (8, 5) = (15, 14) = (2, 1)$。 乘法呢？ 为此，我们需要一个二次模数。 有人可能会猜到它将具有相同的形式

$(a, b)$，但我们如何选择它呢？

首先，让我们看看一个方便算术的技巧。 我们将每个元素都视为一个 1 次多项式； 例如，

$(4, 7)$ 将是

$4 + 7x$，或者

$(0, 5)$ 将是

$0 + 5x$。 在最初的

$F_{13}$ 中的模数是

13，一个素数，这意味着我们无法将其分解（除了

$1 * 13$）。 记住，我们也可以将其称为有限域的零，因为

$13 = 0$。

多项式领域中素数的等价物是 不可约多项式。 例如，多项式

$x^2 - 1$ 可以分解为

$(x - 1)(x + 1)$，因此它是可约的。 直观地说，我们必须选择一个在

$F_{13}$ 中不可约的多项式，它将作为我们二次扩展中的模数。 虽然二次扩展中的元素由 1 次多项式表示，但模数需要更高次。 多项式

$x^2 + 2$ 满足这些要求，因此它将在扩展中充当零，

$x^2 + 2 = 0$ 或

$x^2 = -2$。

回到二次扩展中关于乘法的问题：

$(7, 3) (5, 6) = (7 + 3x) (5 + 6x) = 35 + 15x + 42x + 18x^2 = 35 + 57x + 18x^2$

将系数约简

$\mod 13$，我们最终得到

$9 + 5x + 5x^2$，但请记住，在二次扩展中

$x^2 = -2$，因此

$9 + 5x + 5x^2 = 9 + 5x - 10 = -1 + 5x = 12 + 5x$ (其中

$-1 = 12 \mod 13$)。

因此，

$(7, 3) * (5, 6) = (12, 5)$

相同的过程可以应用于更高次扩展。

一些关键要点：

1. 扩展一个域意味着向每个元素添加一个新的维度。
2. 每个更高的扩展都包含来自先前扩展的元素，并添加更多元素。
3. 作为扩展域模数的多项式，其阶数必须比域中元素的阶数高 1，并且在基本有限域中不可约。

我们可以回到“迷你 JubJub”曲线，并更好地描述其在

$F_{13^2}$ 上的点。 例如，点

$(5, 2)$ 变为

$((5 + 0x), (2 + 0x)) = ((5, 0), (2, 0))$。 此外，我们还将找到全新的点，例如

$((12 + 3x), (9 + x)) = ((12, 3), (9, 1))$。 除了最初的

20 个点之外，我们还可以计算另外

140 个点。 这使得曲线在

$F_{13^2}$ 上的阶数等于

160.

完全 r-扭群

现在我们对扩展域上的 EC 有了基本的了解，我们可以深入研究以寻找具有相同素数阶的点的不同子群。 为此，我们将基本域扩展一个特定值，

$m$。 我们如何确定

$m$？

以下是要遵循的步骤：

1. 找到曲线阶数的一个素数因子，通常是最大的一个。 回想一下“迷你 JubJub”曲线的阶数

$n = 20$ 且

$20 = 2 \times 2 \times 5$。 将此因子分配给

$r = 5$。

2. 找到最小的

$k$，使得

$r$ 无余数地整除

$q^k - 1$。

• $k = 1$ 不起作用，因为

  $13^1 - 1 = 12$，并且

  $5$ 不能整除

  $12$

• $k = 2$ 且

  $k = 3$ 产生相同的结果

• 对于

  $k = 4$，我们发现

  $13^4 - 1 = 28560$，它可以被

  $5$ 整除

因此，我们将

$k = 4$ 指定为 嵌入度。

3. 将基本域

$F_{13}$ 扩展

$m$，其中

$m = k$。 这定义了在

$F_{13^4}$ 上的“迷你 JubJub”，产生

28,800 个点。

4. 在这

28,800 个点中，识别那些在乘以

$r$ 时的阶数导致无穷远点的点。 这些点构成了 完全 5-扭群，总共有

$25$ 个点。

5. 将完全 5-扭群划分为

$6$ 个子群 ($r + 1$)。 你可能已经猜到，我们即将找到圣杯：

$G_1$ 和

$G_2$ 是这些子群中的一些。 值得注意的是，其中一个子群（顶部中心）包含与来自非扩展曲线的一些点相同的点。

注意：“完全

$r$-扭群”部分提出了是否存在非完全

$r$-扭群的问题，答案是肯定的：通过将域扩展

$m$，其中

$m < k$。 但是，这并不总是保证我们会找到我们正在寻找的子群。

Frobenius 自同态和迹映射

在确定嵌入度

$k = 4$ 并将基本域扩展

$m = k$ 之后，我们探索了由此产生的具有许多新点的群（28,800 个），重点关注那些乘以

$r = 5$ 时映射到无穷远点

$O$ 的点。 这个由 25 个点组成的群被称为完全 5-扭群。 此外，我们将完全 5-扭群划分为 6 个不同的子群。 现在的目标是识别

$G_1$ 和

$G_2$。 为了实现此目标，我们首先必须了解 Frobenius 自同态和迹映射

$Tr(P)$。

Frobenius 自同态

Frobenius 自同态是一个映射

$\pi$，它简单地将 EC 点的每个坐标提高到基本域的幂：

$\pi(x, y) \rightarrow (x^q, y^q)$

此操作保证了结果点仍保留在群中（因此称为“自同态”）。 例如，从非扩展域上的 EC 中取一个点并将其提高到

$q$ 的幂，我们得到相同的点：

$(7, 11) \rightarrow 7^{13} = 7 \pmod{13} \text{ 且 } 11^{13} = 11 \pmod{13}$

在更大的扩展中，例如在

$F_{13^4}$ 上，我们首先将

$q = 13$ 提升到

$m = 4 \Rightarrow 13^4 = 28561$，然后：

$(7, 11) \rightarrow 7^{28561} = 7 \pmod{13} \text{ 且 } 11^{28561} = 11 \pmod{13}$

乍一看，你可能不会觉得 Frobenius 自同态有趣，但请耐心听我说。

迹映射

迹映射

$Tr(P)$ 提高一个点的的坐标，类似于 Frobenius 自同态。 但是，它根据嵌入度进行迭代，并导致中间点的总和：

$Tr(P) = \sum_{i=0}^{k-1} (x^{q^i}, y^{q^i})$

记住，我们找到了嵌入度

$k = 4$，所以在我们的例子中，

$Tr(P)$ 看起来像这样：

$Tr(P) = (x^{q^0}, y^{q^0}) + (x^{q^1}, y^{q^1}) + (x^{q^2}, y^{q^2}) + (x^{q^3}, y^{q^3})$

如果我们应用迹映射，那么对于来自完全 5-扭群的一些点，会发生一些有趣的事情。

子群 G1

你可能已经猜到，

$G_1$ 点是那些令人怀疑地类似于非扩展曲线的点。 将迹映射应用于它们将导致来自同一子群的另一个点；

$Tr$ 具有乘以

$k$ 的效果。

让我们用

$R = (7, 11)$ 来演示：

• $R_0 = R = (7, 11)$
• $R_1 = (7^{13}, 11^{13}) = (7, 11)$
• $R_2 = (7^{13^2}, 11^{13^2}) = (7, 11)$
• $R_3 = (7^{13^3}, 11^{13^3}) = (7, 11)$

$R_0 + R_1 + R_2 + R_3 = (7, 2) = (7, 11) k = (7, 11) 4$

子群 G2

让我们从较低的中心子群中取

$S = (4x^2 + 7, 5x^3 + 10x)$：

1. 通过连续提高点的坐标来计算

$k$ 个中间点

• $S_0 = S = (4x^2 + 7, 5x^3 + 10x)$
• $S_1 = ((4x^2 + 7)^{13}, (5x^3 + 10x)^{13}) = (9x^2 + 7, x^3 + 11x)$
• $S_2 = ((4x^2 + 7)^{13^2}, (5x^3 + 10x)^{13^2}) = (4x^2 + 7, 8x^3 + 3x)$
• $S_3 = ((4x^2 + 7)^{13^3}, (5x^3 + 10x)^{13^3}) = (9x^2 + 7, 12x^3 + 2x)$
  2. 使用群加法法则将这些中间点加起来

$S_0 + S_1 + S_2 + S_3$ 得到

$O$，无穷远点。 将迹映射应用于来自子群的其他

$4$ 个点会产生相同的结果。 恭喜，我们刚刚找到

$G_2$ 中的点。

结论

在本文中，我们介绍了理解域扩展上的椭圆曲线配对的基本概念，重点关注 Frobenius 自同态和迹映射以识别子群

$G_1$ 和

$G_2$。

在 下一部分 中，我们将逐步实现 Tate 配对，应用我们获得的知识。 请继续关注！

---

我欢迎任何反馈、更正或建议，以改进内容并帮助所有读者更好地理解该主题。 感谢你加入我的旅程，并随时通过 X 在 @BoyanBarakov 上与我联系。

• 原文链接： hackmd.io/@brozorec/pair...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～