写在前面的时隔两个多月终于有机会给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 />
这张图节自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系的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的目标是为recursive long-running计算任务提供压缩后的R1CS proof(或者witness-instance pair)。
<br />
recursive long-running计算任务大概长下面这个样子:
通过电路把recursive long-running计算任务的R1CS proof给吐出来:
<br />
通过zkp 后端,产生verifier 所需要的snark proof:
<br />
我们一般说的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 />
<br />
<br />
<br />
<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 />
非fold 状态下,需要与verifier交互多次,验证多次。那我们引入folding之后看看变成什么样子?
<br />
加上离线的folding 部分后,交互次数和验证次数减少了,但此时的问题是,只是把业务计算的proof 进行了folding,并给verifier 提供了一个folding后的业务计算的proof。谁来保证folding的过程合法性?所以prover 还需要提供IVC folding过程的proof 。
<br />
类似地,套用上面的思路,把业务计算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,复用 最上面一层的业务电路。
到目前为止,NOVA整体的构架图就完整了,简单总结一下:
<br />
<br />
<br />
<br />
prover 这边的校验分两部分,recursive 过程中的校验 和 recursive 最后(进入ZKP后端之前)的校验。
<br />
recursive 过程中的校验:
<br />
<br />
recursive 最后的校验:
<br />
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)})$
folding 过程的合法性,如 $Ui^{(1)}⟵ U{i−1}^{(1)} ⊕ r∗u_i^{(1)}$
业务电路计算过程的合法性,如 $z_{i+1}^{(1)}⟵F(z_i^{(1)})$
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 />
$$ \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 />
revisiting nova 给出的attack 方案就是基于上面这个并不成立的assumption,构造出了两条独立的 chain 吐出来的proof能通过所有的校验,但input 却是伪造的。我们看看这两条chain 分别长什么样子?
最终拿到 $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 />
pub struct AllocatedR1CSInstance<G: Group> {
pub(crate) W: AllocatedPoint<G>,
pub(crate) X0: AllocatedNum<G::Base>,
pub(crate) X1: AllocatedNum\<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
【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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!