[镜像] 探索椭圆曲线配对

这是对在https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627的帖子进行的镜像.

触发警告：数学。

各种构造背后的关键密码学原语之一，包括确定性阈值签名、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都有P⋅n=O（当然，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）仍然在计算上是不可行的（至少，如果在之前是不可行的话）。

查看配对所做的第三种方式，对于大多数我们正在使用的用例来说，可能是最具启发性的就是，如果你将椭圆曲线点视为单向加密的数字（即，加密(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)=2xy。那么，我们可以看到：

e(3,4+5)=23⋅9=227

e(3,4)⋅e(3,5)=23⋅4⋅23⋅5=212⋅215=227

它是双线性的！

然而，这种简单的配对不适合密码学，因为它们操作的对象是简单的整数，容易分析；整数使得分割、计算对数和进行各种其他计算变得简单；简单的整数没有“公钥”或“单向函数”的概念。此外，使用上述描述的配对你可以逆向操作——知道x，以及知道e(x,y)，你可以简单地计算一个分割和对数来确定y。我们希望数学对象尽可能接近“黑盒”，你可以加、减、乘和除，但什么也做不了。这就是椭圆曲线和椭圆曲线配对的应用场景。

事实证明，可以在椭圆曲线点上构造双线性映射——即，想出一个函数e(P,Q)，其中输入P和Q是椭圆曲线上的点，而输出是称为(Fp)12的元素（至少在我们将讨论的特定情况下；具体取决于曲线的细节，稍后会讨论），但实现这一目标的数学是相当复杂的。

首先，让我们讨论素域和扩展域。之前帖子中漂亮的椭圆曲线照片仅在假设曲线方程使用常规实数定义的情况下才是这样的。然而，如果我们在密码学中实际使用常规实数，那么你可以使用对数“逆向推导”，而一切都会崩溃；此外，实际存储和表示这些数字所需的空间可能会任意增长。因此，我们使用素域中的数字。

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

a+b:(a+b) % p

a⋅b:(a⋅b) % p

a−b:(a−b) % p

a/b:(a⋅bp−2) % p

基本上，所有数学都是模p的（有关模数学介绍，请参见这里）。除法是一个特殊情况；通常情况下，32不是一个整数，这里我们希望仅处理整数，因此我们尝试找到数字x，使得x⋅2=3，其中⋅当然指的是上述定义的模乘法。得益于费马小定理，上述的指数技巧能奏效，但还有更快速的办法，可以使用扩展欧几里得算法。假设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⋅25) % 7=5

5⋅2=10 % 7=3

如果你在这种数学上进行操作，你会发现它是完全一致的，满足所有常规规则。上面最后两个例子展示了(a/b)⋅b=a；你还可以看到(a+b)+c=a+(b+c)、(a+b)⋅c=a⋅c+b⋅c，你所熟悉和喜爱的所有其他高中代数恒等式继续保持有效。在实际的椭圆曲线中，点和方程通常是在素域中计算的。

现在，让我们谈谈扩展域。你可能已经在以前见过扩展域；你在数学教科书中遇到的最常见的例子是复数域，其中实数域通过添加元素−1=i“扩展”。基本上，扩展域的工作方式是取一个现有域，然后“发明”一个新元素并定义该元素与现有元素之间的关系（在这种情况下，i2+1=0），确保此方程在原域中的任何数字上都不成立，接着查看源域元素和新元素的所有线性组合的集合。

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

(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，然后，因为我们在mod7数学中工作，所以这变成了i+3。为了除法，我们求:

a/b:(a⋅b(p2−2)) % p

请注意，费马小定理的指数现在是p2而不是p，尽管如果我们希望更高效，也可以将扩展欧几里得算法扩展到此目的。注意xp2−1=1对于此域中的任何x都成立，因此我们称p2−1为“域中乘法群的顺序”。

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

对于那些对在代码中写出所有这些操作的确切数学感兴趣的人，素域和域扩展在这里被实现：<https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py>

现在，谈到椭圆曲线配对。椭圆曲线配对（或者更确切地说，我们在这里将讨论的特定形式的配对；还有其他类型的配对，尽管它们的逻辑相当相似）是一个映射G2×G1→Gt，其中：

• G1是一个椭圆曲线，其中点满足方程y2=x3+b，并且两个坐标都是Fp的元素（即，它们是简单的数字，除了所有算术都在某个素数模下进行）

• G2是一个椭圆曲线，其中点满足与G1相同的方程，只是坐标是(Fp)12的元素（即，它们是我们上面讨论的超充复数；我们定义一个新的“魔法数字”w，这由一个12次多项式如w12−18⋅w6+82=0定义）

• Gt是椭圆曲线结果进入的对象类型。在我们查看的曲线中，Gt是(Fp)12（与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=(Px,Py)，并考虑如下函数：

f(x,y)=x−Px

除数为[P]+[−P]−2⋅[O]（方括号用于表示我们指的是_点P在函数的零点和无穷远点集合中的存在，而不是点P本身；[P]+[Q]绝对不是[P+Q]）。推理如下：

• 函数在P处等于零，因为x 是 Px，因此x−Px=0

• 函数在−P处等于零，因为−P和P共享相同的x坐标

• 当x趋向于无穷大时，函数趋向于无穷远，因此我们说函数在O处等于无穷远。因为在这个无穷远需要数两次，所以O以“重数”−2被加入（因为这是无穷远而不是零，重数为负，因双重计数所以重数为2）。

我们知道的技术原因大约是这样的：因为曲线方程是x3=y2+b，y的增长速度是“1.5倍更快”以使y2跟上x3；因此，如果线性函数只包括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)=Px−x，那么(f3)=3⋅[P]+3⋅[−P]−6⋅[O]；在那些点上P和−P被“三重计数”，以表明f3在这些点趋向零的速度在某种数学意义上是“三倍更快”。

请注意，有一个定理指出，如果你“去掉方括号”，函数的除数中的点必须最终加起来到O（[P]+[Q]+[−P−Q]−3⋅[O]显然适合，因为P+Q−P−Q−3⋅O=O），并且任何具有此性质的除数都是某个函数的除数。

现在，我们准备看看泰特配对。考虑根据它们的除数定义的如下函数：

• (FP)=n⋅[P]−n⋅[O]，其中n是G1的阶，即n⋅P=O对于任何P

• (FQ)=n⋅[Q]−n⋅[O]

• (g)=[P+Q]−[P]−[Q]+[O]

现在，让我们看看产品FP⋅FQ⋅gn。除数为：

n⋅[P]−n⋅[O]+n⋅[Q]−n⋅[O]+n⋅[P+Q]−n⋅[P]−n⋅[Q]+n⋅[O]

这简化为：

n⋅[P+Q]−n⋅[O]

注意这个除数恰好与上面FP和FQ的格式相同。因此，FP⋅FQ⋅gn=FP+Q。

现在，我们引入一个称为“最终指数化”步骤的过程，在这个过程中，我们将上述函数的结果(FP、FQ等)提高到z=(p12−1)/n的幂，其中p12−1是(Fp)12中乘法群的阶（即，对于_Fp)12中的任何x，x(p12−1)=1）。注意，如果你将此指数应用于已经提升到n的任意结果，你将得到提升到p12−1的幂，因此结果变为1。因此，在最终指数之后，gn会抵消，得到FPz⋅FQz=(FP+Q)z。这正是一些双线性属性。

现在，如果你想构建一个在两个参数上都是双线性的函数，你需要进入更复杂的数学领域，其中不是直接取FP某个值，而是取FP某个除数，这就是完整的“泰特配对”来自何处。为了证明一些结果，你必须处理“线性等价”和“魏尔互换”等概念，接下来的内容将更加深入。你可以在这里和这里找到更多阅读材料。

有关一种称为最优Ate配对的泰特配对修改版的实现，请参见这里。该代码实现了Miller算法，这是实际计算FP所需的。

请注意，配对如上所述是可能的，这在某种程度上是福祉的混合体：一方面，这意味着我们可以用配对的所有协议都变得可能，但这也意味着我们必须更加小心我们使用的椭圆曲线。

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

如果k=1，则椭圆曲线的“离散对数”问题（本质上，知道点P=G⋅p而仅恢复p的问题，即你必须解决的问题以“破解”椭圆曲线私钥）可以转化为在Fp上类似的数学问题，其中问题变得简单得多（这被称为MOV攻击）；使用嵌入度为12或更高的曲线确保这种转化不可用，或者在配对结果上解决离散对数问题至少与“正常方式”从公钥恢复私钥（即，从计算上不可行）一样困难。请不必担心；所有标准曲线参数已被彻底检查以解决这个问题。

敬请期待关于zk-SNARKs如何工作的数学解释，敬请期待。

特别感谢Christian Reitwiessner、Ariel Gabizon（来自Zcash）和Alfred Menezes的审阅和更正.

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