近期NOVA作为当前ZK领域热门的Folding Scheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：

• [Pederson and Poseidon]()
• [R1CS and relaxed R1CS]()
• NIFS
• [Circuit]()
• [RecursiveSNARK]()
• [CompressedSNARK]()

<br />

希望通过详尽且直白的逻辑能够把NOVA整个框架的设计理念传达到读者，最终落地到实际的crypto应用场景中。 <br />

其中前两个主题为crypto primitives，后四个主题为NOVA论文中的主线内容。本章节主题可能是论文中最令人费解的地方，我们先从宏观上去把握它的脉络，再从细节上去扣它的设计理念。

!建议：最好配合着paper去理解，paper上找不到的答案或许这里可以给你-_-

本章节内容涉及到NOVA一些非常巧妙的设计理念，内容有些干，所以多喝水-）

需要了解的一些术语

• relaxed R1CS 是NOVA中为方便folding而对标准R1CS的拓展，细节部分在后面章节会展开，这里大致了解一下它的等式：

$$ \begin{aligned}

AZ \circ BZ &= u* CZ + E \

Z &= (W, u, X) \

\end{aligned} $$

• SAT，是R1CS 或者 relaxed R1CS Instance-Witness pair对$(U', W') $ satisfactory 的简单表述，包含两部分，R1CS 等式验证和commitment验证，具体的验证逻辑如下：

$$ \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的整个逻辑中有三个重要角色，NIFS Prover 、NIFS Verifier和除它们之外的第三者，它们的任务分别是：

• NIFS Prover (离线进行) 每个step 需要分别对两个R1CS Instance 进行fold，生成一个relaxed R1CS Instance，和两个R1CS Witness 进行fold，生成一个relaxed R1CS Witness <br />

• NIFS Verifier (线上进行) 每个step 只需要对两个R1CS Instance进行fold，生成一个relaxed R1CS Instance <br />

• 第三者负责对两者每个step fold后的relaxed R1CS Instance 进行匹配验证是否相等，以及一系列step fold之后最后生成的R1CS Instance-Witness pair对进行SAT校验 <br />

我们总结一下：NIFS要做的就是，SNARK Prover对业务电路经过N次step 迭代后生成的proof进行fold，最终只生成一个proof，并递交给SNARK Verifier 进行验证。前提是，SNARK Prover 它自己要保证fold的正确性，而且fold 与 不fold效果一致。本系列专题的核心就是为了解决这两个问题。

circuit 的由来和目标

一句话，这里的circuit 就是NIFS Verifier的电路。那么问题来了：

1. 为什么是NIFS Verifier电路？
2. 这里的NIFS Verifier电路与上节NIFS的逻辑有什么关系？
3. 业务电路呢？ <br />

这里我们把整个逻辑再梳理一遍，尽量弄清楚NIFS Verifier出现的原委，排除一切障碍。

为什么要有NIFS Verifier 电路

其实我们最终的目的是要fold 两个标准的R1CS Witness

$$ \begin{aligned}

\begin{rcases}

AZ_1 \circ BZ_1 = CZ_1 \

AZ_2 \circ BZ_2 = CZ_2 \

\end{rcases} \stackrel{fold} \Longrightarrow AZ \circ BZ = CZ

\end{aligned} $$

但如何保证Prover 不做假，保证fold的正确性？所以就出现了Verifier，需要对Prover fold之后的R1CS Witness进行验证。 <br />

但为了保证privacy 需要对Witness进行commit，所以就有与R1CS Witness匹配的R1CS Instance。Verifier 表面上只fold Instance，本质上跟Prover fold Witness是等效的，前提是它们之间满足R1CS SAT。为了保证验证逻辑的完备性，Prover 同样也要fold Instance，然后把二者fold的Instance 放在一起比对，看它们是否相等。 <br />

到这儿，fold 的正确与否的校验逻辑就通了。

谁来校验fold的结果

在上一章节NIFS中我们提到，判定Prover 与 Verifier fold的Instance 是否相等是由第三方来完成的，这确实是make sense的，由第三方来做鉴定保证公平公正。但是， <br />

NOVA的设计理念是想实现SNARK Prover 自证，这个校验过程不会与第三方有交互。那么 NOVA是如何做到的？这也是circuit 的电路设计非常巧妙的地方，值得研究学习！这里先把答案写出来，我们后面再剖析它： <br />

当前step 对应的电路会校验前一个step NIFS Prover 离线fold的Instance 与 NIFS Verifier 线上fold的Instance 是否相等。 <br />

为什么可以这样？因为当前step 的NIFS Verifier电路对于上一个step NIFS Verifier电路和离线的NIFS Prover 来说就是第三方，所以这么设计逻辑上是走得通的。 <br />

细心的读者可能还会存在一个疑虑，既然是当前step 校验上一个step，那最后一个step谁来校验？答案很简单，在电路的外面执行。在最后一个step后，电路外面会check 一下最后一个step Primary/Secondary 电路fold的结果是否分别与离线fold的结果相等。

回答上面的三个问题

1. 因为NIFS Prover 本来就是离线进行的，线上验证交给电路的Verifier
2. 跟上一章节的NIFS 关系，到这儿应该比较清晰了，就是把线上fold的任务 和 校验的任务全部放在NIFS Verifier 电路里做了
3. 业务电路，其实也是放在NIFS Verifier 电路里了，会在适当的时候触发业务逻辑，这个后面会展开 <br />

NIFS Verifier 电路的任务

NIFS Verifier 电路的任务有两个：其一，完成当前step 既定的fold工作，其二，完成上一个step的验证工作。

双簧电路

所谓双簧，就是为了同一全局目标由两个互相搭档的Primary-Secondary 电路。 <br />

如果你去看NOVA的原始论文，其中会提到通过Fiat-Shamir Transform 实现non-interactive，然后把当前step fold后的Instance 进行hash，并输出...... 估计有一大批读者都会倒在这个地方，怎么输出，输出后怎么接上，后面怎么验证上面说的两个Instance 是否相等？ <br />

先帖一张双簧电路最简单的逻辑结构图：

本章节重点在梳理电路的设计逻辑，图中relaxed R1CS Instance是离线产出的，我们会在后面的章节中详细展开。 <br />

这是一个简洁版的两个step的逻辑流图，到目前为止我们大概明确这么几点：

1. Primary 电路的核心任务是触发业务电路$F $的forward 计算 <br />

2. 业务电路$F $forward 计算产出的R1CS Witness 经过commit 之后变成R1CS Instance，传递给Secondary 电路 <br />

3. Secondary 电路的核心任务是fold 当前step业务电路的R1CS Instance 和 上一次fold后的relaxed R1CS Instance <br />

4. Secondary 电路的业务电路是一个空的$Trivial $电路，所以触发它结果仍然为空，但它仍然会把当前step fold后的relaxed R1CS Instance以hash的形式向后面传递，保证下一个step 的Secondary 能够接收到 <br />

下面部分会尽可能详尽地勾画出电路设计的巧妙之处。

双簧电路的宏观描述

【Primary NIFS Verifier 电路】接收Secondary 电路的吐出来的R1CS Instance，线上进行fold 操作。 <br />

$$ \begin{rcases}

U_{secondary} \

u_{secondary} \

\textcolor{green}{\text{\textcircled 1} u{secondary}.x[0]} \stackrel{?} = \textcolor{red}{\text{\textcircled 1} H(U{secondary})} \

\end{rcases}

\underset{z_{i+1} = F(z_i)} {\overset{Fold}\Longrightarrow }

\begin{cases}

\textcolor{blue}{\text{\textcircled 2} u{secondary}.x[1]} \longrightarrow \textcolor{blue}{u{primary}'.x[0]} \

\textcolor{green}{\text{\textcircled 3} U{secondary}''} \stackrel{Hash} \longrightarrow \textcolor{green}{u{primary}'.x[1]} \

w_{primary}' \

\end{cases} $$ <br />

【Secondary NIFS Verifier 电路】接收Primary 电路吐出来的R1CS Instance，线上进行fold 操作。 <br />

$$ \begin{rcases}

U_{primary} \

u_{primary}' \

\textcolor{blue}{\text{\textcircled 1} u{primary}'.x[0]} \stackrel{?} = \textcolor{teal}{\text{\textcircled 1} H(U{primary})} \

\end{rcases}

\stackrel{Fold}\Longrightarrow

\begin{cases}

\textcolor{green}{\text{\textcircled 2} u{primary}'.x[1] \stackrel{?} \longrightarrow u{secondary}'.x[0]} \

\textcolor{blue}{\text{\textcircled 3} U{primary}''} \stackrel{Hash}\longrightarrow \textcolor{blue}{u{secondary}'.x[1]} \

w_{secondary}'

\end{cases} $$

双簧电路更多的细节

验证逻辑

我们可以看到在fold 的左边(之前)需对即将进行fold的两个Instance 进行校验，判断R1CS Instance中是否包含relaxed R1CS Instance的Hash值。

这一步的校验就是上面反复提到的如何验证离线fold的Instance 与电路里fold的 Instance是否相等。 <br />

注意，这里的trace逻辑比较耐人寻味，拿Primary NIFS Verifier 电路，我们可以展开看一下。 <br />

先trace 等式左边的值

$$ \textcolor{green}{\text{\textcircled 1}} \longrightarrow \text{last step of } \textcolor{green}{\text{\textcircled 2}} \longrightarrow \text{last step of } \textcolor{green}{\text{\textcircled 3}} $$

最终得到的是上一个step 的Primary NIFS Verifier 电路中fold Secondary的结果$U_{secondary}′′$ <br />

再trace 等式右边的值(这里涉及到离线计算的部分，我们会在后面章节展开)

$$ \textcolor{red}{\text{\textcircled 1}} \longrightarrow \text{last step of } \textcolor{red}{\text{\textcircled 2}} $$

最终得到的是上一个step 的Primary NIFS Prover 离线fold Secondary的结果$U_{secondary}′$

所以最终它要验证上一个step 中离线fold Secondary 的结果与线上或者电路中fold Secondary 的结果是否相等，从而保证电路中fold Secondary的结果是satisfiable的：

$$ \begin{aligned}

U{prmary}' &== U{prmary}''

\begin{cases}

\text{if true we can say } U{prmary}'' \text{ is satisfiable only if } U{prmary}' &\stackrel{satisfiable}\longleftarrow W_{prmary}' \

\text{if false we can say } U_{prmary}'' \text{ is not satisfiable } \

\end{cases}

\end{aligned} $$

业务电路forward计算

这个是在fold之后被触发的 $$ z_{i + 1} = F(z_i) $$ 它的触发会伴随着相应的Witness 输出

输出与接收

1. 上一个step 中Primary Fold后的relaxed R1CS Instance的Hash值 <br />

2. 当前Secondary Fold后的relaxed R1CS Instance的Hash值 <br />

3. 当前电路的所有Witness 包括业务电路的Witness全部输出，生成一个新的R1CS Witness <br />

4. 对新生成的R1CS Witness 进行commit 得到新的R1CS Instance <br />

5. 其中这个新的R1CS Instance 会接收上面的两个hash值，作为public variable 丢到$x$中 <br />

Secondary 电路的逻辑跟上面的类似，只是它的业务电路为空的而已，这里就不再展开。 目前为止，我们明确一点就好，Primary 核心任务是业务电路的forward 计算，Secondary的核心任务才是真正的fold操作。

总结与后续

到目前为止，我们已经把电路在NOVA 整个scheme中的定位，以及它具体的任务，还有设计的技巧都尽可能地表达清楚了，希望能给读者带来paper 之外更多的干货。 <br />

接下来的章节，会把NIFS 离线fold的部分添加进来，使得整个逻辑更加完整，对电路设计的理解会更透彻。