JesseQ: 面向任意域上电路的高效零知识证明系统

我将简单介绍我们最近发表在 IEEE S&P(Oakland) 2025 上的文章 JesseQ: Efficient Zero-Knowledge Proofs for Circuits over Any Field

基于向量不经意线性评估（VOLE）的零知识证明（ZKPs）近期因其高效性和可扩展性获得显著关注。最新实现方案每秒可证明数千万逻辑门，并能平滑扩展至万亿级逻辑门验证。相较于现有简洁零知识证明系统，这类方案显著降低了证明方的计算开销。具体而言，工作LPZKv2表明在验证百万级逻辑门时，基于VOLE的ZKPs比其他方案（如Groth16、Virgo、Cerberus）快3-10倍。

基于VOLE的ZKPs性能如下表所示。在该框架下，零知识证明协议（LPZK）首次实现大域算术电路中每个逻辑门约1个通信元素的里程碑，后续QuickSilver将其改进为支持任意数域。另一改进方向LPZKv2则将通信量减半并降低计算成本。这些方案的通信复杂度与电路规模呈线性关系。AntMan首次实现  的亚线性通信构造（  为大域算术电路规模），虽然计算成本仍保持高效，但引入了  的开销。在计算效率方面，QuickSilver和LPZKv2分别在布尔电路和大域算术电路中表现最优。值得注意的是，支持任意数域的VOLE-ZKPs与仅适用于大域的方案存在显著性能差异。

另一研究方向针对特定结构电路（如表示析取式  的  分支子电路）进行优化。最先进的Batchman实现了批量析取式的亚线性通信和计算，其框架可通过黑盒方式实例化基于VOLE的ZKPs来处理乘法运算。

• 本表格将我们的工作（JQv1 和 JQv2）与先前相关工作的证明者成本进行了对比，数据来源包括他们研究中报告的结果以及在相同硬件上运行的实验（AntMan 除外，其使用了更高配置的实例）。

• Size 表示每个乘法门需要发送的域元素数量（AntMan 除外，其具有亚线性通信特性）。
  Speed 表示在无限带宽和单线程条件下每秒可执行的乘法门数量（AntMan除外，其使用1 Gbps网络带宽并在四线程下运行）。

• 此外，其他工作将算术电路的素数设为 ，而由于同态加密的特性，AntMan 要求将  设为更小的素数 。

JesseQ的贡献

我们提出JesseQ（JQv1与JQv2）——一种基于VOLE的常数轮零知识证明新方案，适用于预处理模型中任意数域上的电路（与LPZKv2框架相同）。其中JQv1支持任意结构电路，JQv2针对分层电路优化，二者均具备更优的在线阶段性能 （和LPZKv2协议一样，在预处理全部完成后，我们报告已知见证值（witness）时生成证明的在线阶段成本）。如既往研究，我们重点分析证明方效率：对于任意数域电路，JQv1/JQv2的证明方与验证方计算量均优于现有最优方案。唯一例外是：在大域电路场景下，JQv1验证方每个乘法门需比LPZKv2多执行一次乘法运算。但我们的协议仍通过全数域兼容性保持整体优势。

基于VOLE的零知识证明

我们首先回顾先前工作的相关背景，再对协议的技术概要进行说明。

消息认证码与VOLE

大多数基于VOLE的零知识证明将VOLE关联性用作信息论消息认证码（IT-MAC，使得证明者（Prover）能够向验证者（Verifier）提交线值承诺。
设  为有限域，  是验证者已知的全局密钥，  是证明者已知的值。对  的IT-MAC承诺由一对值  组成，其中  由证明者持有，  由验证者持有，且满足关系式 。

• 承诺打开阶段：证明者发送  给验证者，验证者检查是否满足 。
• 符号表示：记全局密钥  下对  的承诺为 ，也称  为认证值，  是  的MAC标签。
• 安全性：该MAC具有信息论隐藏性和绑定性。
• 同态性：支持对承诺值的同态加法运算，即 。
• 公开常数处理：对于公开常数 ，其MAC定义为  和 ，从而支持任意来自承诺值的仿射运算。

VOLE功能

VOLE功能允许证明者和验证者共同构造一组认证随机值。调用后：

• 证明者获得两个随机域元素向量 (  )；
• 验证者获得全局密钥  和向量  ，且满足  。
  该过程实现了对随机向量  的认证。

承诺转换

若证明者已知某向量  的承诺，可将随机向量  的承诺转换为  的承诺：

1. 证明者发送差值向量  给验证者；
2. 验证者更新  为 。

基于VOLE的零知识证明框架

大多数恒定轮次的基于VOLE的零知识证明遵循"承诺-证明"框架，并包含预处理阶段以提高效率。具体包含以下阶段：

1. 预处理阶段
   Prover 和 Verifier 调用VOLE功能，获得对随机向量  的承诺 ，这些值将在在线阶段被消耗。
   （对应步骤标签 step:1）

2. 在线阶段 - 承诺
   Prover 将电路中所有线值承诺给 Verifier：

• 对于电路的输入线和乘法门的输出线，Prover 发送差值向量 
• 通过该操作，将预处理阶段生成的随机值承诺转换为线值承诺
• 由于IT-MAC的加法同态性，加法门输出线的承诺可由双方在本地计算
• 发送的域元素总数 = 乘法门数量 + 输入线数量
  （对应步骤标签 step:2）

3. 在线阶段 - 证明[乘法正确性]
   Prover 和 Verifier 协作验证每个乘法门输出线  的计算正确性。
   （对应步骤标签 step:3）

4. 在线阶段 - 证明[输出正确性]

• Prover 发送电路输出线的MAC标签  给 Verifier
• 当输出线  预期为1时，Verifier 验证  是否成立

核心差异：现有恒定轮次VOLE-ZKP方案的主要区别在于步骤 step:3 的实现方式。

乘法验证：LPZK与QuickSilver方案

LPZK 及其后续改进方案 QuickSilver采用了相似的思路来验证乘法运算的正确性。下面我们将具体阐述 Prover 如何在承诺线值后向 Verifier 证明乘法门的正确计算。假设某乘法门的输入线为  ，输出线为  ，给定承诺值  ，Prover 需证明  。

核心思想：是将IT-MACs解释为的线性多项式：定义  （其中   ），构造二次多项式  。Verifier 已知其在  处的取值  ，而 Prover 掌握其系数。具体展开为：

其中系数分别为：

关键性质：当且仅当 时，  退化为线性多项式。为证明这一点，Prover可发送  和  给Verifier，后者验证  。但直接发送每个门的两个域元素效率低下，因此QuickSilver采用批量验证策略：

批量验证流程：

1. 设有  个乘法门对应线性多项式  （  至  ）
2. Verifier发送随机挑战值 
3. Prover计算聚合多项式  并发送 
4. Verifier验证 

*注：为实现零知识性，需额外VOLE关联值来掩盖  和  ，此处暂不展开。

小域场景的增强： 上述方案在大域算术电路上有效，但在小域存在安全风险， 攻击者以不可忽略概率猜测全局密钥  从而伪造IT-MAC。为此，QuickSilver引入子域VOLE（sVOLE）变体，其关联随机数形式为   ，其中  ，  ，  。

乘法验证：LPZKv2改进方案

LPZKv2通过两项技术改进实现了对LPZK的优化：

技术改进1：IT-MAC重构
将见证值置于  而非  中。新架构下：

• 认证  时，Prover持有  ，Verifier持有  和  ，满足 
• 优势：Verifier在收到Prover发送的  后，可直接通过  更新  （原方案需计算  ），每门节省一次乘法运算

技术改进2：二次VOLE（qVOLE）
通过生成额外关联随机数提升在线阶段效率。除基础关联式  （  ）外，qVOLE还生成：

该机制显著降低复杂度，具体原理如下：

乘法验证流程

1. 承诺阶段：采用常数项承诺形式  （  ）

2. 预处理阶段：通过qVOLE获取  （Prover）和  （Verifier），满足 

3. 多项式构造：定义二次多项式
• （因  ）
• Verifier已知 
• Prover掌握其系数：

  其中：

4. 验证阶段：

• 当且仅当  时 
• Prover发送  ，Verifier验证 

批量验证协议
对于  个需验证的常数多项式  （Verifier已知  ）：

1. Prover 计算并发送 
2. Verifier 验证 核心原理：当且仅当所有多项式均为常数时，其乘积才是常数多项式。

电路优化扩展
LPZKv2对特定电路类有额外优化。关键发现是表达式：

其中：

• 天然构成对  的认证，且无需任何通信开销。

JesseQ方案技术概览

本节阐述JesseQ的设计原理。我们通过二次子域VOLE(qsVOLE)技术融合QuickSilver与LPZKv2的优势，并设计了适配qsVOLE的高效乘法验证协议。相较于现有基于二次多项式的方法，我们的方案采用一次多项式实现更高效的验证，同时设计了创新的批量验证机制。

通用域电路方案JQv1

对于输入线  和输出线  的乘法门：

预处理阶段

1. 双方通过qsVOLE获取随机认证值  及 
2. Prover发送差值   （  ）
3. 双方计算 

验证多项式构造

1. 线性多项式定义：
    （  ）
   
   

2. 一次多项式构造：
   

其中：

验证逻辑
当且仅当乘法门计算正确时：

此时  退化为常数多项式。虽然Prover可发送  供Verifier验证  ，但会导致每门传输一个域元素。

高效批量验证协议

我们采用随机预言机模型下的哈希函数  实现批量验证：

1. 对于  个待验证常数多项式 
2. Prover 计算并发送 
3. Verifier 验证 

方案扩展性
如LPZKv2，本方案可从标准算术电路推广至任意二次多项式门电路[详见文章第3节]。

技术优势说明：

1. 布尔电路优化：一次多项式  的构造避免了扩域元素乘法运算。在布尔电路中，标量乘法， 如  ，比扩域乘法，如  效率显著提升
2. 批量验证效率：相比QuickSilver与LPZKv2分别需要的  三次乘法和  一次乘法，基于哈希的验证具有更优实际性能。例如在Amazon EC2m5.2xlarge 实例上，BLAKE3 处理1000万61/128位域元素的速度至少是同规模域乘法运算的2倍[详见文章第6.4节]

JQv2 面向任意域上的分层电路

JQv2 将分层电路中每个乘法门由证明者发送的域元素数量（均摊值）降低至  。这一优化基于与 LPZKv2 相似的观察：

其中：

该多项式已能直接认证  而无需任何通信。为简化描述，此处假设偶数层的导线数量多于奇数层。具体而言，我们允许证明者和验证者直接使用输入导线关联的值计算偶数层门输出的 ，从而避免证明者向验证者发送 。但对于奇数层的门，证明者仍需发送  供验证者计算 。由于奇数层输入（偶数层输出）的关联值不再是随机值  与双方已知值  的简单线性组合，JQv1 中的校验方法在此不适用。

因此，在给定输入输出导线的认证值后，我们采用与 QuickSliver 相似的基于二次多项式在  处求值的校验方法，具体细节在 [文章第4节]中阐述。

作者&联系方式：刘梦玲（https://mengling-l.github.io/）

参考文献

我们的在线版本: https://eprint.iacr.org/2025/533