我们如何在lambdaworks中实现BN254 Ate配对

lambdaclass
发布于 2024-08-21 16:38
阅读 34

本文深入探讨了BN254椭圆曲线配对的实现，该曲线是目前以太坊上唯一具有预编译合约的曲线，文章详细介绍了曲线参数、坐标表示、域扩展塔的概念，以及Ate配对算法的各个步骤，包括米勒循环和最终指数化，同时还讨论了子群检查、线函数计算和弗罗贝尼乌斯自同态等关键技术，为理解和实现BN254曲线上的配对操作提供了全面的技术指导。

## 介绍

椭圆曲线 BN254 是目前以太坊上唯一具有预编译合约的曲线，使其成为链上[zk-SNARK](https://learnblockchain.cn/article/22996/)验证（使用 [Groth16](https://blog.lambdaclass.com/groth16/) 和 [PlonK](https://blog.lambdaclass.com/all-you-wanted-to-know-about-plonk/) 等证明系统）最实用的 pairing-friendly 曲线选择。这项工作源于我们需要[自己实现的 BN254 Ate pairing](https://github.com/lambdaclass/lambdaworks/blob/main/math/src/elliptic_curve/short_weierstrass/curves/bn_254/pairing.rs)。这篇文章的想法是作为我们实现的伴侣，解释理解它所需的数学理论和算法。一些论文和文章介绍了用于此 pairing 及其函数的不同算法，因此我们认为将所有这些信息组织到一篇文章中会很有帮助。

关于阅读本文所需的数学背景，我们仅假设你对群、有限域和椭圆曲线有轻微的概念。如果你对这些主题没有信心，我们建议阅读我们的文章 [开发者的数学生存工具包](https://blog.lambdaclass.com/math-survival-kit-for-developers/) 和 [每个开发者需要了解的关于椭圆曲线的知识](https://blog.lambdaclass.com/what-every-developer-needs-to-know-about-elliptic-curves/)。

## 曲线参数

BN254（在 Lambdaworks 中为 `BN254Curve`）是 Barreto-Naehrig pairing friendly 椭圆曲线 $E$，其形式为

$y^2=x^3+3$

在有限域 $F_p$ 上，其中：

- $p=36x^4+36x^3+24x^2+6x+1$ 是 254 位素数：

```rust
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
x = 4965661367192848881
```

- $t=6x^2+1$ 是 Frobenius 的迹。
- $r=36x^4+36x^3+18x^2+6x+1=p+1-t$ 是曲线 $E(F_p)$ 中的点数。

## 点坐标

由于我们将椭圆曲线定义为满足上述方程的点集，因此很自然地想到使用两个坐标 $P=(x,y)$ 表示 $E(F_p)$ 中的元素 $P$。这种表示形式称为 **仿射表示**，其坐标称为 **仿射坐标**。但是，为了优化算术，许多时候使用 **射影坐标** 会很方便，射影坐标用三个坐标 $x, y, z$ 表示点，其构造方式如下：

如果 $P=(x,y)$ 是仿射坐标中的点，则 $(x,y,1)$ 是其射影表示。如果 $P=(x,y,z)$ 是射影坐标中的点，则 $(\frac{x}{z},\frac{y}{z})$ 是其仿射表示。你将在我们的实现中看到，我们根据每种情况下的需要使用这两种表示形式，使用 `to_affine()` 等函数。

还有第三种表示形式，我们不会使用，但你可能会在一些论文中找到，称为 **雅可比坐标**：如果 $P=(x,y,z)$ 是雅可比坐标中的点，则 $(\frac{x}{z^2},\frac{y}{z^3})$ 和 $(\frac{x}{z},\frac{y}{z^2})$ 分别是其射影坐标和仿射坐标。

## 域扩展塔

pairing 是一个映射 $e:G_1 \times G_2 \rightarrow G_t$，这意味着它将两个点作为输入，每个点来自具有相同点数（或阶）$r$ 的群。这个数 $r$ 必须是素数，并且为了保证安全，它必须很大。此外，由于一些技术原因，这两个群需要是不同的。因此，要定义 pairing，我们需要选择这些定义域和值域群。群 $G_1$ 将是曲线 $E(F_p)$，但要定义 $G_2$ 和 $G_t$，我们需要 **扩展** 域 $F_p$。我们不会停下来详细解释什么是域扩展以及如何构建它们，因此如果你正在寻找更好的理解，我们建议阅读 _BLS12-381 For the Rest of US_ 中的 [域扩展](https://hackmd.io/@benjaminion/bls12-381#Field-extensions) 部分。在这里，我们将总结理解我们的实现和我们使用的算法所必需的基本概念。

粗略地说，我们的目标是将域 $F_p$ 扩展到 $F_{p^{12}}$，我们将以以下方式进行扩展。首先，我们将 $F_p$ 扩展到 $F_{p^2}$，就像将实数域 $\mathbb{R}$ 扩展到复数域 $\mathbb{C}$ 一样：我们定义 $F_{p^2}=F_p[u]/(u^2+1)$。这需要处理很多符号。好消息是，我们需要理解的是，$F_{p^2}$ 是一个有限域，其元素是 1 次多项式和变量 $u$；也就是说，它们的形式为 $a+bu$，其中 $a,b \in F_p$。如果我们将其视为复数，$a$ 将是实部，$b$ 将是虚部。请注意，$F_p \subseteq F_{p^2}$，因为我们可以将左侧的元素视为具有“虚部”零或 $b=0$ 的右侧元素。因此，$F_{p^2}$ 确实是 $F_p$ 的扩展。

其次，我们以类似的方式扩展 $F_{p^2}$，定义 $F_{p^6}=F_{p^2}[v]/(v^3-(9+u))$。在这种情况下，由于 $v^3-(9+u)$ 是一个 3 次多项式，$F_{p^6}$ 的元素将是 2 次多项式和变量 $v$，其形式为 $a+bv+cv^2$，其中 $a,b,c \in F_{p^2}$。最后，我们扩展 $F_{p^6}$，定义 $F_{p^{12}}=F_{p^6}[w]/(w^2-v)$，也就是说，它的元素又是 1 次多项式和变量 $w$，其形式为 $a+bw$，其中 $a,b \in F_{p^6}$。

现在，在实践中，使用 lambdaworks，我们有两种不同的方式来定义元素 $f=a+bw \in F_{p^{12}}$。我们可以使用 `new()`，

```rust
let f = Fp12E::new([a, b])
```

或者我们可以使用 `from_coefficients()`。

```rust
let f = Fp12E::from_coefficients([\
"a_00", "a_01", "a_10", "a_11", "a_20", "a_21",\
"b_00", "b_01", "b_10", "b_11", "b_20", "b_21"\
])
```

在最后一种情况下，我们使用 12 个系数来定义 $f$，因为 $f=a+bw$，其中 $a,b \in F_{p^6}$。然后，$a=a_0+a_1v+a_2v^2$，并且 $b=b_0+b_1v+b_2v^2$，其中 $a_i,b_i \in F_{p^2}$。因此，$a_i=a_{i0}+a_{i1}u$，并且 $b_i=b_{i0}+b_{i1}u$，因此达到 12 个系数。

还有另一种 $F_{p^{12}}$ 元素的表示形式，你可以在我们实现中使用的论文和算法中找到。由于 $v^3=9+u$ 并且 $w^2=v$，因此我们有 $w^6=9+u$，然后，$F_{p^{12}}=F_{p^2}[w]/(w^6-(9+u))$。同样，你不必理解上一句话；重要的是，我们不仅可以将 $f$ 表示为 1 次多项式，还可以表示为 11 次多项式，还可以使用 $a_i$ 和 $b_i$ 将其表示为 5 次多项式，如下所示：

$f=a_0+b_0w+a_1w^2+b_1w^3+a_2w^4+b_2w^5$。因此，每次你看到 $F_{p^{12}}$ 的元素表示为 5 次多项式时，你都会知道如何将其写成 $a+bw$，使用其系数构建 $a=a_0+a_1v+a_2v^2$ 和 $b=b_0+b_1v+b_2v^2$（反之亦然）。拥有相同扩展域的不同表示形式将使我们能够在实现 pairing 时应用一些优化（参见 _计算 BN254 曲线上的最佳 Ate Pairing_ 中的 [扩展域塔](https://hackmd.io/@Wimet/ry7z1Xj-2#Tower-of-Extension-Fields) 部分）。

这可能有很多新信息，但请不要担心；你不需要详细了解它。在阅读实现时，目的是手头有这些等式，以识别每个变量所属的位置以及它有多少个系数。在 lambdaworks `bn_254` 中，你将找到这些域 $F_p$、$F_{p^2}$、$F_{p^6}$ 和 $F_{p^{12}}$（及其实现的运算）作为 `BN254PrimeField`、`Degree2ExtensionField`、`Degree6ExtensionField` 和 `Degree12ExtensionField`。

## Twist

由于在 $F_{p^{12}}$ 中进行算术运算既复杂又效率低下，我们将使用 **twist**，这就像一个坐标转换，它将我们的 $E(F_{p^{12}})$ 曲线转换为以下定义在 $F_{p^2}$ 上的曲线 $E'$：

$y^2=x^3+\frac{3}{9+u}$。

我们将调用 $b=\frac{3}{9+u}$，实现为 `BN254TwistCurve::b()`。

```rust
b = 19485874751759354771024239261021720505790618469301721065564631296452457478373
    + 266929791119991161246907387137283842545076965332900288569378510910307636690
    * u
```

因此，总之，我们将使用以下子群作为 pairing 的输入：

$G_1=E(F_p)$，

$G_2 \subseteq E'(F_{p^2})$。

以及以下输出：

$G_t \subseteq F_{p^{12}}^{\star}$，其中 $F_{p^{12}}^{\star}=F_{p^{12}}-{0}$（域的乘法群）。

准确地知道我们应该采用哪些子群 $G_2$ 和 $G_t$ 与理解我们的实现无关。我们只想对那些具有数学背景或有兴趣深入研究这些主题的人说，$G_1$ 和 $G_2$ 是 $r$- **挠群**（即 **阶** 为 $r$ 的元素集合），而 $G_t$ 是 $r$- **th 次单位根**的集合。

## Pairing

### 什么是 pairing？

现在，在我们定义了构建 pairing 所需的一切之后，让我们更好地理解它。pairing 是一个双线性映射 $e:G_1 \times G_2 \rightarrow G_t$。**双线性** 意味着它具有以下属性：对于所有点 $P_1,P_2 \in G_1$ 和 $Q_1,Q_2 \in G_2$，

$e(P_1,Q_1+Q_2)=e(P_1,Q_1) \cdot e(P_1,Q_2)$
$e(P_1+P_2,Q_1)=e(P_1,Q_1) \cdot e(P_2,Q_1)$
由此属性可以推导出下一个属性：对于所有 $n,m \in \mathbb{N}$，

$e(nP,mQ)=e(mQ,nP)=e(P,mQ)^n=e(nP,Q)^m=e(P,Q)^{nm}$。
回想一下，通常，加法符号 $+$ 用于表示群 $G_1$ 和 $G_2$ 的运算，而乘法符号 $\cdot$ 用于表示 $G_t$ 的运算。

### Ate Pairing 算法

我们将使用 [这篇论文](https://eprint.iacr.org/2010/354.pdf)（第 4 页，算法 1）中的 Ate pairing 算法：

* * *

**输入**：$P \in G_1$ 和 $Q \in G_2$

**输出：** $f \in G_t$

01. 定义 $T \in G_2$；
02. $T \leftarrow Q$；
03. 定义 $f \in G_t$；
04. $f \leftarrow 1$；
05. 对于 $i$=$`miller_length`-2$ 到 0 执行
06. $f \leftarrow f^2$；
07. $T \leftarrow 2T$；
08. 如果 `$MILLER_CONSTANT`\[i\]=-1$ 则
09. $f \leftarrow f \cdot l_{T,-Q}(P)$；
10. $T \leftarrow T-Q$；
11. 否则，如果 `$MILLER_CONSTANT`\[i\]=1$ 则
12. $f \leftarrow f \cdot l_{T,Q}(P)$；
13. $T \leftarrow T+Q$；
14.      结束 if
15. 结束 for
16. $Q_1 \leftarrow \varphi(Q)$；
17. $f \leftarrow f \cdot l_{T,Q_1}(P)$；
18. $T \leftarrow T+Q_1$；
19. $Q_2 \leftarrow \varphi(Q_1)$；
20. $f \leftarrow f \cdot l_{T,-Q_2}(P)$；
21. $f \leftarrow f^{\frac{p^{12}-1}{r}}$；
22. 返回 $f$；

* * *

其中：

- 数字 `$MILLER_CONSTANT`=6x+2$，其中 $x$ 是我们之前提到的曲线参数。但是，我们需要使用 2 的幂和系数 $\{-1,0,1\}$ 来表示这个数字。这种表示类似于 [NAF 表示](https://en.wikipedia.org/wiki/Non-adjacent_form#:~:text=The%20non%2Dadjacent%20form%20(NAF,8%20%E2%88%92%202%20%2B%201%20%3D%207))，尽管它不是 NAF，因为它具有相邻的非零值。

```rust
// MILLER_CONSTANT = 6x + 2 = 29793968203157093288 =
// 2^3 + 2^5 - 2^7 + 2^10 - 2^11 + 2^14 + 2^17 + 2^18 - 2^20 + 2^23
// - 2^25 + 2^30 + 2^31 + 2^32 - 2^35 + 2^38 - 2^44 + 2^47 + 2^48
// - 2^51 + 2^55 + 2^56 - 2^58 + 2^61 + 2^63 + 2^64
pub const MILLER_CONSTANT: [i32; 65] = [\
      0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 0, -1, 0, 0,\
      1, 0, -1, 0, 0, 0, 0, 1, 1, 1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0,\
      0, 1, 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, 1, 1\
];
```

```rust
let miller_length = MILLER_CONSTANT.len()
```

- 函数 $l_{T,Q}(P)$ 是通过 $T$ 和 $Q$ 的直线在 $P$ 处的值。稍后我们将看到如何计算它。

- Frobenius 同态 $\varphi:E'(F_{p^2}) \rightarrow E'(F_{p^2})$ 定义为 $\varphi(x,y)=(x^p,y^p)$。稍后我们还将看到它。

### Batch

我们将提出的算法分为 Miller 循环和最终指数运算来实现它。`miller()` 函数执行算法的第 1 行到第 20 行的所有工作，而 `final_exponentiation()` 仅计算最后一行 21（这是一个需要一些工作量的计算）。但是，如果我们有不同的点对 $(P,Q)$ 并且我们想要计算它们的每个 pairing 以将所有结果相乘在一起（例如，看看它是否等于 1），最有效的方法是先执行 Miller 循环对于每对点，将结果相乘，然后将最终指数运算应用于最终结果。执行此过程的函数称为 `compute_batch()`。

```rust=
fn compute_batch(
    pairs: &[(&Self::G1Point, &Self::G2Point)],
) -> Result<FieldElement<Self::OutputField>, PairingError> {
    let mut result = Fp12E::one();
    for (p, q) in pairs {
        // do some checks before computing the Miller loop
        // ...
        if !p.is_neutral_element() && !q.is_neutral_element() {
            let p = p.to_affine();
            let q = q.to_affine();
            result *= miller(&p, &q);
        }
    }
    Ok(final_exponentiation(&result))
}
```

## 子群检查

在将 pairing 应用于给定的点对 $(P,Q)$ 之前，有必要检查这些点是否属于其域。换句话说，我们需要检查 $P \in G_1$ 并且 $Q \in G_2$。由于 $G_1=E(F_p)$，因此无需检查 $P$。但是，由于 $G_2$ 与 $E'(F_{p^2})$ 不同，因此我们需要一种有效的方法来检查 $Q$ 是否属于该子群。

我们将使用 [这篇文章](https://hackmd.io/@Wimet/ry7z1Xj-2#Subgroup-Checks)，其中指出，当且仅当以下条件成立时，$E'(F_{p^2})$ 中的点 $Q$ 属于 $G_2$

$(x+1)Q+\varphi(xQ)+\varphi^2(xQ)=\varphi^3(2xQ)$。
回想一下，$x$ 是曲线的参数之一，$\varphi$ 是之前提到的 Frobenius 同态。因此，首先，我们需要有效地实现这个同态，避免将元素提升到 $p$ 的幂（因为 $p$ 是一个非常大的数字）。为此，我们将使用两个常数 $\gamma_{1,2},\gamma_{1,3} \in F_{p^2}$（稍后，我们将更详细地看到它们）。

```rust=
pub const GAMMA_12: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("2FB347984F7911F74C0BEC3CF559B143B78CC310C2C3330C99E39557176F553D"),\
    FpE::from_hex_unchecked("16C9E55061EBAE204BA4CC8BD75A079432AE2A1D0B7C9DCE1665D51C640FCBA2"),\
]);

pub const GAMMA_13: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("63CF305489AF5DCDC5EC698B6E2F9B9DBAAE0EDA9C95998DC54014671A0135A"),\
    FpE::from_hex_unchecked("7C03CBCAC41049A0704B5A7EC796F2B21807DC98FA25BD282D37F632623B0E3"),\
]);
```

有了这些常数，计算 $\varphi$ 就非常容易了。我们简单地使用 $\varphi(x,y)=(\gamma_{1,2}\overline{x},\gamma_{1,3}\overline{y})$，其中 $\overline{x}$ 是 $x$ 的共轭的符号：如果 $x=a+bw \in F_{p^2}$，则 $\overline{x}=a-bw$。

```rust=
pub fn phi(&self) -> Self {
    let [x, y, z] = self.coordinates();
    Self::new([\
        x.conjugate() * GAMMA_12,\
        y.conjugate() * GAMMA_13,\
        z.conjugate(),\
    ])
}
```

现在我们有了 $\varphi$，我们可以实现一个函数，该函数确定扭曲曲线 $E'(F_{p^2})$ 的某个点 $Q$ 是否属于子群 $G_2$。

```rust=
pub fn is_in_subgroup(&self) -> bool {
    let q_times_x = &self.operate_with_self(X);
    let q_times_x_plus_1 = &self.operate_with(q_times_x);
    let q_times_2x = q_times_x.double();

q_times_x_plus_1.operate_with(&q_times_x.phi().operate_with(&q_times_x.phi().phi()))
        == q_times_2x.phi().phi().phi()
}
```

## 直线

现在让我们看看如何为所有 $T,Q \in G_2$ 和 $P \in G_1$ 实现直线 $l_{T,Q}(P)$，在 lambdaworks 中称为 `line()`，这是 Miller 循环的基本函数。首先，我们可能有两种情况：$T=Q$ 或 $T \neq Q$。在第一种情况下，$l_{T,T}(P)$ 是 $T$ 的切线在 $P$ 处的值。在第二种情况下，它是通过 $T$ 和 $Q$ 的直线在 $P$ 处的值。

对于我们的实现，我们依赖于 [Pairing Realm](https://eprint.iacr.org/2013/722.pdf) 中提出的算法。我们使用第 13 页上的方程 11 表示 $T=Q$ 的情况，并使用第 14 页上的第一个方程表示 $T \neq Q$ 的情况。你还可以看到 [Arkworks 实现](https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/bn/g2.rs#L25) 的相同算法，其中计算 $T=Q$ 情况的函数称为 `double_in_place()`，而计算 $T \neq Q$ 情况的函数称为 `add_in_place()`。你会看到，论文和 Arkworks 都定义了比我们更多的变量。这是因为这些函数计算了直线和 $2T$（在第一种情况下）和 $T+Q$（在第二种情况下），这是 Ate pairing 算法的第 7、10、13 和 18 行的必要值。我们不必这样做，因为在这些行中，为了使群的元素加倍或添加两个元素，我们使用了 lambdaworks 函数 `operate_with_self()` 和 `operate_with()`。为了简化理解，我们保留了论文和 Arkworks 中出现的相同变量名称。请注意，以他们的方式添加或复制点只需要在我们的函数 `line()` 中包含几行，因此比较这两个实现并在需要时优化我们的实现很简单。

最后，值得注意的是，该论文将直线的结果给出为 5 次多项式，而在 lambdaworks 中，$F_{p^{12}}$ 的元素具有另一种表示形式。因此，我们需要使用字段扩展塔部分中解释的转换。

```rust=
fn line(p: &G1Point, t: &G2Point, q: &G2Point) -> Fp12E {
    let [x_p, y_p, _] = p.coordinates();

if t == q {
        let b = t.y().square();
        let c = t.z().square();
        //Define all the variables necessary
        //...

// We transform one representation of Fp12 into another one:
        Fp12E::new([\
            Fp6E::new([y_p * (-h), Fp2E::zero(), Fp2E::zero()]),\
            Fp6E::new([x_p * (j.double() + &j), i, Fp2E::zero()]),\
        ])
    } else {
        let [x_q, y_q, _] = q.coordinates();

let theta = t.y() - (y_q * t.z());
        let lambda = t.x() - (x_q * t.z());
        let j = &theta * x_q - (&lambda * y_q);

Fp12E::new([\
            Fp6E::new([y_p * lambda, Fp2E::zero(), Fp2E::zero()]),\
            Fp6E::new([x_p * (-theta), j, Fp2E::zero()]),\
        ])
    }
}
```

## 最终指数运算

我们需要做的最后一件事是有效地计算 $f^{\frac{p^{12}-1}{r}}$。我们从 [这里](https://hackmd.io/@Wimet/ry7z1Xj-2#Final-Exponentiation) 获取了最终指数运算算法，该算法将指数按以下方式划分：

$\frac{p^{12}-1}{r}=(p^6-1)(p^2+1)\frac{p^4-p^2+1}{r}$

### 简单部分

我们要计算

$f^{(p^6-1)(p^2+1)}=(f^{p^6}f^{-1})^{p^2} \cdot (f^{p^6}f^{-1})$。

使用以下方法可以轻松完成此操作：

- $f^{p^6}=\overline{f}$，我们可以使用 `conjugate()` 计算它。这是真的，因为 $f \in F_{p^{12}}$，并且此属性来自 [此处看到的 Frobenius 同态](https://github.com/mratsim/constantine/blob/master/constantine%2Fmath%2Fpairings%2Fcyclotomic_subgroups.nim#L154)。

- 函数 `inv()` 计算 $f^{-1}$。

- 要计算 $(f^{p^6}f^{-1})^{p^2}$，我们可以使用 Frobenius 平方同态 $\pi_p^2:F_{p^{12}} \rightarrow F_{p^{12}}$，定义为 $\pi_p^2(f)=\pi_p(\pi_p(f))=f^{p^2}$。在上一节中，我们解释了如何实现它。

```rust=
let f_easy_aux = f.conjugate() * f.inv().unwrap();
let f_easy = &frobenius_square(&f_easy_aux) * f_easy_aux;
```

### 困难部分

现在我们需要将简单部分的结果提升到幂 $\frac{p^4-p^2+1}{r}$。我们采用了[这里](https://hackmd.io/@Wimet/ry7z1Xj-2#The-Hard-Part) 提出的精确算法，分为四个步骤，其中 `f_easy` 在那里被称为 $m$。正如该帖子中所解释的那样，可以使用向量加法链技术来改进此算法。

## Frobenius 同态

最后，让我们看看如何实现最终指数运算中使用的 Frobenius 同态 $\pi_p$、$\pi_p^2$ 和 $\pi_p^3$。

你可能还记得我们已经实现了一个 Frobenius 同态 $\varphi$。尽管它们的名称相同，但 $\varphi$ 和 $\pi_p$ 之间存在细微的差异：函数 $\pi_p$ 将 $F_{p^{12}}$ 的元素提升到 $p$ 的幂，而 $\varphi$ 将扭曲曲线点的坐标提升到 $p$ 的幂。换句话说，$\pi_p:F_{p^{12}} \rightarrow F_{p^{12}}$，而 $\varphi:E'(F_{p^2}) \rightarrow E'(F_{p^2})$。这就是为什么它们的实现不完全相同的原因。

为了实现这些同态，我们需要为所有 $j=1,\dots,5$ 定义常数 $\gamma_{1,j}=(9+u)^{\frac{j(p-1)}{6}}$
$\gamma_{2,j}=\gamma_{1,j} \cdot \overline{\gamma_{1,j}}$
$\gamma_{3,j}=\gamma_{1,j} \cdot \gamma_{2,j}$```rust=
pub const GAMMA_11: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("1284B71C2865A7DFE8B99FDD76E68B605C521E08292F2176D60B35DADCC9E470"),\
    FpE::from_hex_unchecked("246996F3B4FAE7E6A6327CFE12150B8E747992778EEEC7E5CA5CF05F80F362AC"),\
]);

pub const GAMMA_12: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("2FB347984F7911F74C0BEC3CF559B143B78CC310C2C3330C99E39557176F553D"),\
    FpE::from_hex_unchecked("16C9E55061EBAE204BA4CC8BD75A079432AE2A1D0B7C9DCE1665D51C640FCBA2"),\
]);

// 等等
```

现在，我们使用如果 $f=a+bw$，那么
```rust=
pub fn frobenius(f: &Fp12E) -> Fp12E {
    let [a, b] = f.value();
    let [a0, a1, a2] = a.value();
    let [b0, b1, b2] = b.value();

let c1 = Fp6E::new([\
        a0.conjugate(),\
        a1.conjugate() * GAMMA_12,\
        a2.conjugate() * GAMMA_14,\
    ]);

let c2 = Fp6E::new([\
        b0.conjugate() * GAMMA_11,\
        b1.conjugate() * GAMMA_13,\
        b2.conjugate() * GAMMA_15,\
    ]);

Fp12E::new([c1, c2])
}

// similarly, frobenius_square and frobenius_cube.
// 类似地，还有 frobenius_square 和 frobenius_cube。
// ...
```

最后，如果我们对 $f$ 应用十二次 $\pi_p$，六次 $\pi_p^2$，或四次 $\pi_p^3$，我们会得到 $f$（即，它们变成了恒等函数）。这是因为 $f \in \mathbb{F}_{p^{12}}$，然后 $f^{p^{12}} = f$。这个性质将帮助我们测试是否正确实现了这些同态。

## 总结

这篇文章探讨了我们如何结合各种工作和论文来实现我们的配对。通过这样做，我们通过在点坐标之间或相同域扩展的不同表示之间进行转换，成功地整合了来自不同实现的算法。

#### 接下来是什么？

现在我们有了一个可以工作的配对，下一步是了解这个实现与其他实现的比较情况。因此，我们将执行一些基准测试，并进行一些我们已经知道的优化。正如[Lambda 的工程哲学](https://blog.lambdaclass.com/lambdas-engineering-philosophy/)中所写：“先让它工作，然后让它变得漂亮，如果真的，真的有必要，再让它变快。”

>- 原文链接： [blog.lambdaclass.com/how...](https://blog.lambdaclass.com/how-we-implemented-the-bn254-ate-pairing-in-lambdaworks)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

介绍

椭圆曲线 BN254 是目前以太坊上唯一具有预编译合约的曲线，使其成为链上zk-SNARK验证（使用 Groth16 和 PlonK 等证明系统）最实用的 pairing-friendly 曲线选择。这项工作源于我们需要自己实现的 BN254 Ate pairing。这篇文章的想法是作为我们实现的伴侣，解释理解它所需的数学理论和算法。一些论文和文章介绍了用于此 pairing 及其函数的不同算法，因此我们认为将所有这些信息组织到一篇文章中会很有帮助。

关于阅读本文所需的数学背景，我们仅假设你对群、有限域和椭圆曲线有轻微的概念。如果你对这些主题没有信心，我们建议阅读我们的文章开发者的数学生存工具包和每个开发者需要了解的关于椭圆曲线的知识。

曲线参数

BN254（在 Lambdaworks 中为 BN254Curve）是 Barreto-Naehrig pairing friendly 椭圆曲线 $E$，其形式为

$y^2=x^3+3$

在有限域 $F_p$ 上，其中：

$p=36x^4+36x^3+24x^2+6x+1$ 是 254 位素数：

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
x = 4965661367192848881

$t=6x^2+1$ 是 Frobenius 的迹。
$r=36x^4+36x^3+18x^2+6x+1=p+1-t$ 是曲线 $E(F_p)$ 中的点数。

点坐标

由于我们将椭圆曲线定义为满足上述方程的点集，因此很自然地想到使用两个坐标 $P=(x,y)$ 表示 $E(F_p)$ 中的元素 $P$。这种表示形式称为 仿射表示，其坐标称为 仿射坐标。但是，为了优化算术，许多时候使用 射影坐标 会很方便，射影坐标用三个坐标 $x, y, z$ 表示点，其构造方式如下：

如果 $P=(x,y)$ 是仿射坐标中的点，则 $(x,y,1)$ 是其射影表示。如果 $P=(x,y,z)$ 是射影坐标中的点，则 $(\frac{x}{z},\frac{y}{z})$ 是其仿射表示。你将在我们的实现中看到，我们根据每种情况下的需要使用这两种表示形式，使用 to_affine() 等函数。

还有第三种表示形式，我们不会使用，但你可能会在一些论文中找到，称为 雅可比坐标：如果 $P=(x,y,z)$ 是雅可比坐标中的点，则 $(\frac{x}{z^2},\frac{y}{z^3})$ 和 $(\frac{x}{z},\frac{y}{z^2})$ 分别是其射影坐标和仿射坐标。

域扩展塔

pairing 是一个映射 $e:G_1 \times G_2 \rightarrow G_t$，这意味着它将两个点作为输入，每个点来自具有相同点数（或阶）$r$ 的群。这个数 $r$ 必须是素数，并且为了保证安全，它必须很大。此外，由于一些技术原因，这两个群需要是不同的。因此，要定义 pairing，我们需要选择这些定义域和值域群。群 $G_1$ 将是曲线 $E(F_p)$，但要定义 $G_2$ 和 $G_t$，我们需要扩展域 $F_p$。我们不会停下来详细解释什么是域扩展以及如何构建它们，因此如果你正在寻找更好的理解，我们建议阅读 BLS12-381 For the Rest of US 中的域扩展部分。在这里，我们将总结理解我们的实现和我们使用的算法所必需的基本概念。

粗略地说，我们的目标是将域 $Fp$ 扩展到 $F{p^{12}}$，我们将以以下方式进行扩展。首先，我们将 $Fp$ 扩展到 $F{p^2}$，就像将实数域 $\mathbb{R}$ 扩展到复数域 $\mathbb{C}$ 一样：我们定义 $F_{p^2}=Fp[u]/(u^2+1)$。这需要处理很多符号。好消息是，我们需要理解的是，$F{p^2}$ 是一个有限域，其元素是 1 次多项式和变量 $u$；也就是说，它们的形式为 $a+bu$，其中 $a,b \in F_p$。如果我们将其视为复数，$a$ 将是实部，$b$ 将是虚部。请注意，$Fp \subseteq F{p^2}$，因为我们可以将左侧的元素视为具有“虚部”零或 $b=0$ 的右侧元素。因此，$F_{p^2}$ 确实是 $F_p$ 的扩展。

其次，我们以类似的方式扩展 $F{p^2}$，定义 $F{p^6}=F{p^2}[v]/(v^3-(9+u))$。在这种情况下，由于 $v^3-(9+u)$ 是一个 3 次多项式，$F{p^6}$ 的元素将是 2 次多项式和变量 $v$，其形式为 $a+bv+cv^2$，其中 $a,b,c \in F{p^2}$。最后，我们扩展 $F{p^6}$，定义 $F{p^{12}}=F{p^6}[w]/(w^2-v)$，也就是说，它的元素又是 1 次多项式和变量 $w$，其形式为 $a+bw$，其中 $a,b \in F_{p^6}$。

现在，在实践中，使用 lambdaworks，我们有两种不同的方式来定义元素 $f=a+bw \in F_{p^{12}}$。我们可以使用 new()，

let f = Fp12E::new([a, b])

或者我们可以使用 from_coefficients()。

let f = Fp12E::from_coefficients([\
"a_00", "a_01", "a_10", "a_11", "a_20", "a_21",\
"b_00", "b_01", "b_10", "b_11", "b_20", "b_21"\
])

在最后一种情况下，我们使用 12 个系数来定义 $f$，因为 $f=a+bw$，其中 $a,b \in F_{p^6}$。然后，$a=a_0+a_1v+a_2v^2$，并且 $b=b_0+b_1v+b_2v^2$，其中 $a_i,bi \in F{p^2}$。因此，$ai=a{i0}+a_{i1}u$，并且 $bi=b{i0}+b_{i1}u$，因此达到 12 个系数。

还有另一种 $F{p^{12}}$ 元素的表示形式，你可以在我们实现中使用的论文和算法中找到。由于 $v^3=9+u$ 并且 $w^2=v$，因此我们有 $w^6=9+u$，然后，$F{p^{12}}=F_{p^2}[w]/(w^6-(9+u))$。同样，你不必理解上一句话；重要的是，我们不仅可以将 $f$ 表示为 1 次多项式，还可以表示为 11 次多项式，还可以使用 $a_i$ 和 $b_i$ 将其表示为 5 次多项式，如下所示：

$f=a_0+b_0w+a_1w^2+b_1w^3+a_2w^4+b2w^5$。因此，每次你看到 $F{p^{12}}$ 的元素表示为 5 次多项式时，你都会知道如何将其写成 $a+bw$，使用其系数构建 $a=a_0+a_1v+a_2v^2$ 和 $b=b_0+b_1v+b_2v^2$（反之亦然）。拥有相同扩展域的不同表示形式将使我们能够在实现 pairing 时应用一些优化（参见 计算 BN254 曲线上的最佳 Ate Pairing 中的扩展域塔部分）。

这可能有很多新信息，但请不要担心；你不需要详细了解它。在阅读实现时，目的是手头有这些等式，以识别每个变量所属的位置以及它有多少个系数。在 lambdaworks bn_254 中，你将找到这些域 $Fp$、$F{p^2}$、$F{p^6}$ 和 $F{p^{12}}$（及其实现的运算）作为 BN254PrimeField、Degree2ExtensionField、Degree6ExtensionField 和 Degree12ExtensionField。

Twist

由于在 $F{p^{12}}$ 中进行算术运算既复杂又效率低下，我们将使用 twist，这就像一个坐标转换，它将我们的 $E(F{p^{12}})$ 曲线转换为以下定义在 $F_{p^2}$ 上的曲线 $E'$：

$y^2=x^3+\frac{3}{9+u}$。

我们将调用 $b=\frac{3}{9+u}$，实现为 BN254TwistCurve::b()。

b = 19485874751759354771024239261021720505790618469301721065564631296452457478373
    + 266929791119991161246907387137283842545076965332900288569378510910307636690
    * u

因此，总之，我们将使用以下子群作为 pairing 的输入：

$G_1=E(F_p)$，

$G2 \subseteq E'(F{p^2})$。

以及以下输出：

$Gt \subseteq F{p^{12}}^{\star}$，其中 $F{p^{12}}^{\star}=F{p^{12}}-{0}$（域的乘法群）。

准确地知道我们应该采用哪些子群 $G_2$ 和 $G_t$ 与理解我们的实现无关。我们只想对那些具有数学背景或有兴趣深入研究这些主题的人说，$G_1$ 和 $G_2$ 是 $r$- 挠群（即阶为 $r$ 的元素集合），而 $G_t$ 是 $r$- th 次单位根的集合。

Pairing

什么是 pairing？

现在，在我们定义了构建 pairing 所需的一切之后，让我们更好地理解它。pairing 是一个双线性映射 $e:G_1 \times G_2 \rightarrow G_t$。双线性 意味着它具有以下属性：对于所有点 $P_1,P_2 \in G_1$ 和 $Q_1,Q_2 \in G_2$，

$e(P_1,Q_1+Q_2)=e(P_1,Q_1) \cdot e(P_1,Q_2)$ $e(P_1+P_2,Q_1)=e(P_1,Q_1) \cdot e(P_2,Q_1)$ 由此属性可以推导出下一个属性：对于所有 $n,m \in \mathbb{N}$，

$e(nP,mQ)=e(mQ,nP)=e(P,mQ)^n=e(nP,Q)^m=e(P,Q)^{nm}$。回想一下，通常，加法符号 $+$ 用于表示群 $G_1$ 和 $G_2$ 的运算，而乘法符号 $\cdot$ 用于表示 $G_t$ 的运算。

Ate Pairing 算法

我们将使用这篇论文（第 4 页，算法 1）中的 Ate pairing 算法：

输入：$P \in G_1$ 和 $Q \in G_2$

输出： $f \in G_t$

定义 $T \in G_2$；
$T \leftarrow Q$；
定义 $f \in G_t$；
$f \leftarrow 1$；
对于 $i$=$miller_length-2$ 到 0 执行
$f \leftarrow f^2$；
$T \leftarrow 2T$；
如果 $MILLER_CONSTANT[i]=-1$ 则
$f \leftarrow f \cdot l_{T,-Q}(P)$；
$T \leftarrow T-Q$；
否则，如果 $MILLER_CONSTANT[i]=1$ 则
$f \leftarrow f \cdot l_{T,Q}(P)$；
$T \leftarrow T+Q$；
结束 if
结束 for
$Q_1 \leftarrow \varphi(Q)$；
$f \leftarrow f \cdot l_{T,Q_1}(P)$；
$T \leftarrow T+Q_1$；
$Q_2 \leftarrow \varphi(Q_1)$；
$f \leftarrow f \cdot l_{T,-Q_2}(P)$；
$f \leftarrow f^{\frac{p^{12}-1}{r}}$；
返回 $f$；

其中：

数字 $MILLER_CONSTANT=6x+2$，其中 $x$ 是我们之前提到的曲线参数。但是，我们需要使用 2 的幂和系数 ${-1,0,1}$ 来表示这个数字。这种表示类似于 NAF 表示，尽管它不是 NAF，因为它具有相邻的非零值。

// MILLER_CONSTANT = 6x + 2 = 29793968203157093288 =
// 2^3 + 2^5 - 2^7 + 2^10 - 2^11 + 2^14 + 2^17 + 2^18 - 2^20 + 2^23
// - 2^25 + 2^30 + 2^31 + 2^32 - 2^35 + 2^38 - 2^44 + 2^47 + 2^48
// - 2^51 + 2^55 + 2^56 - 2^58 + 2^61 + 2^63 + 2^64
pub const MILLER_CONSTANT: [i32; 65] = [\
      0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 0, -1, 0, 0,\
      1, 0, -1, 0, 0, 0, 0, 1, 1, 1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0,\
      0, 1, 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, 1, 1\
];

let miller_length = MILLER_CONSTANT.len()

函数 $l_{T,Q}(P)$ 是通过 $T$ 和 $Q$ 的直线在 $P$ 处的值。稍后我们将看到如何计算它。
Frobenius 同态 $\varphi:E'(F{p^2}) \rightarrow E'(F{p^2})$ 定义为 $\varphi(x,y)=(x^p,y^p)$。稍后我们还将看到它。

Batch

我们将提出的算法分为 Miller 循环和最终指数运算来实现它。miller() 函数执行算法的第 1 行到第 20 行的所有工作，而 final_exponentiation() 仅计算最后一行 21（这是一个需要一些工作量的计算）。但是，如果我们有不同的点对 $(P,Q)$ 并且我们想要计算它们的每个 pairing 以将所有结果相乘在一起（例如，看看它是否等于 1），最有效的方法是先执行 Miller 循环对于每对点，将结果相乘，然后将最终指数运算应用于最终结果。执行此过程的函数称为 compute_batch()。

fn compute_batch(
    pairs: &[(&Self::G1Point, &Self::G2Point)],
) -> Result&lt;FieldElement&lt;Self::OutputField>, PairingError> {
    let mut result = Fp12E::one();
    for (p, q) in pairs {
        // do some checks before computing the Miller loop
        // ...
        if !p.is_neutral_element() && !q.is_neutral_element() {
            let p = p.to_affine();
            let q = q.to_affine();
            result *= miller(&p, &q);
        }
    }
    Ok(final_exponentiation(&result))
}

子群检查

在将 pairing 应用于给定的点对 $(P,Q)$ 之前，有必要检查这些点是否属于其域。换句话说，我们需要检查 $P \in G_1$ 并且 $Q \in G_2$。由于 $G_1=E(F_p)$，因此无需检查 $P$。但是，由于 $G2$ 与 $E'(F{p^2})$ 不同，因此我们需要一种有效的方法来检查 $Q$ 是否属于该子群。

我们将使用这篇文章，其中指出，当且仅当以下条件成立时，$E'(F_{p^2})$ 中的点 $Q$ 属于 $G_2$

$(x+1)Q+\varphi(xQ)+\varphi^2(xQ)=\varphi^3(2xQ)$。回想一下，$x$ 是曲线的参数之一，$\varphi$ 是之前提到的 Frobenius 同态。因此，首先，我们需要有效地实现这个同态，避免将元素提升到 $p$ 的幂（因为 $p$ 是一个非常大的数字）。为此，我们将使用两个常数 $\gamma{1,2},\gamma{1,3} \in F_{p^2}$（稍后，我们将更详细地看到它们）。

pub const GAMMA_12: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("2FB347984F7911F74C0BEC3CF559B143B78CC310C2C3330C99E39557176F553D"),\
    FpE::from_hex_unchecked("16C9E55061EBAE204BA4CC8BD75A079432AE2A1D0B7C9DCE1665D51C640FCBA2"),\
]);

pub const GAMMA_13: Fp2E = Fp2E::const_from_raw([\
    FpE::from_hex_unchecked("63CF305489AF5DCDC5EC698B6E2F9B9DBAAE0EDA9C95998DC54014671A0135A"),\
    FpE::from_hex_unchecked("7C03CBCAC41049A0704B5A7EC796F2B21807DC98FA25BD282D37F632623B0E3"),\
]);

有了这些常数，计算 $\varphi$ 就非常容易了。我们简单地使用 $\varphi(x,y)=(\gamma{1,2}\overline{x},\gamma{1,3}\overline{y})$，其中 $\overline{x}$ 是 $x$ 的共轭的符号：如果 $x=a+bw \in F_{p^2}$，则 $\overline{x}=a-bw$。

pub fn phi(&self) -> Self {
    let [x, y, z] = self.coordinates();
    Self::new([\
        x.conjugate() * GAMMA_12,\
        y.conjugate() * GAMMA_13,\
        z.conjugate(),\
    ])
}

现在我们有了 $\varphi$，我们可以实现一个函数，该函数确定扭曲曲线 $E'(F_{p^2})$ 的某个点 $Q$ 是否属于子群 $G_2$。

pub fn is_in_subgroup(&self) -> bool {
    let q_times_x = &self.operate_with_self(X);
    let q_times_x_plus_1 = &self.operate_with(q_times_x);
    let q_times_2x = q_times_x.double();

    q_times_x_plus_1.operate_with(&q_times_x.phi().operate_with(&q_times_x.phi().phi()))
        == q_times_2x.phi().phi().phi()
}

直线

现在让我们看看如何为所有 $T,Q \in G_2$ 和 $P \in G1$ 实现直线 $l{T,Q}(P)$，在 lambdaworks 中称为 line()，这是 Miller 循环的基本函数。首先，我们可能有两种情况：$T=Q$ 或 $T \neq Q$。在第一种情况下，$l_{T,T}(P)$ 是 $T$ 的切线在 $P$ 处的值。在第二种情况下，它是通过 $T$ 和 $Q$ 的直线在 $P$ 处的值。

对于我们的实现，我们依赖于 Pairing Realm 中提出的算法。我们使用第 13 页上的方程 11 表示 $T=Q$ 的情况，并使用第 14 页上的第一个方程表示 $T \neq Q$ 的情况。你还可以看到 Arkworks 实现的相同算法，其中计算 $T=Q$ 情况的函数称为 double_in_place()，而计算 $T \neq Q$ 情况的函数称为 add_in_place()。你会看到，论文和 Arkworks 都定义了比我们更多的变量。这是因为这些函数计算了直线和 $2T$（在第一种情况下）和 $T+Q$（在第二种情况下），这是 Ate pairing 算法的第 7、10、13 和 18 行的必要值。我们不必这样做，因为在这些行中，为了使群的元素加倍或添加两个元素，我们使用了 lambdaworks 函数 operate_with_self() 和 operate_with()。为了简化理解，我们保留了论文和 Arkworks 中出现的相同变量名称。请注意，以他们的方式添加或复制点只需要在我们的函数 line() 中包含几行，因此比较这两个实现并在需要时优化我们的实现很简单。

fn line(p: &G1Point, t: &G2Point, q: &G2Point) -> Fp12E {
    let [x_p, y_p, _] = p.coordinates();

    if t == q {
        let b = t.y().square();
        let c = t.z().square();
        //Define all the variables necessary
        //...

        // We transform one representation of Fp12 into another one:
        Fp12E::new([\
            Fp6E::new([y_p * (-h), Fp2E::zero(), Fp2E::zero()]),\
            Fp6E::new([x_p * (j.double() + &j), i, Fp2E::zero()]),\
        ])
    } else {
        let [x_q, y_q, _] = q.coordinates();

        let theta = t.y() - (y_q * t.z());
        let lambda = t.x() - (x_q * t.z());
        let j = &theta * x_q - (&lambda * y_q);

        Fp12E::new([\
            Fp6E::new([y_p * lambda, Fp2E::zero(), Fp2E::zero()]),\
            Fp6E::new([x_p * (-theta), j, Fp2E::zero()]),\
        ])
    }
}

最终指数运算

我们需要做的最后一件事是有效地计算 $f^{\frac{p^{12}-1}{r}}$。我们从这里获取了最终指数运算算法，该算法将指数按以下方式划分：

$\frac{p^{12}-1}{r}=(p^6-1)(p^2+1)\frac{p^4-p^2+1}{r}$

简单部分

我们要计算

$f^{(p^6-1)(p^2+1)}=(f^{p^6}f^{-1})^{p^2} \cdot (f^{p^6}f^{-1})$。

使用以下方法可以轻松完成此操作：

$f^{p^6}=\overline{f}$，我们可以使用 conjugate() 计算它。这是真的，因为 $f \in F_{p^{12}}$，并且此属性来自此处看到的 Frobenius 同态。
函数 inv() 计算 $f^{-1}$。
要计算 $(f^{p^6}f^{-1})^{p^2}$，我们可以使用 Frobenius 平方同态 $\pip^2:F{p^{12}} \rightarrow F_{p^{12}}$，定义为 $\pi_p^2(f)=\pi_p(\pi_p(f))=f^{p^2}$。在上一节中，我们解释了如何实现它。

let f_easy_aux = f.conjugate() * f.inv().unwrap();
let f_easy = &frobenius_square(&f_easy_aux) * f_easy_aux;

困难部分

现在我们需要将简单部分的结果提升到幂 $\frac{p^4-p^2+1}{r}$。我们采用了这里提出的精确算法，分为四个步骤，其中 f_easy 在那里被称为 $m$。正如该帖子中所解释的那样，可以使用向量加法链技术来改进此算法。

Frobenius 同态

最后，让我们看看如何实现最终指数运算中使用的 Frobenius 同态 $\pi_p$、$\pi_p^2$ 和 $\pi_p^3$。

你可能还记得我们已经实现了一个 Frobenius 同态 $\varphi$。尽管它们的名称相同，但 $\varphi$ 和 $\pi_p$ 之间存在细微的差异：函数 $\pip$ 将 $F{p^{12}}$ 的元素提升到 $p$ 的幂，而 $\varphi$ 将扭曲曲线点的坐标提升到 $p$ 的幂。换句话说，$\pip:F{p^{12}} \rightarrow F{p^{12}}$，而 $\varphi:E'(F{p^2}) \rightarrow E'(F_{p^2})$。这就是为什么它们的实现不完全相同的原因。

为了实现这些同态，我们需要为所有 $j=1,\dots,5$ 定义常数 $\gamma{1,j}=(9+u)^{\frac{j(p-1)}{6}}$ $\gamma{2,j}=\gamma{1,j} \cdot \overline{\gamma{1,j}}$ $\gamma{3,j}=\gamma{1,j} \cdot \gamma_{2,j}$```rust= pub const GAMMA_11: Fp2E = Fp2E::const_from_raw([\ FpE::from_hex_unchecked("1284B71C2865A7DFE8B99FDD76E68B605C521E08292F2176D60B35DADCC9E470"),\ FpE::from_hex_unchecked("246996F3B4FAE7E6A6327CFE12150B8E747992778EEEC7E5CA5CF05F80F362AC"),\ ]);

pub const GAMMA_12: Fp2E = Fp2E::const_from_raw([\ FpE::from_hex_unchecked("2FB347984F7911F74C0BEC3CF559B143B78CC310C2C3330C99E39557176F553D"),\ FpE::from_hex_unchecked("16C9E55061EBAE204BA4CC8BD75A079432AE2A1D0B7C9DCE1665D51C640FCBA2"),\ ]);

// 等等


现在，我们使用如果 $f=a+bw$，那么
```rust=
pub fn frobenius(f: &Fp12E) -> Fp12E {
    let [a, b] = f.value();
    let [a0, a1, a2] = a.value();
    let [b0, b1, b2] = b.value();

    let c1 = Fp6E::new([\
        a0.conjugate(),\
        a1.conjugate() * GAMMA_12,\
        a2.conjugate() * GAMMA_14,\
    ]);

    let c2 = Fp6E::new([\
        b0.conjugate() * GAMMA_11,\
        b1.conjugate() * GAMMA_13,\
        b2.conjugate() * GAMMA_15,\
    ]);

    Fp12E::new([c1, c2])
}

// similarly, frobenius_square and frobenius_cube.
// 类似地，还有 frobenius_square 和 frobenius_cube。
// ...

最后，如果我们对 $f$ 应用十二次 $\pi_p$，六次 $\pi_p^2$，或四次 $\pip^3$，我们会得到 $f$（即，它们变成了恒等函数）。这是因为 $f \in \mathbb{F}{p^{12}}$，然后 $f^{p^{12}} = f$。这个性质将帮助我们测试是否正确实现了这些同态。

总结

接下来是什么？

现在我们有了一个可以工作的配对，下一步是了解这个实现与其他实现的比较情况。因此，我们将执行一些基准测试，并进行一些我们已经知道的优化。正如Lambda 的工程哲学中所写：“先让它工作，然后让它变得漂亮，如果真的，真的有必要，再让它变快。”

原文链接： blog.lambdaclass.com/how...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

翻译
学分: 0
分类: 以太坊
标签: BN254椭圆曲线配对 Ate配对算法米勒循环最终指数化弗罗贝尼乌斯自同态

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。