维塔利克·布特林 (Vitalik Buterin) Vitalik Buterin 博客
这是帖子的镜像 https://medium.com/@VitalikButerin/探索椭圆曲线配对-c73c1864e627
触发警告:数学。
各种结构(包括确定性阈值签名、zk-SNARK 和其他更简单形式的零知识证明)背后的关键密码学原语之一是椭圆曲线配对。椭圆曲线配对(或“双线性映射”)是椭圆曲线用于加密应用(包括加密和数字签名)长达 30 年历史的最新成员;配对引入了一种“加密乘法”形式,极大地扩展了基于椭圆曲线的协议的功能。本文的目的是详细介绍椭圆曲线配对,并解释它们如何工作的概要。
你不需要在第一次甚至第十次阅读时就理解这里的所有内容;这东西真的很难。但希望这篇文章至少能让您对幕后发生的事情有一些了解。
椭圆曲线本身是一个需要理解的重要主题,本文通常假设您知道它们是如何工作的;如果您不这样做,我推荐这篇文章作为入门: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/。简而言之,椭圆曲线密码学涉及称为“点”的数学对象(这些是具有 (�,�) 坐标的二维点),以及用于添加和减去它们的特殊公式(即,用于计算 �= 的坐标) �+�),您还可以将一个点乘以一个整数(即 �⋅�=�+�+…+�,尽管如果 � 很大,则有一种更快的计算方法)。
以下是点添加的图形外观。
存在一个特殊的点,称为“无穷远点”(�),相当于点算术中的零;总是这样 �+�=�。此外,曲线有一个“秩序“;存在一个数字 �,对于任何 �,����=��(当然,���(�+1)=��,���(7��+5)=���5,依此类推)。还有一些普遍认同的“生成点”�,在某种意义上可以理解为代表数字1。理论上,曲线上的任何点(除了�)都可以是�;重要的是 � 是标准化的。
配对更进一步,它们允许您检查椭圆曲线点上某些更复杂的方程 - 例如,如果 �=�⋅�,�=�⋅� 和 �=�⋅�,您可以检查是否或不是 ⋅�=�,只有 �、� 和 � 作为输入。这看起来似乎是椭圆曲线的基本安全保障被打破了,因为有关 � 的信息只是因为知道 P 才被泄露,但事实证明,泄露是高度可控的——具体来说, 决策迪菲赫尔曼问题 很容易,但是计算 Diffie Hellman 问题(在上面的例子中知道 � 和 �, 计算 �=�⋅�⋅�) 和 离散对数问题 (从 � 中恢复 �)在计算上仍然不可行(至少,如果以前是这样的话)。
查看配对作用的第三种方法,对于我们所讨论的大多数用例来说,这可能是最有启发性的一种方法,那就是,如果您将椭圆曲线点视为单向加密数字(即 ���� ���(�)=�⋅�=�),那么传统的椭圆曲线数学可以让您检查 线性 对数字的约束(例如,如果 �=�⋅�,�=�⋅� 且 �=�⋅�,则检查 5⋅�+7⋅�=11⋅� 为 真 检查 5⋅�+7⋅�=11⋅�),配对可以让您检查 二次的 约束(例如,检查 �(�,�)⋅�(�,��5)=1 是 真 检查 ��+5=0)。上升到二次就足以让我们使用确定性阈值签名、二次算术程序和所有其他好东西。
现在,我们上面介绍的这个有趣的 �(�,�) 运算符是什么?这就是配对。数学家有时也称其为 双线性映射;这里的“双线性”一词基本上意味着它满足以下约束:
�(�,�+�)=�(�,�)��(�,�)
�(�+�,�)=�(�,�)��(�,�)
请注意,+ 和 ⋅ 可以是任意运算符;当你创建奇特的新型数学对象时,抽象代数并不关心 + 和 ⋅ 是怎样的 定义,只要它们与通常的方式一致,例如。 �+�=�+�,(�⋅�)��=�⋅(���) 且 (�⋅�)+(���)=(�+�)��。
如果 �, �, � 和 � 很简单 数字,那么进行简单的配对就很容易了:我们可以做到 �(�,�)=2��。然后,我们可以看到:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
它是双线性的!
然而,这种简单的配对并不适合密码学,因为它们处理的对象是简单的整数并且太容易分析;整数使得除法、计算对数以及进行各种其他计算变得容易;简单整数没有“公钥”或“单向函数”的概念。此外,通过上述配对,您可以倒退 - 知道 �,并知道 �(�,�),您可以简单地计算除法和对数来确定 �。我们想要尽可能接近“黑匣子”的数学对象,你可以在其中加、减、乘、除, 但什么都不做。这就是椭圆曲线和椭圆曲线配对的用武之地。
事实证明,可以在椭圆曲线点上建立双线性映射 - 也就是说,提出一个函数 �(�,�),其中输入 � 和 �� 是椭圆曲线点,输出是所谓的(��)12 个元素(至少在我们将在这里介绍的特定情况下;具体情况根据曲线的细节而有所不同,稍后会详细介绍),但这样做背后的数学相当复杂。
首先,让我们介绍一下素域和扩展域。只有当您假设曲线方程是使用常规实数定义的时,本文前面图片中漂亮的椭圆曲线才会看起来像这样。然而,如果我们实际上在密码学中使用常规实数,那么你可以使用对数来“倒退”,一切都会崩溃;此外,实际存储和表示数字所需的空间量可能会任意增长。因此,我们在 a 中使用数字 质域.
素数字段由数字 0,1,2…�−1 的集合组成,其中 � 是素数,各种运算定义如下:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
基本上,所有数学运算都是对 � 取模(参见 此处 有关模块化数学的介绍)。除法是一种特殊情况;通常,32 不是整数,这里我们只想处理整数,因此我们尝试找到数字 � 使得 �⋅2=3,其中 ⋅ 当然指的是上面定义的模乘法。谢谢 费马小定理,上面显示的求幂技巧可以完成这项工作,但还有一种更快的方法,使用 扩展欧几里得算法。假设 �=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
如果您尝试一下这种数学,您会发现它完全一致并且满足所有通常的规则。上面的最后两个例子展示了 (�/�)⋅�=� 的原理;您还可以看到 (�+�)+�=�+(�+�),(�+�)��=���+���,以及您知道和喜爱的所有其他高中代数恒等式也保持正确。在现实中的椭圆曲线中,点和方程通常在素数域中计算。
现在,让我们谈谈 扩展字段。您之前可能已经见过扩展字段;在数学教科书中遇到的最常见的例子是复数域,其中实数域被附加元素−1=�“扩展”。基本上,扩展域的工作原理是采用现有域,然后“发明”一个新元素并定义该元素与现有元素之间的关系(在本例中,2+1=0),确保该等式不成立对于原始字段中的任何数字,并查看原始字段的元素和刚刚创建的新元素的所有线性组合的集合。
我们也可以进行素数域的扩展;例如,我们可以用 � 扩展上面描述的素数域 mod7,然后我们可以这样做:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�·(2+�)=3+�
最后的结果可能有点难以弄清楚;发生的情况是,我们首先将乘积分解为 4�⋅2+4�⋅�,得到 8�−4,然后因为我们正在使用 mod7 数学,所以变成 �+3。为了划分,我们这样做:
�/�:(�⋅�(�2−2)) % �
请注意,费马小定理的指数现在是 2,而不是 �,不过,如果我们想提高效率,我们也可以扩展扩展欧几里得算法来完成这项工作。请注意,对于该域中的任何 �,��2−1=1,因此我们将�2−1 称为“域中乘法群的阶”。
对于实数, 代数基本定理 确保我们称之为复数的二次扩展是“完整的”——你不能进一步扩展它,因为对于任何数学关系(至少是由代数公式定义的任何数学关系),你都可以在一些新元素之间得出 � 和现有的复数,有可能想出至少一个已经满足该关系的复数。然而,对于素数域,我们就不存在这个问题,因此我们可以更进一步进行三次扩展(其中一些新元素 � 和现有域元素之间的数学关系是一个三次方程,因此 1,� 和 �2 是彼此线性独立)、高阶扩展、扩展的扩展等。椭圆曲线配对正是建立在这些增强的模复数之上。
对于那些有兴趣查看以代码编写所有这些操作所涉及的精确数学的人,这里实现了素数字段和字段扩展: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
现在,讨论椭圆曲线配对。椭圆曲线配对(或者更确切地说,我们将在这里探讨的配对的具体形式;还有其他类型的配对,尽管它们的逻辑非常相似)是一个映射 �2×�1→��,其中:
- �1 是一条椭圆曲线,其中点满足 �2=�3+� 形式的方程,并且两个坐标都是 �� 的元素(即,它们是简单的数字,除了算术都是以某个素数为模完成的)
- �2 是一条椭圆曲线,其中点满足与 �1 相同的方程,除了坐标是 (��)12 的元素(即,它们是我们上面讨论的增压复数;我们定义一个新的“幻数” ” �,由 12 次多项式定义,如 �12−18⋅�6+82=0)
- �� 是椭圆曲线的结果进入的对象类型。在我们看到的曲线中,�� 是 (��)12(与 �2 中使用的增压复数相同)
它必须满足的主要属性是双线性,在这种情况下意味着:
- �(�,�+�)=�(�,�)��(�,�)
- �(�+�,�)=�(�,�)��(�,�)
还有另外两个重要标准:
- 高效的可计算性 (例如,我们可以通过简单地取所有点的离散对数并将它们相乘来进行简单的配对,但这在计算上就像首先打破椭圆曲线密码学一样困难,所以它不算)
- 非简并性 (当然,您可以定义 �(�,�)=1,但这不是一个特别有用的配对)
那么我们怎么做呢?
配对函数工作背后的数学原理非常棘手,涉及相当多的高级代数,甚至超出了我们迄今为止所看到的范围,但我将提供一个概述。首先,我们需要定义一个概念: 分离器,基本上是椭圆曲线点上表示函数的另一种方法。函数的除数基本上计算函数的零和无穷大。为了了解这意味着什么,让我们看几个例子。让我们固定一些点 �=(��,��),并考虑以下函数:
�(�,�)=�−��
除数是 [�]+[−�]−2⋅[�](方括号用于表示我们所指的事实 函数的零点和无穷大集合中存在点 �,不是点 P 本身; [�]+[�] 是 不能 与 [�+�] 相同)。推理如下:
- 该函数在 � 处等于 0,因为 � is ��,所以��−��=0
- 该函数在 −� 处等于 0,因为 −� 和 � 共享相同的 � 坐标
- 当 � 趋向无穷大时,函数也趋于无穷大,因此我们说函数在 � 处等于无穷大。由于技术原因,这个无穷大需要计算两次,因此 � 会加上 −2 的“重数”(负数,因为它是无穷大而不是零,因为重复计算而为 XNUMX)。
技术原因大致是这样的:因为曲线方程为 �3=�2+�,为了使 �1.5 跟上 �2,�会比�“快 3 倍”趋向无穷大;因此,如果线性函数仅包含 �,则它被表示为重数 2 的无穷大,但如果它包含 �,则它被表示为重数 3 的无穷大。
现在,考虑一个“线函数”:
��+��+��=0
其中 �、� 和 � 是经过仔细选择的,以便直线穿过点 � 和 �。由于椭圆曲线加法的工作原理(参见顶部的图表),这也意味着它通过 -�−�。它上升到无穷大,取决于 � 和 �,因此除数变为 [�]+[�]+[−�−�]−3⋅[�]。
我们知道,每个“有理函数”(即仅使用点坐标上有限数量的 +、−、⋅ 和 / 运算定义的函数)唯一对应于某个除数,最多乘以一个常数(即如果两个函数 � 和 �� 具有相同的除数,则 ��=�⋅� 对于某个常数 �)。
对于任意两个函数 � 和 ��,��� 的除数等于 �� 的除数加上 �� 的除数(在数学教科书中,您会看到 (����)=(��)+(��)),例如,如果 �(�,�)=��−�,则 (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � 和 −� 被“三次计算”,以说明 �3 在这些点上接近 0 的速度在某种数学意义上是“三倍快”。
请注意,有一个定理指出,如果您从函数的除数中“删除方括号”,则这些点的总和必须为 �([�]+[�]+[−�−�]−3⋅[ �] 显然适合,如 �+�−�−�−3⋅�=�),并且任何具有此属性的除数都是函数的除数。
现在,我们准备看看泰特美术馆的配对。考虑以下通过除数定义的函数:
- (��)=�⋅[�]−�⋅[�],其中�是�1的阶数,即 �·�=� 对于任何 �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
现在,让我们看看乘积 ��⋅��⋅��。除数是:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
这巧妙地简化为:
�·[�+�]−�·[�]
请注意,该除数与上面 �� 和 �� 的除数格式完全相同。因此,��⋅��⋅��=��+�。
现在,我们引入一个称为“最终求幂”步骤的过程,在该步骤中,我们获取上述函数的结果(��、�� 等)并将其求幂 �=(�12−1)/�,其中 �12−1 是 (��)12 中乘法群的阶数(即对于 任何 �ε(��)12,�(�12−1)=1)。请注意,如果您将此指数应用于任何具有 已经 进行 � 幂,得到 �12−1 次幂,因此结果变为 1。因此,在最终取幂后,�� 抵消,我们得到 ����⋅����=( ��+�)�。对你来说有一些双线性。
现在,如果你想创建一个在两个参数中都是双线性的函数,你需要进入更诡异的数学,其中不是直接取值的 ��,而是取 a 的 �� 分离器,这就是完整的“泰特配对”的来源。为了证明更多的结果,你必须处理“线性等价”和“韦尔互易”等概念,兔子洞就从这里继续下去。您可以找到有关所有这些的更多阅读材料 此处 和 此处.
对于 Tate 配对的修改版本的实现,称为最佳 Ate 配对, 看到这里。代码实现了 米勒算法,这是实际计算 �� 所需要的。
请注意,像这样的配对是可能的,这一事实有点喜忧参半:一方面,这意味着我们可以通过配对执行的所有协议都成为可能,但也意味着我们必须更加小心椭圆曲线我们用。
每条椭圆曲线都有一个值,称为 嵌入度;本质上,最小的 � 使得 ��−1 是 � 的倍数(其中 �� 是用于域的素数,� 是曲线阶)。在上面的领域中,�=12,以及在用于传统ECC的领域(即我们不关心配对的领域),嵌入程度通常非常大,以至于配对在计算上无法计算;然而,如果我们不小心的话,我们可能会生成 �=4 甚至 1 的字段。
如果 �=1,则可以减少椭圆曲线的“离散对数”问题(本质上,恢复仅知道点 �=�⋅�,即“破解”椭圆曲线私钥所必须解决的问题)变成一个关于 �� 的类似数学问题,问题变得更容易(这称为 MOV攻击);使用嵌入度为 12 或更高的曲线可确保这种减少不可用,或者解决配对结果的离散对数问题至少与“正常方式”从公钥恢复私钥一样困难(即计算上不可行)。不用担心;所有标准曲线参数都已针对此问题进行了彻底检查。
请继续关注 zk-SNARK 工作原理的数学解释,即将推出。
特别感谢 Christian Reitwiessner、Ariel Gabizon(来自 Zcash)和 Alfred Menezes 的审核和更正。