GARUDA算法是一种基于"PIOP + EPC"架构的SNARK, 针对广义秩1约束系统(GR1CS)设计, 其核心流程可分为Setup(参数生成), Prove(证明生成), Verify(证明验证) 三个阶段, 具体步骤如下:
1. Setup
生成公共参数, 供证明者和验证者后续使用, 依赖电路特定的可信设置(Trusted Setup).
输入: GR1CS约束系统的描述(包括自定义门数量, 变量维度等).
步骤:
- 选择双线性群 $ \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T $ 及配对函数 $ e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T $.
- 采样秘密参数 $ \alpha, \beta \in \mathbb{F}_p $($ \mathbb{F}_p $ 为群的标量域), 生成生成元 $ g \in \mathbb{G}_1, h \in \mathbb{G}_2 $.
- 为等系数多项式承诺(EPC)生成参数: 包括多线性多项式空间的规范基, 承诺密钥(如 $ g^\alpha, h^\beta $ 等).
- 为多线性PIOP生成参数: 包括随机评估点, 选择器多项式的系数等.
输出: 公共参数 $ \text{pk} $(证明密钥)和 $ \text{vk} $(验证密钥).
2. Prove
证明者根据输入的见证(满足GR1CS约束的变量赋值)生成证明, 时间复杂度为线性 $ O(n) $($ n $ 为约束数量).
输入: 证明密钥 $ \text{pk} $, GR1CS约束 $ {L_j} $, 满足约束的见证 $ z $(变量向量).
步骤:
-
变量的多线性扩展:
将见证 $ z $ 映射为多线性多项式 $ \hat{z} $(定义在布尔超立方体上), 使得 $ \hat{z}(x) $ 在特定点 $ x $ 的取值对应 $ z $ 中的变量.
-
堆叠矩阵与选择器激活:
- 将不同自定义门的约束矩阵堆叠为 $ M_1^, ..., M_t^ $($ t $ 为门的类型数), 计算矩阵-向量乘积 $ M_i^* \cdot z $, 得到中间结果向量.
- 用选择器多项式 $ S_j $ 激活第 $ j $ 个自定义门的约束, 仅对相关变量子集生效.
-
EPC处理线性约束:
对线性约束(如 $ a + b = c $), 通过EPC生成多项式承诺:
- 计算线性约束对应的多项式 $ P $, 使得 $ P(z) = 0 $ 当且仅当约束满足.
- 用EPC对 $ P $ 承诺, 生成 $ \text{com}_\text{lin} $.
-
PIOP处理非线性约束:
对自定义门的非线性约束(如三次门 $ a \cdot b \cdot c = d $), 通过多线性PIOP验证:
- 利用Sumcheck协议证明所有约束点满足 $ L_j(\hat{z}) = 0 $.
- 生成PIOP的中间证明 $ \pi_{\text{piop}} $.
-
合并证明:
结合EPC承诺, PIOP证明, 生成最终的SNARK证明 $ \pi = (\text{com}\text{lin}, \pi{\text{piop}}, \text{openings}) $, 其中 $ \text{openings} $ 是多项式在特定点的评估证明.
输出: 证明 $ \pi $.
3. Verify(证明验证阶段)
验证者检查证明是否有效, 时间复杂度为 $ O(\log n) $(随约束数对数增长).
- 输入: 验证密钥 $ \text{vk} $, GR1CS约束描述, 证明 $ \pi $.
-
步骤:
-
验证EPC承诺:
检查线性约束对应的多项式承诺 $ \text{com}_\text{lin} $ 是否有效, 通过EPC的配对检查确认多项式系数满足等系数约束.
-
验证PIOP证明:
检查非线性约束的PIOP证明 $ \pi_{\text{piop}} $:
- 验证Sumcheck协议的交互结果是否正确.
- 确认选择器多项式 $ S_j $ 激活的约束均满足 $ L_j = 0 $.
-
合并验证结果:
若EPC和PIOP的验证均通过, 则证明有效;否则无效.
- 输出: 布尔值(证明是否有效).
4. 堆叠矩阵与非线性约束
在GARUDA算法中, 非线性约束(如高次多项式门、逻辑门、查找表约束等)的处理是通过多线性PIOP(多项式交互式Oracle证明) 实现的, 核心是利用Sumcheck协议验证自定义门的谓词在所有约束点上满足 $ L_j = 0 $. 以下是其详细流程和技术细节:
4.1. 非线性约束的表示形式
GARUDA支持的非线性约束基于广义秩1约束系统(GR1CS), 每个非线性约束被表示为局部谓词 $ L_j $, 其形式为:
$$ Lj(z{a1}, z{a2}, ..., z{a_k}) = 0 $$
其中:
- $ z_{a1}, ..., z{a_k} $ 是变量向量 $ z $ 中的一个子集(对应自定义门的输入输出变量);
- $ L_j $ 可以是任意非线性函数, 例如:
- 三次门: $ L_j(z_1, z_2, z_3, z_4) = z_1 \cdot z_2 \cdot z_3 - z_4 $;
- 逻辑异或门: $ L_j(z_1, z_2, z_3) = (z_1 + z_2 - 2z_1z_2) - z_3 $;
- 查找表约束: $ L_j(z_a, zb) = \prod{(x,y) \notin T} (z_a - x)(z_b - y) $($ T $ 为合法键值对集合).
4.2. 非线性约束处理的核心思路
GARUDA通过"多项式化 + 求和验证"处理非线性约束:
- 将离散变量映射为多线性多项式(通过多线性扩展);
- 将非线性约束 $ L_j = 0 $ 转化为多项式等式;
- 利用Sumcheck协议证明该多项式在所有约束点上的求和为零, 间接验证所有约束满足.
4.3. 详细处理步骤
步骤1: 变量的多线性扩展
将原始变量向量 $ z $ 转换为多线性多项式, 为后续多项式操作奠定基础.
- 设变量总数为 $ n $, 取最小的 $ k $ 使得 $ 2^k \geq n $, 则变量可对应到 $ k $-维布尔超立方体 $ {0,1}^k $ 上的点(如第 $ i $ 个变量对应二进制坐标 $ x_i \in {0,1}^k $).
- 构造多线性多项式 $ \hat{z}: {0,1}^k \to \mathbb{F}_p $, 使得 $ \hat{z}(x_i) = z_i $(即多项式在 $ x_i $ 处的取值等于变量 $ z_i $ 的值).
- 多线性性质确保 $ \hat{z} $ 在每个维度上都是线性的(如 $ \hat{z}(a, b+c) = \hat{z}(a,b) + \hat{z}(a,c) $), 便于后续求和与验证.
步骤2: 堆叠矩阵与预言生成
通过堆叠矩阵整合多类非线性约束, 生成供PIOP验证的多项式预言.
- 对每类非线性门(如三次门、异或门), 构造对应的约束矩阵 $ M_i $, 并通过"堆叠"技术整合为 $ M_i^* $(见"堆叠矩阵"详解).
- 计算矩阵-向量乘积 $ v_i = M_i^ \cdot z^ $($ z^* $ 为扩展变量向量), 得到中间结果向量 $ v_i $, 其元素对应第 $ i $ 类门的约束输出.
- 对 $ v_i $ 进行低次扩展(LDE), 得到多线性多项式 $ \hat{v}_i $, 作为证明者提供的"预言"(供验证者查询多项式在任意点的取值).
步骤3: 选择器多项式激活特定约束
通过选择器多项式 $ S_j $ 定位并激活第 $ j $ 个非线性约束, 避免无关变量干扰.
- 选择器多项式 $ S_j: {0,1}^k \to \mathbb{F}_p $ 被设计为: 仅在第 $ j $ 个约束涉及的变量坐标上取值为1, 其余点取值为0.
- 例如, 若第 $ j $ 个约束涉及变量 $ z_1, z_2, z_3 $, 则 $ S_j(x) = 1 $ 当且仅当 $ x $ 对应这三个变量的坐标, 否则 $ S_j(x) = 0 $.
- 通过 $ S_j $ 与预言多项式 $ \hat{v}_i $ 相乘, 得到仅包含第 $ j $ 个约束信息的多项式: $ \hat{v}_i' = S_j \cdot \hat{v}_i $.
步骤4: Sumcheck协议验证多项式求和为零
Sumcheck协议是验证非线性约束的核心工具, 用于证明"所有约束点满足 $ L_j = 0 $". 其本质是通过交互式协议将高维求和问题分解为低维问题, 最终通过单点评估验证.
Sumcheck协议流程(证明者与虚拟验证者交互):
- 目标: 证明者需证明 $ \sum_{x \in {0,1}^d} L_j(\hat{v}_i'(x)) = 0 $($ d $ 为多项式维度, 求和覆盖所有约束点).
- 第一轮分解:
- 证明者将多项式按第一个变量 $ x_1 $ 分解: $ L_j(\hat{v}_i'(x)) = A_0(x_2,...,x_d) + x_1 \cdot A_1(x_2,...,x_d) $.
- 构造关于 $ x_1 $ 的多项式 $ P_1(x1) = \sum{x_2,...,x_d} [A_0 + x_1 \cdot A_1] $, 并发送 $ P_1 $ 给验证者.
- 验证者采样: 验证者随机选择 $ r_1 \in \mathbb{F}_p $, 发送给证明者, 要求证明 $ P_1(r_1) = 0 $.
- 迭代分解: 重复上述过程, 每次固定一个变量(如 $ x_2, ..., x_d $), 证明者发送分解多项式, 验证者采样随机点 $ r_2, ..., r_d $.
- 最终验证: 经过 $ d $ 轮后, 证明者需提供 $ L_j(\hat{v}_i'(r_1, ..., r_d)) $ 的值, 验证者直接检查该值是否为零, 并确认中间分解多项式的一致性.
步骤5: 批量处理与证明压缩
为减少证明大小和计算量, GARUDA对多个非线性约束的Sumcheck证明进行批量处理:
- 采用批量打开技术: 为多个多项式在同一点的评估生成单个证明, 而非每个多项式单独生成证明.
- 合并Sumcheck中间结果: 将不同约束的分解多项式合并为少数几个多项式, 降低证明者的通信开销.
4. 安全性与正确性保证
- 正确性: 若所有非线性约束满足 $ L_j = 0 $, 则Sumcheck协议的最终评估值必为零, 验证者将接受证明.
- 安全性: 若存在不满足的约束, 证明者欺骗验证者的概率可忽略(在代数群模型AGM下证明), 因为随机采样点 $ r_1,...,r_d $ 极大概率会命中不满足约束的点.
5. 总结
- 通用性: 支持任意形式的非线性约束, 无需为特定门设计专用电路, 突破了传统R1CS仅支持二次门的限制.
- 高效性: Sumcheck协议的证明者时间复杂度为 $ O(n) $(与约束数量线性相关), 且可并行处理多类约束.
- 紧凑性: 通过批量处理, 证明大小随约束数量对数增长($ O(\log n) $), 避免了线性增长的开销.
- 线性时间证明: Prove阶段通过EPC和PIOP的分工, 避免冗余计算, 实现 $ O(n) $ 时间复杂度.
- 免费线性门: 线性约束由EPC直接处理, 无需消耗PIOP的证明资源, 降低计算开销.
GARUDA通过"多线性扩展将变量多项式化→选择器激活特定约束→Sumcheck协议验证求和为零"的流程, 高效处理非线性约束. 这一机制使其能够灵活支持复杂自定义门, 同时保持线性时间的证明生成效率, 为隐私计算、区块链等场景中的复杂电路验证提供了有力工具.
Reference
[1] Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments, <https://eprint.iacr.org/2024/1245>