【二】NOVA 系列之circuit

白菜
更新于 2023-06-19 23:13
阅读 2328

近期NOVA作为当前ZK领域热门的FoldingScheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：PedersonandPoseidonR1CSNIFSCircuitRecursiveSNARKCompressedSNARK希望通过详尽且直白的逻辑能够把NOVA

近期[NOVA](https://eprint.iacr.org/2021/370.pdf)作为当前ZK领域热门的Folding Scheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：
* [Pederson and Poseidon]()
* [R1CS and relaxed R1CS]()
* [NIFS](https://learnblockchain.cn/article/5978)
* [Circuit]()
* [RecursiveSNARK]()
* [CompressedSNARK]()

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

其中前两个主题为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](https://learnblockchain.cn/article/5978)的整个逻辑中有三个重要角色，NIFS Prover 、NIFS Verifier和除它们之外的第三者，它们的任务分别是：

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

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

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

*我们总结一下：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](https://learnblockchain.cn/article/5978)的逻辑有什么关系？
3. 业务电路呢？

这里我们把整个逻辑再梳理一遍，尽量弄清楚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进行验证。

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

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

##  谁来校验fold的结果

在上一章节[NIFS](https://learnblockchain.cn/article/5978)中我们提到，判定Prover 与 Verifier fold的Instance 是否相等是由第三方来完成的，这确实是make sense的，由第三方来做鉴定保证公平公正。但是，

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

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

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

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

## 回答上面的三个问题

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

## NIFS Verifier 电路的任务

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

---

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

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

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

![circuit1.drawio.png](https://img.learnblockchain.cn/attachments/2023/06/D9s5aikY648b364332e6c.png)

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

这是一个简洁版的两个step的逻辑流图，到目前为止我们大概明确这么几点：
1. Primary 电路的核心任务是触发业务电路$F $的forward 计算

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

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

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

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

----
# 双簧电路的宏观描述

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

$$
\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}
$$

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

$$
\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是否相等**。

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

---
先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}′′$

再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值

2. 当前Secondary Fold后的relaxed R1CS Instance的Hash值

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

4. 对新生成的R1CS Witness 进行commit 得到新的R1CS Instance

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

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

---
# 总结与后续

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

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

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

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

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

!建议：最好配合着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
NIFS Verifier (线上进行) 每个step 只需要对两个R1CS Instance进行fold，生成一个relaxed R1CS Instance
第三者负责对两者每个step fold后的relaxed R1CS Instance 进行匹配验证是否相等，以及一系列step fold之后最后生成的R1CS Instance-Witness pair对进行SAT校验

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

circuit 的由来和目标

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

为什么是NIFS Verifier电路？
这里的NIFS Verifier电路与上节NIFS的逻辑有什么关系？
业务电路呢？

这里我们把整个逻辑再梳理一遍，尽量弄清楚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进行验证。

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

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

谁来校验fold的结果

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

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

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

回答上面的三个问题

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

NIFS Verifier 电路的任务

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

双簧电路

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

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

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

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

Primary 电路的核心任务是触发业务电路$F $的forward 计算
业务电路$F $forward 计算产出的R1CS Witness 经过commit 之后变成R1CS Instance，传递给Secondary 电路
Secondary 电路的核心任务是fold 当前step业务电路的R1CS Instance 和上一次fold后的relaxed R1CS Instance
Secondary 电路的业务电路是一个空的$Trivial $电路，所以触发它结果仍然为空，但它仍然会把当前step fold后的relaxed R1CS Instance以hash的形式向后面传递，保证下一个step 的Secondary 能够接收到

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

双簧电路的宏观描述

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

$$ \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} $$

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

$$ \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是否相等。

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

先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}′′$

再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 输出

输出与接收

上一个step 中Primary Fold后的relaxed R1CS Instance的Hash值
当前Secondary Fold后的relaxed R1CS Instance的Hash值
当前电路的所有Witness 包括业务电路的Witness全部输出，生成一个新的R1CS Witness
对新生成的R1CS Witness 进行commit 得到新的R1CS Instance
其中这个新的R1CS Instance 会接收上面的两个hash值，作为public variable 丢到$x$中

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

总结与后续

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

原创
学分: 17
分类: 零知识证明
标签: Nova zkSNARK folding

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

【二】NOVA 系列之circuit

需要了解的一些术语

可能已经知晓的

circuit 的由来和目标

为什么要有NIFS Verifier 电路

谁来校验fold的结果

回答上面的三个问题

NIFS Verifier 电路的任务

双簧电路

双簧电路的宏观描述

双簧电路更多的细节

验证逻辑

业务电路forward计算

输出与接收

总结与后续

0 条评论

文章目录