近期NOVA作为当前ZK领域热门的Folding Scheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：
- [Pederson and Poseidon]()
- [R1CS]()
- [NIFS]()
- [Circuit]()
- [RecursiveSNARK]()
- [CompressedSNARK]()
<br />
希望通过详尽且直白的逻辑能够把NOVA整个框架的设计理念传达到读者，最终落地到实际的crypto应用场景中。
<br />
其中前两个主题为crypto primitives，后四个主题为NOVA论文中的主线内容。本章节主题为论文中最为核心的部分NIFS，全称为None-interactive Folding Scheme，先从宏观上把握NOVA的主脉。
!建议：最好配合着paper去理解，paper上找不到的答案或许这里可以给你-_-
在梳理NIFS的逻辑之前，我们先明确一下，NIFS的目标是什么？
需要了解的一些术语
-
$ \widetilde{W} $ 代表对W的pederson commitment，可以是scaler field的标量也可以是向量，细节我们会在后面的章节中展开。这里我们只需要简单地知道pederson commitment是crypto 中private 数据的public表现形式，由verifier 掌握，它是可以被verifier打开验证的，因此它能够完全代表private 数据
<br />
-
challenge factor $r$，它是一个poseidon hash值，细节部分我们也会在后面的章节中展开。这里我们需要了解的是，通过它实现Non-interactive，比如说在KZG10 commitment中，需要Verifier 产出challenge factor $r$并递交给Prover，它是一种Interactive 的方式
<br />
-
relaxed R1CS，也是NOVA为了实现recursive folding而比较创新的一点，paper中有着重讲解，细节部分我们也会在后面展开
<br />
-
satisfiable，是校验(U, W)满足R1CS等式及pederson commitment 的一种表达
NIFS的目标
假定业务电路的表达式：
$$
y = x^3 + x + 1
$$
则，业务电路输出的R1CS witness：
$$
\begin{aligned}
W &= (W_0, W_1, W_2, W_3) \
其中&\begin{cases}
W_0 &= x * x \
W_1 &= W_0 * x \
W_2 &= W_1 + x \
W_3 &= 0 \
\end{cases}
\end{aligned}
$$
则，在x 和 y为public情况下，业务电路输出的R1CS instance:
$$
\begin{aligned}
U &= (\widetilde{W}, X) \
其中&\begin{cases}
X &= (X_0, X_1) \
X_0 &= x \
X_1 &= W_2 + 1 \
\end{cases}
\end{aligned}
$$
假设有两个多项式值的求解，即:
$$
\begin{aligned}
x &= 1, y = 3 \
x &= 2, y = 11 \
\end{aligned}
$$
电路的求解过程会产生两个R1CS Instance-Witness 对:
$$
\begin{aligned}
&(U{(1)}, W{(1)} ) \
&(U{(2)}, W{(2)} ) \
&其中\begin{cases}
W_{(1)} &= [1, 1, 2, 0] \
W_{(2)} &= [4, 8, 10, 0] \
U{(1)} &= [\widetilde{W{(1)}}, [1, 3]] \
U{(2)} &= [\widetilde{W{(2)}}, [2, 11]] \
\end{cases}
\end{aligned}
$$
正常情况下，SNARK Prover 由这两个R1CS Instance-Witness 对产生的约束，最终生成对应的proof，递交给SNARK Verifier。如果每个R1CS Instance-Witness 对有N个约束，那么上面的2个R1CS Instance-Witness 对的proof size就会变成2N，k个R1CS Instance-Witness 对就会有kN个约束。那么是否能对proof 的数量做一下压缩，变成1个R1CS Instance-Witness 对的约束，也就是N个约束？
<br />
NIFS的愿景就是SNARK Prover 把众多R1CS Instance-Witness 对压缩成一个，最终只生成一个proof，递交给SNARK Verifier。那么问题来了：
- 如何保证fold的正确性？
- 如何保证fold与不fold效果一致？
这样才能在保证目标相同的情况下，降低proof size，从而实现性能上的飞越，这也是整个zk领域正在突破的方向。这两个问题会伴随着这一系列章节，希望系列专题的最后大家都会找到自己的解释。
NIFS 的两个角色
NIFS Prover 和NIFS Verifier，确切地说还有一个除他们之外的角色，我们估且叫它第三者，它们的任务概括一下：
NIFS 详尽的执行步骤
-
【第三方】分别初始化一个空的relaxed R1CS Instance $U$和一个空的relaxed R1CS Witness $W$，分别用来接收所有即将要fold的R1CS Instance和 R1CS Witness
<br />
-
【NIFS Prover】 针对第一个Instance-Witness pair对$(U(1),W(1))$，$x=1$对应的Instance-Witness pair对，离线进行fold 操作，内部通过transcript 生成非交互式challenge factor $r$，最终产出NIFS Verifier所需要的中间变量$\widetilde{T}$和 fold之后的Instance-Witness pair对 $(U′,W′)$
<br />
-
【NIFS Verifier】 同样针对第一个Instance $U(1)$，$x=1$对应的Instance，线上进行fold操作，内部同样通过transcript 生成非交互式challenge factor $r$，最终产出fold 之后的relaxed R1CS Instance $U′′$
<br />
-
【第三方】校验此次fold的过程是否正确
$$
\begin{aligned}
U' &== U''
\begin{cases}
\text{if true we can say } U'' \text{ is satisfiable only if } U' &\stackrel{satisfiable}\longleftarrow W' \
\text{if false we can say } U'' \text{ is not satisfiable } \
\end{cases}
\end{aligned}
$$
<br />
- 【第三方】如果上面的校验通过，更新relaxed R1CS Instance $U $和relaxed R1CS Witness $W$
$$
U = U' \
W = W' \
$$
-
循环步骤2 - 5的过程，fold 第二个Instance-Witness pair对$(U(2),W(2))$，$x=2$对应的Instance-Witness pair对，最后再更新relaxed R1CS Instance-Witness pair对$(U, W)$
<br />
-
【第三方】最终得到fold后的relaxed Instance-Witness pair对$(U,W)$，在一系列fold的过程中不管是NIFS Prover 内部还是第三方，都没有验证$R1CS$ $satisfiable$ 的性质，也就是$U' \stackrel{satisfiable}\longleftarrow W′$，但需要对最终的relaxed Instance-Witness pair对做验证
$$
\begin{aligned}
Z &= [W'.W, U'.u, U'.X] \
&\begin{cases}
AZ \circ BZ &\stackrel{?} = U'.u * CZ + W'.E \
U'.\widetilde{W} &\stackrel{?}= commit(W'.W) \
\end{cases}
\end{aligned}
$$
后续
理解记住NIFS的整体逻辑很重要，是整个NOVA的核心，它虽然看起来并不复杂，比较直白，非常make sense，但后面引入circuit 之后，尤其是引入recursive snark后就会让人忘记NIFS的本质。
