GARUDA and PARI: Faster and Smaller SNARKs via Equifficient Polynomial Commitments

longerd
发布于 3天前
阅读 202

PARI: Smaller SNARKs via Equifficient Polynomial Commitments

### **1. 核心基础与前置知识**
#### **Square R1CS**  
 PARI针对Square R1CS设计, 其约束形式为 $A z \circ A z = B z$($\circ$ 为哈达玛积), 需先将计算问题转化为该约束系统.   
   - 输入: 变量向量 $z = (x, w)$($x$ 为公开输入, $w$ 为私密 witness).   
   - 约束: 对于每个约束行, 需满足 $ (A z)_i^2 = (B z)_i $.

#### **Equifficient Polynomial Commitments(EPC)**  
   PARI依赖基于KZG扩展的单变量EPC方案, 核心是强制多个多项式在特定基下的系数向量相等, 实现线性约束的高效验证.   
   - 关键功能: 批量承诺(Batched Commitments)和批量打开(openings), 减少证明大小.

### **2. PARI 算法实现步骤**

#### **Setup**
- **参数生成**:  
  - 选择配对友好曲线(如BLS12-381), 生成群元素 $ \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T $ 及配对函数 $ e $.   
  - 采样随机数 $ \tau \in \mathbb{F} $, 生成多项式承诺的结构化参考串(SRS): $ \sum :=(G, \tau \cdot G, \tau^2 \cdot G, \cdots, \tau^{D-1} \cdot G) \in \mathbb{G}_{1}^{D}$($ G $ 为 $ \mathbb{G}_1 $ 的生成元, $ D $ 为多项式最大次数).   
  - 生成用于EPC的基转换参数, 包括矩阵 $ A, B $ 的列多项式插值基 $ \mathscr{A}, \mathscr{B} $.

- **密钥生成**:   
  - 证明密钥(ipk): 包含EPC的承诺密钥(基于 $ \mathscr{A}, \mathscr{B} $ 生成), SRS片段.   
  - 验证密钥(ivk): 包含 $ \mathbb{G}_2 $ 中的随机系数(如 $ \alpha H, \beta H $), 曲线参数.

#### **Prove**
- **步骤1: 约束计算与多项式插值**  
  - 计算 $ z_A = A z $ 和 $ z_B = B z $ ($ z = (x, w) $).   
  - 将 $ z_A, z_B $ 插值为多项式 $ \hat{z}_A, \hat{z}_B $(基于光滑乘法子群 $ K $, 满足 $ |K| \geq m $, $ m $ 为约束数).

- **步骤2: 商多项式计算**  
  - 验证 $ \hat{z}_A^2 - \hat{z}_B $ 能被消失多项式 $ v_K(X) = \prod_{k \in K} (X - k) $ 整除, 计算商多项式 $ q = (\hat{z}_A^2 - \hat{z}_B) / v_K $.

- **步骤3: EPC批量承诺**  
  - 对多项式 $ \hat{z}_A, \hat{z}_B, q $ 进行批量承诺:   
    - 利用EPC的一致性密钥(线性组合 $ \alpha \mathscr{A} + \beta \mathscr{B} $)生成单个承诺 $ T $, 包含所有多项式的系数信息.

- **步骤4: 评估与 openings**  
  - 从随机预言机获取评估点 $ r $, 计算 $ \hat{z}_A(r), \hat{z}_B(r), q(r) $.   
  - 生成 openings 证明: 对每个多项式计算 witness 多项式 $ w_A = (\hat{z}_A - \hat{z}_A(r))/(X - r) $ 等, 批量合并为单个证明 $ U $.

- **输出证明**: $ \pi = (T, U, \hat{z}_A(r), \hat{z}_B(r)) $ (2个群元素 + 2个域元素).

#### **Verify**
- **步骤1: 公开输入处理**  
  - 计算公开输入对应的多项式评估 $ \hat{x}_A(r), \hat{x}_B(r) $ (基于 $ x $ 生成).

- **步骤2: 商多项式评估验证**  
  - 验证 $ q(r) = (\hat{z}_A(r) + \hat{x}_A(r))^2 - (\hat{z}_B(r) + \hat{x}_B(r)) / v_K(r) $.

- **步骤3: 配对检查**  
  - 验证EPC承诺的一致性:   
    $$
    e(T, \delta_2 H) \stackrel{?}{=} e(U, \delta_1 (\tau - r) H) \cdot e(v_a \alpha G + v_b \beta G + v_q G, H)
    $$
这里 $ v_a = \hat{z}_A(r), v_b = \hat{z}_B(r), v_q = q(r) $, $ \delta_1, \delta_2 $ 为随机系数.

### **3. 关键优化实现**
#### **批量承诺与 openings**  
   - 利用EPC的线性组合特性, 将多个多项式的承诺合并为单个群元素, 减少证明大小.   
   - Openings 阶段通过随机系数合并多个 witness 多项式的证明, 降低验证成本.

#### **多项式插值与消失多项式**  
   - 选择 $ K $ 为2的幂次子群, 利用FFT加速插值和多项式乘法, 降低 prover 时间复杂度至 $ O(m \log m) $.

#### **安全性保证**  
   - 在代数群模型(AGM)下证明安全性, 依赖强Diffie-Hellman(SDH)假设确保承诺的绑定性.

### **4. 实现工具与参考**
- **框架选择**: 基于arkworks(Rust)实现, 复用其多项式操作、配对计算和R1CS工具链.   
- **核心模块**:   
  - EPC实现: 扩展KZG方案, 支持批量承诺和系数相等约束.   
  - PIOP实现: 针对SR1CS的简单交互证明, 验证 $ \hat{z}_A^2 = \hat{z}_B $ 在所有点成立.

通过以上步骤, 可实现PARI算法的核心功能, 其证明大小在BLS12-381曲线上为(2个群元素 + 2个域元素), 为目前已知最小.

### **5. 与 groth16 对比**

#### **核心设计目标**
- **Groth16**: 追求证明大小, 生成效率和验证效率的平衡, 是目前应用最广泛的 zk-SNARK 之一, 适合大多数通用场景. 
- **PARI**: 专注于**最小化证明大小**, 通过创新的多项式承诺技术(EPC)将证明压缩到极致, 适用于对带宽, 存储或链上空间极度敏感的场景(如区块链 Layer2, 高频交易验证).

#### **底层约束系统**
- **Groth16**: 基于 **R1CS(Rank-1 Constraint System)**, 约束形式为 $ (A z) \cdot (B z) = C z $(向量内积), 支持任意 NP 问题的转化, 但线性约束的表达成本较高. 
- **PARI**: 基于 **Square R1CS(SR1CS)**, 约束形式为 $ (A z) \circ (A z) = B z $(哈达玛积, 即元素-wise 平方), 更适合表达平方关系, 减少冗余约束.

#### **证明结构与大小**
- **Groth16**: 证明由 **3 个群元素**组成(如 BLS12-381 曲线上约 1536 bits), 与约束数量无关, 是早期 zk-SNARK 中证明大小的标杆. 
- **PARI**: 证明由 **2 个群元素 + 2 个域元素**组成(BLS12-381 上约 1280 bits), 是目前已知最小的 zk-SNARK 证明之一, 比 Groth16 小约 17%.

#### **多项式承诺与验证技术**
- **Groth16**: 使用传统双线性配对技术, 依赖指数知识假设(KEA), 验证时需检查 3 个群元素间的配对关系. 
- **PARI**: 基于创新的 **EPC(Equifficient Polynomial Commitments)**, 是 KZG 方案的扩展, 通过"强制多项式系数在特定基下相等"实现高效批量承诺和验证, 验证时仅需 1 次配对运算, 且常数因子更小.

#### **效率对比**
| 指标                | Groth16                  | PARI                     |
|---------------------|--------------------------|--------------------------|
| **证明生成时间**    | $ O(n \log n) $(优化成熟) | $ O(n \log n) $(理论相当, 工程实现待优化) |
| **验证时间**        | $ O(1) $(1 次配对, 常数较大) | $ O(1) $(1 次配对, 常数更小) |
| **可信初始化**      | 需电路专属 setup(单电路效率高) | 支持通用 setup(多电路共享参数) |
| **零知识支持**      | 原生支持(可隐藏私密输入) | 支持(默认特性)          |

#### **安全性假设**
- **Groth16**: 依赖双线性群上的**指数知识假设(KEA)** 和离散对数假设, 安全性在标准模型下证明. 
- **PARI**: 依赖**代数群模型(AGM)** 下的强 Diffie-Hellman(SDH)假设, 模型更强, 但假设更简洁.

#### **适用场景**
- **Groth16**: 适合对成熟度, 工程实现友好性要求高的场景(如 ZCash 隐私交易, 链上合约验证), 尤其单电路场景下性能优异. 
- **PARI**: 适合对证明大小有极致要求的场景(如带宽受限的物联网设备, 高频 Layer2 交易), 但目前理论性较强, 实际应用较少.

#### **总结**
Groth16 是"平衡型经典方案", 成熟度高, 应用广泛: PARI 是"极致压缩方案", 通过创新技术实现更小证明, 但工程落地仍需时间. 两者均基于配对密码学, 但 PARI 在证明大小和通用 setup 上更具潜力.

### Reference
[1] Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments, https://eprint.iacr.org/2024/1245

1. 核心基础与前置知识

Square R1CS

PARI针对Square R1CS设计, 其约束形式为 $A z \circ A z = B z$($\circ$ 为哈达玛积), 需先将计算问题转化为该约束系统.

输入: 变量向量 $z = (x, w)$($x$ 为公开输入, $w$ 为私密 witness).
约束: 对于每个约束行, 需满足 $ (A z)_i^2 = (B z)_i $.

Equifficient Polynomial Commitments(EPC)

PARI依赖基于KZG扩展的单变量EPC方案, 核心是强制多个多项式在特定基下的系数向量相等, 实现线性约束的高效验证.

关键功能: 批量承诺(Batched Commitments)和批量打开(openings), 减少证明大小.

2. PARI 算法实现步骤

Setup

参数生成:
- 选择配对友好曲线(如BLS12-381), 生成群元素 $ \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T $ 及配对函数 $ e $.
- 采样随机数 $ \tau \in \mathbb{F} $, 生成多项式承诺的结构化参考串(SRS): $ \sum :=(G, \tau \cdot G, \tau^2 \cdot G, \cdots, \tau^{D-1} \cdot G) \in \mathbb{G}_{1}^{D}$($ G $ 为 $ \mathbb{G}_1 $ 的生成元, $ D $ 为多项式最大次数).
- 生成用于EPC的基转换参数, 包括矩阵 $ A, B $ 的列多项式插值基 $ \mathscr{A}, \mathscr{B} $.
密钥生成:
- 证明密钥(ipk): 包含EPC的承诺密钥(基于 $ \mathscr{A}, \mathscr{B} $ 生成), SRS片段.
- 验证密钥(ivk): 包含 $ \mathbb{G}_2 $ 中的随机系数(如 $ \alpha H, \beta H $), 曲线参数.

Prove

步骤1: 约束计算与多项式插值
- 计算 $ z_A = A z $ 和 $ z_B = B z $ ($ z = (x, w) $).
- 将 $ z_A, z_B $ 插值为多项式 $ \hat{z}_A, \hat{z}_B $(基于光滑乘法子群 $ K $, 满足 $ |K| \geq m $, $ m $ 为约束数).
步骤2: 商多项式计算
- 验证 $ \hat{z}_A^2 - \hat{z}_B $ 能被消失多项式 $ vK(X) = \prod{k \in K} (X - k) $ 整除, 计算商多项式 $ q = (\hat{z}_A^2 - \hat{z}_B) / v_K $.
步骤3: EPC批量承诺
- 对多项式 $ \hat{z}_A, \hat{z}_B, q $ 进行批量承诺:
- 利用EPC的一致性密钥(线性组合 $ \alpha \mathscr{A} + \beta \mathscr{B} $)生成单个承诺 $ T $, 包含所有多项式的系数信息.
步骤4: 评估与 openings
- 从随机预言机获取评估点 $ r $, 计算 $ \hat{z}_A(r), \hat{z}_B(r), q(r) $.
- 生成 openings 证明: 对每个多项式计算 witness 多项式 $ w_A = (\hat{z}_A - \hat{z}_A(r))/(X - r) $ 等, 批量合并为单个证明 $ U $.
输出证明: $ \pi = (T, U, \hat{z}_A(r), \hat{z}_B(r)) $ (2个群元素 + 2个域元素).

Verify

步骤1: 公开输入处理
- 计算公开输入对应的多项式评估 $ \hat{x}_A(r), \hat{x}_B(r) $ (基于 $ x $ 生成).
步骤2: 商多项式评估验证
- 验证 $ q(r) = (\hat{z}_A(r) + \hat{x}_A(r))^2 - (\hat{z}_B(r) + \hat{x}_B(r)) / v_K(r) $.
步骤3: 配对检查
- 验证EPC承诺的一致性:
  $$ e(T, \delta_2 H) \stackrel{?}{=} e(U, \delta_1 (\tau - r) H) \cdot e(v_a \alpha G + v_b \beta G + v_q G, H) $$ 这里 $ v_a = \hat{z}_A(r), v_b = \hat{z}_B(r), v_q = q(r) $, $ \delta_1, \delta_2 $ 为随机系数.

3. 关键优化实现

批量承诺与 openings

利用EPC的线性组合特性, 将多个多项式的承诺合并为单个群元素, 减少证明大小.
Openings 阶段通过随机系数合并多个 witness 多项式的证明, 降低验证成本.

多项式插值与消失多项式

选择 $ K $ 为2的幂次子群, 利用FFT加速插值和多项式乘法, 降低 prover 时间复杂度至 $ O(m \log m) $.

安全性保证

在代数群模型(AGM)下证明安全性, 依赖强Diffie-Hellman(SDH)假设确保承诺的绑定性.

4. 实现工具与参考

框架选择: 基于arkworks(Rust)实现, 复用其多项式操作、配对计算和R1CS工具链.
核心模块:
- EPC实现: 扩展KZG方案, 支持批量承诺和系数相等约束.
- PIOP实现: 针对SR1CS的简单交互证明, 验证 $ \hat{z}_A^2 = \hat{z}_B $ 在所有点成立.

通过以上步骤, 可实现PARI算法的核心功能, 其证明大小在BLS12-381曲线上为(2个群元素 + 2个域元素), 为目前已知最小.

5. 与 groth16 对比

核心设计目标

Groth16: 追求证明大小, 生成效率和验证效率的平衡, 是目前应用最广泛的 zk-SNARK 之一, 适合大多数通用场景.
PARI: 专注于最小化证明大小, 通过创新的多项式承诺技术(EPC)将证明压缩到极致, 适用于对带宽, 存储或链上空间极度敏感的场景(如区块链 Layer2, 高频交易验证).

底层约束系统

Groth16: 基于 R1CS(Rank-1 Constraint System), 约束形式为 $ (A z) \cdot (B z) = C z $(向量内积), 支持任意 NP 问题的转化, 但线性约束的表达成本较高.
PARI: 基于 Square R1CS(SR1CS), 约束形式为 $ (A z) \circ (A z) = B z $(哈达玛积, 即元素-wise 平方), 更适合表达平方关系, 减少冗余约束.

证明结构与大小

Groth16: 证明由 3 个群元素组成(如 BLS12-381 曲线上约 1536 bits), 与约束数量无关, 是早期 zk-SNARK 中证明大小的标杆.
PARI: 证明由 2 个群元素 + 2 个域元素组成(BLS12-381 上约 1280 bits), 是目前已知最小的 zk-SNARK 证明之一, 比 Groth16 小约 17%.

多项式承诺与验证技术

Groth16: 使用传统双线性配对技术, 依赖指数知识假设(KEA), 验证时需检查 3 个群元素间的配对关系.
PARI: 基于创新的 EPC(Equifficient Polynomial Commitments), 是 KZG 方案的扩展, 通过"强制多项式系数在特定基下相等"实现高效批量承诺和验证, 验证时仅需 1 次配对运算, 且常数因子更小.

效率对比

指标	Groth16	PARI
证明生成时间	$ O(n \log n) $(优化成熟)	$ O(n \log n) $(理论相当, 工程实现待优化)
验证时间	$ O(1) $(1 次配对, 常数较大)	$ O(1) $(1 次配对, 常数更小)
可信初始化	需电路专属 setup(单电路效率高)	支持通用 setup(多电路共享参数)
零知识支持	原生支持(可隐藏私密输入)	支持(默认特性)

安全性假设

Groth16: 依赖双线性群上的指数知识假设(KEA) 和离散对数假设, 安全性在标准模型下证明.
PARI: 依赖代数群模型(AGM) 下的强 Diffie-Hellman(SDH)假设, 模型更强, 但假设更简洁.

适用场景

Groth16: 适合对成熟度, 工程实现友好性要求高的场景(如 ZCash 隐私交易, 链上合约验证), 尤其单电路场景下性能优异.
PARI: 适合对证明大小有极致要求的场景(如带宽受限的物联网设备, 高频 Layer2 交易), 但目前理论性较强, 实际应用较少.

总结

Groth16 是"平衡型经典方案", 成熟度高, 应用广泛: PARI 是"极致压缩方案", 通过创新技术实现更小证明, 但工程落地仍需时间. 两者均基于配对密码学, 但 PARI 在证明大小和通用 setup 上更具潜力.

Reference

[1] Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments, https://eprint.iacr.org/2024/1245

原创
学分: 10
分类: 零知识证明
标签: zk ZKP

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。