【二】NOVA 系列之circuit

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

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

近期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 />

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

circuit1.drawio.png

本章节重点在梳理电路的设计逻辑,图中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的部分添加进来,使得整个逻辑更加完整,对电路设计的理解会更透彻。

点赞 2
收藏 1
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
白菜
白菜
0x6b50...a615
crypto