双线性配对（有时也称为双线性映射）允许我们取三个数 $a$、$b$ 和 $c$（其中 $ab = c$），将它们加密为 $E(a)$、$E(b)$、$E(c)$（其中 $E$ 是加密函数），然后将这两个加密值发送给验证者，验证者可以验证 $E(a)E(b) = E(c)$，但无法知道原始值。我们可以使用双线性配对来证明第三个数是前两个数的乘积，而无需知道前两个原始数字。

我们将在高层次上解释双线性配对，并在 Python 中提供一些示例。

先决条件

• 读者应该了解在椭圆曲线背景下的点加法和标量乘法是什么。
• 读者还应该了解该背景下的离散对数问题：一个标量乘以一个点会产生另一个点，而通常情况下，给定椭圆曲线上的点来计算该标量是不可行的。
• 读者应该了解什么是有限域和循环群，以及在椭圆曲线背景下的生成元是什么。我们将使用变量 G 来指代生成元。
• 读者应该了解 Ethereum 预编译。
  我们将使用大写字母表示 EC（椭圆曲线）点，使用小写字母表示有限域的元素（“标量”）。当我们说元素时，它可以是有限域中的整数，也可以是椭圆曲线上的点。上下文会使其含义明确。

即使没有完全理解上述所有内容，也可以阅读本教程，但要对该主题建立良好的直觉会比较困难。

双线性配对是如何工作的

当一个标量乘以椭圆曲线上的一个点时，会产生另一个椭圆曲线点。即 $P = pG$，其中 $p$ 是标量，$G$ 是生成元。给定 $P$ 和 $G$，我们无法确定 $p$。

假设 $pq = r$。我们要尝试做的是取

并向验证者证明 $P$ 和 $Q$ 的离散对数相乘会产生 $R$ 的离散对数。

如果 $pq = r$，且 $P = pG$、$Q = qG$、$R = rG$，那么我们希望存在一个函数，使得

且在 $pq ≠ r$ 时不等于 $R$。对于群中 $p$、$q$ 和 $r$ 的所有可能组合，这都应该成立。

然而，这通常不是我们在使用双线性配对时表达 $R$ 的方式。出于稍后我们将讨论的原因，它通常计算为

$G$ 是生成元点，在这个语境下可以将其看作 $1$。例如，$pG$ 意味着我们将 $(G + G + … + G)$ 执行了 $p$ 次。$G$ 仅仅意味着我们取了 $G$ 且没有添加任何东西。因此在某种意义上，这与说 $P \times Q = R \times 1$ 是一样的。

因此，我们的双线性配对是一个函数：如果你输入两个椭圆曲线点，你会得到一个对应于这两个点离散对数乘积的输出。

记号

双线性配对通常写为 $e(P, Q)$。在这里，$e$ 与自然对数无关，且 $P$ 和 $Q$ 是椭圆曲线点。

泛化：检查两个乘积是否相等

假设有人给了我们四个椭圆曲线点 $P_1$、$P_2$、$Q_1$ 和 $Q_2$，并声称 $P_1$ 和 $P_2$ 的离散对数乘积与 $Q_1$ 和 $Q_2$ 的相同，即 $p_1p_2 = q_1q_2$。使用双线性配对，我们可以在不知道 $p_1$、$p_2$、$q_1$ 或 $q_2$ 的情况下检查这是否为真。我们只需执行：

“双线性”意味着什么

双线性意味着，如果一个函数接受两个参数，且其中一个保持不变，而另一个发生变化，那么输出将随非恒定参数线性变化。

如果 $f(x,y)$ 是双线性的，且 $c$ 为常数，则 $z = f(x, c)$ 随 $x$ 线性变化，$z = f(c, y)$ 随 $y$ 线性变化。

由此我们可以推断，椭圆曲线双线性配对具有以下属性：

$e(P, Q)$ 返回了什么？

说实话，其输出在数学上非常可怕，试图真正解释它可能会适得其反。这就是为什么本书前面花了大量篇幅解释群，因为理解什么是群比理解 $e(P, Q)$ 返回的内容要容易成千上万倍。

双线性配对的输出是一个群元素，具体来说是一个有限循环群的元素。

最好将 $e(P, Q)$ 视为一个黑盒，就像大多数程序员将哈希函数视为黑盒一样。

然而，尽管它是一个黑盒，我们仍然对其输出的属性了解很多，我们将其称为 $G_T$：

• $G_T$ 是一个循环群，因此它具有封闭的二元运算符。
• $G_T$ 的二元运算符满足结合律。
• $G_T$ 有一个单位元。
• $G_T$ 中的每个元素都有一个逆元。
• 因为该群是循环的，所以它有一个生成元。
• 因为该群是循环且有限的，所以有限循环群同态于 $G_T$。也就是说，我们有某种方法将有限域中的元素同态映射到 $G_T$ 中的元素。

因为该群是循环群，所以我们有了 $G_T$、$2G_T$、$3G_T$ 等概念。$G_T$ 的二元运算符大致可以称为“乘法”，所以 $8G_T = 2G_T * 4G_T$。

如果你真的想知道 $G_T$“看起来”是什么样子，它是一个 12 维的物体。不过，它的单位元看起来并不那么吓人：

对称群与非对称群

上面的记号暗示，当我们说以下等式时，我们在所有地方使用了相同的生成元和椭圆曲线群

然而在实践中，当双线性配对的两个参数使用不同（但阶数相同）的群时，事实证明创建双线性配对更容易。

具体来说，我们表示为

使用的群完全不相同。

然而，我们关心的属性仍然成立。

在上面的等式中，群 $G_T$ 没有明确显示，但它是 $e(G_1, G_2)$ 的陪域（输出空间）。

我们可以将 $G_1$ 和 $G_2$ 视为具有不同参数（但点数相同）的不同椭圆曲线方程，这是有效的，因为它们是不同的群。

在对称配对中，双线性配对函数的两个参数使用相同的椭圆曲线群。这意味着两个参数中使用的生成元和椭圆曲线群是相同的。在这种情况下，配对函数通常表示为：

在非对称配对中，参数使用不同的群。例如，第一个参数可以使用与第二个参数不同的生成元和椭圆曲线群。配对函数仍然可以满足所需的属性

在实践中，我们使用非对称群，我们所使用的群之间的区别将在下一节中解释。

$G_1$ 是我们在前几章中讨论的同一个群，在 Ethereum 的语境下，它是我们从库中导入的同一个 G1：

Copy
from py_ecc.bn128 import G1

我们还可以从同一个库中导入 G2：

Copy
from py_ecc.bn128 import G1, G2

但 $G_2$ 是什么？

扩域以及 Python 中的 G2 点

双线性配对对你选择哪种群并没有太多限制，但 Ethereum 的 $G_2$ 使用了带有扩域（field extensions）的椭圆曲线。如果你希望能够阅读使用 ZK-SNARKS 的 Solidity 代码，你至少需要对这些概念有一个大致的了解。

我们通常认为 EC 点是由 $x$ 和 $y$ 两个坐标点组成。但在扩域下，$x$ 和 $y$ 本身变成了二维对象 $(x, y)$ 对。这类似于复数如何“扩展”实数，并将其变成具有 2 个维度的对象（实部和虚部）。

扩域是一个非常抽象的概念，坦率地说，从纯粹的功能概念来看，域与其扩域之间的关系并不重要。

可以这样来理解：

$G_2$ 中的椭圆曲线是一条 $x$ 和 $y$ 元素都是二维对象的椭圆曲线。

Python 中的 G2 点

理论讲够了，让我们编写代码来看看 $G_2$ 点。通过以下方式安装 py_ecc 库。

Copy
python -m pip install py_ecc

现在让我们从中导入我们需要使用的函数

Copy
from py_ecc.bn128 import G1, G2, pairing, add, multiply, eq

print(G1)
# (1, 2)
print(G2)
#((10857046999023057135944570762232829481370756359578518086990519993285655852781, 11559732032986387107991004021392285783925812861821192530917403151452391805634), (8495653923123431417604973247489272438418190587263600148770280649306958101930, 4082367875863433681332203403145435568316851327593401208105741076214120093531))

如果你仔细观察 G2，你会发现 G2 是一对元组。第一个元组是二维的 $x$ 坐标点，第二个元组是二维的 $y$ 坐标点。

G1 和 G2 分别是其对应群的生成元点。

G1 和 G2 具有相同的阶（曲线上点的数量）：

Copy
from py_ecc.bn128 import G1, G2, eq, curve_order, multiply, eq, curve_order

x = 10 # chosen randomly
assert eq(multiply(G2, x + curve_order), multiply(G2, x))
assert eq(multiply(G1, x + curve_order), multiply(G1, x))

尽管 G2 点似乎有点奇怪，但它们的行为与其他循环群相同，尤其是我们熟悉的 G1 群。这意味着我们可以像预期那样通过标量乘法（实际上是重复相加）来构造其他点

Copy
print(eq(add(G1, G1), multiply(G1, 2)))
# True
print(eq(add(G2, G2), multiply(G2, 2)))
# True

显而易见，你只能将同一群中的元素相加。

Copy
add(G1, G2) # TypeError

顺便说一下，这个库重载了一些算术运算符（在 Python 中可以这么做），这意味着你可以执行以下操作：

Copy
print(G1 + G1 + G1 == G1*3)
# True

# The above is the same as this:
eq(add(add(G1, G1), G1), multiply(G1, 3))
# True

Python 中的双线性配对

在本文开头我们提到，双线性配对可用于检查 $P$ 和 $Q$ 的离散对数相乘是否产生 $R$ 的离散对数，即 $PQ = R$。

在 Python 中我们可以这样做：

Copy
from py_ecc.bn128 import G1, G2, pairing, multiply, eq

P = multiply(G1, 3)
Q = multiply(G2, 8)

R = multiply(G1, 24)

assert eq(pairing(Q, P), pairing(G2, R))

有点令人烦恼的是，该库要求你将 G2 点作为 pairing 的第一个参数传入。

乘积的相等性

同样在本文的开头，我们说配对可以检查：

在 Python 中我们可以这样做：

Copy
from py_ecc.bn128 import G1, G2, pairing, multiply, eq

P_1 = multiply(G1, 3)
P_2 = multiply(G2, 8)

Q_1 = multiply(G1, 6)
Q_2 = multiply(G2, 4)

assert eq(pairing(P_2, P_1), pairing(Q_2, Q_1))

$G_T$ 的二元运算符

$G_T$ 中的元素使用“乘法”进行组合，但请记住，这实际上是 Python 中的语法重载：

Copy
from py_ecc.bn128 import G1, G2, pairing, multiply, eq

# 2 * 3 = 6
P_1 = multiply(G1, 2)
P_2 = multiply(G2, 3)

# 4 * 5 = 20
Q_1 = multiply(G1, 4)
Q_2 = multiply(G2, 5)

# 10 * 12 = 120 (6 * 20 = 120 also)
R_1 = multiply(G1, 10)
R_2 = multiply(G2, 12)

assert eq(pairing(P_2, P_1) * pairing(Q_2, Q_1), pairing(R_2, R_1))

# Fails!

但断言失败了！

$G_T$ 中的元素行为类似于某个底数的“幂”。

回忆一下代数中的规则：

假设我们在 $G_T$ 中生成一个元素作为 $e(3G_2, 2G_1)$。我们可能会将该元素视为 $6G_T$，但将其视为 $b^6G_T$ 会有帮助得多。在这种情况下不需要知道 $b$ 是什么，只需要知道它存在即可。

因此，为了使我们上面的代码有效运行，请将 $R_1$ 和 $R_2$ 更改为相乘等于 26。

我们的代码实际上在计算：

Copy
from py_ecc.bn128 import G1, G2, pairing, multiply, eq

# 2 * 3 = 6
P_1 = multiply(G1, 2)
P_2 = multiply(G2, 3)

# 4 * 5 = 20
Q_1 = multiply(G1, 4)
Q_2 = multiply(G2, 5)

# 13 * 2 = 26
R_1 = multiply(G1, 13)
R_2 = multiply(G2, 2)

# b ^ {2 * 3} * b ^ {4 * 5} = b ^ {13 * 2}
# b ^ 6 * b ^ 20 = b ^ 26

assert eq(pairing(P_2, P_1) * pairing(Q_2, Q_1), pairing(R_2, R_1))

Ethereum 中的双线性配对

EIP 197 规范

py_ecc 库实际上由 Ethereum Foundation 维护，它是 PyEVM 实现中地址 0x8 处预编译的核心驱动力。

在 EIP-197 中定义的 Ethereum 预编译对 G1 和 G2 中的点进行操作，并隐式地对 $G_T$ 中的点进行操作。

这个预编译的规范乍看之下可能会觉得有些奇怪。它接收以如下形式排列的 G1 和 G2 点列表：

A₁B₁A₂B₂...AₙBₙ : Aᵢ ∈ G1, Bᵢ ∈ G2

它们最初被创建为

Copy
A₁ = a₁G1
B₁ = b₁G2
A₂ = a₂G1
B₂ = b₂G2
...
Aₙ = aₙG1
Bₙ = bₙG2

如果以下条件为真，则预编译返回 1

Copy
a₁b₁ + a₂b₂ + ... + aₙbₙ = 0

否则返回 0。

起初这可能会令人费解！这似乎意味着预编译正在获取每个点的离散对数，而这通常被认为是不可行的。此外，为什么它的行为不像前面 Python 示例中的配对？前面的示例返回了 $G_T$ 中的一个元素，但这个预编译返回一个布尔值。

EIP 197 设计决策的理由

第一个问题是 $G_T$ 中的元素很大，具体来说，它们是 12 维的对象。

这会占用大量的内存空间，从而导致更高的 gas 成本。而且，由于大多数 ZK 验证算法的工作原理（这超出了本文的范围），我们通常不检查配对输出的值，而只检查它是否等于其他配对。具体来说，Groth16（tornado cash 使用的零知识算法）的最后一步如下所示

其中每个变量根据其下标标记是 $\mathbb{G}_1$ 或 $\mathbb{G}_2$ 的椭圆曲线点（我们本可以继续使用大写希腊字母以与我们的记号保持一致，但它们看起来与拉丁字母太相似了）。

这些变量的含义现阶段并不重要。重要的是它可以写为“乘积”（椭圆曲线配对）的总和。具体而言，我们可以将其写为

现在它完美匹配了预编译的规范！

不仅是 Groth16，大多数 zk 算法都有看起来像那样的验证公式，这就是为什么该预编译被设计为处理配对的总和，而不是返回单一配对的值。

如果我们查看 Tornado Cash 的验证代码，我们可以看到它完全实现了这一点（甚至希腊字母都匹配，不过如果你还没看懂也不用担心）。$\beta_2$ 仅仅意味着它是一个 $\mathbb{G}_2$ 点，$\alpha_1$ 意味着 $\mathbb{G}_1$ 点，等等。

在配对函数内部调用了 address(8) 以完成配对计算，并确定证明是否有效。

在 EIP 197 的上下文中，群 $G_T$ 有时被称为 $G_{12}$。

离散对数之和

这里的关键见解是，如果

那么以下等式也必定成立

在 $\mathbb{G}_{12}$ 群中。

该预编译实际上并没有计算离散对数，它只是在检查配对之和是否为零。

当且仅当离散对数乘积的总和为零时，配对的总和才会为零。

双线性配对的端到端 Solidity 示例

让我们采用 a、b、c 和 d 的这些输入值。

Copy
a = 4
b = 3
c = 6
d = 2

-ab + cd = 0

将其代入公式中，我们可以得到

在 Python 中，这将等同于

Copy
from py_ecc.bn128 import neg, multiply, G1, G2
a = 4
b = 3
c = 6
d = 2
# negate G1 * a to make the equation sum up to 0

print(neg(multiply(G1, a)))
#(3010198690406615200373504922352659861758983907867017329644089018310584441462, 17861058253836152797273815394432013122766662423622084931972383889279925210507)
print(multiply(G2, b))
# ((2725019753478801796453339367788033689375851816420509565303521482350756874229, 7273165102799931111715871471550377909735733521218303035754523677688038059653), (2512659008974376214222774206987427162027254181373325676825515531566330959255, 957874124722006818841961785324909313781880061366718538693995380805373202866))
print(multiply(G1, c))
# (4503322228978077916651710446042370109107355802721800704639343137502100212473, 6132642251294427119375180147349983541569387941788025780665104001559216576968)
print(multiply(G2, d))
# ((18029695676650738226693292988307914797657423701064905010927197838374790804409, 14583779054894525174450323658765874724019480979794335525732096752006891875705), (2140229616977736810657479771656733941598412651537078903776637920509952744750, 11474861747383700316476719153975578001603231366361248090558603872215261634898))

以下是结构化格式的输出

Copy
aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462,
aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507,

bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229,
bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653,
bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255,
bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866,

cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473,
cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968,

dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409,
dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705,
dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750,
dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898

现在我们已经将这些值加密到了 $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 群中的点，其他人或程序可以在不知道 a、b、c 或 d 具体值的情况下，确认我们正确地计算了 $e(A_1,B_2)+e(C_1,D_2)=0$。下面是一个 Solidity 合约，它使用 ecPairing 预编译来确认我们使用有效值计算了方程式。

我们创建一个文件 Pairings.sol，以用于 Foundry 中的单元测试（接下来我们将提供测试文件）

Copy
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;
contract Pairings {
    /** 
     *  returns true if == 0,
     *  returns false if != 0,
     *  reverts with "Wrong pairing" if invalid pairing
     */
     function run(uint256[12] memory input) public view returns (bool) {
        assembly {
            let success := staticcall(gas(), 0x08, input, 0x0180, input, 0x20)
            if success {
                return(input, 0x20)
            }
        }
        revert("Wrong pairing");
    }
}

我们使用这个 Foundry 测试文件来部署和调用我们的 Pairings 合约，以确认我们的 ecPairing 计算。我们将以下文件命名为 TestPairings.sol。

Copy
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;
import "forge-std/Test.sol";
import "../src/Pairings.sol";

contract PairingsTest is Test {
    Pairings public pairings;

    function setUp() public {
        pairings = new Pairings();
    }

    function testPairings() public view {
        uint256 aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462;
        uint256 aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507;

        uint256 bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229;
        uint256 bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653;
        uint256 bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255;
        uint256 bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866;

        uint256 cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473;
        uint256 cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968;

        uint256 dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409;
        uint256 dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705;
        uint256 dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750;
        uint256 dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898;

        uint256[12] memory points = [
            aG1_x,
            aG1_y,
            bG2_x2,
            bG2_x1,
            bG2_y2,
            bG2_y1,
            cG1_x,
            cG1_y,
            dG2_x2,
            dG2_x1,
            dG2_y2,
            dG2_y1
        ];

        bool x = pairings.run(points);
        console2.log("result:", x);
    }
}

请注意，G2 点排列的方式与 Python 排列 G2 点的方式不同。

该测试通过并在控制台打印出 true。请注意，这些点已经通过它们的变量名、所属的群以及它们代表的是椭圆曲线点的 x 还是 y 进行了标记。

需要着重指出的是，ecPairing 预编译不期望也不强制要求使用数组，我们选择将其与内联汇编（inline-assembly）结合使用完全是可选的。我们可以像下面这样在 Solidity 中执行相同的操作：

Copy
function run(bytes calldata input) public view returns (bool) {
    // optional, the precompile checks this too and reverts (with no error) if false, this helps narrow down possible errors
    if (input.length % 192 != 0) revert("Points must be a multiple of 6");
    (bool success, bytes memory data) = address(0x08).staticcall(input);
    if (success) return abi.decode(data, (bool));
    revert("Wrong pairing");
}

并按如下方式更新测试文件：

Copy
function testPairings() public view {
    uint256 aG1_x = 3010198690406615200373504922352659861758983907867017329644089018310584441462;
    uint256 aG1_y = 17861058253836152797273815394432013122766662423622084931972383889279925210507;

    uint256 bG2_x1 = 2725019753478801796453339367788033689375851816420509565303521482350756874229;
    uint256 bG2_x2 = 7273165102799931111715871471550377909735733521218303035754523677688038059653;
    uint256 bG2_y1 = 2512659008974376214222774206987427162027254181373325676825515531566330959255;
    uint256 bG2_y2 = 957874124722006818841961785324909313781880061366718538693995380805373202866;

    uint256 cG1_x = 4503322228978077916651710446042370109107355802721800704639343137502100212473;
    uint256 cG1_y = 6132642251294427119375180147349983541569387941788025780665104001559216576968;

    uint256 dG2_x1 = 18029695676650738226693292988307914797657423701064905010927197838374790804409;
    uint256 dG2_x2 = 14583779054894525174450323658765874724019480979794335525732096752006891875705;
    uint256 dG2_y1 = 2140229616977736810657479771656733941598412651537078903776637920509952744750;
    uint256 dG2_y2 = 11474861747383700316476719153975578001603231366361248090558603872215261634898;

    bytes memory points = abi.encode(
        aG1_x,
        aG1_y,
        bG2_x2,
        bG2_x1,
        bG2_y2,
        bG2_y1,
        cG1_x,
        cG1_y,
        dG2_x2,
        dG2_x1,
        dG2_y2,
        dG2_y1
    );

    bool x = pairings.run(points);
    console2.log("result:", x);
}

这会像最初的实现一样通过测试并返回 true，因为它向预编译发送了完全相同的 calldata。

唯一的区别在于：在第一个实现中，测试文件向 pairing 合约发送了一个点数组，合约使用内联汇编截掉前 32 个字节（数组长度），然后将其余部分发送到预编译；而在第二个实现中，测试文件向 pairing 合约发送 ABI 编码的点数据，合约将其原封不动地转发给预编译。

从 RareSkills 了解更多

本材料摘自我们的零知识课程。请查看该计划以了解更多信息。

我真的想了解双线性配对背后的数学原理

之前已经警告过你，这些数学知识相当深奥，而理解它对于你实际去实现 ZK 证明（这也是本书的目标）并没有太大帮助。你可能已经能够高效地使用 SHA-256 或 Keccak256 而无需了解它们的内部原理，我们强烈建议在你学习的现阶段对配对采取同样的态度。尽管如此，如果我们的警告并没有吓退你，并且你依然想深入研究它，这里有一个很好的资源：Pairings for Beginners。前方充满未知与挑战。

最初发布于 2023 年 7 月 18 日