NOVA from scratch

  • 白菜
  • 更新于 2023-08-24 22:42
  • 阅读 2450

写在前面的时隔两个多月终于有机会给NOVAresearch做个了结,期间一直没有机会读revisitingnova,认真读完之后感触比较深,写点儿东西记录下来,也算给自己之前的research一个交待。当然期间也不乏出现hypernova/protostar这些可能更接近“真实战场”的

写在前面的

时隔两个多月终于有机会给NOVA research做个了结,期间一直没有机会读revisiting nova ,认真读完之后感触比较深,写点儿东西记录下来,也算给自己之前的research一个交待。

<br />

当然期间也不乏出现hypernova/protostar 这些可能更接近“真实战场”的尖端武器,NOVA作为NOVA 系的开篇之作代表意义就更大了,尤其是在代码实现中大胆引入cycle curves。

<br />

尽管revisiting nova 的出现震惊了很多人,但NOVA的原始paper 仍然能hold 住,因为paper中根本就没提cycle curves的实现方案,说明作者早已给自己留有余地。

<br />

NOVA原始的相关讨论及资料很多,会在最后附上以供参考。本文会从另外一个角度去思考NOVA,也许会给大家带来不一样的感观。

<br />

目标

image.png

这张图节自revisiting nova  ,看到这张图大家可能会猜想这张图如何得来的?本文的目标试图把这张图一步一步倒推出来,尽量涵盖其中的所有细节。

<br />

可能感兴趣的问题

我把自己学习过程中思考的问题列出来,看看大家是否也思考过同样的问题: <br />

  • NOVA 是如何跟ZKP 后端对接的?

  • 为什么要有folding 的过程?

  • folding 过程的合法性如何保证?

  • 引入cycle curves 时的背景是什么?

  • 为什么要在电路里面做hash?

  • prover 这边哪些需要校验,哪些可以postpone?

  • revisiting nova   出现之前,NOVA源代码vulnerability 的根源在哪里?为什么revisiting nova 这个版本能work?

  • NOVA 的电路必须得是结构化对称的吗?是否可以只把non-native 的folding部分代理到“外面”的电路里去,变成一个非结构化的?

<br />

NOVA的轮廓

以NOVA为代表的NOVA系的folding scheme 整体上分为两部分:IVC 和 ZKP,鉴于NOVA 用的是R1CS circuit arithmatic,所以zkp 后端也是基于R1CS。通过IVC prover 把N 个recursive long-running计算任务的R1CS proof(或者witness-instance pair)压缩成1个,然后再喂给基于R1CS 电路约束的zkp 后端(NOVA源代码用的是spartan),吐出相应的snark proof,供snark verifier 来验证。

<br />

IVC

IVC的目标是为recursive long-running计算任务提供压缩后的R1CS proof(或者witness-instance pair)。

<br />

recursive long-running计算任务大概长下面这个样子:

image.png

通过电路把recursive long-running计算任务的R1CS proof给吐出来:

image.png

<br />

基于R1CS的ZKP

通过zkp 后端,产生verifier 所需要的snark proof:

image.png

<br />

预备知识

non-native 椭圆曲线运算

我们一般说的non-native椭圆曲线运算指的是在电路中执行非当前电路field的椭圆曲线运算。

<br />

为什么会有【非当前电路field的椭圆曲线运算】?问题的根源在于椭圆曲线order取值的不确定性,如果椭圆曲线order确定在电路field 上,那么就不会有non-native 椭圆曲线运算这么一说了。那么椭圆曲线的order 的domain到底是多少?

$$ p + 1 - 2\sqrt{p} < |E/\mathbb{F_p}| < p + 1 + 2\sqrt{p} $$

<br />

看得出来,椭圆曲线的order有可能小于椭圆曲线field $p$ 也有可能大于它。有什么影响吗?有,熟悉KZG10 PCS的应该知道,目标向量的commitment 最终归于椭圆曲线的scalar mul运算,比如:

$$ r * g \

g_x, g_y \in [1, p - 1] \text{ or } \in \mathbb{F_p^*} $$

<br />

其中$r$ 为目标向量的某个元素,它的domain 肯定是在椭圆曲线order (点的个数)的上限以内,即:

$$ r \in [1, |E/\mathbb{F_p}|) $$

<br />

也就是说乘法因子$r$ 与 点$g$ 分两个不同的field,所以我们习惯上定义乘法因子$r$ 所属的field 叫作group 的scalar field,点$g$ 所属的field 叫作group 的base field:

$$ r \in \mathbb{F_r} \

g \in \mathbb{F_p} $$

如果我们要在电路中执行椭圆曲线的scalar mul运算,为了尽量减少约束数量,当前电路的field 会尽量与要计算的椭圆曲线点$g$ 的base field对齐:

$$ \boxed{ g' \leftarrow g_1 + r * g_2 }

\textcolor{red} {

\overset{G_1\text{: scalar} = G_2\text{: base}}

\Longleftarrow

}

\begin{cases}

g_1, g_2 \in G_2 \text{: base} \

r \in G_2 \text{: scalar} \

\end{cases} $$

但乘法因子$r$ 的field仍然是non-native的,而且根据上面椭圆曲线order的domain取值范围公式,有可能 $G_2​:scalar$ > $G_2​:base$。怎么办?通常电路中这里的$r$ 是通过限制它的bit size,强制限制它的值域在$G_2​:base$ 上,不然电路里的椭圆曲线运算就会变得很麻烦。

<br />

cycle curves

image.png

<br />

  • R1CS 电路吐出来的proof本身是一组向量,比如电路$C_2$​ 吐出来的proof 向量就是在$F_r$​ 上,但由于它反应的是电路计算的trace过程,直接通过它来验证R1CS约束是不行的,需要进行commit

<br />

  • commit 之后就会变成椭圆曲线上的一个点,变成另外一个field $F_p$​。如果要在另外一个电路$C_1$​中对这个commit 后的proof 进行验证,那么这个验证电路的field就得尽量与commit 的field对齐,这样约束就会尽量少

<br />

  • 同样的,如果想在电路$C_2$​ 中验证 电路$C_1$​ 吐出来的proof的commitment,那么这个commitment 就必须是与$C_2$​ 的field 对齐的

<br />

所以,两个电路的proof commit用的椭圆曲线就得是两个特殊的椭圆曲线,使得任意一个椭圆曲线的base field正好是另外一个椭圆曲线的order。像这种曲线比较少见,NOVA的代码实现中使用是scalar field 和 base field都是255 bits 的pasta curves,而NOVA的代码实现中使用的folding factor $r$是250 bits,正好可以同时fits 进两个field。

<br />

这就样完全避开了non-native 的folding计算。

<br />

从零构建NOVA

ROUND ONE

image.png

非fold 状态下,需要与verifier交互多次,验证多次。那我们引入folding之后看看变成什么样子?

<br />

ROUND TWO

image.png

加上离线的folding 部分后,交互次数和验证次数减少了,但此时的问题是,只是把业务计算的proof 进行了folding,并给verifier 提供了一个folding后的业务计算的proof。谁来保证folding的过程合法性?所以prover 还需要提供IVC folding过程的proof 。

<br />

ROUND THREE

image.png

类似地,套用上面的思路,把业务计算proof的folding电路的proof 通过离线的方式把它们给fold起来,最终又多生成一个folding电路的accumulator proof。同样把这个accumulator 通过zkp 后端生成相应的SNARK proof,连同public instance一并递交给verifier。这样一来,verifier 需要对两个SNARK proof 做验证,一个是业务电路的proof,一个是folding过程的proof。

<br />

同样的,仍然面临一个问题,离线过程的合法性谁来保证,所以最下面一层folding过程同样需要电路化。但是,如果还是同上面的思路直接在下面引入电路层 的话,就会出现“死循环”。怎么办?

<br />

引入cycle curves,复用 最上面一层的业务电路。

ROUND FOUR

image.png

到目前为止,NOVA整体的构架图就完整了,简单总结一下:

  • 有两层电路$(1)$ 和$(2)$,$(1)$ 通常叫它业务电路,$(2)$ 通常叫它folding 电路。$(1)$ 但它不光只是业务电路的计算,还有对folding 电路proof的folding过程。$(2)$主要是对业务电路proof的folding,但NOVA强调结构化对称性所以在代码实现中加了一个trivial 电路,在cycle-fold 里就是一个单纯的更轻量级的folding了,后面也会提到。

<br />

  • 电路folding 后的proof 用$U_i^{(1)}$​ 和 $U_i^{(2)}$​ 表示。对于SNARK verifier 来说,这些才是需要验证的对象。

<br />

  • SNARK 的proof 用 $π_i^{(1)}$​ 和 $π_i^{(2)}$​ 表示,用来验证 $U_i^{(1)}$​ 和 $U_i{(2)}$​

<br />

  • 在recursive 的最后一个step 电路$(2)$ 的proof 没有被fold,所以SNARK prover在电路 $(1)$侧特意添加了一个离线的folding过程,之后才把folding的最终结果送到zkp 后端生成相应的SNARK proof。因为是离线的folding,所以对等地,SNARK verifier在校验之前也需要folding一次,然后才拿着SNARK proof进行验证。

<br />

校验过程 与 Vulnerability

prover 这边的校验分两部分,recursive 过程中的校验 和 recursive 最后(进入ZKP后端之前)的校验。

<br />

recursive 过程中的校验:

  • 离线folding 后的proof $U_i^{(1)}$​ 和 $U_i^{(2)}$​ 是直接递交给SNARK verifier的,需要保证与电路产生是否一致(得有相应的proof吐出来)。所以引入hash,把电路中更新后的状态$z_i$​ 和 $U_i$​ 进行hash,publisize 化变成一个public IO,透传到下一个step 电路中,并在folding之前校验,保证每次folding输入的$U_i^{(1)}$​ 和 $U_i^{(2)}$​ 都是合法的

<br />

  • 电路吐出来的proof $u_i^{(1)}$​ 和 $u_i^{(2)}$​ ,不能直接校验其是否满足R1CS约束,NOVA 是postpone 到了最后。校验$U_i^{(1)}$​ 和 $U_i^{(2)}$​ 满足R1CS约束,通过knowledge soundness倒推出电路吐出来的$u_i^{(1)}$​ 和 $u_i^{(2)}$​ 也是合法的

<br />

recursive 最后的校验:

  • 离线folding后的$U_i^{(1)} / Wi^{(1)}$ 对是否满足R1CS约束。通过验证它们满足R1CS约束,基于knowledge soundness倒推出 $U{i−1}^{(1)} / W_{i−1}^{(1)}$​ 和 $u_i^{(1)}​/w_i^{(1)}$​ 都满足R1CS约束。$U_i^{(2)}​/W_i^{(2)}$​ 同理

<br />

  • 电路吐出来的proof $u_i^{(1)}​/w_i^{(1)}$​ 和 $u_i^{(2)}​/w_i^{(2)}$​ 都满足R1CS约束。通过验证它们满足R1CS约束,证明电路的计算过程的是passed的。包含四个方面:
  1. folding 前的hash 操作,校验输入的$U_i^{(1)}$​ 或者 $U_i^{(2)}$​ 是否合法,如$ui^{(1)}​.x0 == H{(i−1}^{(2)}, z0^{(2)}​,z{i−1}^{(2)}​,U_{i−1}^{(1)})$

  2. folding 过程的合法性,如 $Ui^{(1)}​⟵ U{i−1}^{(1)} ⊕ r∗u_i^{(1)}$

  3. 业务电路计算过程的合法性,如 $z_{i+1}^{(1)}​⟵F(z_i^{(1)})$

  4. folding 后的hash操作然后publisize,如 $x_1​⟵H(i^{(2)},z_0^{(2)}​,z_i^{(2)}​,U_i^{(1)}​), x_0​⟵u_i^{(i)}.x_1$​

<br />

  • 校验离线folding 后的$U_i^{(1)}$​ 和 $U_i^{(2)}$​ 是否和电路folding的结果一致。通过验证它们是否一致,保证提交给SNARK verifier的$U_i^{(1)}$​ 和 $U_i^{(2)}$​ 是合法的​

$$ \textcolor{red} {u_i^{(1)}.x_1} \overset{?} = \text{H}({i}^{(1)}, z0^{(1)}, z{i}^{(1)}, U_{i }^{(2)}) \

u_i^{(2)}.x_1 \overset{?} = \text{H}({i}^{(2)}, z0^{(2)}, z{i}^{(2)}, U_{i }^{(1)}) \ $$

看着似乎一切都很完美!可Vulnerability 的根源就在这里,revisiting nova 给出了修订版是:

$$ \textcolor{red} {u_i^{(2)}.x_0} \overset{?} = \text{H}({i}^{(1)}, z0^{(1)}, z{i}^{(1)}, U_{i }^{(2)}) \

u_i^{(2)}.x_1 \overset{?} = \text{H}({i}^{(2)}, z0^{(2)}, z{i}^{(2)}, U_{i }^{(1)}) \ $$

第一眼看会认为这跟上面没什么区别,那是因为你心中已经默认有个已经成立的assumption了,就是$u_i^{(1)}$​ 已经传递到了电路$(2)$ 中,但是真是这样吗?不是吧

<br />

Double Chain Attack 与 Fixed NOVA

revisiting nova 给出的attack 方案就是基于上面这个并不成立的assumption,构造出了两条独立的 chain 吐出来的proof能通过所有的校验,但input 却是伪造的。我们看看这两条chain 分别长什么样子?

构造第一条Chain

image.png

构造第二条Chain

image.png

最终拿到 $U_i^{(1)}​/W_i^{(1)}$​、 $U_i^{(2)}​/W_i^{(2)}$​ 和 $u_i^{(2)}​/w_i^{(2)}$​ 三个pair对,仍然能通过recursive 的最后一步的校验过程。上面的double chain从何而来,为什么这种伪造的double chain可以成功?

<br />

校验$U_i^{(1)}​/Wi^{(1)}$​ 满足R1CS,根据knowledge sound 可以推导出$U{i−1}^{(1)}​/W_{i−1}^{(1)}$​ 和 $u_i^{(1)}​/wi^{(1)}$​ 都满足R1CS约束,但推导不出$u{i−1}^{(1)}​/w{i−1}^{(1)}$​ 是否满足R1CS约束,所以可以伪造一对并不满足R1CS约束的$u{i−1}^{(1)}​/w_{i−1}^{(1)}$​ ;$U_i^{(2)}​/Wi^{(2)}$​ 同理,可以伪造一对并不满足R1CS约束的$u{i−1}^{(2)}​/w_{i−1}^{(2)}$​ 。所以才有上面的double chain...

<br />

但是,为什么Fixed 版本的NOVA又可以work,或者说能避免上面的问题呢?

$$ \textcolor{red} {u_i^{(2)}.x_0} \overset{?} = \text{H}({i}^{(1)}, z0^{(1)}, z{i}^{(1)}, U_{i }^{(2)}) \

u_i^{(2)}.x_1 \overset{?} = \text{H}({i}^{(2)}, z0^{(2)}, z{i}^{(2)}, U_{i }^{(1)}) \ $$

<br />

通过$u_i^{(2)}.x_0$​ 来验证最后一个step 的电路$(1)$离线fold的合法性,而不是通过$u_i^{(1)}​.x_1$​。

<br />

上面的等式反应的是$u_i^{(2)}​.x_0$​ 是从真实的电路$(1)$ 吐出来的proof $u_i^{(1)}​.x1$​ 中copy 过来的,从而保证最后一个step 两个电路之间的衔接性,也就是说之前的那个assumption不存在了。在此条件下,再通过knowledge soundness自然能推导出$u{i−1}^{(1)}​/w{i−1}^{(1)}$​ 和 $u{i−1}^{(2)}​/w{i−1}^{(2)}$​ 都满足R1CS约束,然后递归地,$U{i−1}^{(1)}​/W{i−1}^{(1)}$ 满足R1CW约束,又能倒推出$U{i - 2}^{(1)}/W{i - 2}^{(1)}$ 和 $u{i - 1}^{(1)}/w_{i - 1}^{(1)}$;...

<br />

结构化folding 与 非结构化folding

pub struct AllocatedR1CSInstance&lt;G: Group> { 
    pub(crate) W: AllocatedPoint&lt;G>, 
    pub(crate) X0: AllocatedNum&lt;G::Base>, 
    pub(crate) X1: AllocatedNum\&lt;G::Base>, 
}

<br />

在cycle curves 的primary电路(上面扮演过程中的电路1)的proof commitment W的fold是在基于另外一条曲线的secondary 电路里进行的,这是一个标准的MSM 的native folding的过程;但还需要对public variables  X0 和 X1进行fold,可是这里是non-native folding的过程,必须得通过bigint 的方式来解决,NOVA里只有 X0 和 X1这两个bigint 的folding,所以还好,成本并不是特别高。

<br />

那么,我们可不可以只把primary 电路的proof commitment W的fold工作代理给基于另外一条曲线的secondary电路,而X0 和 X1 的fold工作留在primary 电路呢,这样就没有任何non-native 的运算了,不是吗?可以,cycle-fold 就是这么干的!后面会展开讲这个topic。

参考资料

【1】revisiting nova:https://eprint.iacr.org/2023/969.pdf 【2】cycle fold:https://eprint.iacr.org/2023/1192.pdf 【3】NOVA 源代码:https://github.com/microsoft/Nova

其它NOVA相关讨论及资料

【1】@po 汇总的资料:https://github.com/dajuguan/awesome-nova-based-Recursive-Zero-Knowledge-Arguments-knowlege/blob/main/README.md 【2】@邹老师汇总的资料:https://blog.csdn.net/mutourend?type=blog

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

0 条评论

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