SuperNova论文赏析

1. 引言

前序博客有：

Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记

卡内基梅隆大学 Abhiram Kothapalli 和微软研究中心 Srinath Setty 2022年论文《SuperNova: Proving universal machine executions without universal circuits》，为Nova的扩展版，开源代码见：

https://github.com/jules/supernova（Rust）
https://github.com/hero78119/SuperNova（Rust）【活跃开发中】

本文主要参考：

2023年3月视频分享 SuperNova with Srinath and Abhiram
2022年8月在Session at Crypto 2022上分享 Nova: Recursive Zero-Knowledge Arguments from Folding Schemes - Abhiram Kothapalli
2023年4月视频分享 zkStudyClub: Supernova (Srinath Setty - MS Research)

2. Nova回顾

2.1 IVC计算模型

所谓IVC（Incremental Verifiable Computation）计算模型，是指：

对于（非确定性）函数 $F$ 和 statement $n, z_0, z_n)$ ，证明存在 $z_0=z_0'$ 和 $z_{i+1}'\leftarrow F(z_i', w_i)$ ，使得 $z_n=z_n'$ 。

IVC（Incremental Verifiable Computation）最早由Valiant在其2008年论文[Val08] Incrementally verifiable computation or proofs of knowledge imply time/space efficiency 中首次提出，其核心思想为：
在这里插入图片描述
IVC的关键在于，随着迭代次数的增加，其proof size并不会增加。具体为：

不过，其中存在的问题在于：

实际实现时，在电路中验证SNARK proof是昂贵的。

2.2 Nova（本文称为NIVC）：为针对单个指令的IVC

从SuperNova的角度来看Nova（本文称为NIVC）：

Nova为针对单个指令的IVC。

Nova通过引入Folding scheme，在 $F^{'}$ 中不再做任何proof验证工作：
在这里插入图片描述

2.3 Folding Schemes

交互式folding scheme是指Prover $P$ 和Verifier $V$ 交互式地将"2个claim $(u_1,w_1),(u_2,w_2)\in R$ " reduce为 “1个claim $(u,w)\in R$ ”。
Folding scheme需满足如下属性：

Completeness完备性：若 $u_1,u_2$ 为satisfiable的，则 $u$ 也是satisfiable的。
Knowledge Soundness可靠性：若Prover可输出satisfying $w$ ，则Prover必然知道satisfying $w_1,w_2$ 。
Efficiency高效性：Verifier “做Folding操作”，必须比， “对某instance做check操作（即验证proof）” ，要便宜很多。

在这里插入图片描述
以上交互式folding scheme可通过Fiat-Shamir Transformation 来实现非交互式folding scheme。
已知某NP的非交互式folding scheme，通过运行folding Verifier， $F^{'}$ 可verifiably fold $u_i$ 和 $U_i$ ：【fold前后的3个instance具有相同的结构和相同的size。】
在这里插入图片描述

2.4 针对R1CS约束系统的Folding Scheme

标准R1CS表示为：
在这里插入图片描述
其中：

$Z = (W, x, 1)$ ， $W$ 为witness vector， $x$ 为public input/output vector。

需在标准R1CS表示的基础之上，额外引入error vector $E$ 和scalar $u$ ，从而构建出Relaxed R1CS：
在这里插入图片描述
其中：

$Z = (W, x, u)$ ， $W$ 为witness vector， $x$ 为public input/output vector。
当 $u=1,E=\vec{0}$ ，则为标准R1CS。即可将标准R1CS看成是Relaxed R1CS的特例情况。

然后是结合具有加法同态属性的承诺方案，来实现对Relaxed R1CS的Folding Scheme：【为避免Prover作弊，并实现Verifier succinctness，需将 $(E, W)$ 一起作为witness，并提前在statement中公开其承诺值 $(\bar{E},\bar{W})$ 。】
在这里插入图片描述

3. SuperNova

3.1 NIVC计算模型

所谓NIVC（Non-uniform IVC）计算模型，是指：

对于（非确定性）指令集 $F_1,\cdots, F_l$ 、控制函数 $\varphi$ 和 statement $n, z_0, z_n)$ ，证明存在 $z_0=z_0'$ 和 $z_{i+1}'\leftarrow F_{\varphi(z_i', w_i)}(z_i', w_i)$ ，使得 $z_n=z_n'$ 。

以上为SuperNova核心思想，SuperNova为对Nova的扩展，理论上可将SuperNova用于实现虚拟机。在递归过程中，每个step可动态选择所执行的指令，不再需要在每个step实现所有指令集的电路，而是，在每个step只需实现实际用到的指令的电路。

SuperNova实现了"a la carte（按菜单点菜）" cost profile：

pay only for what is executed。

在这里插入图片描述

3.2 SuperNova的Folding Scheme

Nova中要求 fold前后的3个instance（claim）具有相同的结构和相同的size。
而SuperNova中，针对所支持的每个指令，构建了一个Running Claim（又名Running Instance）：
在这里插入图片描述
其中：

每个step的running instance集合 $\{U_{i,1},U_{i,2}, \cdots, U_{i,l}\}$ 可以Merkle tree或multi-set hash等成熟技术来表示，因为实际在每个step仅使用该running instance集合中的一个，实际电路中没必要枚举所有的running instance。
$pc_i$ 为program counter，用于：
- 决定集合 $\{U_{i,1},U_{i,2}, \cdots, U_{i,l}\}$ 中哪个running instance参与Fold。
- 决定用Fold结果来更新集合 $\{U_{i+1,1},U_{i+1,2}, \cdots, U_{i+1,l}\}$ 中哪个running instance。
基于控制函数 $\varphi$ 和 $w_i,z_i$ ，来决定下一个step的program counter $pc_{i+1}$ 。