## 概述
https://eprint.iacr.org/2025/941
> 本论文针对在小素域上构造的 zkSNARKs （例如 Goldilocks 域、小梅森素数域及二进制塔域）在证明**代数语句**（如 RSA 或 ECDSA 签名验证）时效率低下的问题，提出了**带指数门的算术电路模型**及基于该模型的**Hash-committed Commit-and-Prove (HCP)** 框架，有效地将大数和椭圆曲线指数运算“脱出”SNARK 电路，转而使用仅与安全参数相关的轻量级哈希运算，大幅度提升证明者效率，同时维持同等水平的证明大小与验算开销 。
>
> 通过在 SNARK 之外使用专门设计的 Sigma 协议（称为 **Sigma Argument of Knowledge**）来证明指数门的正确性，仅需在电路内验证常数次的群运算与若干 zk-friendly 哈希函数（如 Poseidon）应用，相比将完整指数运算映射为数百乃至上千次原生约束，证明者速度提升近一个数量级 。
![[CleanShot 2025-05-24 at
[email protected]]]
## 背景与动机
当前多种 SNARK 构造高度优化了对**哈希前像**的证明效率，但当需要证明如 $g^x=y$ 之类的大域指数运算时，必须通过**非本域算术**（Non-Native Arithmetic, NNA）将大域运算拆解为小素域上的加法与乘法，这会引入巨量约束，严重拖慢证明者速度。 尽管已有 xJsnark、CRT 方法、Windowed 技术以及Commit-and-Prove(CP)-SNARK 方法(使用Pederson Commitment) 等优化手段，但在架构最佳化、兼顾通用性与性能方面仍有显著提升空间。
- Kosba, A.E., Papamanthou, C., Shi, E.: xJsnark: A framework for efficient verifiable computation. In: 2018 IEEE Symposium on Security and Privacy. pp. 944961. IEEE Computer Society Press, San Francisco, CA, USA (May 21–23, 2018). https://doi.org/10.1109/SP.2018.00018
- JkY: Non-native field arithmetic. https://hackmd.io/@JkY-zACaSqerTtn_UwFjKg/SJZw6x75o (2023)
- Zakharov, D., Kurbatov, O., Bista, M., Bist, B.: Optimizing big integer multiplication on bitcoin: Introducing w-windowed approach. Cryptology ePrint Archive, Report 2024/1236 (2024), https://eprint.iacr.org/2024/1236
- Orrù, M., Kadianakis, G., Maller, M., Zaverucha, G.: Beyond the circuit: How to minimize foreign arithmetic in ZKP circuits. IACR Commun. Cryptol. 2(1), 23 (2025). https://doi.org/10.62056/AN-4C3C2H, https://doi.org/10.62056/an-4c3c2h
## EXP 门与 HCP 框架
### EXP 门的定义
论文引入了一个新的电路元素——**指数门（EXP gate）**，用于高效表达群指数运算：
- 当给定循环群 $(G, \circ)$ 与指数集合 $I$ 时，EXP 门接受输入 $(g_1, x)$ 并输出 $g_2$，满足：
$
g_2 \;=\; g_1^x\;.
$
- 在离散对数安全群的设定下，取 $G = G_p$、$I = \mathbb{F}_p$，定义四种关系：
$
R^{dl}_i \;=\; \{\,st_i : g_1^x = g_2\},\quad i \in \{0,1,2,3\},
$
其中
- $st_0 = ((g_1, g_2); x)$
- $st_1 = (g_1; (g_2, x))$
- $st_2 = (x; (g_1, g_2))$
- $st_3 = (\emptyset; (g_1, g_2, x))$
![[CleanShot 2025-05-24 at
[email protected]]]
这些定义为后续构建各种代数关系提供了基础。
### Hash-committed Commit-and-Prove (HCP) 框架
在此基础上，作者构建了一个**Hash-committed Commit-and-Prove** 证明系统：
1. 对每个 EXP 门的输出 $g_2$ 使用**zk-friendly 哈希函数**（如 Poseidon）生成承诺。
2. 在 Sigma 协议层面，通过**Sigma Argument of Knowledge (AoK)** 证明对数知识或 RSA 指数知识。
3. 在 SNARK 电路内仅需验证哈希承诺一致性和常数次数的群运算证明，而无需展开完整指数计算 。
## Sigma Argument of Knowledge 协议设计
本节我们详细介绍用于高效证明 EXP 门正确性的 **Sigma Argument of Knowledge (Sigma AoK)** 协议。Sigma AoK 是一种 **三轮公开抛币**（3-move public-coin）交互式协议，结合了经典 Sigma 协议与内部 zkSNARK，用于证明以下两类关键关系：
- **离散对数关系** $R^{dl}_i$：证明 $Q = P^x$ 且 $h = H(Q, x, r)$
- **RSA 指数关系** $R^{rsa}_j$：证明 $Q = P^x$ 且 $h = H(P, Q, r)$
### 1. 通用协议框架
1. **Setup**
- 运行内部 SNARK $Π_\text{int}.Setup(1^λ, R^{int})$，生成公共参数 `crs`。
1. **输入定义** :
- **公共输入**：`crs, P, h`（或 `(P,h)`、`(P,Q,h)`，视关系而定）
- **私有输入**：`Q, x, r`，其中 $r \in \{0,1\}^\lambda$ 用于哈希承诺。
3. **承诺 (Commitment)**
- Prover 随机选取掩码 `k ← F_p`、随机数 `r_k ← {0,1}^λ`，计算
$
A = P^k, \quad h_k = H(A, k, r_k),
$
并将 `(h_k, A)` 发送给 Verifier。
1. **质询 (Challenge)**
- Verifier 随机取比特 `c ← {0,1}`，并发送给 Prover。
1. **响应 (Response)**
- 若 `c=0`，Prover 发送 `(z=k, r_k)`；
- 若 `c=1`，Prover 计算 `z = k + x (mod p)`，并运行内部 SNARK 证明：
$
\pi_\text{int} \leftarrow Π_\text{int}.P(crs,\,h,\,h_k,\,z,\,T;\,(Q,x,k,A,r,r_k)),
$
其中 `T = A ◦ Q` 为群运算结果。
1. **验证 (Verification)**
- Verifier 计算 `T' = P^z` 并根据 `c` 检查：
- 若 `c=0`，验证
$
h_k \overset{?}{=} H(T',\,z,\,r_k).
$
- 若 `c=1`，验证
$
Π_\text{int}.V(crs,\,h,\,h_k,\,z,\,T',\,\pi_\text{int}) \overset{?}{=} 1.
$
### 2. 离散对数 Sigma AoK $\Pi_1^{dl}$
- **目标关系**
$
R^{dl}_1 := \{\, (P,h;\,(Q,x,r)) \mid Q = P^x \;\wedge\; h = H(Q, x, r)\}.
$
- **内部 SNARK 关系**
$
R^{int}_5 := \{\, (h,h_k,Z,T;\,(P,Q,K,A,r,r_k)) :
h = H(P,Q,r)\;\wedge\;
h_k = H(K,A,r_k)\;\wedge\;
Z = K ◦ P\;\wedge\;
T = A ◦ Q \}.
$
![[CleanShot 2025-05-24 at
[email protected]]]
### 3. RSA Sigma AoK Π₁^{rsa}
- **目标关系**
$
R^{rsa}_1 := \{\, (x,h;\,(P,Q,r)) \mid Q = P^x \;\wedge\; h = H(P,Q,r)\}.
$
![[CleanShot 2025-05-24 at
[email protected]]]
### 4. 并行与专项优化
- **并行重复**：对单次知识可靠性错误率 $1/2$ 的 Sigma AoK 进行并行执行，可将错误率降至 $2^{-κ}$。
- **结构化优化**：针对特定 EXP 门（如 $R^{dl}_1$ 和 $R^{rsa}_1$），省略部分重复验证步骤，进一步提升证明效率。
## 性能评估
实验证明，相较于直接在 SNARK 电路中完成指数运算的 NNA 方法（需数百至上千次群加法/点倍或大整数乘法），本方法在 **离散对数群** 上将昂贵运算次数减少约 **10 倍**，在 **RSA 群** 上减少数十倍。同时，整体证明大小保持在数百字节量级，验证开销与传统 SNARK 技术相当。
![[CleanShot 2025-05-24 at
[email protected]]]
## 结论与展望
本文提出的 **带指数门算术电路模型** 与 **HCP 框架**，通过将大域指数运算“脱圈”并借助专门 Sigma 协议大幅提升了 SNARK 的证明者效率，兼容离散对数与 RSA 场景。未来可进一步探索：
- 将该框架与递归证明结合，实现更大规模语句的高效压缩；
- 在更丰富的代数结构（如配对群、多变量模 $n$ 运算）中推广 EXP 门与 AoK 协议设计。