HyperNova：针对CCS的递归证明系统

HyperNova：针对CCS的递归证明系统

1. 引言

前序博客有：

• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记
• SuperNova论文赏析
• Customizable constraint systems for succinct arguments学习笔记（1）【CCS（Customizable constraint system）】
• Customizable constraint systems for succinct arguments学习笔记（2）【CCS（Customizable constraint system）】

Nova、HyperNova及ProtoStar之间的关系为：

• Nova：fold with error terms
• HyperNova：fold with sumcheck
• ProtoStar：fold the sumcheck itself

HyperNova为基于sumcheck协议的、针对CCS的递归证明系统，开源代码实现见：

• （Rust）
• （Rust，启用hypernova feature）

与SuperNova类似，HyperNova也用于证明半结构化计算，不同之处在于：

• SuperNova中每个step表示为Relaxed R1CS，而HyperNova中每个step表示为CCS（Customizable Constraint System）。
  • 在不增加开销的情况下，可将现有流行的算术化电路类型（如R1CS、Plonkish、AIR）均转换为CCS算术化电路。
  • CCS算术化表示，与证明CCS的证明系统，是相互独立的。
    • 1）原来针对R1CS的SNARKs方案，可很容易扩展为针对CCS（以及Plonkish），如：
      • Spartan（R1CS）-》SuperSpartan（CCS）
      • Marlin（R1CS）-》SuperMarlin（CCS）
    • 2）原来针对Plonkish的SNARKs方案（如Plonk、HyperPlonk等），无法在不增加开销的情况下，用于处理CCS（或R1CS）。

HyperNova关键点为：

• 1）对通用zkSNARKs（Groth16，Plonk等）的关键改进为：
  • HyperNova的Recursive verifier circuit中有：1次scalar multiplication运算 + logarithmic次哈希运算。
  • HyperNova的Prover开销为：对witness进行承诺的1次MSM运算 + 1次sum-check运算（仅包含有限域运算）。即 HyperNova的证明速度 ≈ approx ≈ 通过MSM对witness的承诺速度。
• 2）采用multi-folding scheme：待fold的2个input instance可具有不同的NP relations，但共享某兼容结构。
• 3）nlookup算法：与Nova家族兼容的lookup argument算法。

2. 目标：针对半结构化计算的快速递归zkSNARKs

所谓zkSNARKs，是指：Prover P P P证明其知道witness W W W，使得 C ( x , W ) = 1 C(x,W)=1 C(x,W)=1，其中 C C C为某public circuit， x x x为public input/output。
而递归zkSNARKs形如：

如证明：基于某初始输入 z 0 z_0 z0​，运行某非确定性计算 C mathcal{C} C n n n次，输出为 z n z_n zn​：

• 所谓半结构化，是指：每个step计算为 { C 1 , C 2 , ⋯ , C l } {mathcal{C}_1,mathcal{C}_2,cdots,mathcal{C}_l} {C1​,C2​,⋯,Cl​}之一，由selector circuit ϕ phi ϕ决定。
• 所谓递归，是指：按step-by-step生成proof（不要求按顺序生成）

半结构化计算递归zkSNARK方案衍化路径为：【具有越来越简单的底层原语，以及，越来越高的效率】

• 1）基于SNARKs的递归证明方案有：[Val08, BCTV14]。

• 2）基于(S)NARKs+accumulation的递归证明方案有：[BGH19,BCMS20（Halo）]、[BDFG21]、[BCLMS21（采用split accumulation）]。

• 3）基于folding scheme的递归证明方案有：[KST22（Nova）]、[KS22（SuperNova）]、[M23（Sangria（“PlonkNova”））]、paraNova、AIRNova、TypedNova、Origami、MoonMoon、[KS23（HyperNova）]、[CB23（ProtoStar）]等等。
  

  • 3.1）[KST22（Nova）]：Nova中的电路为R1CS格式，其Prover开销比通用SNARK更便宜，如Marlin中需要 多于22个MSM和FFT运算，而Nova中仅需要2个size为 O ( ∣ C ∣ ) O(|mathcal{C}|) O(∣C∣)的MSM运算。
  • 3.2）[M23（Sangria（“PlonkNova”））]：将Nova扩展为degree- d d d Plonkish。Sangria的主要缺陷在于：Prover必须做 d d d个size为 O ( ∣ C ∣ ) O(|mathcal{C}|) O(∣C∣)的MSM运算——1个对witness的MSM运算 + ( d − 1 ) (d-1) (d−1)个对cross-terms的MSM运算。

  以MinRoot [KMT22]一次迭代为例：

  • a）以R1C2/degree-2 constraints为例：一次MinRoot迭代对应3个约束 -》Nova的开销为每个迭代对应6个exps运算。
  • b）以degree-5 constraints为例：一次MinRoot迭代对应1个约束 -》Sangria的开销为每个迭代对应6个exps运算。

递归证明系统的具体用途可为：

• 1）VDF： C mathcal{C} C为对某delay函数调用一次或多次（如MinRoot）。
• 2）zkVM： C mathcal{C} C为某VM（如EVM、Wasm、LLVM）的某step，或，某CPU（如RISC-V）的某step。
• 3）zkBridge： C mathcal{C} C为根据某链的共识规则来验证状态。
• 4）zkML： C mathcal{C} C为某模型的某layer。
• 5）PhotoProof： C mathcal{C} C对某图片做特定的转换。
• 6）Public key transparency： C mathcal{C} C为检查某目录在每个epoch是append-only的。

3. HyperNova

HyperNova的主要技术贡献点为：

• 对CCS的Folding scheme
  

其中：

• IVC（Incrementally Verifiable Computation）主要侧重为：对顺序执行计算的证明。
• PCD（Proof Carrying Data）主要侧重为：对并行计算的证明。

3.1 R1CS vs. CCS

所谓R1CS是指：

CCS为对R1CS、Plonkish和AIR的通用表示：

• 具有至少3个矩阵来定义电路： M 1 , M 2 , ⋯ , M t M_1,M_2,cdots, M_t M1​,M2​,⋯,Mt​
• 通过multisets来对约束进行定制： S 1 , S 2 , ⋯ , S q S_1,S_2,cdots, S_q S1​,S2​,⋯,Sq​
• 公开输入/输出： x x x
• 存在witness W W W使得 Z = ( W , x , 1 ) Z=(W,x,1) Z=(W,x,1)满足：
  ∑ i ∈ [ q ] ◯ j ∈ S i M j ⋅ Z = 0 sum_{iin [q]}bigcirc_{jin S_i} M_jcdot Z=0 ∑i∈[q]​◯j∈Si​​Mj​⋅Z=0
• 通过对矩阵和multiset进行“编程”，可表示任意多项式约束。
• 对于HyperNova和SuperSpartan中的AIR约束，具有“free” addition gates。

以R1CS为例，转换为CCS表示时，有：

• M 1 = A , M 2 = B , M 3 = − C M_1=A,M_2=B,M_3=-C M1​=A,M2​=B,M3​=−C
• S 1 = { 1 , 2 } , S 2 = { 3 } S_1={1,2},S_2={3} S1​={1,2},S2​={3}

3.2 对Committed CCS的folding scheme

3.2.1 Folding Committed CCS：CCCS × times × CCCS -> CCCS

Folding Committed CCS：CCCS × times × CCCS -> CCCS：

为实现对Committed CCS的folding scheme，在instance（即public input）中还需包含 C = C o m ( W ) C=Com(W) C=Com(W)。
主要挑战在于：

• 挑战一：对于non-linear terms，无法做random linear combination。
• 挑战二：Nova-style relaxation，会引入 O ( max ⁡ i ∣ S i ∣ ) O(max_{i}|S_i|) O(maxi​∣Si​∣)个error vector commitments。

3.2.2 Folding Committed CCS：CCCS × times × LCCCS -> LCCCS

进一步的解决方案为CCCS × times × LCCCS -> LCCCS：

• 将CCCS进行线性化，并fold进入一个linearized instance中。这足以用于IVC场景。
  • 注意 Linearized CCCS 不是NP-complete的，但更易于fold。

其中Linearized CCCS instance中包含：

• 矩阵 ( M 1 , M 2 , ⋯ , M t ) (M_1,M_2,cdots, M_t) (M1​,M2​,⋯,Mt​)
• multiset ( S 1 , S 2 , ⋯ , S q ) (S_1,S_2,cdots, S_q) (S1​,S2​,⋯,Sq​)
• 承诺值 C C C
• scalar值 u u u
• public input/output：vector x x x
• random challenge r r r
• scalars列表 ( v 1 , v 2 , ⋯ , v t ) (v_1, v_2,cdots, v_t) (v1​,v2​,⋯,vt​)

存在witness vector W W W，使得 Z = ( W , x , u ) Z=(W,x, u) Z=(W,x,u)满足：

• 1） ∀ i ∈ [ t ] forall iin [t] ∀i∈[t]，有 v i = ∑ y ∈ { 0 , 1 } log ⁡ n M i ( r , y ) ⋅ Z ( y ) v_i=sum_{yin {0,1}^{log n}}M_i(r,y)cdot Z(y) vi​=∑y∈{0,1}logn​Mi​(r,y)⋅Z(y)
• 2） C = C o m ( W ) C=Com(W) C=Com(W)

不过此时Folding Committed CCS：CCCS × times × LCCCS -> LCCCS 仍然存在如下挑战：

• 仍然不清楚如何来fold
  

3.2.3 Folding Constrained Instances：LCCCS × ~ tilde{times} ×~​ LCCCS -> LCCCS

进一步的解决方案为LCCCS × ~ tilde{times} ×~​ LCCCS -> LCCCS，以实现对2个具有相同randomness（即具有相同的random challenge r r r）的LCCCS instance进行fold的简单目标，即：

很容易将 CCCS × times × LCCCS reduce为 LCCCS × ~ tilde{times} ×~​ LCCCS（即a pair of constrained LCCCS instances）：

Folding Constrained Instances：LCCCS × ~ tilde{times} ×~​ LCCCS -> LCCCS，即为：

注意其中 v i = ∑ y ∈ { 0 , 1 } log ⁡ n M i ( r , y ) ⋅ Z ( y ) v_i=sum_{yin {0,1}^{log n}}M_i(r,y)cdot Z(y) vi​=∑y∈{0,1}logn​Mi​(r,y)⋅Z(y)，使得 [ ( C , u , x , γ , v 1 , ⋯ , v t ) , W ] [(C,u,x,gamma,v_1,cdots,v_t),W] [(C,u,x,γ,v1​,⋯,vt​),W]的correctness具备线性性：
v i ( 1 ) + γ ⋅ v i ( 2 ) = ∑ y ∈ { 0 , 1 } log ⁡ n M i ( r , y ) ⋅ Z 1 ( y ) + γ ⋅ ∑ y ∈ { 0 , 1 } log ⁡ n M i ( r , y ) ⋅ Z 2 ( y ) = ∑ y ∈ { 0 , 1 } log ⁡ n M i ( r , y ) ⋅ ( Z 1 ( y ) + γ ⋅ Z 2 ( y ) ) v_i^{(1)}+gammacdot v_i^{(2)}=sum_{yin {0,1}^{log n}}M_i(r,y)cdot Z_1(y)+gammacdot sum_{yin {0,1}^{log n}}M_i(r,y)cdot Z_2(y)=sum_{yin {0,1}^{log n}}M_i(r,y)cdot (Z_1(y)+gammacdot Z_2(y)) vi(1)​+γ⋅vi(2)​=∑y∈{0,1}logn​Mi​(r,y)⋅Z1​(y)+γ⋅∑y∈{0,1}logn​Mi​(r,y)⋅Z2​(y)=∑y∈{0,1}logn​Mi​(r,y)⋅(Z1​(y)+γ⋅Z2​(y))

3.2.4 Linearizing Reduction：CCCS × times × LCCCS -> LCCCS × ~ tilde{times} ×~​ LCCCS

为实现Folding Committed CCS：CCCS × times × LCCCS -> LCCCS，接下来的任务是将CCCS × times × LCCCS reduce为 LCCCS × ~ tilde{times} ×~​ LCCCS：

核心思想为：使用sum-check协议，来将CCCS reduce为 “基于相同challenge的LCCCS”。【】

最终实现的Folding Committed CCS：CCCS × times × LCCCS -> LCCCS 方案为：

参考资料

[1] arnaucube 2023年5月笔记 Notes on HyperNova
[2] Oskar 2023年5月hackmd HyperNova Notes
[3] 2023年6月 PSE培训视频 CCS & HyperNova with Srinath - Folding Schemes FTW
[4] 2023年8月 Carlos Pérez hackmd CCS
[5] 2023年5月 Oskar hackmd R1CS to CCS overview
[6] Ariel Gabizon 2023年5月twitter recent history of folding

Nova系列博客

• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记
• Nova 和 SuperNova：无需通用电路的通用机器执行证明系统
• Sangria：类似Nova folding scheme的relaxed PLONK for PLONK
• 基于Nova/SuperNova的zkVM
• SuperNova：为多指令虚拟机执行提供递归证明
• Lurk——Recursive zk-SNARKs编程语言
• Research Day 2023：Succinct ZKP最新进展
• 2023年 ZK Hack以及ZK Summit 亮点记
• 基于cycle of curves的Nova证明系统（1）
• 基于cycle of curves的Nova证明系统（2）
• Nova代码解析
• Nova中 Vitalik R1CS例子 的 folding scheme
• 基于Nova的MinRoot VDF实现
• 基于Nova的SHA256证明
• Nova-Scotia代码解析
• Customizable constraint systems for succinct arguments学习笔记（1）
• Customizable constraint systems for succinct arguments学习笔记（2）
• SuperNova论文赏析