【一】NOVA 系列之NIFS

  • 白菜
  • 更新于 2023-07-11 09:45
  • 阅读 2752

本系列专题为NOVA系列专题,分六个主题:PedersonandPoseidon, R1CS, NIFS, Circuit, RecursiveSNARK, CompressedSNARK希望通过详尽且直白的阐述能够把NOVA整个框架的设计理念传达到读者,最终落地到实际的crypto应用场景中。

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

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

<br />

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

其中前两个主题为crypto primitives,后四个主题为NOVA论文中的主线内容。本章节主题为论文中最为核心的部分NIFS,全称为None-interactive Folding Scheme,先从宏观上把握NOVA的主脉。

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


在梳理NIFS的逻辑之前,我们先明确一下,NIFS的目标是什么?

需要了解的一些术语

  • $ \widetilde{W} $ 代表对W的pederson commitment,可以是scaler field的标量也可以是向量,细节我们会在后面的章节中展开。这里我们只需要简单地知道pederson commitment是crypto 中private 数据的public表现形式,由verifier 掌握,它是可以被verifier打开验证的,因此它能够完全代表private 数据 <br />

  • challenge factor $r$,它是一个poseidon hash值,细节部分我们也会在后面的章节中展开。这里我们需要了解的是,通过它实现Non-interactive,比如说在KZG10 commitment中,需要Verifier 产出challenge factor $r$并递交给Prover,它是一种Interactive 的方式 <br />

  • relaxed R1CS,也是NOVA为了实现recursive folding而比较创新的一点,paper中有着重讲解,细节部分我们也会在后面展开 <br />

  • satisfiable,是校验(U, W)满足R1CS等式及pederson commitment 的一种表达


NIFS的目标

假定业务电路的表达式: $$ y = x^3 + x + 1 $$

则,业务电路输出的R1CS witness: $$ \begin{aligned}

W &= (W_0, W_1, W_2, W_3) \

其中&\begin{cases}

W_0 &= x * x \

W_1 &= W_0 * x \

W_2 &= W_1 + x \

W_3 &= 0 \

\end{cases}

\end{aligned} $$

则,在x 和 y为public情况下,业务电路输出的R1CS instance:

$$ \begin{aligned}

U &= (\widetilde{W}, X) \

其中&\begin{cases} X &= (X_0, X_1) \

X_0 &= x \

X_1 &= W_2 + 1 \

\end{cases}

\end{aligned} $$

假设有两个多项式值的求解,即:

$$ \begin{aligned}

x &= 1, y = 3 \

x &= 2, y = 11 \

\end{aligned} $$

电路的求解过程会产生两个R1CS Instance-Witness 对:

$$ \begin{aligned}

&(U{(1)}, W{(1)} ) \

&(U{(2)}, W{(2)} ) \

&其中\begin{cases}

W_{(1)} &= [1, 1, 2, 0] \

W_{(2)} &= [4, 8, 10, 0] \

U{(1)} &= [\widetilde{W{(1)}}, [1, 3]] \

U{(2)} &= [\widetilde{W{(2)}}, [2, 11]] \

\end{cases}

\end{aligned} $$

正常情况下,SNARK Prover 由这两个R1CS Instance-Witness 对产生的约束,最终生成对应的proof,递交给SNARK Verifier。如果每个R1CS Instance-Witness 对有N个约束,那么上面的2个R1CS Instance-Witness 对的proof size就会变成2N,k个R1CS Instance-Witness 对就会有kN个约束。那么是否能对proof 的数量做一下压缩,变成1个R1CS Instance-Witness 对的约束,也就是N个约束? <br />

NIFS的愿景就是SNARK Prover 把众多R1CS Instance-Witness 对压缩成一个,最终只生成一个proof,递交给SNARK Verifier。那么问题来了:

  1. 如何保证fold的正确性?
  2. 如何保证fold与不fold效果一致?

这样才能在保证目标相同的情况下,降低proof size,从而实现性能上的飞越,这也是整个zk领域正在突破的方向。这两个问题会伴随着这一系列章节,希望系列专题的最后大家都会找到自己的解释。


NIFS 的两个角色

NIFS Prover 和NIFS Verifier,确切地说还有一个除他们之外的角色,我们估且叫它第三者,它们的任务概括一下:

  • NIFS Prover (离线进行)同时拥有R1CS Witness 和 R1CS Instance,它需要分别对两个R1CS Instance 进行fold,和两个R1CS Witness 进行fold <br />

  • NIFS Verifier (线上进行)只拥有 R1CS Instance,只需要对两个R1CS Instance进行fold <br />

  • 第三者负责对两者每个step fold后的R1CS Instance 进行匹配校验,以及一系列step fold之后R1CS Instance-Witness pair对进行校验

NIFS 详尽的执行步骤

  1. 【第三方】分别初始化一个空的relaxed R1CS Instance $U$和一个空的relaxed R1CS Witness $W$,分别用来接收所有即将要fold的R1CS Instance和 R1CS Witness <br />

  2. 【NIFS Prover】 针对第一个Instance-Witness pair对$(U(1)​,W(1)​)$,$x=1$对应的Instance-Witness pair对,离线进行fold 操作,内部通过transcript 生成非交互式challenge factor $r$,最终产出NIFS Verifier所需要的中间变量$\widetilde{T}$和 fold之后的Instance-Witness pair对 $(U′,W′)$ <br />

  3. 【NIFS Verifier】 同样针对第一个Instance $U(1)​$,$x=1$对应的Instance,线上进行fold操作,内部同样通过transcript 生成非交互式challenge factor $r$,最终产出fold 之后的relaxed R1CS Instance $U′′$ <br />

  4. 【第三方】校验此次fold的过程是否正确

$$ \begin{aligned}

U' &== U''

\begin{cases}

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

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

\end{cases}

\end{aligned} $$

<br />

  1. 【第三方】如果上面的校验通过,更新relaxed R1CS Instance $U $和relaxed R1CS Witness $W​$

$$ U = U' \

W = W' \ $$

  1. 循环步骤2 - 5的过程,fold 第二个Instance-Witness pair对$(U(2)​,W(2)​)​$,$x=2$对应的Instance-Witness pair对,最后再更新relaxed R1CS Instance-Witness pair对$(U, W)$ <br />

  2. 【第三方】最终得到fold后的relaxed Instance-Witness pair对$(U,W)$,在一系列fold的过程中不管是NIFS Prover 内部还是第三方,都没有验证$R1CS$ $satisfiable$ 的性质,也就是$U' \stackrel{satisfiable}\longleftarrow W′$,但需要对最终的relaxed Instance-Witness pair对做验证

$$ \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的整体逻辑很重要,是整个NOVA的核心,它虽然看起来并不复杂,比较直白,非常make sense,但后面引入circuit 之后,尤其是引入recursive snark后就会让人忘记NIFS的本质。

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

0 条评论

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