【论文速递】指数运算证明：提升代数语句的证明者效率

概述

背景与动机

当前多种 SNARK 构造高度优化了对哈希前像的证明效率，但当需要证明如  之类的大域指数运算时，必须通过非本域算术（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），用于高效表达群指数运算：

• 当给定循环群  与指数集合  时，EXP 门接受输入  并输出 ，满足：

• 在离散对数安全群的设定下，取 、，定义四种关系：

  其中
• 
  

这些定义为后续构建各种代数关系提供了基础。

Hash-committed Commit-and-Prove (HCP) 框架

在此基础上，作者构建了一个Hash-committed Commit-and-Prove 证明系统：

1. 对每个 EXP 门的输出  使用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，用于证明以下两类关键关系：

• 离散对数关系：证明  且 
• RSA 指数关系：证明  且 

1. 通用协议框架

1. Setup

• 运行内部 SNARK ，生成公共参数 crs。

2. 输入定义  :

• 公共输入：crs, P, h（或 (P,h)、(P,Q,h)，视关系而定）
• 私有输入：Q, x, r，其中  用于哈希承诺。

3. 承诺 (Commitment)

• Prover 随机选取掩码 k ← F_p、随机数 r_k ← {0,1}^λ，计算

  并将 (h_k, A) 发送给 Verifier。

4. 质询 (Challenge)

• Verifier 随机取比特 c ← {0,1}，并发送给 Prover。

5. 响应 (Response)

• 若 c=0，Prover 发送 (z=k, r_k)；
• 若 c=1，Prover 计算 z = k + x (mod p)，并运行内部 SNARK 证明：

  其中 T = A ◦ Q 为群运算结果。

6. 验证 (Verification)

• 若 c=0，验证
• 若 c=1，验证
• Verifier 计算 T' = P^z 并根据 c 检查：

2. 离散对数 Sigma AoK 

• 目标关系
• 内部 SNARK 关系

3. RSA Sigma AoK Π₁^{rsa}

• 目标关系

4. 并行与专项优化

• 并行重复：对单次知识可靠性错误率  的 Sigma AoK 进行并行执行，可将错误率降至 。
• 结构化优化：针对特定 EXP 门（如  和 ），省略部分重复验证步骤，进一步提升证明效率。

性能评估

实验证明，相较于直接在 SNARK 电路中完成指数运算的 NNA 方法（需数百至上千次群加法/点倍或大整数乘法），本方法在 离散对数群 上将昂贵运算次数减少约 10 倍，在 RSA 群 上减少数十倍。同时，整体证明大小保持在数百字节量级，验证开销与传统 SNARK 技术相当。

结论与展望

本文提出的 带指数门算术电路模型 与 HCP 框架，通过将大域指数运算“脱圈”并借助专门 Sigma 协议大幅提升了 SNARK 的证明者效率，兼容离散对数与 RSA 场景。未来可进一步探索：

• 将该框架与递归证明结合，实现更大规模语句的高效压缩；

• 在更丰富的代数结构（如配对群、多变量模  运算）中推广 EXP 门与 AoK 协议设计。