NOVA from scratch

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

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

# 写在前面的

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

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

尽管[revisiting nova ](https://eprint.iacr.org/2023/969.pdf)的出现震惊了很多人，但NOVA的原始paper 仍然能hold 住，因为paper中根本就没提cycle curves的实现方案，说明作者早已给自己留有余地。

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

# 目标

![image.png](https://img.learnblockchain.cn/attachments/2023/08/JMehRH5g64e36d721b1bf.png)

这张图节自[revisiting nova ](https://eprint.iacr.org/2023/969.pdf) ，看到这张图大家可能会猜想这张图如何得来的？本文的目标试图把这张图一步一步倒推出来，尽量涵盖其中的所有细节。

# 可能感兴趣的问题
我把自己学习过程中思考的问题列出来，看看大家是否也思考过同样的问题：

- NOVA 是如何跟ZKP 后端对接的？

- 为什么要有folding 的过程？

- folding 过程的合法性如何保证？

- 引入cycle curves 时的背景是什么？

- 为什么要在电路里面做hash？

- prover 这边哪些需要校验，哪些可以postpone？

- [revisiting nova ](https://eprint.iacr.org/2023/969.pdf)  出现之前，NOVA源代码vulnerability 的根源在哪里？为什么revisiting nova 这个版本能work?

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

# 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 来验证。

## IVC

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

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

![image.png](https://img.learnblockchain.cn/attachments/2023/08/FQDAZuRP64e36ee77bde0.png)

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

![image.png](https://img.learnblockchain.cn/attachments/2023/08/44U0bVFA64e36f12e7843.png)

## 基于R1CS的ZKP

通过zkp 后端，产生verifier 所需要的snark proof：

![image.png](https://img.learnblockchain.cn/attachments/2023/08/HJldNqO664e36f3b00c42.png)

# 预备知识

## non-native 椭圆曲线运算

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

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

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

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

$$
r * g \\

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

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

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

也就是说乘法因子$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$ 上，不然电路里的椭圆曲线运算就会变得很麻烦。

## cycle curves

![image.png](https://img.learnblockchain.cn/attachments/2023/08/3RikJw9464e371012ce04.png)

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

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

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

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

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

# 从零构建NOVA

## ROUND ONE

![image.png](https://img.learnblockchain.cn/attachments/2023/08/MrS64ZXF64e37245a8653.png)

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

## ROUND TWO

![image.png](https://img.learnblockchain.cn/attachments/2023/08/StWsMTLE64e3727c240e1.png)

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

## ROUND THREE

![image.png](https://img.learnblockchain.cn/attachments/2023/08/WnaxaQOb64e372b30fb8a.png)

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

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

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

## ROUND FOUR

![image.png](https://img.learnblockchain.cn/attachments/2023/08/g7mhgMpK64e373163cf93.png)

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

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

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

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

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

# 校验过程 与 Vulnerability

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

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)}$ 都是合法的

- 电路吐出来的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)}$ 也是合法的

recursive 最后的校验：

- 离线folding后的$U_i^{(1)} / W_i^{(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)}$ 同理

- 电路吐出来的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)}$ 是否合法，如$u_i^{(1)}.x0 == H_{(i−1}^{(2)}, z_0^{(2)},z_{i−1}^{(2)},U_{i−1}^{(1)})$
> 
> 
> 
>2. folding 过程的合法性，如 $U_i^{(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$

- 校验离线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)}, z_0^{(1)}, z_{i}^{(1)}, U_{i }^{(2)}) \\

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

看着似乎一切都很完美！可Vulnerability 的根源就在这里，[revisiting nova ](https://eprint.iacr.org/2023/969.pdf)给出了修订版是：

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

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

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

# Double Chain Attack 与 Fixed NOVA

[revisiting nova](https://eprint.iacr.org/2023/969.pdf) 给出的attack 方案就是基于上面这个并不成立的assumption，构造出了两条独立的 chain 吐出来的proof能通过所有的校验，但input 却是伪造的。我们看看这两条chain 分别长什么样子？

## 构造第一条Chain

![image.png](https://img.learnblockchain.cn/attachments/2023/08/YfdnGc8B64e37adf06fb2.png)

## 构造第二条Chain

![image.png](https://img.learnblockchain.cn/attachments/2023/08/Pr2vrRV864e37b0b8a35f.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可以成功？

校验$U_i^{(1)}/W_i^{(1)}$ 满足R1CS，根据knowledge sound 可以推导出$U_{i−1}^{(1)}/W_{i−1}^{(1)}$ 和 $u_i^{(1)}/w_i^{(1)}$ 都满足R1CS约束，但推导不出$u_{i−1}^{(1)}/w_{i−1}^{(1)}$ 是否满足R1CS约束，所以可以伪造一对并不满足R1CS约束的$u_{i−1}^{(1)}/w_{i−1}^{(1)}$ ；$U_i^{(2)}/W_i^{(2)}$ 同理，可以伪造一对并不满足R1CS约束的$u_{i−1}^{(2)}/w_{i−1}^{(2)}$ 。所以才有上面的double chain...

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

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

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

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

上面的等式反应的是$u_i^{(2)}.x_0$ 是从**真实**的电路$(1)$ 吐出来的proof $u_i^{(1)}.x_1$ 中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)}$；...

# 结构化folding 与 非结构化folding

```rust
pub struct AllocatedR1CSInstance<G: Group> { 
 pub(crate) W: AllocatedPoint<G>, 
 pub(crate) X0: AllocatedNum<G::Base>, 
 pub(crate) X1: AllocatedNum\<G::Base>, 
}
```

在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，所以还好，成本并不是特别高。

那么，我们可不可以只把primary 电路的proof commitment `W`的fold工作代理给基于另外一条曲线的secondary电路，而`X0` 和 `X1` 的fold工作留在primary 电路呢，这样就没有任何non-native 的运算了，不是吗？可以，[cycle-fold](https://eprint.iacr.org/2023/1192.pdf) 就是这么干的！后面会展开讲这个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

写在前面的

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

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

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

目标

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

可能感兴趣的问题

我把自己学习过程中思考的问题列出来，看看大家是否也思考过同样的问题：

NOVA 是如何跟ZKP 后端对接的？
为什么要有folding 的过程？
folding 过程的合法性如何保证？
引入cycle curves 时的背景是什么？
为什么要在电路里面做hash？
prover 这边哪些需要校验，哪些可以postpone？
revisiting nova 出现之前，NOVA源代码vulnerability 的根源在哪里？为什么revisiting nova 这个版本能work?
NOVA 的电路必须得是结构化对称的吗？是否可以只把non-native 的folding部分代理到“外面”的电路里去，变成一个非结构化的？

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 来验证。

IVC

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

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

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

基于R1CS的ZKP

通过zkp 后端，产生verifier 所需要的snark proof：

预备知识

non-native 椭圆曲线运算

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

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

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

$$ r * g \

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

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

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

也就是说乘法因子$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$ 上，不然电路里的椭圆曲线运算就会变得很麻烦。

cycle curves

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

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

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

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

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

从零构建NOVA

ROUND ONE

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

ROUND TWO

ROUND THREE

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

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

ROUND FOUR

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

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

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

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

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

校验过程与 Vulnerability

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

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)}$ 都是合法的

电路吐出来的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)}$ 也是合法的

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)}$ 同理

电路吐出来的proof $u_i^{(1)}/w_i^{(1)}$ 和 $u_i^{(2)}/w_i^{(2)}$ 都满足R1CS约束。通过验证它们满足R1CS约束，证明电路的计算过程的是passed的。包含四个方面：

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$

校验离线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)$ 中，但是真是这样吗？不是吧

Double Chain Attack 与 Fixed NOVA

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

构造第一条Chain

构造第二条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可以成功？

校验$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...

但是，为什么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)}) \ $$

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

上面的等式反应的是$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)}$；...

结构化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>, 
}

在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，所以还好，成本并不是特别高。

那么，我们可不可以只把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

原创
学分: 19
分类: 零知识证明
标签: Nova folding zkSNARK

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

NOVA from scratch

写在前面的

目标

可能感兴趣的问题

NOVA的轮廓

IVC

基于R1CS的ZKP

预备知识

non-native 椭圆曲线运算

cycle curves

从零构建NOVA

ROUND ONE

ROUND TWO

ROUND THREE

ROUND FOUR

校验过程与 Vulnerability

Double Chain Attack 与 Fixed NOVA

构造第一条Chain

构造第二条Chain

结构化folding 与非结构化folding

参考资料

其它NOVA相关讨论及资料

0 条评论

文章目录

NOVA from scratch

写在前面的

目标

可能感兴趣的问题

NOVA的轮廓

IVC

基于R1CS的ZKP

预备知识

non-native 椭圆曲线运算

cycle curves

从零构建NOVA

ROUND ONE

ROUND TWO

ROUND THREE

ROUND FOUR

校验过程 与 Vulnerability

Double Chain Attack 与 Fixed NOVA

构造第一条Chain

构造第二条Chain

结构化folding 与 非结构化folding

参考资料

其它NOVA相关讨论及资料

0 条评论

文章目录

校验过程与 Vulnerability

结构化folding 与非结构化folding