{"content":{"title":"CycleFold Based Nova","body":"# Thanks\r\n- 非常感谢secbit labs的@郭宇老师 和 @even ，讨论过程中收获颇多，对folding 有了更抽象层次的理解\r\n\r\n# CycleFold 是什么\r\n[CycleFold](https://eprint.iacr.org/2023/1192.pdf) 是针对NOVA系的folding scheme 在代码实现层面的优化技巧，适用于所有基于cycle curves 的诸如SuperNova/HyperNova/Protostar，使得电路的成本更低，[原始paper](https://eprint.iacr.org/2023/1192.pdf) 是针对HyperNova 进行地论证，为了陈述方便，本文是基于Nova的讨论。\r\n\r\n
\r\n文章最后有一个自己的“思考”，是论文中没有涉及到的，感兴趣的欢迎讨论。\r\n\r\n# 背景\r\n\r\n下面这张图是[revisiting nova](https://eprint.iacr.org/2023/969.pdf) 中非常经典的描述cycle curves 的图：\r\n\r\n\r\n\r\n\r\n通过上面这张图，我们可以有以下共识：\r\n\r\n\r\n* 我们通常称上面一层电路为primary 电路，下面一层电路为secondary 电路。以secondary 电路为例，secondary 电路需要把primary 电路的proof $u_i^{(1)}$ fold 进$U_i^{(1)}$，生成$U_{i+1}^{(1)}$\r\n\r\n
\r\n\r\n\r\n* primary 电路会以public IO 形式吐出来两个hash值，$x_0$ 和 $x_1$，这两个hash会随着$u_i^{(1)}$ 传递给secondary 电路\r\n\r\n
\r\n\r\n先看一下$u_i^{(1)}$ 的数据结构：\r\n```rust\r\npub struct AllocatedR1CSInstance { \r\n pub(crate) W: AllocatedPoint, \r\n pub(crate) X0: AllocatedNum, \r\n pub(crate) X1: AllocatedNum, \r\n}\r\n```\r\n\r\n
\r\n\r\n再看一下$U_i^{(1)}$ 的数据结构：\r\n\r\n```rust\r\n\r\npub struct AllocatedRelaxedR1CSInstance { \r\n pub(crate) W: AllocatedPoint, \r\n pub(crate) E: AllocatedPoint, \r\n pub(crate) u: AllocatedNum, \r\n pub(crate) X0: BigNat, \r\n pub(crate) X1: BigNat, \r\n}\r\n```\r\n\r\n
\r\n\r\n我们把folding的过程大概展开一下看看：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&U_{i + 1}^{(1)}.W \\leftarrow U_i^{(1)}.W \\overset{\\text{fold}} \\oplus r * u_i^{(1)}.W, \\in \\mathbb{F_q} \\\\\r\n\r\n&U_{i + 1}^{(1)}.E \\leftarrow U_i^{(1)}.E \\overset{\\text{fold}} \\oplus r * \\widetilde{T}, \\in \\mathbb{F_q} \\\\\r\n\r\n&U_{i + 1}^{(1)}.u \\leftarrow U_i^{(1)}.u \\overset{\\text{fold}} \\oplus r * 1, \\in \\mathbb{F_q} \\\\\r\n\r\n&U_{i + 1}^{(1)}.x_0 \\leftarrow U_i^{(1)}.x_0 \\overset{\\text{fold}} \\oplus r * u_i^{(1)}.x_0, \\textcolor{red} {\\in \\mathbb{F_p}} \\\\\r\n\r\n&U_{i + 1}^{(1)}.x_1 \\leftarrow U_i^{(1)}.x_1 \\overset{\\text{fold}} \\oplus r * u_i^{(1)}.x_1, \\textcolor{red} {\\in \\mathbb{F_p}} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\nfolding的计算主要分为两种，一种是椭圆曲线上的点的folding，另一种是hash值的folding。 熟悉EC运算的应该知道第一种比较复杂的计算过程；而第二种就非常简单了。但因为它们分别属于两个不同的field，所以即使引入cycle curves也避免不了non-native计算，只是看孰轻孰重了。\r\n\r\n\r\n
\r\n\r\n\r\n椭圆曲线上的点的folding比较贵，所以，cycle curves 就尽量照顾到它，把它变成native 的计算，那么$x_0$ 和$x_1$ 的folding就变成了non-native的计算，最大限度的降低了电路的成本。细心地会发现，它是通过把field 转成bigint 来完成non-native 计算的。bigint 的计算成本也不算很低，但相对non-native的椭圆曲线点的计算肯定要低很多很多了。那么有没有更轻量级的secondary电路呢？\r\n\r\n
\r\n\r\n# 更轻量级的secondary 电路\r\n有没有一种可能在secondary 电路中完全避开这种non-native的计算？产生non-native的根源在于我们把椭圆曲线点的folding 和 hash值的folding放在一个电路里做了，导致cycle curve只能二选一。那么有没有可能拆开，使得他们都在native field上？\r\n\r\n
\r\n\r\n\r\n下面这张图节选自[Cycle-Fold ](https://eprint.iacr.org/2023/1192.pdf)原文中比较经典的图：\r\n\r\n\r\n\r\n
\r\n\r\n我们先描述一下它的宗旨：\r\n\r\n\r\n1. 把基于椭圆曲线E1 的primary 电路的proof $u_i^{(1)}$ 中椭圆曲线的folding工作**代理**给基于椭圆曲线E2 的secondary 电路 $C_{EC}$\r\n\r\n
\r\n\r\n2. 剩余的两个hash 值$x_0$ 和 $x_1$ 的folding工作**透传**给下一个step 的primary 电路(HN Partial 部分)，也就是说下一个step 的primary 电路会验证上一个step primary 电路\r\n\r\n
\r\n\r\n3. secondary 电路 $C_{EC}$的proof $u_{EC}$ 还是交给primary 电路(Nova 部分)来完成(这里有个细节后面会提到)\r\n\r\n\r\n
\r\n\r\n下面主要把**代理**的整个过程给展开一下看看，对应上面的第1、2步：\r\n\r\n\r\n\r\n\r\n
\r\n\r\n大概流程如下：\r\n\r\n\r\n1. primary 电路吐出proof $u_i^{(1)}$的时候，需要对当前电路更新后的状态$U_{i−1}^{(1)}$ 进行hash，并publisize 给$u_i^{(1)}.x_1$，最后再通过$u_i^{(2)}$ 透传给下一个step 的primary 电路。\r\n> \r\n>
\r\n> \r\n> 目的是，在下一个step 的primary 电路folding之前对电路 $C(EC)^{(2)}$ 的input $U_{i−1}^{(1)}$ 进行合法性校验，校验通过，就**默认** 电路 $C(EC)^{(2)}$ 对椭圆曲线点$u_i^{(1)}.w$ 的folding 结果$u_i^{(2)}.w′$是正确的，这样primary 电路就可以进行其它的工作了。\r\n> \r\n>
\r\n> \r\n> 而电路$C(EC)^{(2)}$ 的验证工作是通过上面第3步中提到的primary 电路中的Nova folding verifier 来完成的，跟原始Nova的primary 电路一样，上图只是**代理**的过程，这部分就没有标出。\r\n\r\n\r\n2. 正是由于primary 电路吐出proof $u_i^{(1)}$中包含hash值 $u_i^{(1)}.x_1$，而电路 $C(EC)^{(2)}$ 只是完成了$u_i^{(1)}$中的$u_i^{(1)}.w$ 的folding，$u_i^{(1)}.x_1$ 的field 又刚好与primary 电路的field 相同，所以$u_i^{(1)}.x_1$ 的folding工作轮到了下一个step 的primary 电路。\r\n\r\n
\r\n\r\n\r\n到这里，Cycle-Fold 的核心理念就完成了。\r\n\r\n
\r\n\r\n# 思考\r\n\r\n\r\nCycleFold 强调的是轻量级的secondary 电路，主要思想是最大限度地减轻secondary 电路的成本，只是负责**代理** primary 电路的proof中的椭圆曲线点的计算，最后把**代理**计算的结果publisize后返回给primary 电路，primary 电路完成验证后接着就可以进行其它的工作了。\r\n\r\n
\r\n\r\n而secondary 电路本身的验证工作，同Nova一样，仍然需要primary 电路来做，secondary 电路吐出来的proof 中因为有public IO，所以secondary 电路proof 的folding 过程仍然免不了有少量的non-native 计算(1-2个)。\r\n\r\n
\r\n\r\n如果套用上面的思路，可不可以也把这部分non-native 的计算放到下一个step 的secondary 电路中呢？这样最终就会形成：**primary 电路proof中椭圆曲线的计算代理给了secondary 电路，secondary 电路proof中的椭圆曲线的计算代理给了primary 电路，整个folding scheme中就完全避开了non-native 的计算**。理论上是可行的，只是CycleFold原始论文中并没有提到这一点，它只是强调了轻量级的secondary 电路。\r\n\r\n\r\n
\r\n最终的逻辑大概是这样子的：\r\n\r\n\r\n\r\n# 参考资料\r\n【1】CycleFold论文: https://eprint.iacr.org/2023/1192.pdf\r\n\r\n# 其它相关资料\r\n【1】关于cycle curve更多的细节：https://learnblockchain.cn/article/6429"},"author":{"user":"https://learnblockchain.cn/people/15677","address":null},"history":"QmPv1aDNVzAJSrXgXnmotJWpTpYWXZD1BcQBGic8oS6jAb","timestamp":1693191327,"version":1}