探索椭圆曲线配对

探索椭圆曲线配对

椭圆曲线配对是许多构造背后的关键密码原语，包括确定性阈值签名、zk-SNARKs 以及其他更简单的零知识证明形式。椭圆曲线配对（或称为“双线性映射”）是使用椭圆曲线进行密码应用的 30 年历史中的最近新元素，包括加密和数字签名；配对引入了一种“加密乘法”的形式，大大扩展了基于椭圆曲线的协议所能实现的功能。本文的目的是详细探讨椭圆曲线配对，并解释它们的工作原理的一般轮廓。

你不需要在第一次阅读时理解这里的所有内容，甚至在第十次也一样；这些内容确实很难。不过，期望这篇文章至少能让你对其背后的运行机制有一点了解。

椭圆曲线本身是一个相当复杂的主题，本文一般假设你了解它们的工作原理；如果你不了解，建议阅读这篇作为入门的文章：https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ 。快速总结一下，椭圆曲线密码学涉及被称为“点”的数学对象（这些是带有 (x, y) 坐标的实际二维点），并有特殊的公式用于加法和减法（即计算 R = P + Q 的坐标），你还可以将一个点乘以一个整数（即 P * n = P + P + … + P，不过如果 n 很大，这里有更快的计算方法）。

这是点加法的图形表示。

存在一个特殊的点称为“无穷远点”（O），相当于点算术中的零；总是有 P + O = P。此外，曲线有一个“阶”；存在一个数字 n 使得 P * n = O 对任何 P 成立（当然，P * (n+1) = P，P * (7*n + 5) = P * 5，等等）。还存在一些普遍认可的“生成点” G，可以在某种意义上表示数字 1。从理论上讲，曲线上的任何点（除了 O）都可以是 G；所有重要的是 G 是标准化的。

配对进一步一步，使你能够检查某些复杂的椭圆曲线点上的方程——例如，如果 P = G * p，Q = G * q 和 R = G * r，你可以检查 p * q = r 是否成立，仅通过 P、Q 和 R 作为输入。这可能看起来像是椭圆曲线的基本安全保证正在被破坏，因为有关 p 的信息从知道 P 中泄漏出来，但事实证明，这种泄漏是高度受限的——具体而言，可决 Diffie-Hellman 问题 是简单的，但计算 Diffie-Hellman 问题（在上述示例中知道 P 和 Q，计算 R = G * p * q）和离散对数问题（从 P 恢复 p）仍然在计算上是不可行的（至少，如果它们之前是不可行的话）。

查看配对功能的另一种方式，也许对我们考虑的大多数用例最为直观，是如果你将椭圆曲线点视为单向加密的数字（即 encrypt(p) = p * G = P），那么传统的椭圆曲线数学允许你检查 线性 约束（例如，如果 P = G * p，Q = G * q 和 R = G * r，检查 5 * P + 7 * Q = 11 * R 实际上是在检查 5 * p + 7 * q = 11 * r），配对允许你检查 二次 约束（例如，检查 e(P, Q) * e(G, G * 5) = 1 实际上是在检查 p * q + 5 = 0）。上升到二次是足够的，使我们能够处理确定性阈值签名、二次算术程序以及其他相关内容。

那么，我们上面引入的这个奇怪的 e(P, Q) 操作是什么呢？这就是配对。数学家有时也称其为 双线性映射；在这里，“双线性”这个词基本上意味着它满足以下约束：

e(P, Q + R) = e(P, Q) * e(P, R)

e(P + S, Q) = e(P, Q) * e(S, Q)

请注意 + 和 * 可以是任意运算符；当你创建新型的数学对象时，抽象代数并不关心 + 和 * 是如何 定义，只要它们在通常的方式中保持一致，例如 a + b = b + a，(a * b) * c = a * (b * c) 和 (a * c) + (b * c) = (a + b) * c。

如果 P、Q、R 和 S 是简单的 数字，那么做一个简单的配对是容易的：我们可以做 e(x, y) = 2^xy。然后，我们可以看到：

e(3, 4 + 5) = 2^(3 * 9) = 2²⁷

e(3, 4) * e(3, 5) = 2^(3 * 4) * 2^(3 * 5) = 2¹² * 2¹⁵ = 2²⁷

它是双线性的！

然而，这种简单的配对不适合用于密码学，因为它们处理的对象是简单整数，分析起来太容易；整数分割、计算对数和进行各种其他运算都很简单；简单的整数没有“公钥”或“单向函数”的概念。此外，使用上面描述的配对，你可以向后推导——知道 x，并且知道 e(x, y)，你可以简单地计算一个除法和对数来确定 y。我们需要的数学对象是尽可能接近“黑盒”的对象，能够加、减、乘和除，但 什么也做不了。这就是椭圆曲线和椭圆曲线配对的用武之地。

事实证明，在椭圆曲线点上制作双线性映射是可能的——即，构思一个函数 e(P, Q)，其中输入 P 和 Q 是椭圆曲线点，而输出称为 F_p¹² 元素（至少在这里我们将覆盖的特定情况中；具体细节因曲线的不同而异，稍后会详细说明），但实现起来的数学背景非常复杂。

首先，让我们讨论素数域和扩展域。上面这篇帖子中的美丽椭圆曲线只有在假设曲线方程使用常规实数定义的情况下才看起来如此。然而，如果我们在密码学中实际使用常规实数，那么你可以使用对数“回推”，一切都会崩溃；此外，实际存储和表示数字所需的空间可能会干扰。因此，我们改用 素数域 中的数字。

素数域由 0, 1, 2... p-1 的数字集合组成，其中 p 是素数，而各种运算定义如下：

a + b:  (a + b) % p
a * b:  (a * b) % p
a - b:  (a - b) % p
a / b:  (a * b^(p-2)) % p

基本上，所有数学运算都在模 p 下进行（有关模数学的介绍，请参见这里）。除法是一个特殊情况；通常，3/2 不是一个整数，这里我们只想处理整数，因此我们尝试找到数 x，使得 x * 2 = 3，而 * 当然是指上述定义的模乘法。感谢Fermat 小定理，上述的指数技巧就能完成工作，但还有更快的方法，使用扩展欧几里得算法。假设 p = 7；这里有几个例子：

2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3

如果你尝试这种数学，你会发现它完美地一致，并满足所有的常规法则。上面最后两个示例展示了 (a / b) * b = a；你还可以看到 (a + b) + c = a + (b + c)，(a + b) * c = a * c + b * c，所有你知道和喜爱的高中代数恒等式依然成立。在实际的椭圆曲线中，点和方程通常在素数域中计算。

现在，让我们谈谈 扩展域。你可能已在某处看到过扩展域；在数学教科书中，你遇到的最常见例子是复数域，其中实数域通过添加元素 sqrt(-1) = i 进行“扩展”。基本上，扩展域通过取现有的域，然后“发明”一个新元素，并定义该元素与现有元素之间的关系（在这种情况下，i² + 1 = 0），确保这个方程在原始域中的任何数上均不成立，查看原始域和新元素的所有线性组合的集合。

我们也可以对素数域进行扩展；例如，我们可以用 i 扩展上面描述的模 7 的素数域，然后我们可以做：

(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i

最后一个结果可能有点难以计算；发生的事情是，我们首先将乘积分解为 4i * 2 + 4i * i，这给出 8i - 4，然后由于我们在模 7 数学中进行，这变为 i + 3。要进行除法，我们做：

a / b:  (a * b^(p^2-2)) % p

请注意，Fermat 小定理的指数现在是 p² 而不是 p，但再次提醒，如果我们希望更有效，我们也可以扩展扩展欧几里得算法来完成这项工作。请注意，对于该域中的任何 x，都有 x^(p² - 1) = 1，因此我们称 p² - 1 为该域中乘法群的“阶”。

对于实数， 代数基本定理 确保我们称为复数的二次扩展是“完备”的——你无法进一步扩展，因为对于任何数学关系（至少是由代数公式定义的），你可以提出一些新元素 j 与现有复数之间的关系，可以构造至少一个已经满足该关系的复数。然而，在素数域中，我们没有这个问题，因此我们可以继续进行立方扩展（其中某个新元素 w 与现有域元素之间的数学关系是一个立方方程，因此 1、w 和 w² 彼此之间是线性无关的），更高阶扩展，扩展的扩展等等。而正是这些类型的超级充能模复数，构成了椭圆曲线配对的基础。

对于那些想看到实施所有这些运算相关数学的代码的人，素数域和域扩展的实现请参见：

https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py

现在，进入椭圆曲线配对。一种椭圆曲线配对（或更确切地说，我们将在此探讨的特定形式的配对；还有其他类型的配对，尽管它们的逻辑相似）是一个映射 G2 x G1 -> Gt，其中：

• G1 是一个椭圆曲线，点满足形如 y² = x³ + b 的方程，并且两坐标都是 F_p 的元素（即它们是简单数字，除了算术都是模某个素数下进行）
• G2 是一个椭圆曲线，点满足与 G1 相同的方程，不过坐标是 F_p¹² 的元素（即它们是我们上面谈到的超级充能复数；我们定义一个新的“魔法数字” w，它由类似 w^12 - 18 * w^6 + 82 = 0 的 12 次多项式定义）
• Gt 是椭圆曲线结果所进入的对象类型。在我们查看的曲线中，Gt 是 F_p¹²（与在 G2 中使用的超级充能复数相同）

它必须满足的主要属性是双线性，这在此上下文中意味着：

• e(P, Q + R) = e(P, Q) * e(P, R)
• e(P + Q, R) = e(P, R) * e(Q, R)

还有两个其他重要标准：

• 高效可计算性（例如，我们可以通过简单地取所有点的离散对数并将它们相乘来生成简单的配对，但这在计算上与破解椭圆曲线密码学一样困难，因此不算数）
• 非退化性（当然，你可以定义 e(P, Q) = 1，但这并不是一个特别有用的配对）

那么我们如何做到这一点？

配对函数工作原理背后的数学相当棘手，并涉及相当多的高级代数，在我们的讨论之外，但我会提供一个轮廓。首先，我们需要定义 除法子 的概念，基本上是表示椭圆曲线点上函数的另一种方式。一个函数的除法子基本上计算函数的零点和无穷远点。来看一些例子。让我们固定某一点 P = (P_x, P_y)，并考虑以下函数：

f(x, y) = x - P_x

这个除法子是 [P] + [-P] - 2 * [O]（方括号用于表示我们在讨论 点 P 在函数的零和无穷远点集合中的存在，而不是点 P 本身； [P] + [Q] 不 等于 [P + Q]）。推理如下：

• 在 P 处函数为零，因为 x 是 P_x，所以 x - P_x = 0
• 在 -P 处函数为零，因为 -P 和 P 共享相同的 x 坐标
• 当 x 趋向无穷大时，该函数趋向无穷，因此我们说该函数在 O 处等于无穷。这里存在一个技术原因，使得这个无穷需要被计算两次，因此 O 被添加了“重数”为 -2（负数是因为它是无穷而不是零，二是因为这个双重计算）。

该技术原因大体上是这样的：因为曲线的方程是 x³ = y² + b，所以 y 的增长速度“是 x 的 1.5 倍”，才能使 y² 跟得上 x³；因此，如果一个线性函数仅包括 x，则它表示为重数为 2 的无穷，但如果它包括 y，则它表示为重数为 3 的无穷。

现在，考虑一个“线性函数”：

ax + by + c = 0

其中 a、b 和 c 是精心选择的，以确保该线通过 P 和 Q 点。由于椭圆曲线加法的工作原理（见上面的图表），这也意味着它通过 -P-Q。并且它依赖于 x 和 y 的变化趋向无穷，因此除法子变为 [P] + [Q] + [-P-Q] - 3 * [O]。

我们知道每个“有理函数”（即仅使用有限数量的 +、-、* 和 / 操作来定义的函数）唯一对应某个除法子，除了乘以常数（即如果两个函数 F 和 G 具有相同的除法子，则 F = G * k，对某个常数 k 成立）。

对于任何两个函数 F 和 G，F * G 的除法子等于 F 的除法子加上 G 的除法子（在数学教科书中，你会看到 (F * G) = (F) + (G)），因此示例如果 f(x, y) = P_x - x，那么 (f³) = 3 * [P] + 3 * [-P] - 6 * [O]；P 和 -P 在这些点上是“三重计数”的，因为在某种数学意义上，f³ 在那些点上以“快三倍”的速度接近 0。

请注意有这样一个定理：如果你“去掉除法子中的方括号”，那么这些点的和必须等于 O（[P] + [Q] + [-P-Q] - 3 * [O] 显然符合，因为 P + Q - P - Q - 3 * O = O），且所有具有这一性质的除法子都是一个函数的除法子。

现在，我们准备来看看 Tate 配对。考虑以下通过其除法子定义的函数：

• (F_P) = n * [P] - n * [O]，其中 n 是 G1 的阶，即 n * P = O 对任何 P 成立
• (F_Q) = n * [Q] - n * [O]
• (g) = [P + Q] - [P] - [Q] + [O]

现在，让我们看一下 F_P * F_Q * g^n 的乘积。这个除法子是：

n * [P] - n * [O] + n * [Q] - n * [O] + n * [P + Q] - n * [P] - n * [Q] + n * [O]

简化后得到：

n * [P + Q] - n * [O]

注意，这个除法子的格式与上述 F_P 和 F_Q 的除法子完全相同。因此，F_P * F_Q * g^n = F_(P + Q)。

现在，我们引入一个称为“终指数化”步骤的过程，在此过程中，我们将上述函数的结果（F_P、F_Q 等）提升至幂 z = (p¹² - 1) / n，其中 p¹² - 1 是 F_p¹² 中乘法群的阶（即，对于 任何 x ϵ F_p¹²，x^(p¹² - 1) = 1）。注意，如果你对已经被提升至 n 次幂的任何结果进行这个指数运算，你会得到以 p¹² - 1 为幂的运算，因此结果变为 1。因此，在终指数化后，g^n 被消除，我们得到 F_P^z * F_Q^z = F_(P + Q)^z。这里有一些双线性。

现在，如果你想构建一个在两个参数上都是双线性的函数，你需要进入更为复杂的数学，而不是直接取 F_P 的值，而是取 F_P 的 除法子，这就是完整的“Tate 配对”所来自的地方。为了证明更多结果，你必须处理“线性等价”和“Weil 互惠”等概念，接下来的讨论将不断开展。你可以在这里和这里找到更多的阅读材料。

有关称为最佳 Ate 配对的 Tate 配对的改进版本的实现，请见此处。该代码实现了Miller的算法，它是实际计算 F_P 所需的。

请注意，这种配对是可能的这一事实是好坏参半的祝福：一方面，这意味着我们可以做的所有协议都将成为可能，但这也意味着我们必须更加小心选择使用的椭圆曲线。

每个椭圆曲线都有一个称为 嵌入度 的值；本质上，这是使得 p^k - 1 是 n 的倍数的最小 k（其中 p 是用于域的素数，而 n 是曲线阶）。在上述领域中，k = 12，在用于传统 ECC 的领域中（即我们不关心配对时），嵌入度通常是极大的，以至于配对的计算在计算上不可行；然而，如果我们不小心，就可以生成 k = 4 甚至 1 的字段。

如果 k = 1，那么椭圆曲线的“离散对数”问题（本质上是知道 P = G * p 仅恢复 p 的问题，即“破解”椭圆曲线私钥必需解决的问题）可以降低为在 F_p 上的类似数学问题，而这个问题变得容易得多（这被称为 MOV 攻击）；使用嵌入度为 12 或更高的曲线可以确保这个降维要么不可用，要么解决配对结果上的离散对数问题至少与按“正常方式”从公钥恢复私钥（即计算上不可行）一样困难。请放心；所有标准曲线参数都已仔细检查这一问题。

敬请期待即将到来的 zk-SNARKs 工作原理的数学解释。

特别感谢 Christian Reitwiessner、Ariel Gabizon（来自 Zcash）和 Alfred Menezes 的审核与反馈。

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