在深入研究密码学电路中缺失范围检查攻击之前，有必要了解什么是群，它们的大小（阶）如何表现，以及为什么这很重要

hexens 发布于 2025-06-17 阅读 1016

本文深入探讨了密码学电路中缺失范围检查攻击的原理和实例，首先介绍了群论的基础知识，包括群、子群、群的阶、元素的阶、生成器和循环群等概念，以及拉格朗日定理及其推论。

在深入研究密码电路中缺失的范围检查攻击之前，有必要了解什么是群，它们的规模（阶）如何表现，以及为什么这很重要。

## 群、循环结构和拉格朗日定理

#### 群和子群

一个**群** $G$ 是一个集合，带有一个二元运算（例如，加法或乘法），满足以下性质：

- **封闭性**：对于任何 $a, b \in G$，我们有 $ab \in G$。
- **结合性**：$(ab)c = a(bc)$ 对于所有 $a, b, c \in G$。
- **单位元**：存在一个元素 $e \in G$，使得 $ae = ea = a$ 对于所有 $a \in G$。
- **逆元**：对于每个 $a \in G$，存在一个逆元 $a^{-1} \in G$，使得 $aa^{-1} = a^{-1}a = e$。

一个子集 $H \subseteq G$ 被称为**子群**，如果它本身在从 $G$ 继承的运算下也是一个群。

#### 群的阶，元素的阶

**群的阶** $G$，表示为 $|G|$，是群中元素的数量。如果群有无限多个元素，则阶也可能是无限的。

**元素的阶** $g \in G$ 是最小的正整数 $n$，使得 $g^n = e$，其中 $e$ 是群的单位元。如果不存在这样的 $n$，我们说 $g$ 的阶是无限的。

#### 生成元和循环群

群 $G$ 的一个**生成集合**（或**生成元集合**）是一个子集 $S = \{s_1, s_2, \dots, s_k\} \subseteq G$，使得 $G$ 的每个元素都可以写成来自 $S$ 的元素及其逆元的有限乘积。

也就是说，对于每个 $g \in G$，存在一个索引序列 $i_1, i_2, \dots, i_m \in \{1, \dots, k\}$ 和指数 $\epsilon_1, \epsilon_2, \dots, \epsilon_m \in \{\pm 1\}$，使得：

$g = s_{i_1}^{\epsilon_1} s_{i_2}^{\epsilon_2} \cdots s_{i_m}^{\epsilon_m}$。

由 $S$ 生成的群表示为：

$G = \langle S \rangle = \left\{ s_{i_1}^{\epsilon_1} s_{i_2}^{\epsilon_2} \cdots s_{i_m}^{\epsilon_m} \mid m \in \mathbb{N}, i_j \in \{1, \dots, k\}, \epsilon_j \in \{\pm 1\} \right\}$。

如果一个群 $G$ 有一个由单个元素 $g$ 组成的生成集合，即 $G = \langle g \rangle$，我们说 $G$ 是**循环群**。

### 陪集和拉格朗日定理

#### 陪集和划分

设 $G$ 是一个群，设 $H \subseteq G$ 是一个子群。

给定一个元素 $g \in G$，$H$ 关于 $g$ 的**左陪集**是集合：

$gH = \{ gh \mid h \in H \}$。

类似地，$H$ 关于 $g$ 的**右陪集**是：

$Hg = \{ hg \mid h \in H \}$。

通常，左陪集和右陪集是不同的，除非 $H$ 是一个**正规**子群（我们在这里不需要的概念）。

##### 陪集划分群

陪集的一个关键性质是，$H$ 在 $G$ 中的所有左陪集的集合形成了 $G$ 的一个**划分**：

- $G$ 的每个元素都属于某个左陪集。
- 两个陪集要么相同，要么不相交。

也就是说，对于所有 $g_1, g_2 \in G$，要么 $g_1H = g_2H$，要么 $g_1H \cap g_2H = \emptyset$。

我们将 $H$ 在 $G$ 中的所有左陪集的集合表示为：

$G/H = \{ gH \mid g \in G \}$。

不同左陪集的数量称为 $H$ 在 $G$ 中的**指数**，表示为 $[G : H]$。

![image](https://img.learnblockchain.cn/2025/12/04/616105754-e416e6fd-de43-4c0a-8c4c-8a71f87a4be0.png)

##### 陪集之间的双射

一个子群 $H$ 的所有左陪集都具有与 $H$ 相同的大小。事实上，对于任何 $g \in G$，映射：

$\varphi_g : H \to gH \quad \text{定义为} \quad \varphi_g(h) = gh$

是一个**双射**（一个一对一且映上的函数）。

这意味着每个陪集 $gH$ 恰好包含 $|H|$ 个元素，并且没有两个陪集重叠。这种双射对应关系是 **拉格朗日定理** 证明的核心，我们将在接下来陈述和证明它。

#### 拉格朗日定理

设 $G$ 是一个有限群，设 $H \subseteq G$ 是一个子群。 那么：

$|H| \mid |G| \quad \text{和} \quad |G| = [G : H] \cdot |H|$，

其中 $[G : H]$ 表示 $H$ 在 $G$ 中的（左）陪集的数量。

#### 证明

由于 $H$ 是 $G$ 的一个子群，我们可以形成 $H$ 在 $G$ 中的左陪集的集合：

$G/H = \{gH \mid g \in G\}$。

我们现在观察以下事实：

- **不相交并**：$H$ 的陪集形成了 $G$ 的一个**划分**。也就是说，$G$ 的每个元素都恰好属于一个陪集。所以我们可以写成：
$G = \bigsqcup_{i=1}^{[G:H]} g_i H$
对于一些代表 $g_1, \dots, g_{[G:H]} \in G$。

- **陪集的大小相等**：每个左陪集 $gH$ 具有与 $H$ 相同数量的元素。这是因为由 $h \mapsto gh$ 给出的映射 $\varphi_g : H \to gH$ 是一个双射。

- **基数计算**：由于有 $[G : H]$ 个不相交的陪集，每个的大小为 $|H|$，并且它们的并集给出了所有的 $G$，因此：
$|G| = [G : H] \cdot |H|$。

##### 推论：元素的阶

设 $G$ 是一个有限群，其阶为 $n = |G|$，并设 $g \in G$。
考虑由 $g$ 生成的循环子群，表示为 $\langle g \rangle$。

设 $m = |\langle g \rangle|$，根据定义，它是**元素 $g$ 的阶**。

由于 $\langle g \rangle$ 是 $G$ 的一个子群，拉格朗日定理告诉我们，任何子群的阶都能整除群的阶。因此：

$m \mid n$。

换句话说，任何元素的阶都能整除群的阶。

## 有限域上的椭圆曲线

椭圆曲线是现代密码学的核心对象。为了我们的目的，我们对在**有限域**上定义的椭圆曲线感兴趣，特别是它们如何形成与密码协议（以及攻击）相关的结构的**阿贝尔群**。

### 域和有限域

在我们定义椭圆曲线之前，我们需要理解它们在其上定义的代数结构：**域**。

一个**域**是一个集合 $F$，配备了两个运算：

- **加法** $(+)$ 和
- **乘法** $(\cdot)$

它们满足以下性质：

1. **加法群**：$(F, +)$ 是一个阿贝尔群，单位元为 $0$。
2. **乘法群**：$(F \setminus \{0\}, \cdot)$ 是一个阿贝尔群，单位元为 $1$。
3. **分配律**：对于所有 $a, b, c \in F$，我们有
$a \cdot (b + c) = a \cdot b + a \cdot c$。

无限域的著名例子包括有理数 $\mathbb{Q}$、实数 $\mathbb{R}$ 和复数 $\mathbb{C}$。

#### 有限域

一个**有限域**（或 **伽罗瓦域**）是一个具有有限多个元素的域。最常见的有限域是：

- $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$，模素数 $p$ 的整数
- 更一般地，$\mathbb{F}_{p^k}$，$\mathbb{F}_p$ 上的 $k$ 次扩域

在密码学中，我们通常使用 $\mathbb{F}_p$，其中 $p$ 是一个大素数。在这种域中的算术是模 $p$ 进行的：

- 加法：$(a + b) \mod p$
- 乘法：$(a \cdot b) \mod p$
- 逆元存在于模 $p$ 的所有非零元素中

有限域在椭圆曲线密码学和 SNARKs 中至关重要，因为它们为我们提供了一个结构化但有界定的空间来进行计算——非常适合电路和模运算。

### 曲线方程

设 $\mathbb{F}_q$ 是一个具有 $q$ 个元素的有限域（通常对于某个素数 $p$，有 $q = p$，或对于小的 $k$，有 $q = p^k$）。$\mathbb{F}_q$ 上的**椭圆曲线**是方程的解 $(x, y) \in \mathbb{F}_q^2$ 的集合：

$E: \quad y^2 = x^3 + ax + b$，

其中 $a, b \in \mathbb{F}_q$，且曲线是**非奇异的**，意味着：

$4a^3 + 27b^2 \ne 0$。

这个条件确保曲线是平滑的，没有尖点或自相交。

我们还包括一个特殊点，称为**无穷远点**，表示为 $\mathcal{O}$，它在群中充当**单位元**。

![image](https://img.learnblockchain.cn/2025/12/04/616105825-2742e12f-691e-4732-97dd-0abe3636f69f.png)

### 群律

椭圆曲线 $E(\mathbb{F}_q)$ 上的点，连同 $\mathcal{O}$，在几何加法法则下形成一个**阿贝尔群**：

- 给定曲线上两个点 $P$ 和 $Q$，它们的和 $P + Q$ 是通过几何构造定义的（画一条穿过 $P$ 和 $Q$ 的直线，找到它与曲线的第三个交点，并关于 $x$ 轴反射）。
- 单位元是 $\mathcal{O}$。
- 每个点都有一个逆元（它关于 $x$ 轴的反射）。
- 该运算是结合律和交换律的。

加法公式的细节在这里并不重要——只有群律是**良好定义的**，**可高效计算的**，并且赋予曲线点集合一个群结构的这个事实。

### 基域 vs 标量域

当椭圆曲线是在**有限域** $\mathbb{F}_q$ 上定义时，它的点的集合 $E(\mathbb{F}_q)$ 形成一个**有限循环阿贝尔群**。

这意味着存在一个点 $G \in E(\mathbb{F}_q)$，使得重复将 $G$ 加到自身会生成曲线上的所有点。 也就是说：

$E(\mathbb{F}_q) = \langle G \rangle = \{ \mathcal{O}, G, 2G, 3G, \dots, (r-1)G \}$，

对于一些素数 $r$，其中 $rG = \mathcal{O}$，$r$ 是椭圆曲线群的阶。

这种运算——将任何点写成生成元 $G$ 的倍数 $[k]G$——被称为**标量乘法**，标量 $k$ 存在于大小为 $r$ 的有限域中。

这使我们区分了椭圆曲线密码学中的两个域：

- **基域** $\mathbb{F}_q$：这是在其上定义椭圆曲线的域：$(x,y) \in \mathbb{F}_q \times \mathbb{F}_q$。
- **标量域** $\mathbb{F}_r$：这是整数模 $r$ 的域，用于标量乘法 $[k]G$，其中 $k \in \mathbb{F}_r$。

因此，虽然曲线的点存在于 $\mathbb{F}_q$ 中，但将点 $G$ 乘以标量的代数是由 $\mathbb{F}_r$ 中的算术控制的。

当推理密码协议中的**子群结构**、**约束标量范围**和**攻击面**时，这种区分变得至关重要。

## 零知识证明系统中的椭圆曲线

椭圆曲线不仅用于传统的公钥密码学，而且在**零知识证明系统**中也起着至关重要的作用，特别是在基于配对的 SNARKs 中，如 **Groth16** 和 **PLONK**。

### 基于配对的 SNARKs

诸如 **Groth16** 和 **PLONK** 之类的证明系统利用椭圆曲线群之间的 **双线性配对** 来实现：

- **小证明大小**（小至约 200 字节），
- **恒定时间验证**，
- 以及高效的聚合。

一个**配对**是具有以下形式的特殊函数：

$e : G_1 \times G_2 \to G_T$

其中 $G_1$、$G_2$ 和 $G_T$ 是与椭圆曲线（或一对曲线）关联的群。 函数 $e$ 满足：

- **双线性性**：对于所有 $P \in G_1$，$Q \in G_2$ 和 $a, b \in \mathbb{Z}$，$e(aP, bQ) = e(P, Q)^{ab}$，
- **非退化性**：对于某些 $P$，$Q$，$e(P, Q) \ne 1$，
- 和 **效率**：$e$ 可以有效地计算。

#### 示例：Groth16 基于配对的验证方程

在 Groth16 zk-SNARK 协议中，证明者被给予：

- 从可信设置导出的公共参考字符串 (CRS)，
- 一个公共输入向量 $(x_1, \dots, x_\ell)$，
- 一个私有输入向量 $(x_{\ell+1}, \dots, x_m)$。

使用这些数据，证明者计算一个由三个群元素组成的证明：

- $A \in G_1$
- $B \in G_2$
- $C \in G_1$

这些群元素编码对完全赋值 $(x_1, \dots, x_m)$ 的承诺，并证明它满足电路的约束，而无需泄露私有输入。

验证者被给予：

- 验证密钥元素 $[\alpha]_1 \in G_1$、$[\beta]_2 \in G_2$、$[\gamma]_2 \in G_2$ 和 $[\delta]_2 \in G_2$，
- 一组针对每个公共输入 $x_i$ 的承诺 $\{[K_i]_1\}$。

设公共输入线性组合为：

$K_{\text{pub}} = \sum_i x_i [K_i]_1$

如果以下配对等式成立，则验证者接受该证明：

$e(A, B) = e(C, [\delta]_2) \cdot e(K_{\text{pub}}, [\gamma]_2) \cdot e([\alpha]_1, [\beta]_2)$

这里，$e : G_1 \times G_2 \to G_T$ 是一个双线性配对函数。该等式确保证明与电路的 QAP（二次算术程序）表示的一致性以及见证相对于公共输入的正确性。

#### 标量来自哪里

电路中涉及的所有信号——输入、输出和中间信号——都是有限域 $\mathbb{F}_r$ 中的标量，即椭圆曲线的标量域。

当你写：

```circom
signal input a;
signal input b;
signal output c;
c <== a * b;
```

你是在 $\mathbb{F}_r$ 中定义了三个标量上的约束，这些标量成为证明内部结构的一部分。QAP 确保这些值满足电路的逻辑，配对检查确保证明者知道这些值而无需泄露它们。

### BN254 和缺失的范围检查漏洞

零知识证明系统中最广泛使用的椭圆曲线之一是 **BN254**，在以太坊中也称为 **alt\_bn128**。它在基于配对的 SNARKs（如 **Groth16** 和 **PLONK**）中发挥着核心作用，并通过用于快速验证的预编译在以太坊虚拟机中得到原生支持。

#### 曲线概述

BN254 是一条 Barreto-Naehrig (BN) 曲线，定义在 254 位素数域上：

- **基域**：$\mathbb{F}_p$，其中
$p = 21888242871839275222246405745257275088696311157297823662689037894645226208583$。
- **标量域**：$\mathbb{F}_r$，其中
$r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$。

曲线方程以短 Weierstrass 形式书写：

$E: y^2 = x^3 + 3 \mod p$。

BN254 支持高效的双线性配对，并在 zk-SNARK 实现中得到广泛采用。然而，这条曲线并非没有注意事项，尤其是在智能合约等受限环境中。

#### 一个真实的漏洞：ZkDrops 中缺失的无效值范围检查

**a16z 的 ZkDrops**（一个基于 SNARK 的空投系统）中发生了一个安全问题的具体例子，该问题源于对椭圆曲线域大小的处理不当。此漏洞记录在 [0xPARC zk-bug-tracker](https://github.com/0xPARC/zk-bug-tracker) 中。

#### 总结

ZkDrops 要求用户在申领空投时提交一个 **无效值**。这个无效值应该对每个申领都是唯一的确定性值，并作为 256 位整数存储在链上。SNARK 电路使用 254 位的标量域（与 BN254 曲线匹配），因此任何大于此值的值都会在证明生成期间自动模 $r$ 减少。

然而，智能合约**没有**验证无效值是否在标量域范围内。这允许用户提交两个不同的无效值：

$x \text{ 和 } x + r$，

这两个值在 **SNARK 电路中** 模 $r$ 都计算为相同的值，但对于**链上验证者** 来说，它们看起来是不同的，链上验证者将它们视为单独的 256 位整数。

#### 利用

一个恶意用户可以：

1. 使用 $x$ 认领空投，这通过了电路验证并在链上被接受。
2. 使用 $x + r$ 认领**相同的**空投，这在电路中是相同的，但在链上**不同**，因此绕过了无效值检查。

这实际上允许同一个空投**申领**被接受两次。

```solidity
function collectAirdrop(bytes calldata proof, bytes32 nullifierHash) public {
	require(!nullifierSpent[nullifierHash], "Airdrop already redeemed");

uint[] memory pubSignals = new uint[](3);
	pubSignals[0] = uint256(root);
	pubSignals[1] = uint256(nullifierHash);
	pubSignals[2] = uint256(uint160(msg.sender));
	require(verifier.verifyProof(proof, pubSignals), "Proof verification failed");
	nullifierSpent[nullifierHash] = true;
	airdropToken.transfer(msg.sender, amountPerRedemption);
}
```

#### 修复

修复方法是在智能合约中添加一个**范围检查**，以确保无效值位于标量域内：

```solidity
require(uint256(nullifierHash) < SNARK_FIELD ,"Nullifier is not within the field");
```

这保证了链上无效值与 SNARK 电路内部使用的无效值相匹配，从而防止通过模归约进行复制。

## Baby-Jubjub 和子群范围检查攻击

在基于 BN254 的 zk-SNARK 电路中，所有电路内算术运算都在标量域 $\mathbb{F}_r$ 中进行。为了在这些电路中实现椭圆曲线运算，例如 Pedersen 哈希或 EdDSA 签名，我们需要一个定义在 $\mathbb{F}_r$ 上的曲线。这就是 **Baby-Jubjub** 的作用，这是一种专为电路内使用而设计的 twisted Edwards 曲线。

#### 为什么选择 Baby-Jubjub？

Baby-Jubjub 是在 BN254 标量域上定义的：

$r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$

这允许使用 SNARK 电路内的 $\mathbb{F}_r$ 算术来表示和操作 Baby-Jubjub 点。该曲线具有以下结构：

- **形式**：Twisted Edwards,
$ax^2 + y^2 = 1 + dx^2y^2$，
其中 $a = -1$，而 $d$ 是曲线特定的常数。
- **总群阶**：$8 \cdot q$，其中 $q$ 是一个大素数，而 8 是**余因子**。
这意味着 Baby-Jubjub 具有大小为 $q$ 的素数阶子群，但由于余因子，整个曲线具有小的子群。

#### 漏洞：缺失的标量范围检查

在最近对 AvaCloud 的审核中，我们发现在处理 Baby-Jubjub 标量乘法中使用的标量值时存在一个漏洞。具体来说：

Baby-Jubjub 的基点的阶为 $q < r$（BN254 标量字段大小），但标量输入取自完整的标量字段 $\mathbb{F}_r$。 如果没有检查标量是否在正确的范围内（即小于 $q$），则当标量乘以基点时，两个不同的标量可以产生相同的曲线点。

这是因为椭圆曲线标量乘法是模群阶 $q$ 定义的。 因此：

\[k\]G=\[k+n⋅q\]Gfor any n∈Z\[k\]G = \[k + n \cdot q\]G \quad \text{对于任何 } n \in \mathbb{Z}\[k\]G=\[k+n⋅q\]Gfor any n∈Z

这意味着恶意证明者可以提交不同的标量值（例如 $k$ 和 $k+q$），这些值会产生相同的 Baby-Jubjub 点。 这些是**混淆值**：映射到同一点的不同标量。

##### 利用场景

这些混淆值启用了以下攻击：

- 用户可以使用从标量 $k$ 导出的 Baby-Jubjub 公钥**存入资金**。
- 稍后，同一用户可以使用标量 $k+q$ 生成第二个 SNARK 证明，该证明仍然映射到相同的 Baby-Jubjub 点。
- 从电路的角度来看，两个标量都是有效的：它们产生相同的群元素。
- 从应用程序的角度来看，两个存款/取款密钥看起来**不同**，因此系统**允许在新的但冲突的密钥下进行第二次取款**。

通过利用缺少标量范围检查的漏洞，这实际上允许用户提取**超过他们已存入的资金**。

有关 Baby-Jubjub 标量混淆漏洞的更多详细信息，请参见 [此处](https://github.com/Hexens/Smart-Contract-Review-Public-Reports/blob/main/avacloud-etrapay-audit-jan25(Final).pdf) 的完整审核报告。

### 结论

当一个加密系统无法正确约束其操作的值时，就会出现子群攻击——无论这些值是标量、群元素还是曲线点。正如我们所见，即使是像缺少范围检查这样的简单代数疏忽也可能产生严重的后果。

- 在 **BN254 无效值漏洞**中，254 位标量字段和 256 位链上整数之间的不匹配导致了证明重用和空投双重申领。
- 在 **Baby-Jubjub 标量混淆问题**中，未能将标量约束到正确的子群允许恶意用户提取超过他们存入的资金。

这些错误源于相同的基本原理：如果一个值存在于**比预期更大的结构中**，并且没有检查来强制执行正确的域，那么就会产生意想不到的行为。

在零知识密码学中，由于跨不同数学领域（群、域和曲线）证明和验证计算的复杂性，这些问题尤其棘手。 仔细验证和了解群结构——特别是**阶**、**余因子** 和 **子群** ——对于确保可靠性至关重要。

>- 原文链接： [hexens.io/blog/subgroup-...](https://hexens.io/blog/subgroup-attack-exploits)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

在深入研究密码电路中缺失的范围检查攻击之前，有必要了解什么是群，它们的规模（阶）如何表现，以及为什么这很重要。

群、循环结构和拉格朗日定理

群和子群

一个群 $G$ 是一个集合，带有一个二元运算（例如，加法或乘法），满足以下性质：

封闭性：对于任何 $a, b \in G$，我们有 $ab \in G$。
结合性：$(ab)c = a(bc)$ 对于所有 $a, b, c \in G$。
单位元：存在一个元素 $e \in G$，使得 $ae = ea = a$ 对于所有 $a \in G$。
逆元：对于每个 $a \in G$，存在一个逆元 $a^{-1} \in G$，使得 $aa^{-1} = a^{-1}a = e$。

一个子集 $H \subseteq G$ 被称为子群，如果它本身在从 $G$ 继承的运算下也是一个群。

群的阶，元素的阶

群的阶 $G$，表示为 $|G|$，是群中元素的数量。如果群有无限多个元素，则阶也可能是无限的。

元素的阶 $g \in G$ 是最小的正整数 $n$，使得 $g^n = e$，其中 $e$ 是群的单位元。如果不存在这样的 $n$，我们说 $g$ 的阶是无限的。

生成元和循环群

群 $G$ 的一个生成集合（或生成元集合）是一个子集 $S = {s_1, s_2, \dots, s_k} \subseteq G$，使得 $G$ 的每个元素都可以写成来自 $S$ 的元素及其逆元的有限乘积。

也就是说，对于每个 $g \in G$，存在一个索引序列 $i_1, i_2, \dots, i_m \in {1, \dots, k}$ 和指数 $\epsilon_1, \epsilon_2, \dots, \epsilon_m \in {\pm 1}$，使得：

$g = s_{i_1}^{\epsilon_1} s_{i_2}^{\epsilon_2} \cdots s_{i_m}^{\epsilon_m}$。

由 $S$ 生成的群表示为：

$G = \langle S \rangle = \left{ s_{i_1}^{\epsilon_1} s_{i_2}^{\epsilon_2} \cdots s_{i_m}^{\epsilon_m} \mid m \in \mathbb{N}, i_j \in {1, \dots, k}, \epsilon_j \in {\pm 1} \right}$。

如果一个群 $G$ 有一个由单个元素 $g$ 组成的生成集合，即 $G = \langle g \rangle$，我们说 $G$ 是循环群。

陪集和拉格朗日定理

陪集和划分

设 $G$ 是一个群，设 $H \subseteq G$ 是一个子群。

给定一个元素 $g \in G$，$H$ 关于 $g$ 的左陪集是集合：

$gH = { gh \mid h \in H }$。

类似地，$H$ 关于 $g$ 的右陪集是：

$Hg = { hg \mid h \in H }$。

通常，左陪集和右陪集是不同的，除非 $H$ 是一个正规子群（我们在这里不需要的概念）。

陪集划分群

陪集的一个关键性质是，$H$ 在 $G$ 中的所有左陪集的集合形成了 $G$ 的一个划分：

$G$ 的每个元素都属于某个左陪集。
两个陪集要么相同，要么不相交。

也就是说，对于所有 $g_1, g_2 \in G$，要么 $g_1H = g_2H$，要么 $g_1H \cap g_2H = \emptyset$。

我们将 $H$ 在 $G$ 中的所有左陪集的集合表示为：

$G/H = { gH \mid g \in G }$。

不同左陪集的数量称为 $H$ 在 $G$ 中的指数，表示为 $[G : H]$。

陪集之间的双射

一个子群 $H$ 的所有左陪集都具有与 $H$ 相同的大小。事实上，对于任何 $g \in G$，映射：

$\varphi_g : H \to gH \quad \text{定义为} \quad \varphi_g(h) = gh$

是一个双射（一个一对一且映上的函数）。

这意味着每个陪集 $gH$ 恰好包含 $|H|$ 个元素，并且没有两个陪集重叠。这种双射对应关系是 拉格朗日定理 证明的核心，我们将在接下来陈述和证明它。

拉格朗日定理

设 $G$ 是一个有限群，设 $H \subseteq G$ 是一个子群。那么：

$|H| \mid |G| \quad \text{和} \quad |G| = [G : H] \cdot |H|$，

其中 $[G : H]$ 表示 $H$ 在 $G$ 中的（左）陪集的数量。

证明

由于 $H$ 是 $G$ 的一个子群，我们可以形成 $H$ 在 $G$ 中的左陪集的集合：

$G/H = {gH \mid g \in G}$。

我们现在观察以下事实：

不相交并：$H$ 的陪集形成了 $G$ 的一个划分。也就是说，$G$ 的每个元素都恰好属于一个陪集。所以我们可以写成： $G = \bigsqcup_{i=1}^{[G:H]} g_i H$ 对于一些代表 $g_1, \dots, g_{[G:H]} \in G$。
陪集的大小相等：每个左陪集 $gH$ 具有与 $H$ 相同数量的元素。这是因为由 $h \mapsto gh$ 给出的映射 $\varphi_g : H \to gH$ 是一个双射。
基数计算：由于有 $[G : H]$ 个不相交的陪集，每个的大小为 $|H|$，并且它们的并集给出了所有的 $G$，因此： $|G| = [G : H] \cdot |H|$。

推论：元素的阶

设 $G$ 是一个有限群，其阶为 $n = |G|$，并设 $g \in G$。考虑由 $g$ 生成的循环子群，表示为 $\langle g \rangle$。

设 $m = |\langle g \rangle|$，根据定义，它是元素 $g$ 的阶。

由于 $\langle g \rangle$ 是 $G$ 的一个子群，拉格朗日定理告诉我们，任何子群的阶都能整除群的阶。因此：

$m \mid n$。

换句话说，任何元素的阶都能整除群的阶。

有限域上的椭圆曲线

椭圆曲线是现代密码学的核心对象。为了我们的目的，我们对在有限域上定义的椭圆曲线感兴趣，特别是它们如何形成与密码协议（以及攻击）相关的结构的阿贝尔群。

域和有限域

在我们定义椭圆曲线之前，我们需要理解它们在其上定义的代数结构：域。

一个域是一个集合 $F$，配备了两个运算：

加法 $(+)$ 和
乘法 $(\cdot)$

它们满足以下性质：

加法群：$(F, +)$ 是一个阿贝尔群，单位元为 $0$。
乘法群：$(F \setminus {0}, \cdot)$ 是一个阿贝尔群，单位元为 $1$。
分配律：对于所有 $a, b, c \in F$，我们有 $a \cdot (b + c) = a \cdot b + a \cdot c$。

无限域的著名例子包括有理数 $\mathbb{Q}$、实数 $\mathbb{R}$ 和复数 $\mathbb{C}$。

有限域

一个有限域（或 伽罗瓦域）是一个具有有限多个元素的域。最常见的有限域是：

$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$，模素数 $p$ 的整数
更一般地，$\mathbb{F}_{p^k}$，$\mathbb{F}_p$ 上的 $k$ 次扩域

在密码学中，我们通常使用 $\mathbb{F}_p$，其中 $p$ 是一个大素数。在这种域中的算术是模 $p$ 进行的：

加法：$(a + b) \mod p$
乘法：$(a \cdot b) \mod p$
逆元存在于模 $p$ 的所有非零元素中

有限域在椭圆曲线密码学和 SNARKs 中至关重要，因为它们为我们提供了一个结构化但有界定的空间来进行计算——非常适合电路和模运算。

曲线方程

设 $\mathbb{F}_q$ 是一个具有 $q$ 个元素的有限域（通常对于某个素数 $p$，有 $q = p$，或对于小的 $k$，有 $q = p^k$）。$\mathbb{F}_q$ 上的椭圆曲线是方程的解 $(x, y) \in \mathbb{F}_q^2$ 的集合：

$E: \quad y^2 = x^3 + ax + b$，

其中 $a, b \in \mathbb{F}_q$，且曲线是非奇异的，意味着：

$4a^3 + 27b^2 \ne 0$。

这个条件确保曲线是平滑的，没有尖点或自相交。

我们还包括一个特殊点，称为无穷远点，表示为 $\mathcal{O}$，它在群中充当单位元。

群律

椭圆曲线 $E(\mathbb{F}_q)$ 上的点，连同 $\mathcal{O}$，在几何加法法则下形成一个阿贝尔群：

给定曲线上两个点 $P$ 和 $Q$，它们的和 $P + Q$ 是通过几何构造定义的（画一条穿过 $P$ 和 $Q$ 的直线，找到它与曲线的第三个交点，并关于 $x$ 轴反射）。
单位元是 $\mathcal{O}$。
每个点都有一个逆元（它关于 $x$ 轴的反射）。
该运算是结合律和交换律的。

加法公式的细节在这里并不重要——只有群律是良好定义的，可高效计算的，并且赋予曲线点集合一个群结构的这个事实。

基域 vs 标量域

当椭圆曲线是在有限域 $\mathbb{F}_q$ 上定义时，它的点的集合 $E(\mathbb{F}_q)$ 形成一个有限循环阿贝尔群。

这意味着存在一个点 $G \in E(\mathbb{F}_q)$，使得重复将 $G$ 加到自身会生成曲线上的所有点。也就是说：

$E(\mathbb{F}_q) = \langle G \rangle = { \mathcal{O}, G, 2G, 3G, \dots, (r-1)G }$，

对于一些素数 $r$，其中 $rG = \mathcal{O}$，$r$ 是椭圆曲线群的阶。

这种运算——将任何点写成生成元 $G$ 的倍数 $[k]G$——被称为标量乘法，标量 $k$ 存在于大小为 $r$ 的有限域中。

这使我们区分了椭圆曲线密码学中的两个域：

基域 $\mathbb{F}_q$：这是在其上定义椭圆曲线的域：$(x,y) \in \mathbb{F}_q \times \mathbb{F}_q$。
标量域 $\mathbb{F}_r$：这是整数模 $r$ 的域，用于标量乘法 $[k]G$，其中 $k \in \mathbb{F}_r$。

因此，虽然曲线的点存在于 $\mathbb{F}_q$ 中，但将点 $G$ 乘以标量的代数是由 $\mathbb{F}_r$ 中的算术控制的。

当推理密码协议中的子群结构、约束标量范围和攻击面时，这种区分变得至关重要。

零知识证明系统中的椭圆曲线

椭圆曲线不仅用于传统的公钥密码学，而且在零知识证明系统中也起着至关重要的作用，特别是在基于配对的 SNARKs 中，如 Groth16 和 PLONK。

基于配对的 SNARKs

诸如 Groth16 和 PLONK 之类的证明系统利用椭圆曲线群之间的 双线性配对 来实现：

小证明大小（小至约 200 字节），
恒定时间验证，
以及高效的聚合。

一个配对是具有以下形式的特殊函数：

$e : G_1 \times G_2 \to G_T$

其中 $G_1$、$G_2$ 和 $G_T$ 是与椭圆曲线（或一对曲线）关联的群。函数 $e$ 满足：

双线性性：对于所有 $P \in G_1$，$Q \in G_2$ 和 $a, b \in \mathbb{Z}$，$e(aP, bQ) = e(P, Q)^{ab}$，
非退化性：对于某些 $P$，$Q$，$e(P, Q) \ne 1$，
和效率：$e$ 可以有效地计算。

示例：Groth16 基于配对的验证方程

在 Groth16 zk-SNARK 协议中，证明者被给予：

从可信设置导出的公共参考字符串 (CRS)，
一个公共输入向量 $(x_1, \dots, x_\ell)$，
一个私有输入向量 $(x_{\ell+1}, \dots, x_m)$。

使用这些数据，证明者计算一个由三个群元素组成的证明：

$A \in G_1$
$B \in G_2$
$C \in G_1$

这些群元素编码对完全赋值 $(x_1, \dots, x_m)$ 的承诺，并证明它满足电路的约束，而无需泄露私有输入。

验证者被给予：

验证密钥元素 $[\alpha]_1 \in G_1$、$[\beta]_2 \in G_2$、$[\gamma]_2 \in G_2$ 和 $[\delta]_2 \in G_2$，
一组针对每个公共输入 $x_i$ 的承诺 ${[K_i]_1}$。

设公共输入线性组合为：

$K_{\text{pub}} = \sum_i x_i [K_i]_1$

如果以下配对等式成立，则验证者接受该证明：

$e(A, B) = e(C, [\delta]2) \cdot e(K{\text{pub}}, [\gamma]_2) \cdot e([\alpha]_1, [\beta]_2)$

这里，$e : G_1 \times G_2 \to G_T$ 是一个双线性配对函数。该等式确保证明与电路的 QAP（二次算术程序）表示的一致性以及见证相对于公共输入的正确性。

标量来自哪里

电路中涉及的所有信号——输入、输出和中间信号——都是有限域 $\mathbb{F}_r$ 中的标量，即椭圆曲线的标量域。

当你写：

signal input a;
signal input b;
signal output c;
c &lt;== a * b;

BN254 和缺失的范围检查漏洞

零知识证明系统中最广泛使用的椭圆曲线之一是 BN254，在以太坊中也称为 alt_bn128。它在基于配对的 SNARKs（如 Groth16 和 PLONK）中发挥着核心作用，并通过用于快速验证的预编译在以太坊虚拟机中得到原生支持。

曲线概述

BN254 是一条 Barreto-Naehrig (BN) 曲线，定义在 254 位素数域上：

基域：$\mathbb{F}_p$，其中 $p = 21888242871839275222246405745257275088696311157297823662689037894645226208583$。
标量域：$\mathbb{F}_r$，其中 $r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$。

曲线方程以短 Weierstrass 形式书写：

$E: y^2 = x^3 + 3 \mod p$。

BN254 支持高效的双线性配对，并在 zk-SNARK 实现中得到广泛采用。然而，这条曲线并非没有注意事项，尤其是在智能合约等受限环境中。

一个真实的漏洞：ZkDrops 中缺失的无效值范围检查

a16z 的 ZkDrops（一个基于 SNARK 的空投系统）中发生了一个安全问题的具体例子，该问题源于对椭圆曲线域大小的处理不当。此漏洞记录在 0xPARC zk-bug-tracker 中。

总结

ZkDrops 要求用户在申领空投时提交一个 无效值。这个无效值应该对每个申领都是唯一的确定性值，并作为 256 位整数存储在链上。SNARK 电路使用 254 位的标量域（与 BN254 曲线匹配），因此任何大于此值的值都会在证明生成期间自动模 $r$ 减少。

然而，智能合约没有验证无效值是否在标量域范围内。这允许用户提交两个不同的无效值：

$x \text{ 和 } x + r$，

这两个值在 SNARK 电路中 模 $r$ 都计算为相同的值，但对于链上验证者 来说，它们看起来是不同的，链上验证者将它们视为单独的 256 位整数。

利用

一个恶意用户可以：

使用 $x$ 认领空投，这通过了电路验证并在链上被接受。
使用 $x + r$ 认领相同的空投，这在电路中是相同的，但在链上不同，因此绕过了无效值检查。

这实际上允许同一个空投申领被接受两次。

function collectAirdrop(bytes calldata proof, bytes32 nullifierHash) public {
	require(!nullifierSpent[nullifierHash], "Airdrop already redeemed");

	uint[] memory pubSignals = new uint[](3);
	pubSignals[0] = uint256(root);
	pubSignals[1] = uint256(nullifierHash);
	pubSignals[2] = uint256(uint160(msg.sender));
	require(verifier.verifyProof(proof, pubSignals), "Proof verification failed");
	nullifierSpent[nullifierHash] = true;
	airdropToken.transfer(msg.sender, amountPerRedemption);
}

修复

修复方法是在智能合约中添加一个范围检查，以确保无效值位于标量域内：

require(uint256(nullifierHash) &lt; SNARK_FIELD ,"Nullifier is not within the field");

这保证了链上无效值与 SNARK 电路内部使用的无效值相匹配，从而防止通过模归约进行复制。

Baby-Jubjub 和子群范围检查攻击

在基于 BN254 的 zk-SNARK 电路中，所有电路内算术运算都在标量域 $\mathbb{F}_r$ 中进行。为了在这些电路中实现椭圆曲线运算，例如 Pedersen 哈希或 EdDSA 签名，我们需要一个定义在 $\mathbb{F}_r$ 上的曲线。这就是 Baby-Jubjub 的作用，这是一种专为电路内使用而设计的 twisted Edwards 曲线。

为什么选择 Baby-Jubjub？

Baby-Jubjub 是在 BN254 标量域上定义的：

$r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$

这允许使用 SNARK 电路内的 $\mathbb{F}_r$ 算术来表示和操作 Baby-Jubjub 点。该曲线具有以下结构：

形式：Twisted Edwards, $ax^2 + y^2 = 1 + dx^2y^2$，其中 $a = -1$，而 $d$ 是曲线特定的常数。
总群阶：$8 \cdot q$，其中 $q$ 是一个大素数，而 8 是余因子。这意味着 Baby-Jubjub 具有大小为 $q$ 的素数阶子群，但由于余因子，整个曲线具有小的子群。

漏洞：缺失的标量范围检查

在最近对 AvaCloud 的审核中，我们发现在处理 Baby-Jubjub 标量乘法中使用的标量值时存在一个漏洞。具体来说：

Baby-Jubjub 的基点的阶为 $q < r$（BN254 标量字段大小），但标量输入取自完整的标量字段 $\mathbb{F}_r$。如果没有检查标量是否在正确的范围内（即小于 $q$），则当标量乘以基点时，两个不同的标量可以产生相同的曲线点。

这是因为椭圆曲线标量乘法是模群阶 $q$ 定义的。因此：

[k]G=[k+n⋅q]Gfor any n∈Z[k]G = [k + n \cdot q]G \quad \text{对于任何 } n \in \mathbb{Z}[k]G=[k+n⋅q]Gfor any n∈Z

这意味着恶意证明者可以提交不同的标量值（例如 $k$ 和 $k+q$），这些值会产生相同的 Baby-Jubjub 点。这些是混淆值：映射到同一点的不同标量。

利用场景

这些混淆值启用了以下攻击：

用户可以使用从标量 $k$ 导出的 Baby-Jubjub 公钥存入资金。
稍后，同一用户可以使用标量 $k+q$ 生成第二个 SNARK 证明，该证明仍然映射到相同的 Baby-Jubjub 点。
从电路的角度来看，两个标量都是有效的：它们产生相同的群元素。
从应用程序的角度来看，两个存款/取款密钥看起来不同，因此系统允许在新的但冲突的密钥下进行第二次取款。

通过利用缺少标量范围检查的漏洞，这实际上允许用户提取超过他们已存入的资金。

有关 Baby-Jubjub 标量混淆漏洞的更多详细信息，请参见此处的完整审核报告。

结论

在 BN254 无效值漏洞中，254 位标量字段和 256 位链上整数之间的不匹配导致了证明重用和空投双重申领。
在 Baby-Jubjub 标量混淆问题中，未能将标量约束到正确的子群允许恶意用户提取超过他们存入的资金。

这些错误源于相同的基本原理：如果一个值存在于比预期更大的结构中，并且没有检查来强制执行正确的域，那么就会产生意想不到的行为。

在零知识密码学中，由于跨不同数学领域（群、域和曲线）证明和验证计算的复杂性，这些问题尤其棘手。仔细验证和了解群结构——特别是阶、余因子 和子群 ——对于确保可靠性至关重要。

原文链接： hexens.io/blog/subgroup-...

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

0 条评论

群、循环结构和拉格朗日定理

群和子群

群的阶，元素的阶

生成元和循环群

陪集和拉格朗日定理

陪集和划分

陪集划分群

陪集之间的双射

拉格朗日定理

证明

推论：元素的阶

有限域上的椭圆曲线

域和有限域

有限域

曲线方程

群律

基域 vs 标量域

零知识证明系统中的椭圆曲线

基于配对的 SNARKs

示例：Groth16 基于配对的验证方程

标量来自哪里

BN254 和缺失的范围检查漏洞

曲线概述

一个真实的漏洞：ZkDrops 中缺失的无效值范围检查

总结

利用

修复

Baby-Jubjub 和子群范围检查攻击

为什么选择 Baby-Jubjub？

漏洞：缺失的标量范围检查

利用场景

结论

相关文章

0 条评论