如果你是一个SNARKER,你一定听说过KZG Commitment,如果你听说过KZG Commitment,那你一定知道Pairing。这就是我们接下来要讨论的,大家如果想了解Pairing 的底层逻辑(pairing primitives),或者对它的应用感兴趣都可以留言,或者添加文末的联系方式。
至今距离pairing 的“尘埃落定”其实已经大概有6、7年的时间了,网上的资料很完整,但关于它的讨论(工程上)仍未止步,比如On Proving Pairings.
本文所有内容源自hackmd上的note,欢迎follow.
这里没有的
-
group theory, field theory and homomorphism
相关基本概念在这里不会涵盖,详情请查阅任何abstract algebraic 相关的书籍
-
divisors
相关基本概念在这里不会涵盖,对于了解Pairing 来说 Pairing for Beginners 已足够,如果你还想深入理解最好翻阅一下 algebraic geometry 相关的书籍
-
structure of elliptic curve over finite field and its arithmetics (scalar multiplication)
理论和算法部分这里不会涵盖,详情可以查阅 Guide to Elliptic Curve Cryptography
-
hash to curve
bytes string 映射到或者 上的点,简单说就是hash,是pairing 应用层面必备的一大模块,后续会详细补充这块内容
-
non-affine coordinate
affine coordinate 其实只是椭圆曲线元素表达的需要,它的scalar multiplication 并不经济,所以实际计算上都会用non-affine coordinate 来替代,后续会补上这块内容
-
advanced scalar multiplication algorithms GLV/GLS
特定的曲线上充分利用同态映射来加速scalar multiplication,同时还能(GPU)并行化处理也是当下硬件加速卖点,后续也会再补上
这里有的
本篇文章集中讨论了各种Pairing 变体:
和它们的具体实现。除此之外,我们还包含了一些重要的实现层面的tricks,尤其是:
关于代码
-
主要集中在Pairing的计算逻辑上,包括Miller Loop 和 Final Exponentiation。目前已经完成验证。
Finite Field 和 Elliptic Curves的算术运算并没有逐一实现,用的是Sagemath库自带的 Galois Field and Elliptic Curve.
-
从零着手,从 Bigint 算术运算到 Finite Field 算术运算到 Elliptic Curve 算术运算,再到 Pairings Primitives。底层的逻辑已经验证完毕,目前在Pairings验证过程中 …
公共信息
- Modulus of base prime field (characteristic) with 381-bits:
- Embedding degree, or the degree of full extension field :
- Elliptic Curve (additive group) over base prime field :
- Elliptic Curve (additive group) over extension field :
- Largest prime factor of with 255-bits:
- Trace of Frobenius:
- Parameter for BLS12 Pairing-family: for:
- Target (multiplicative) group with order defined over :
Pairing 的演进
Weil Reciprocity
and 是两个定义在椭圆曲线上的divisor function, ,它们的divisor support 不存在交集, 。然后我们就有:
其中 表示函数 的divisor, 表示divisor 在函数 上的evaluation。 也类似.
如果我们放松上面的约束条件, 如果 , 然后就有一个更general 的 Weil Reciprocity 公式: 其中 ,当两个divisor and 的support 存在交集, 否则 .
Details of general definition of Weil Reciprocity, you can refer THEOREM 3.9 of Guide to Pairing-based Cryptography.
那么Weil Reciprocity 究竟有什么意义呢? 它直接诞生了 Weil Pairing.
Weil Pairing
定义
假定在 -torsion subgroup 中有两个线性不相交的点, . 基于此,假定 , and , 同样 . 它们同样满足 .
然后我们就有:
这样,Weil Pairing 就出现了: 其中 , 是乘法group 上的-次单位元根 , 也就是说 .
如何选择合适的divisor and
理论上我们需要选择合适的 divisors and ,让它们的support 不相交, 你可能会奇怪,这应该有很多种选择,那么 and 不同的选择会导致最终pairing的结果 不一样吗?
事实上 Weil Pairing 的结果 它是与 and 的选择无关的。下面简单证明一下:
假定 and 都是与divisor 等效的divisor, 那么一定存在另外一个中间divisor 使得 , 然后:
根据 Weil Reciprocity 定理, 由于 , 所以 . 因此:
既然跟divisor 具体的选择无关,那我们就选择最简单的 divisors: . 这时,它们的support 是存在交集的,根据上面那个general Weil Reciprocity公式,我们就有Weil Pairing的正式定义:
如何对divisor and 进行evaluate
divisor 的evaluation 可以被进行一步简化:
只要 and 是线性不相关的,即 .
注意上面的符号是 不是 ,也就是说它们evaluation的值可能不同,但并不会对Weil Pairing 最终的结果 有影响,即:
因此 Weil Pairing 简化为:
Miller Loop 使得divisor function的evaluation 变得更容易实现,是工程上的一大步。很明显 Weil Pairing 是几何上对称的, 它实际上需要运行两次 Miller Loop. 看起来并不太经济? 实际上单次就够了,这就是 Tate Pairing 要做的事情.
算法
直接参考Guide to Pairing-based Cryptography 中的Algorithm 3.2:
Tate Pairing
你可能会奇怪divisor function的evaluation 长什么样子? 由于 , 然后 , 所以 . 运用coset 的特性, Tate Pairing 就出现了:
它分两步走, Miller Loop 和 Final Exponentiation. 这也是我们所说的 Final Exponentiation 的由来。
定义
其实 Tate Pairing 有一个更正式的定义: 其中 , 并不是-torsion subgroup 中的元素, 它不再跟一样被定义在group 。而是商群的某个元素, 确切的说就是group 上的任意一个与 线性不相关的元素. 看起来似乎是把约束条件放得更宽了。
既然这样,那么divisor function的evaluation值 (result of Miller Loop)会变成什么样子呢? 同样,它一定也是商群的某个元素,确切的说就是group 上的任意一个元素,这也更加坚定了后续提指Final Expoentiation的必要性:
似乎Tate Pairing 要比Weil Pairing更通用 (more relaxed constraints) ,是吧?
Since , usually for the convenience of computation(utilization of Frobenius Automorphism) we let , namely , is so-called Base Group. While , namely , is so-called Trace-zero Group. :::
算法
同样直接参考 Guide to Pairing-based Cryptography 的Algorithm 3.3:
Miller Loop
你可能已经注意到, Weil Pairing 中Miller Loop 的长度 and Tate Pairing 的都是 (bit length of ).
理论上 Tate Pairing 已经够实用了,至少实现起来是没有任何阻碍的了,所以后续的research 其实主要是针对工程实现上的优化,基本框架并没有改变。 基本集中在缩短 Miller Loop 的长度,以及更高效的提指 Final Expoentiation运算.
还有Miller Loop 更短的算法? 是的,但是我们需要深入挖掘一下乘法group 的结构.
Ate Pairing
在Ate Pairing中, 点 被严格约束在 中,同时点 也被约束在 中,即Frobenius Map: 充分利用Frobenius Map的特性,将大大降低pairing的计算成本。
Miller 算法的两个重要特性
关于这两个特性的proof,这里不再推演,熟悉divisor function 后很容易推导出来。
更短的 Miller Loop
由于, 假定 ,因此我们就有:
由于 , 然后 , 我们就有 , 因此:
看起来我们似乎可以用 替代 了, 但是这完全没有必要,因为 ,反而让Miller Loop 变得更长了。
如果 and , 然后 , 假定 , 类似地我们有:
根据上面的两个 Miller 算法的特性, 可以继续推导: 令 , 我们有:
由于 , 我们完全可以用 替换 , 但是如何找到这个 值呢?
Trace of Frobenius
根据 Hesse Bound 定理, 我们有: 令 其中 就是我们据说的Trace of Frobenius, 由于 , 然后 .
最后我们得到:
很明显 Tate Pairing 和 Ate Pairing 有着非常紧密的关系。 你可能已经注意到,这两个pairing的计算结果 很可能不相等,不用紧张,只是pairing策略的差异而已,并不影响它在乘法group 中的唯一性,这才是pairing 的最终目的。
事实上Ate Pairing 在做的就是找到与 的某个倍乘相关的数, 就是我们要找的,它满足 . 但是, 一定是最短的 Miller Loop吗? 可能是(也可能不是),下面写几行代码反证一下:
p = 103
r = 7
k = 6
for i in range(1, k):
print('lambda[{0}] = {1}'.format(i, (p ** i) % r))
运行结果:
lambda[1] = 5
lambda[2] = 4
lambda[3] = 6
lambda[4] = 2
lambda[5] = 3
很明显,并不是最小的, 才是。
Optimal Ate Pairing
在上面的 Ate Pairing 中, 我们直接地用 替换 后得到: 其中 , and .
在 Ate Pairing 中,我们有: 其中 , and .
基于此,我们可以找到二者之间的联系:
因此,Ate Pairing 经过 次方提指后变成: 暂时先把结论放这儿.
在Optimal Ate Pairing中把进行了更通用的定义:, and . 同样运用上面的 Miller 算法的特性, 我们把它的divisor function 进行展开:
其中:
然后 Ate Pairing 就被转换成了:
很明显 Ate Pairing 被划分成了两部分, 左边部分 是基于的 Ate Pairing (length of Miller Loop is )。
既然左边已经是一个Ate Pairing 了,那么右边部分 肯定也是一个Ate Pairing,只要 **。
所以Optimal Ate Pairing 正式定义就来了: 其中系数 都是尽可能小的数.
不用担心指数运算 , 它几乎是免费的,在充分运用 Frobenius Map后. Optimal Ate Pairing 要做的就是并行计算 and , 此时Miller Loop 的长度可能就是 .
可以如何找到这么一组系数 呢? 实际上它是一个关于 Lattice 的问题,感兴趣可以继续研究 Optimal Pairings.
有限域上的算术运算
BLS12-381 曲线的定义是这样的: 其中 。但是这个extension field 是如何构建的呢?
Pairing 中域的切换
为了对Pairing 底层的算术运算有个更直观的sense,下面简单介绍一下Tate/Ate pairings中域的切换。
假定定义在域 上的点,同时点 定义在域 上,实际上点 的坐标必须定义在域 的某个子域上 (先给出结论,后续有推理过程),比如说 。整个过程,可以切分为4个部分:
-
Miller Loop
-
Double-Add
line function 不会改变所在的域,在哪个域,这个函数仍然在那个域,比如 :
-
Evaluation Line Function
比如,单个line function的evaluation:
最终evaluation 的结果, 不再定义在原本的域 上了.
-
-
Final Exponentiation
-
Easy Part
通过提指把Mill Loop 的结果 推进一个特殊的乘法group,这就是我们所说的 Cyclotomic Group, :
-
Hard Part
再次通过提指从Cyclotomic Group 拉到目标乘法group :
-
域塔 Tower Fields
定义
大家知道BLS12-381 Pairing中的目标group 是一个定义在上的-torsion multiplicative subgroup,我们经常表示为。
那么 是如何被构造出来的呢? 这就是tower fields 的由来:
在BLS12-381曲线上,extension field modulus的常量分别为:
模的由来:
is irreducible in
since is one root of , then we have is irreducible in
since is one root of , then we have is irreducible in
therefore we have
也就是说,域 上的算术运算可以通过域 上的算术运算来完成,同时域 的算术运算可以通过域 上的算术运算来完成,同样域 的算术运算可以通过base prime field 上的算术运算来完成。这就是我们据说的域塔 tower fields。
你可能已经注意到域的拓展 和 都是二次拓展 quadratic extension, 而 是三次拓展 cubic extension。所以 quadratic extension 和 cubic extension 在高阶extension field (比如)的算术运算中扮演着非常重要的角色。
Quadratic Extension 上的算术运算
这部分属于常规的计算逻辑,可以直接参考 Guide to Pairing-based Cryptography 5.2.1 章节。
Cubic Extension 上的算术运算
同样,这部分也可以直接参考 Guide to Pairing-based Cryptography 5.2.2 章节。
Cyclotomic Group 上的算术运算
分圆群 Cyclotomic group 在Pairing 的提指运算 Final Expoentiation 扮演着最核心的角色,特别是在 Tate/Ate Pairings中。既然是提指,那么主要就是平方 squaring 和指数 exponentiation 这两个算子。下面主要推演一下squaring 的全过程。
假定 ,表示base prime field,那么如何计算 ?
首先,我们需要利用tower fields来表示 ,比如:
假定 : 则:
由于 , 我们继续推进:
所以最终我们会有3次域 上的squaring (分别是 ), 和5次域 上的multiplication (分别是 )。
域 上的乘法运算可能会比较昂贵,那么有没有改进的方法呢? YES
Squaring Friendly Field
如果 , 而且 是一个非常大的素数characteristic,乘法group 的阶可以用多个cyclotomic polymomials 的连乘来表示:
这里我们称 为 Squaring Friendly Field.
举个例子乘法group :
其中:
换句话说,乘法group 的阶可以被因子分解成:
所以乘法group 中一定存在一个阶为 的subgroup 。
因此,我们得到一个非常重要的结论:
更快的 Squaring 算子
回到上面的Squaring 运算,有 :
Squaring 之后:
现在的问题是如何有效地计算 ?
在Tate/Ate Pairing的Final Exponentiation中 ,根据上面刚刚推演出的结论:
其中:
但是如何有效地计算诸如 ? 我们拆开来看:
-
根据Frobenius Map 的特性,我们很容易得到: (先给出结论,在后面Frobenius Map 部分会进行推理)。因此上面的式子简化成:
-
由于 ,因此: 其中 是域上的 primitive 6-th root of unity,也就是说 .
More properties of primitive 6-th root of unity in :
综合在一起,我们得到:
应用Frobenius map 后:
应用Squaring Friendly Field的特性,我们得到:
展开后,得到:
所以上面的三个乘法运算被转换成:
最终:
域上的5个乘法,只剩下1个乘法,共轭 完全免费。
Twist 的力量
为什么要twist
尽管我们通过tower fields 来表示 ,不幸的是 仍然有点儿贵,尤其应用在链上或者微型终端设备上。所以我们可以简单地把twist 当作pairing实现层面的一种高级的trick来看待。
我们可以通过sextic-twist(twist degree 是 6) 把高阶域 上的元素映射到低阶域 : 但是如何做呢?
Sextic Twist
一个定义在高阶extension field 上的椭圆曲线 :
另一个定义在低阶extension field 上的twisted 椭圆曲线 ,它与有着twist isomorphism关系: 其中 , is both non-quadratic and non-cubic residual, 也就是说:
因此:
但是如何选择一个合适的 呢? 似乎 刚好把域 拓展到了 。幸运的是,刚好 就是这么一个数。
According to above tower fields, we can easily have:
所以这个twisted 的椭圆曲线就是 :-1: :
这就是我们想要的 吗?一定是我们要找的twist参数吗?
不一定,原本 是定义在上的,也就是上面的的subgroup ,但是 上的运算成本较高,所以想通过twist 的方式把 上的点一一映射到,这样运算成本会大大降低。但是,可能会存在: 也就是说可能不能整除 ,曲线 上可能不存在一个-torsion subgroup。这是不满足我们一一映射的目的: 所以我们在选择twist 参数里要特别小心。那如何找到满足条件的twist 参数呢?其实这个参数只有两种可能性。
如果 不合适,那么 一定是那个合适的(论文 也有提及),大家也可以试一下,最终我们确定 所在的曲线: 其中 或者 and .
Sextic Twist Map
下面简单介绍一下两group and 元素之间的映射关系:
-
Twist Operation
把 上的元素映射到 上:
-
Untwist Operation
把 上的元素映射到 上:
twist/untwist的过程是很便宜的,尤其是当我们把期间用到的常量 预先算出来。最后明确一下,既然要用twist trick,那么将尽可能把运算都限制在低阶的域上,只是在必要的时候才通过untwist 把值转换到高阶域上。
Frobenius Map 的力量
同twist 一样,Frobenius Map 同样是pairing 实现层面的高级trick。它在extension field的运算过程中扮演着非常重要的角色,特别是Tate/Ate Pairings 中的提指Final Expoentiation。
下面我们粗略感受一下它分别在extension field 上有哪些特性:
Frobenius Map over
假定:
其中 and , we have .
然后:
由于 一定是个奇数,所以我们有:
结论: Frobenius Map 只要 .
Frobenius Map over
假定:
其中 and , 我们有 , and
然后: