近期NOVA作为当前ZK领域热门的FoldingScheme解决方案,备受工业界追捧,该系列专题将逐一拆解它:Pederson and Poseidon , R1CS and relaxed R1CS, NIFS, Circuit, RecursiveSNARK, CompressedSNARK。
近期NOVA作为当前ZK领域热门的Folding Scheme解决方案,备受工业界追捧,该系列专题将逐一拆解它:
<br />
希望通过详尽且直白的逻辑能够把NOVA整个框架的设计理念传达到读者,最终落地到实际的crypto应用场景中。 <br />
其中前两个主题为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更加完整。 <br />
先上一张完整版的交互逻辑图
重点明确这么几点:
SNARK Prover 这边本质上就是一套NIFS 框架,分离线和线上(电路)两部分 <br />
离线部分对应到图中的NIFS.Prover,它的输入为$(U, u, W, w)$ <br />
线上部分对应到图中的NIFS.Verifier,电路程序,它的输入为$(U, u)$ <br />
每个step 包含两个NIFS,Primary NIFS 和 Secondary NIFS
它们分别包含上面提到的分离线和线上两部分,Primary NIFS.Prover、Primary NIFS.Verifier 和 Secondary NIFS.Prover、Secondary NIFS.Verifier
<br />
当前step 的Primary 电路CS中抽离出来的$(u, w)$ 交给当前step 的Secondary NIFS,当前step 的Secondary 电路CS中抽离出来的$(u, w)$ 交给下一个step 的Primary NIFS
<br />
关于NIFS Prover 与 NIFS Verifier之间的关系,在上章节NIFS 中"为什么要有NIFS Verifier电路" 和 “谁来校验fold的结果” 已经表达得很清晰了,这里我们明确这么几点: <br />
NIFS Verifier电路是离线NIFS Prover 的线上版本,只是fold的Instance,没有Witness而已 <br />
当前step 的 NIFS Verifier电路在fold Instance 之前,会校验上一个step 离线NIFS Prover fold后的Instance $U'$与 线上NIFS Verifier(电路)fold后的Instance $U''$ 是否相等 <br />
$$ \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} $$
我们在上一章节NIFS中大概勾画出Primary NIFS Verifier 与 Secondary NIFS Verifier两个电路的交互逻辑,同样,这里我们补上离线部分,Primary NIFS Prover 与 Secondary NIFS Prover。 <br />
【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}')} $$ <br />
【Primary NIFS Verifier 电路】接收上一个step 中Secondary 电路的吐出来的R1CS Instance,线上进行fold 操作;被fold的relaxed R1CS Instance 为上一个step 中Primary NIFS Prover 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 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}')} $$ <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} $$
NIFS 验证就是校验离线NIFS.Prover old后的Instance $U'$与 线上NIFS.Verifier 电路fold后的Instance $U''$是否相等,即 $$ U' == U'' $$
在上一章节NIFS中电路验证逻辑有详细地trace过等式左边部分,上面我们已经补上离线NIFS.Prover部分,这里我们再review一下trace的逻辑,看看究竟是不是那么回事儿。 <br />
trace主要解决两个问题:
为什么R1CS instance $u$中藏着的是上一个step 的线上NIFS.Verifier(电路)fold后的结果$U''$? <br />
为什么被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''
$$
$$ \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}′′$ <br />
$$ \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' $$
$$ \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}′′$ <br />
$$ \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部分就已经完整了。 <br />
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!