【三】NOVA系列之RecursiveSNARK

白菜
更新于 2023-06-21 22:04
阅读 2255

近期NOVA作为当前ZK领域热门的FoldingScheme解决方案，备受工业界追捧，该系列专题将逐一拆解它：Pederson and Poseidon ， R1CS and relaxed R1CS， NIFS， Circuit， RecursiveSNARK， CompressedSNARK。

近期[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](https://learnblockchain.cn/article/5993)
* [RecursiveSNARK]()
* [CompressedSNARK]()

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

其中前两个主题为crypto primitives，后四个主题为NOVA论文中的主线内容。本章节内容基本上是上两个章节[NIFS](https://learnblockchain.cn/article/5978) 和[Circuit](https://learnblockchain.cn/article/5993)的整合，在整个SNARK里面，这部分对应的是**SNARK Prover**，后面加入CompressedSNARK 后就是一套完整的zkSNARK了。

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

---
# 你可能已经知晓的

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

上一章节中，我们把电路部分，也就是 Primary NIFS.Verifier 和 Secondary NIFS.Verifier 单独拎了出来。本章节我们会加入离线部分，也就是**Primary NIFS.Prover**和 **Secondary NIFS.Prover**，使得NOVA整个fold scheme更加完整。

---
# 宏观结构

先上一张完整版的交互逻辑图

![ivc.drawio.png](https://img.learnblockchain.cn/attachments/2023/06/5uogaa0z6493034f03d9d.png)

重点明确这么几点：
- SNARK Prover 这边本质上就是一套NIFS 框架，分离线和线上(电路)两部分

- 离线部分对应到图中的NIFS.Prover，它的输入为$(U, u, W, w)$

- 线上部分对应到图中的NIFS.Verifier，电路程序，它的输入为$(U, u)$

- 每个step 包含两个NIFS，Primary NIFS  和 Secondary NIFS

>  它们分别包含上面提到的分离线和线上两部分，Primary NIFS.Prover、Primary NIFS.Verifier 和 Secondary NIFS.Prover、Secondary NIFS.Verifier

- Primary NIFS与 Secondary NIFS之间的唯一的交互就是从电路**Constrain System** 中抽离出来的$(u, w)$

> 当前step 的Primary 电路CS中抽离出来的$(u, w)$ 交给当前step 的Secondary NIFS，当前step 的Secondary 电路CS中抽离出来的$(u, w)$ 交给下一个step 的Primary NIFS

----
#  NIFS Prover 与 NIFS Verifier

关于NIFS Prover 与 NIFS Verifier之间的关系，在上章节[NIFS](https://learnblockchain.cn/article/5993) 中"[为什么要有NIFS Verifier电路](https://learnblockchain.cn/article/5993#为什么要有NIFS%20Verifier%20电路)" 和 “[谁来校验fold的结果](https://learnblockchain.cn/article/5993#谁来校验fold的结果)” 已经表达得很清晰了，这里我们明确这么几点：

- **NIFS Verifier电路是离线NIFS Prover 的线上版本**，只是fold的Instance，没有Witness而已

- 当前step 的 NIFS Verifier电路在fold Instance 之前，会校验上一个step 离线NIFS Prover fold后的Instance $U'$与 线上NIFS Verifier(电路)fold后的Instance $U''$ 是否相等

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

---
# Primary NIFS 与 Secondary NIFS

我们在上一章节NIFS中大概勾画出[Primary NIFS Verifier 与 Secondary NIFS Verifier两个电路的交互逻辑](https://learnblockchain.cn/article/5993#双簧电路的宏观描述)，同样，这里我们补上离线部分，Primary NIFS Prover 与 Secondary NIFS Prover。

【Primary NIFS Prover】接收上一个step 中Secondary NIFS Verifier电路的吐出来的R1CS Instance，离线进行fold操作，被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover fold后的结果。同样$(W, w)$ 为对应的Witness。

$$
\begin{rcases}

(U_{secondary}, W_{secondary}) \\

(u_{secondary}, w_{secondary}) \\

\end{rcases}

\stackrel{Fold}\Longrightarrow

\underline{(\textcolor{red}{\text{\textcircled 2}U_{secondary}'}, W_{secondary}')}
$$

【Primary NIFS Verifier 电路】接收上一个step 中Secondary 电路的吐出来的R1CS Instance，线上进行fold 操作；被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover 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 Prover】接收当前step中Primary NIFS Verifier电路的吐出来的R1CS Instance，离线进行fold操作；被fold的relaxed R1CS Instance 为上一个step 中Secondary NIFS Prover fold后的结果。同样$(W, w)$ 为对应的Witness。

$$
\begin{rcases}

(U_{primary}, W_{primary}) \\

(u_{primary}', w_{primary}') \\

\end{rcases}

\overset{Fold} {\Longrightarrow}

\underline{(\textcolor{teal}{\text{\textcircled 2} U_{primary}'}, W_{primary}')}
$$

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

---
# NIFS 验证的细节

NIFS 验证就是校验离线NIFS.Prover old后的Instance $U'$与 线上NIFS.Verifier 电路fold后的Instance $U''$是否相等，即
$$
U' == U''
$$

在上一章节NIFS中[电路验证逻辑](https://learnblockchain.cn/article/5993#验证逻辑)有详细地trace过等式左边部分，上面我们已经补上离线NIFS.Prover部分，这里我们再review一下trace的逻辑，看看究竟是不是那么回事儿。

trace主要解决两个问题：
1. 为什么R1CS instance $u$中藏着的是上一个step 的线上NIFS.Verifier(电路)fold后的结果$U''$?

2. 为什么被fold的relaxed R1CS instance $U$是上一个step的离线NIFS.Prover fold后的结果$U'$?

所以，

\begin{rcases}
u \\
U

\end{rcases} \stackrel{fold} \Longrightarrow U \\

u.x_0 \stackrel{?}= Hash(U) \iff U' \stackrel{?}= U''

---
## Primary NIFS Verifier 电路trace 的过程
- 先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$之后的结果$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$之后的结果$U_{secondary}′$

- 判断两者是否相等

$$
\text{if }U_{secondary}′  = U_{secondary}′′ \text{ we can say } U_{secondary}' \text{ is satisfiable} \\
\text{if and only if } U_{secondary}′ \stackrel{satisfiable} \longleftarrow W'
$$

---

## Secondary NIFS Verifier 电路trace 的过程
- 先trace 等式左边的值

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

得到的是上一个step 的Secondary NIFS Verifier 电路中fold Primary电路吐出来的$u$之后的结果$U_{primary}′′$

- 再trace 等式右边的值

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

得到的是上一个step 的Secondary NIFS Prover 离线fold Primary电路吐出来的$u$之后的结果$U_{primary}′$

- 判断两者是否相等

$$
\text{if }U_{primary}′  = U_{primary}′′ \text{ we can say } U_{primary}' \text{ is satisfiable} \\
\text{if and only if } U_{primary}′ \stackrel{satisfiable} \longleftarrow W_{primary}'
$$

---
# 总结与后续

到目前为止，NOVA的核心内容，也就是SNARK Prover部分就已经完整了。

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

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

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

其中前两个主题为crypto primitives，后四个主题为NOVA论文中的主线内容。本章节内容基本上是上两个章节NIFS 和Circuit的整合，在整个SNARK里面，这部分对应的是SNARK Prover，后面加入CompressedSNARK 后就是一套完整的zkSNARK了。

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

你可能已经知晓的

上一章节中，我们把电路部分，也就是 Primary NIFS.Verifier 和 Secondary NIFS.Verifier 单独拎了出来。本章节我们会加入离线部分，也就是Primary NIFS.Prover和 Secondary NIFS.Prover，使得NOVA整个fold scheme更加完整。

宏观结构

先上一张完整版的交互逻辑图

重点明确这么几点：

SNARK Prover 这边本质上就是一套NIFS 框架，分离线和线上(电路)两部分
离线部分对应到图中的NIFS.Prover，它的输入为$(U, u, W, w)$
线上部分对应到图中的NIFS.Verifier，电路程序，它的输入为$(U, u)$
每个step 包含两个NIFS，Primary NIFS 和 Secondary NIFS

它们分别包含上面提到的分离线和线上两部分，Primary NIFS.Prover、Primary NIFS.Verifier 和 Secondary NIFS.Prover、Secondary NIFS.Verifier

Primary NIFS与 Secondary NIFS之间的唯一的交互就是从电路Constrain System 中抽离出来的$(u, w)$

当前step 的Primary 电路CS中抽离出来的$(u, w)$ 交给当前step 的Secondary NIFS，当前step 的Secondary 电路CS中抽离出来的$(u, w)$ 交给下一个step 的Primary NIFS

NIFS Prover 与 NIFS Verifier

关于NIFS Prover 与 NIFS Verifier之间的关系，在上章节NIFS 中"为什么要有NIFS Verifier电路" 和 “谁来校验fold的结果” 已经表达得很清晰了，这里我们明确这么几点：

NIFS Verifier电路是离线NIFS Prover 的线上版本，只是fold的Instance，没有Witness而已
当前step 的 NIFS Verifier电路在fold Instance 之前，会校验上一个step 离线NIFS Prover fold后的Instance $U'$与线上NIFS Verifier(电路)fold后的Instance $U''$ 是否相等

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

Primary NIFS 与 Secondary NIFS

我们在上一章节NIFS中大概勾画出Primary NIFS Verifier 与 Secondary NIFS Verifier两个电路的交互逻辑，同样，这里我们补上离线部分，Primary NIFS Prover 与 Secondary NIFS Prover。

$$ \begin{rcases}

(U{secondary}, W{secondary}) \

(u{secondary}, w{secondary}) \

\end{rcases}

\stackrel{Fold}\Longrightarrow

\underline{(\textcolor{red}{\text{\textcircled 2}U{secondary}'}, W{secondary}')} $$

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

$$ \begin{rcases}

(U{primary}, W{primary}) \

(u{primary}', w{primary}') \

\end{rcases}

\overset{Fold} {\Longrightarrow}

\underline{(\textcolor{teal}{\text{\textcircled 2} U{primary}'}, W{primary}')} $$

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

NIFS 验证的细节

NIFS 验证就是校验离线NIFS.Prover old后的Instance $U'$与线上NIFS.Verifier 电路fold后的Instance $U''$是否相等，即 $$ U' == U'' $$

在上一章节NIFS中电路验证逻辑有详细地trace过等式左边部分，上面我们已经补上离线NIFS.Prover部分，这里我们再review一下trace的逻辑，看看究竟是不是那么回事儿。

trace主要解决两个问题：

为什么R1CS instance $u$中藏着的是上一个step 的线上NIFS.Verifier(电路)fold后的结果$U''$?
为什么被fold的relaxed R1CS instance $U$是上一个step的离线NIFS.Prover fold后的结果$U'$?

所以，

\begin{rcases} u \ U

\end{rcases} \stackrel{fold} \Longrightarrow U \

u.x_0 \stackrel{?}= Hash(U) \iff U' \stackrel{?}= U''

Primary NIFS Verifier 电路trace 的过程

先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$之后的结果$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$之后的结果$U_{secondary}′$

判断两者是否相等

$$ \text{if }U{secondary}′ = U{secondary}′′ \text{ we can say } U{secondary}' \text{ is satisfiable} \ \text{if and only if } U{secondary}′ \stackrel{satisfiable} \longleftarrow W' $$

Secondary NIFS Verifier 电路trace 的过程

先trace 等式左边的值

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

得到的是上一个step 的Secondary NIFS Verifier 电路中fold Primary电路吐出来的$u$之后的结果$U_{primary}′′$

再trace 等式右边的值

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

得到的是上一个step 的Secondary NIFS Prover 离线fold Primary电路吐出来的$u$之后的结果$U_{primary}′$

判断两者是否相等

$$ \text{if }U{primary}′ = U{primary}′′ \text{ we can say } U{primary}' \text{ is satisfiable} \ \text{if and only if } U{primary}′ \stackrel{satisfiable} \longleftarrow W_{primary}' $$

总结与后续

到目前为止，NOVA的核心内容，也就是SNARK Prover部分就已经完整了。

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

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

【三】NOVA系列之RecursiveSNARK

你可能已经知晓的

宏观结构

NIFS Prover 与 NIFS Verifier

Primary NIFS 与 Secondary NIFS

NIFS 验证的细节

Primary NIFS Verifier 电路trace 的过程

Secondary NIFS Verifier 电路trace 的过程

总结与后续

0 条评论

文章目录