【上篇】ProtoStar from scratch

白菜
更新于 2023-09-07 22:48
阅读 2020

Thanks十分感谢@AntalphaLabs上月底提供的线下hackerhouse，有机会亲历并学习SecbitLabs@郭宇老师、@even做zkresearch的思路和方法，并讨论了很多foldingscheme相关的问题非常感谢参加hackerhouse一起交流

# Thanks

- 十分感谢@AntalphaLabs 上月底提供的线下hackerhouse ，有机会亲历并学习SecbitLabs @郭宇 老师、@even 做zk research 的思路和方法，并讨论了很多folding scheme相关的问题

- 非常感谢参加hackerhouse 一起交流讨论过protostar的小伙伴们 @yingfei、 @Harry L 、@周洋、 @CJ 、@hhh，尽管当时对protostar的认识还比较肤浅，还没摸到它的门框儿，但至少有一个初步的overview 概念 -)

# 写在前面的

ProtoStar 论文中非常经典的一张图：
![image.png](https://img.learnblockchain.cn/attachments/2023/09/SHdpIAk664f83b8feea9e.png)

- ProtoStar 论文中最核心、最具创新的应该就是3.5 章节，其它部分基本都是对整个folding scheme 的抽象，如果读完还是不知道3.5 章节的compress verification tech在整个协议中怎么用，建议反复研究上面这张图(论图的重要性)

- 为了方便描述，我们以最简单的R1CS约束系统为base来讨论，更容易感知到Protostar 的intuition，适当的时候会拓展到plonkish约束系统，以便有更全局的sense

- 本文旨在厘清3.5章节的compress verification tech 在整个folding scheme中应用，IVC部分基本可以参考 revisiting Nova 的cycle curves方案。本文的tag是"上篇"，“下篇”将会整合plonkish 的三大约束GATE 约束、Wiring 约束、Lookup约束系统地串一下ProtoStar 协议

# Compress Verification Degree

## ROUND ONE

在R1CS约束系统里面只有一种约束，就是GATE的约束，Witness 是z 向量。电路的描述，也就是A、B、C三个矩阵，在setup 阶段就已经完成，矩阵的每一行对应一个gate。SPS prover 要做的就是根据业务计算逻辑填充这个z 向量，SPS verifier 拿着这个z 向量验证是否满足所有GATE的约束：

$$
Cz - Az \circ Bz \overset{?}= \bold{0}
$$

但是这里有个问题，这个等式的左右两边是一个长度为$l$ 的向量，$l$ 代表的是GATE的个数。也就是说，在R1CS约束系统中，SPS verifier 需要校验$l$ 个degree 为2的等式：

$$
\begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \\

&C_1 z - A_1 z \circ B_1 z \overset{?} = 0 \\

&... \\

&C_{l - 1} z - A_{l - 1} z \circ B_{l - 1} z \overset{?} = 0 \\

\end{aligned}
$$

有没有可能把它压缩成一个等式？

## ROUND TWO
引入一个public 的变量，fold factor $$\beta$$：

$$
\begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \\

&\beta^1* (C_1 z - A_1 z \circ B_1 z) \overset{?} = 0 \\

&... \\

&\beta^{l - 1} * (C_{l - 1} z - A_{l - 1} z \circ B_{l - 1} z) \overset{?} = 0 \\

\end{aligned}
$$

最后变成一个等式：

$$
\beta^0 * (C_0 z - A_0 z \circ B_0 z) + \beta^1 * (C_1 z - A_1 z \circ B_1 z) + ... + \beta^{l - 1} * (C_{l - 1} z - A_{l - 1} z \circ B_{l - 1} z) \overset{?} = 0
$$

所以放在SPS 协议里，prover 除了向verifier 发送message $$z$$ 向量，还需要发送另外一个message $$β$$ 向量 $\begin{bmatrix}\beta^0 \\\beta^1 \\... \\\beta^{l - 1} \\\end{bmatrix}$ ，verifier 拿着这两个向量验证上面的等式是否成立就行了，对吗？还漏掉了一件事儿，需要验证message $$β$$ 向量的合法性(正确性)，需要满足：

$$
\begin{aligned}

&\beta_0 \overset{?} = 1 \\

&\beta_{i + 1} \overset{?} = \beta_{i} * \beta, \forall i \in [0, l - 2] \\

\end{aligned}
$$

$$β$$ 向量的每个元素都要校验，这里要校验$$l$$ 个degree 为2的等式。另外还要校验压缩后的等式：

$$
\beta_0 * (C_0 z - A_0 z \circ B_0 z) + \beta_1 * (C_1 z - A_1 z \circ B_1 z) + ... + \beta_{l - 1} * (C_{l - 1} z - A_{l - 1} z \circ B_{l - 1} z) \overset{?} = 0
$$

由于增加了一个变量$\beta_i$，所以等式的degree变成了3。

> 为什么要校验$$\beta$$ 向量？
> 
> 
> 如果不校验$$β$$ 向量，prover 随便给定一个不满足R1CS约束的$$z$$ 向量，然后再给一组可以满足上面等式的$β$ 向量(比如$\bold{0}$ 向量)，这样就很容易骗过verifier。

这里的问题是，prover 发送的message $β$ 向量长度$l$ 不可控，verifier 验证的复杂度$O(l)$ 也不可控，有可能很大。有没有可能再压缩一下？

## ROUND THREE
prover 发送这么一个message，由两个向量组成：

$$
\beta =

\begin{bmatrix}

\beta^0 \\

\beta^1 \\

\beta^2 \\

... \\

\beta^{\sqrt{l} - 1}

\end{bmatrix}

\beta' =

\begin{bmatrix}

\beta^{0 * \sqrt{l}} \\

\beta^{1 * \sqrt{l}} \\

\beta^{2 * \sqrt{l}} \\

... \\

\beta^{(\sqrt{l} - 1)\sqrt{l}}

\end{bmatrix}
$$

然后，原压缩后的等式变成了：

$$
\sum_{a = 0}^{\sqrt{l} - 1} \sum_{b = 0}^{\sqrt{l} - 1} \beta_a * \beta_b' * (C_{a + b\sqrt{l}}z - A_{a + b\sqrt{l}}z \circ B_{a + b\sqrt{l}}z) \overset{?} = 0
$$

等式的degree 增加了2，变成了4。

同样，verifier 需要验证这个新增加的message 的合法性：

$$
\begin{aligned}

&\textcircled {1} \beta_1 \overset{?} = \beta \\

&\textcircled {2} \beta_{i + 1} \overset{?} = \beta_{i} * \beta, \forall i \in [1, \sqrt{l} - 2] \\

&\textcircled {3} \beta_1' \overset{?} = \beta_{\sqrt{l} - 1} * \beta \\

&\textcircled {4} \beta_{i + 1}' \overset{?} = \beta_{i}' * \beta_1', \forall i \in [1, \sqrt{l} - 2]  \\

\end{aligned}
$$

这里需要验证$2\sqrt{l} - 2$ 个degree 为2的等式。

## Deserve it or not

到这里，在R1CS约束系统中，verifier 从原本要验证$l$ 个degree为2的等式，变成了验证1个degree为4的等式加上$2\sqrt{l} - 2$ 个degree 为2的等式，那么这么做是否值得：

$$
l * \text{deg}(2) \textcolor{red} {\overset{?} >} 1 * \text{deg}(2 + 2) + (2\sqrt{l} - 2) * \text{deg}(2)
$$

可能在R1CS约束系统中优势还不够明显，没关系，在支持customer gate的plonkish 约束系统中，gate的degree就不再是2了，而是自定义的degree-$d$：

$$
l * \text{deg}(d) \textcolor{red} {\overset{?} >} 1 * \text{deg}(d + 2) + (2\sqrt{l} - 2) * \text{deg}(2)
$$

所以当gate 的个数$l$ ，gate的degree $d$，都变得很大时，这里压缩的优势就变得相当明显。它计算的复杂度由$O(ld)$ 变成了 $O((d+2)+4\sqrt{l} - 4)$ ，直接降了一个数量级，所以答案是Deserve it!

# Compressed Verification in Accumulation

经过压缩后，SPS verifier 不再是验证$l$ 个等式：

$$
\begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \\

&C_1 z - A_1 z \circ B_1 z \overset{?} = 0 \\

&... \\

&C_{l - 1} z - A_{l - 1} z \circ B_{l - 1} z \overset{?} = 0 \\

\end{aligned}
$$

而是$1+ (2\sqrt{l} - 2)$ 个等式：

$$
\begin{aligned}

&\textcircled {1} \sum_{a = 0}^{\sqrt{l} - 1} \sum_{b = 0}^{\sqrt{l} - 1} \beta_a * \beta_b' * (C_{a + b\sqrt{l}}z - A_{a + b\sqrt{l}}z \circ B_{a + b\sqrt{l}}z) \overset{?} = 0 \\

&\textcircled {2} \beta_1 \overset{?} = \beta \\

&\textcircled {3} \beta_{i + 1} \overset{?} = \beta_{i} * \beta, \forall i \in [1, \sqrt{l} - 2] \\

&\textcircled {4} \beta_1' \overset{?} = \beta_{\sqrt{l} - 1} * \beta \\

&\textcircled {5} \beta_{i + 1}' \overset{?} = \beta_{i}' * \beta_1', \forall i \in [1, \sqrt{l} - 2]  \\

\end{aligned}
$$

在R1CS约束系统中，假设有两个组instance$\text{acc} = \{\beta_\text{acc}, \beta_\text{acc}', z_\text{acc}\}$ 和$\pi = \{\beta_\pi, \beta_\pi', z_{\pi}\}$，前者为**relaxed instance**，后者为 **incremental instance**：

$$
\begin{aligned}

&\sum_{a = 0}^{\sqrt{l} - 1} \sum_{b = 0}^{\sqrt{l} - 1} \beta_{\text{acc}, a} * \beta_{\text{acc},b}' * (\mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\text{acc}} ) \overset{?} = e_{\text{acc}} \\

&\sum_{a = 0}^{\sqrt{l} - 1} \sum_{b = 0}^{\sqrt{l} - 1} \beta_{\pi, a} * \beta_{\pi,b}' * (C_{a + b\sqrt{l}} z_{\pi} - A_{a + b\sqrt{l}} z_{\pi}  \circ B_{a + b\sqrt{l}} z_{\pi} ) \overset{?} = 0 \\

\end{aligned}
$$

我们将这两个instance 进行fold：

$$
\begin{aligned}

&(\beta_{\text{acc}, a} + r \beta_{\pi, a}) * (\beta_{\text{acc}, b}' + r \beta_{\pi, b}') * [(\mu_{\text{acc}} + r) C_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi}) - A_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi})  \circ B_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi})] \\

&= (\beta_{\text{acc}, a} + r \beta_{\pi, a}) * (\beta_{\text{acc}, b}' + r \beta_{\pi, b}') \\

&*[(\mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\text{acc}}) + r (\mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\pi} + C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\pi} - A_{a + b\sqrt{l}} z_{\pi}  \circ B_{a + b\sqrt{l}} z_{\text{acc}})] \\

&= e_{\text{acc}} +\boxed{ (\beta_{\pi, a} \beta_{\pi, b}' T) }  r^3 + \boxed{ (\beta_{\pi, a} \beta_{\pi, b}' K + \beta_{\pi, a}  \beta_{\text{acc}, b}' T +  \beta_{\text{acc}, a} \beta_{\pi, b}' T) } r^2 + \boxed{ (\beta_{\pi, a} \beta_{\text{acc, b}}' K + \beta_{\text{acc}, a} \beta_{\pi, b}' K + \beta_{\text{acc}, a} \beta_{\text{acc, b}}' T) } r^1 \\

\end{aligned}
$$

> 方框内的就是我们最终要计算得到的三个error term，注意这是三个scalar

其中$T$ 和$K$ 代表的两个多项式：

$$
\begin{aligned}

&T =  \mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\pi} + C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\pi} - A_{a + b\sqrt{l}} z_{\pi}  \circ B_{a + b\sqrt{l}} z_{\text{acc}} \\

&K = \mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\text{acc}} \\

\end{aligned}
$$

# Overhead for Compressed Verification

我们对比一下压缩之前的R1CS 约束系统：

$$
\begin{rcases}

\mu_{\text{acc}} C z_{\text{acc}} - A z_{\text{acc}} \circ B z_{\text{acc}}  = \bold{e} \\

C z_{\pi} - A z_{\pi} \circ B z_{\pi}  = \bold{0} \\

\end{rcases}

\overset{\text{fold}} \Longrightarrow

(\mu_{\text{acc}} + r) C (z_{\text{acc}} + r z_{\pi}) - A (z_{\text{acc}} + r z_{\pi})  \circ B (z_{\text{acc}} + r z_{\pi}) = \bold{e} + \boxed{T} r^1
$$

其中$T$ 代表多项式：

$$
T = \mu_{\text{acc}} C z_{\pi} + C z_{\text{acc}} - A z_{\text{acc}}  \circ B z_{\pi} - A  z_{\pi}  \circ B z_{\text{acc}}
$$

更intuitive 的数据对比：

$$
\def\arraystretch{1.5}
\begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \\ \hline

\#\text{error term} & 1 & 3 \\ \hdashline

\text{Is error vector} & \text{true} & \text{false} \\ \hdashline

\text{Commit or not} & \text{true} & \text{false} \\ \hdashline

\text{EC-op} & l & 0 \\ \hdashline

\end{array}
$$

如果觉得在R1CS约束系统中优势不够明显，没关系，我们把它放在支持customer gate的Plonk约束系统中优势就会变得相当明显了：

$$
\def\arraystretch{1.5}
\begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \\ \hline

\#\text{error term} & d - 1 & d + 1 \\ \hdashline

\text{Is error vector} & \text{true} & \text{false} \\ \hdashline

\text{Commit or not} & \text{true} & \text{false} \\ \hdashline

\text{EC-op} & (d - 1)l & 0 \\ \hdashline

\end{array}
$$

其中$d$ 代表gate 的degree，不压缩的话，pover需要对$d−1$个error term vector 做commit，就会有 $(d−1)l$个椭圆曲线的scalar mul 运算；如果压缩的话，error term 是一个scalar，不需要做commit。因此，压缩后省掉了GATE 约束fold 产生的error term vector，其commit 带来的 $(d−1)l$个椭圆曲线的scalar mul 运算。

-----

天下没有免费的午餐，那么压缩的成本在哪里呢？需要验证这$2\sqrt{l} - 2$ 个power of beta值$\beta_a, \beta_b' \text{ } \forall a,b \in [1, \sqrt{l} - 1]$ 满足下面的等式约束，这个校验也叫压缩过程的验证：

$$
\begin{aligned}

& \beta_1 \overset{?} = \beta \\

& \beta_{a + 1} \overset{?} = \beta_{a} * \beta, \forall a \in [1, \sqrt{l} - 2] \\

& \beta_1' \overset{?} = \beta_{\sqrt{l} - 1} * \beta \\

& \beta_{b + 1}' \overset{?} = \beta_{b}' * \beta_1', \forall b \in [1, \sqrt{l} - 2]  \\

\end{aligned}
$$

验证通过后才能对GATE 约束进行验证：

$$
\sum_{a = 0}^{\sqrt{l} - 1} \sum_{b = 0}^{\sqrt{l} - 1} \textcolor{red} {\beta_{a}} * \textcolor{red} {\beta_{b}'} * (\textcolor{green} {\mu} C_{a + b\sqrt{l}} \textcolor{red} {z} - A_{a + b\sqrt{l}} \textcolor{red} {z}  \circ B_{a + b\sqrt{l}} \textcolor{red} {z} ) \overset{?} = \textcolor{green} {e} \\
$$

> 用绿色标出来的是scalar 不需要commit，用红色标出来的是vector 需要commit。
>

----

在IVC电路中，**压缩过程的验证同GATE约束的验证一样，也需要delay 到最后，中间过程只需要把这两个验证过程的proof进行fold**，这也是自20年开始folding scheme的标准做法，具体细节可以参考这篇文章，其中有详尽的security 证明。

两个压缩过程的proof 实例在fold的过程中会产生的**error term vector**，为什么又出现了一个**error term vector**，error term vector 不是已经通过power of beta 压缩成一个scalar 了吗？这里可能有些绕，原始paper 在这里也是一句话带过，没关系，我们具象化一下看看：

假定$l=9$，一个由$2\sqrt{l} - 2$ 个power of beta组成的向量$\beta_{\text{acc}, i} \forall i \in [0, 2\sqrt{l} - 3]$ 作为R1CS 约束系统的witness ，上述的$2\sqrt{l} - 2$ 个degree为2的等式验证相当于$2\sqrt{l} - 2$ 个gate，因此我们可以构造出这么一个running R1CS 实例出来：

$$
\begin{bmatrix}

1 & 0 & 0 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 & 0 & 0 \\

0 & 0 & 1 & 0 & 0 & 0 \\

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \\

\beta_{\text{acc}, 1}   \\

\beta_{\text{acc}, 2}  \\

\beta_{\text{acc}, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\text{acc}}}\\

\end{bmatrix}

\circ

\begin{bmatrix}

0 & 0 & 0 & 0 & 1 & 0 \\

0 & 0 & 0 & 0 & 0 & 1 \\

0 & 0 & 1 & 0 & 0 & 0 \\

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \\

\beta_{\text{acc}, 1}   \\

\beta_{\text{acc}, 2}  \\

\beta_{\text{acc}, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\text{acc}}}\\

\end{bmatrix}

\mu_{\text{acc}}'

\begin{bmatrix}

0 & 0 & 0 & 0 & 0  & 1 \\

0 & 1 & 0 & 0 & 0  & 0 \\

0 & 0 & 1 & 0 & 0  & 0 \\

0 & 0 & 0 & 1 & 0  & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \\

\beta_{\text{acc}, 1}   \\

\beta_{\text{acc}, 2}  \\

\beta_{\text{acc}, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\text{acc}}}\\

\end{bmatrix}

\begin{bmatrix}

e_{\text{acc}, 0}' \\

e_{\text{acc}, 1}' \\

e_{\text{acc}, 2}' \\

e_{\text{acc}, 3}' \\

e_{\text{acc}, 4}' \\

e_{\text{acc}, 5}' \\

\end{bmatrix}
$$

其中绿色标记的是public variable。

同样的，我们也可以构造出一个incremental R1CS 实例出来：

$$
\begin{bmatrix}

1 & 0 & 0 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 & 0 & 0 \\

0 & 0 & 1 & 0 & 0 & 0 \\

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \\

\beta_{\pi, 1}   \\

\beta_{\pi, 2}  \\

\beta_{\pi, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\pi}}\\

\end{bmatrix}

\circ

\begin{bmatrix}

0 & 0 & 0 & 0 & 1 & 0 \\

0 & 0 & 0 & 0 & 0 & 1 \\

0 & 0 & 1 & 0 & 0 & 0 \\

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \\

\beta_{\pi, 1}   \\

\beta_{\pi, 2}  \\

\beta_{\pi, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\pi}}\\

\end{bmatrix}

\begin{bmatrix}

0 & 0 & 0 & 0 & 0  & 1 \\

0 & 1 & 0 & 0 & 0  & 0 \\

0 & 0 & 1 & 0 & 0  & 0 \\

0 & 0 & 0 & 1 & 0  & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \\

\beta_{\pi, 1}   \\

\beta_{\pi, 2}  \\

\beta_{\pi, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\pi}}\\

\end{bmatrix}

把两个proof 进行fold，令：

$$
z_{\text{acc}}' =

\begin{bmatrix}

\beta_{\text{acc}, 0} \\

\beta_{\text{acc}, 1}   \\

\beta_{\text{acc}, 2}  \\

\beta_{\text{acc}, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\text{acc}}}\\

\end{bmatrix},

z_{\pi}' =

\begin{bmatrix}

\beta_{\pi, 0} \\

\beta_{\pi 1}   \\

\beta_{\pi, 2}  \\

\beta_{\pi, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\pi}}\\

\end{bmatrix}
$$

则：

$$
\begin{aligned}

&\mu_{\text{acc}}' C' z_{\text{acc}}' - A' z_{\text{acc}}' \circ B' z_{\text{acc}}' = \bold{e_{\text{acc}}'} \\

&C' z_{\pi}' - A' z_{\pi}' \circ B' z_{\pi}' = 0 \\

\end{aligned}
$$

fold的过程当然会产生cross/error term vector了，我们会很自然地计算得到相应的error term vector：

$$
\begin{aligned}

&(\mu_{\text{acc}}' + r) C' (z_{\text{acc}}' + r z_{\pi}') - A' (z_{\text{acc}}' + r z_{\pi}') \circ B' (z_{\text{acc}}' + r z_{\pi}') \\

&= (\mu_{\text{acc}}' C' z_{\text{acc}}' - A' z_{\text{acc}}' \circ B' z_{\text{acc}}') + r \boxed{(\mu_{\text{acc}}' z_{\pi}' + z_{\text{acc}}' - A' z_{\pi}' B' z_{\text{acc}}' - A' z_{\text{acc}}' B' z_{\pi}')} \\

&= e_{\text{acc}}' + r \boxed{(\mu_{\text{acc}}' z_{\pi}' + z_{\text{acc}}' - A' z_{\pi}' B' z_{\text{acc}}' - A' z_{\text{acc}}' B' z_{\pi}')} \\

\end{aligned}
$$

只是这个长度不再是$l$ 而是$2\sqrt{l} - 2$，已经不在一个量级上了！**因为是另外一套R1CS实例了，所以需要额外的一个电路来验证压缩过程**。

----

加上压缩verification 带来的成本，我们先看一下R1CS约束系统的对比数据：

$$
\def\arraystretch{1.5}
\begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \\ \hline

\#\text{commitment} & 2 & 3 \\ \hdashline

\#\text{EC-op for commitment} & m+ l & m + (2\sqrt{l} - 2) * 2 \\ \hdashline

\#\text{F-op for error term}  & 0 & 2 \\

\end{array}
$$

压缩前有两个commitment，一个是$z$ 向量中的witness 部分，一个是error term vector $e$，长度分别为$m$ 和$l$；压缩后，除了$z$ 向量中的witness 部分需要commitment，还有两个长度均为$2\sqrt{l} - 2$ 的power of beta 和 其相应的error term vector $e′$。

如果觉得在R1CS约束系统中优势不够明显，没关系，我们再看看支持customer gate的Plonk约束系统的对比数据：

$$
\def\arraystretch{1.5}
\begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \\ \hline

\#\text{commitment} & d & (d -1) + 2 \\ \hdashline

\#\text{EC-op for commitment} & m + \textcolor{red} {(d - 1)l} & m + \textcolor{green} {2 * (2\sqrt{l} - 2)} \\ \hdashline

\#\text{F-op for error term}  & 0 & d \\

\end{array}
$$

可以很明显地看到，椭圆曲线的运算量不是跟约束的数量$l$ 成线性关系，而是与 $2\sqrt{l} - 2$ 成正比；而且跟gate 的degree $d$ 无关。鉴于$d−1$ 个error term vector已经被压缩成了$d−1$个scalar 值，原本的$d$ 个commitment 加法变成了$d$ 个scalar 值的加法。scalar 的加法相比EC的加法不是要便宜太多？

最后，我们把压缩技术放在IVC 的SPS 协议里看看整个流程长什么样子。

# Updated Protocol

我们仍然基于R1CS约束系统来detail 整个协议的过程：

## Accumulation Prover

### step 1: 初始化两个R1CS实例

一个是为Compress Verification用的$(A′,B′,C′)$，另外一个是Accumulation 用的$(A,B,C)$。

### step 2: 计算Compress Verification error term

基于：

$$
\mu_{\text{acc}}', z_{\text{acc}}' =

\begin{bmatrix}

\beta_{\text{acc}, 0} \\

\beta_{\text{acc}, 1}   \\

\beta_{\text{acc}, 2}  \\

\beta_{\text{acc}, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\text{acc}}}\\

\end{bmatrix},

z_{\pi}' =

\begin{bmatrix}

\beta_{\pi, 0} \\

\beta_{\pi 1}   \\

\beta_{\pi, 2}  \\

\beta_{\pi, 3} \\

\textcolor{green} {1} \\

\textcolor{green} {\beta_{\pi}}\\

\end{bmatrix},

(A', B', C')
$$

计算得到压缩proof 生成的error term $e′$：

$$
\begin{aligned}

&(\mu_{\text{acc}}' + r) C' (z_{\text{acc}}' + r z_{\pi}') - A' (z_{\text{acc}}' + r z_{\pi}') \circ B' (z_{\text{acc}}' + r z_{\pi}') \\

&= e_{\text{acc}}' + r \boxed{(\mu_{\text{acc}}' z_{\pi}' + z_{\text{acc}}' - A' z_{\pi}' B' z_{\text{acc}}' - A' z_{\text{acc}}' B' z_{\pi}')} \\

e' &= (\mu_{\text{acc}}' z_{\pi}' + z_{\text{acc}}' - A' z_{\pi}' B' z_{\text{acc}}' - A' z_{\text{acc}}' B' z_{\pi}')

\end{aligned}
$$

因为本身就是degree 为2的check，所以error term就是一个长度为$2\sqrt{l} - 2$ 的向量。

### step 3: 生成error term 相应的commitment
对compressed verification error term vector $e′$ 进行commit:

$$
\widetilde{e'} =\text{commit}(e')
$$

对power of beta vector $\beta_{\pi}$ 本身进行commit：

$$
\widetilde{\boldsymbol{\beta}_{\pi}} = \text{commit}(\boldsymbol{\beta}_{\pi})
$$

### step 4: 计算Accumulation error term
基于：

$$
\mu_{\text{acc}}、z_{\text{acc}}、z_{\pi}、\{A, B, C\}
$$

计算Accumulation error term：

$$
\begin{aligned}

&\sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (\beta_{\text{acc}, a} + r \beta_{\pi, a}) * (\beta_{\text{acc}, b}' + r \beta_{\pi, b}') * [(\mu_{\text{acc}} + r) C_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi}) - A_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi})  \circ B_{a + b\sqrt{l}} (z_{\text{acc}} + r z_{\pi})] \\

&= \sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (\beta_{\text{acc}, a} + r \beta_{\pi, a}) * (\beta_{\text{acc}, b}' + r \beta_{\pi, b}') \\

&= \sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (e_{\text{acc}, a + b\sqrt{l}} +\boxed{ (\beta_{\pi, a} \beta_{\pi, b}' T) }  r^3 + \boxed{ (\beta_{\pi, a} \beta_{\pi, b}' K + \beta_{\pi, a}  \beta_{\text{acc}, b}' T +  \beta_{\text{acc}, a} \beta_{\pi, b}' T) } r^2 + \boxed{ (\beta_{\pi, a} \beta_{\text{acc, b}}' K + \beta_{\text{acc}, a} \beta_{\pi, b}' K + \beta_{\text{acc}, a} \beta_{\text{acc, b}}' T) } r^1) \\

e_1 &= \sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (\beta_{\pi, a} \beta_{\text{acc, b}}' K + \beta_{\text{acc}, a} \beta_{\pi, b}' K + \beta_{\text{acc}, a} \beta_{\text{acc, b}}' T)  \\

e_2 &= \sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (\beta_{\pi, a} \beta_{\pi, b}' K + \beta_{\pi, a}  \beta_{\text{acc}, b}' T +  \beta_{\text{acc}, a} \beta_{\pi, b}' T) \\

e_3 &= \sum_{a = 0}^{\sqrt{l} -1} \sum_{b = 0}^{\sqrt{l} -1} (\beta_{\pi, a} \beta_{\pi, b}' T) \\

\end{aligned}
$$

其中：

$$
\begin{aligned}

&K = \mu_{\text{acc}} C_{a + b\sqrt{l}} z_{\text{acc}} - A_{a + b\sqrt{l}} z_{\text{acc}}  \circ B_{a + b\sqrt{l}} z_{\text{acc}} \\

\end{aligned}
$$

经过了压缩处理，已经变成了3个scalar 值。

### step 5: fold R1CS witness

$$
\begin{aligned}

& \boldsymbol{\beta}_{\text{acc}}^{*} \leftarrow \boldsymbol{\beta}_{\text{acc}} \oplus r \boldsymbol{\beta}_{\pi} \\

& e_{\text{acc}}'^{*} \leftarrow e_{\text{acc}}' \oplus r e' \\

&w_{\text{acc}}^{*} \leftarrow w_{\text{acc}} \oplus r w_{\pi} \\

\end{aligned}
$$

### step 6: fold R1CS intance
 
 
$$
\begin{aligned}

& \textcolor{red} {\widetilde{\boldsymbol{\beta}_{\text{acc}}^{*}}} \leftarrow \widetilde{\boldsymbol{\beta}_{\text{acc}}} \oplus r \widetilde{\boldsymbol{\beta}_{\pi}} \\

& \textcolor{red} {\widetilde{e_{\text{acc}}'^{*}}} \leftarrow \widetilde{e_{\text{acc}}'} \oplus r \widetilde{e'} \\

& \textcolor{red} {\widetilde{w_{\text{acc}}^{*}}} \leftarrow \widetilde{w_{\text{acc}}} \oplus r \widetilde{w_{\pi}} \\

& \textcolor{red} {e} \leftarrow e_{\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \\

\end{aligned}
$$

## Accumulation Verifier

### step 1: fold R1CS instance

基于Accumulation Prover提供的四个accumuation error term scalar 值$e_{\text{acc}}、e_1 、e_2、e_3$，accumulation witness 对应的commitment $\widetilde{w_{\text{acc}}}、\widetilde{w_{\pi}}$，compress verification error term 对应的commitment $\widetilde{e_{\text{acc}}'} 、\widetilde{e'} $，以及power of beta vector $\widetilde{\beta_{\text{acc}}}、\widetilde{\beta_{\pi}}$，进行instance的fold任务：

$$
\begin{aligned}

& \textcolor{green} {\widetilde{\boldsymbol{\beta}_{\text{acc}}^{*}}} \leftarrow \widetilde{\boldsymbol{\beta}_{\text{acc}}} \oplus r \widetilde{\boldsymbol{\beta}_{\pi}} \\

& \textcolor{green} {\widetilde{e_{\text{acc}}'^{*}}} \leftarrow \widetilde{e_{\text{acc}}'} \oplus r \widetilde{e'} \\

& \textcolor{green} {\widetilde{w_{\text{acc}}^{*}}} \leftarrow \widetilde{w_{\text{acc}}} \oplus r \widetilde{w_{\pi}} \\

& \textcolor{green} {e} \leftarrow e_{\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \\

\end{aligned}
$$

### step 2: consistancy check

验证accumulation prover fold的正确性，或者校验accumuation verifier 与 accumulation prover fold的一致性。也就是，比较上面红色标记的部分是否与绿色标记的部分相等。

在基于cycle curves 的实现方案中，这部分校验工作是在IVC的下一个step 完成的。关于cycle curves 更多的细节，感兴趣的可以参考[Nova from scratch](https://learnblockchain.cn/article/6429) 和 [CycleFold based Nova](https://learnblockchain.cn/article/6452)。

# 参考资料

【1】ProtoStar 论文：https\://eprint.iacr.org/2023/620.pdf

# Cycle curves 实现相关资料：

【1】Revisiting Nova论文: https\://eprint.iacr.org/2023/969.pd

【2】CycleFold 论文：https\://eprint.iacr.org/2023/1192.pdf

【3】Nova from scratch ： https\://learnblockchain.cn/article/6429

【4】CycleFold base Nova: https\://learnblockchain.cn/article/6452

Thanks

十分感谢@AntalphaLabs 上月底提供的线下hackerhouse ，有机会亲历并学习SecbitLabs @郭宇老师、@even 做zk research 的思路和方法，并讨论了很多folding scheme相关的问题

非常感谢参加hackerhouse 一起交流讨论过protostar的小伙伴们 @yingfei、 @Harry L 、@周洋、 @CJ 、@hhh，尽管当时对protostar的认识还比较肤浅，还没摸到它的门框儿，但至少有一个初步的overview 概念 -)

写在前面的

ProtoStar 论文中非常经典的一张图：

ProtoStar 论文中最核心、最具创新的应该就是3.5 章节，其它部分基本都是对整个folding scheme 的抽象，如果读完还是不知道3.5 章节的compress verification tech在整个协议中怎么用，建议反复研究上面这张图(论图的重要性)

为了方便描述，我们以最简单的R1CS约束系统为base来讨论，更容易感知到Protostar 的intuition，适当的时候会拓展到plonkish约束系统，以便有更全局的sense

本文旨在厘清3.5章节的compress verification tech 在整个folding scheme中应用，IVC部分基本可以参考 revisiting Nova 的cycle curves方案。本文的tag是"上篇"，“下篇”将会整合plonkish 的三大约束GATE 约束、Wiring 约束、Lookup约束系统地串一下ProtoStar 协议

Compress Verification Degree

ROUND ONE

在R1CS约束系统里面只有一种约束，就是GATE的约束，Witness 是z 向量。电路的描述，也就是A、B、C三个矩阵，在setup 阶段就已经完成，矩阵的每一行对应一个gate。SPS prover 要做的就是根据业务计算逻辑填充这个z 向量，SPS verifier 拿着这个z 向量验证是否满足所有GATE的约束：

$$ Cz - Az \circ Bz \overset{?}= \bold{0} $$

但是这里有个问题，这个等式的左右两边是一个长度为$l$ 的向量，$l$ 代表的是GATE的个数。也就是说，在R1CS约束系统中，SPS verifier 需要校验$l$ 个degree 为2的等式：

$$ \begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \

&C_1 z - A_1 z \circ B_1 z \overset{?} = 0 \

&... \

&C{l - 1} z - A{l - 1} z \circ B_{l - 1} z \overset{?} = 0 \

\end{aligned} $$

有没有可能把它压缩成一个等式？

ROUND TWO

引入一个public 的变量，fold factor $$\beta$$：

$$ \begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \

&\beta^1* (C_1 z - A_1 z \circ B_1 z) \overset{?} = 0 \

&... \

&\beta^{l - 1} * (C{l - 1} z - A{l - 1} z \circ B_{l - 1} z) \overset{?} = 0 \

\end{aligned} $$

最后变成一个等式：

$$ \beta^0 (C_0 z - A_0 z \circ B_0 z) + \beta^1 (C_1 z - A_1 z \circ B1 z) + ... + \beta^{l - 1} * (C{l - 1} z - A{l - 1} z \circ B{l - 1} z) \overset{?} = 0 $$

所以放在SPS 协议里，prover 除了向verifier 发送message $$z$$ 向量，还需要发送另外一个message $$β$$ 向量 $\begin{bmatrix}\beta^0 \\beta^1 \... \\beta^{l - 1} \\end{bmatrix}$ ，verifier 拿着这两个向量验证上面的等式是否成立就行了，对吗？还漏掉了一件事儿，需要验证message $$β$$ 向量的合法性(正确性)，需要满足：

$$ \begin{aligned}

&\beta_0 \overset{?} = 1 \

&\beta{i + 1} \overset{?} = \beta{i} * \beta, \forall i \in [0, l - 2] \

\end{aligned} $$

$$β$$ 向量的每个元素都要校验，这里要校验$$l$$ 个degree 为2的等式。另外还要校验压缩后的等式：

$$ \beta_0 (C_0 z - A_0 z \circ B_0 z) + \beta_1 (C_1 z - A_1 z \circ B1 z) + ... + \beta{l - 1} * (C{l - 1} z - A{l - 1} z \circ B_{l - 1} z) \overset{?} = 0 $$

由于增加了一个变量$\beta_i$，所以等式的degree变成了3。

为什么要校验$$\beta$$ 向量？

如果不校验$$β$$ 向量，prover 随便给定一个不满足R1CS约束的$$z$$ 向量，然后再给一组可以满足上面等式的$β$ 向量(比如$\bold{0}$ 向量)，这样就很容易骗过verifier。

这里的问题是，prover 发送的message $β$ 向量长度$l$ 不可控，verifier 验证的复杂度$O(l)$ 也不可控，有可能很大。有没有可能再压缩一下？

ROUND THREE

prover 发送这么一个message，由两个向量组成：

$$ \beta =

\begin{bmatrix}

\beta^0 \

\beta^1 \

\beta^2 \

... \

\beta^{\sqrt{l} - 1}

\end{bmatrix}

\beta' =

\begin{bmatrix}

\beta^{0 * \sqrt{l}} \

\beta^{1 * \sqrt{l}} \

\beta^{2 * \sqrt{l}} \

... \

\beta^{(\sqrt{l} - 1)\sqrt{l}}

\end{bmatrix} $$

然后，原压缩后的等式变成了：

$$ \sum{a = 0}^{\sqrt{l} - 1} \sum{b = 0}^{\sqrt{l} - 1} \beta_a \beta_b' (C{a + b\sqrt{l}}z - A{a + b\sqrt{l}}z \circ B_{a + b\sqrt{l}}z) \overset{?} = 0 $$

等式的degree 增加了2，变成了4。

同样，verifier 需要验证这个新增加的message 的合法性：

$$ \begin{aligned}

&\textcircled {1} \beta_1 \overset{?} = \beta \

&\textcircled {2} \beta{i + 1} \overset{?} = \beta{i} * \beta, \forall i \in [1, \sqrt{l} - 2] \

&\textcircled {3} \beta1' \overset{?} = \beta{\sqrt{l} - 1} * \beta \

&\textcircled {4} \beta{i + 1}' \overset{?} = \beta{i}' * \beta_1', \forall i \in [1, \sqrt{l} - 2] \

\end{aligned} $$

这里需要验证$2\sqrt{l} - 2$ 个degree 为2的等式。

Deserve it or not

到这里，在R1CS约束系统中，verifier 从原本要验证$l$ 个degree为2的等式，变成了验证1个degree为4的等式加上$2\sqrt{l} - 2$ 个degree 为2的等式，那么这么做是否值得：

$$ l \text{deg}(2) \textcolor{red} {\overset{?} >} 1 \text{deg}(2 + 2) + (2\sqrt{l} - 2) * \text{deg}(2) $$

可能在R1CS约束系统中优势还不够明显，没关系，在支持customer gate的plonkish 约束系统中，gate的degree就不再是2了，而是自定义的degree-$d$：

$$ l \text{deg}(d) \textcolor{red} {\overset{?} >} 1 \text{deg}(d + 2) + (2\sqrt{l} - 2) * \text{deg}(2) $$

所以当gate 的个数$l$ ，gate的degree $d$，都变得很大时，这里压缩的优势就变得相当明显。它计算的复杂度由$O(ld)$ 变成了 $O((d+2)+4\sqrt{l} - 4)$ ，直接降了一个数量级，所以答案是Deserve it!

Compressed Verification in Accumulation

经过压缩后，SPS verifier 不再是验证$l$ 个等式：

$$ \begin{aligned}

&C_0 z - A_0 z \circ B_0 z \overset{?} = 0 \

&C_1 z - A_1 z \circ B_1 z \overset{?} = 0 \

&... \

&C{l - 1} z - A{l - 1} z \circ B_{l - 1} z \overset{?} = 0 \

\end{aligned} $$

而是$1+ (2\sqrt{l} - 2)$ 个等式：

$$ \begin{aligned}

&\textcircled {1} \sum{a = 0}^{\sqrt{l} - 1} \sum{b = 0}^{\sqrt{l} - 1} \beta_a \beta_b' (C{a + b\sqrt{l}}z - A{a + b\sqrt{l}}z \circ B_{a + b\sqrt{l}}z) \overset{?} = 0 \

&\textcircled {2} \beta_1 \overset{?} = \beta \

&\textcircled {3} \beta{i + 1} \overset{?} = \beta{i} * \beta, \forall i \in [1, \sqrt{l} - 2] \

&\textcircled {4} \beta1' \overset{?} = \beta{\sqrt{l} - 1} * \beta \

&\textcircled {5} \beta{i + 1}' \overset{?} = \beta{i}' * \beta_1', \forall i \in [1, \sqrt{l} - 2] \

\end{aligned} $$

在R1CS约束系统中，假设有两个组instance$\text{acc} = {\beta\text{acc}, \beta\text{acc}', z\text{acc}}$ 和$\pi = {\beta\pi, \beta\pi', z{\pi}}$，前者为relaxed instance，后者为 incremental instance：

$$ \begin{aligned}

&\sum{a = 0}^{\sqrt{l} - 1} \sum{b = 0}^{\sqrt{l} - 1} \beta{\text{acc}, a} * \beta{\text{acc},b}' * (\mu{\text{acc}} C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z{\text{acc}} ) \overset{?} = e{\text{acc}} \

&\sum{a = 0}^{\sqrt{l} - 1} \sum{b = 0}^{\sqrt{l} - 1} \beta{\pi, a} * \beta{\pi,b}' * (C{a + b\sqrt{l}} z{\pi} - A{a + b\sqrt{l}} z{\pi} \circ B{a + b\sqrt{l}} z{\pi} ) \overset{?} = 0 \

\end{aligned} $$

我们将这两个instance 进行fold：

$$ \begin{aligned}

&(\beta{\text{acc}, a} + r \beta{\pi, a}) (\beta{\text{acc}, b}' + r \beta{\pi, b}') [(\mu{\text{acc}} + r) C{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi}) - A{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi}) \circ B{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi})] \

&= (\beta{\text{acc}, a} + r \beta{\pi, a}) * (\beta{\text{acc}, b}' + r \beta{\pi, b}') \

&*[(\mu{\text{acc}} C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z{\text{acc}}) + r (\mu{\text{acc}} C{a + b\sqrt{l}} z{\pi} + C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z{\pi} - A{a + b\sqrt{l}} z{\pi} \circ B{a + b\sqrt{l}} z{\text{acc}})] \

&= e{\text{acc}} +\boxed{ (\beta{\pi, a} \beta{\pi, b}' T) } r^3 + \boxed{ (\beta{\pi, a} \beta{\pi, b}' K + \beta{\pi, a} \beta{\text{acc}, b}' T + \beta{\text{acc}, a} \beta{\pi, b}' T) } r^2 + \boxed{ (\beta{\pi, a} \beta{\text{acc, b}}' K + \beta{\text{acc}, a} \beta{\pi, b}' K + \beta{\text{acc}, a} \beta_{\text{acc, b}}' T) } r^1 \

\end{aligned} $$

方框内的就是我们最终要计算得到的三个error term，注意这是三个scalar

其中$T$ 和$K$ 代表的两个多项式：

$$ \begin{aligned}

&T = \mu{\text{acc}} C{a + b\sqrt{l}} z{\pi} + C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z{\pi} - A{a + b\sqrt{l}} z{\pi} \circ B{a + b\sqrt{l}} z_{\text{acc}} \

&K = \mu{\text{acc}} C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z_{\text{acc}} \

\end{aligned} $$

Overhead for Compressed Verification

我们对比一下压缩之前的R1CS 约束系统：

$$ \begin{rcases}

\mu{\text{acc}} C z{\text{acc}} - A z{\text{acc}} \circ B z{\text{acc}} = \bold{e} \

C z{\pi} - A z{\pi} \circ B z_{\pi} = \bold{0} \

\end{rcases}

\overset{\text{fold}} \Longrightarrow

(\mu{\text{acc}} + r) C (z{\text{acc}} + r z{\pi}) - A (z{\text{acc}} + r z{\pi}) \circ B (z{\text{acc}} + r z_{\pi}) = \bold{e} + \boxed{T} r^1 $$

其中$T$ 代表多项式：

$$ T = \mu{\text{acc}} C z{\pi} + C z{\text{acc}} - A z{\text{acc}} \circ B z{\pi} - A z{\pi} \circ B z_{\text{acc}} $$

更intuitive 的数据对比：

$$ \def\arraystretch{1.5} \begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \ \hline

#\text{error term} & 1 & 3 \ \hdashline

\text{Is error vector} & \text{true} & \text{false} \ \hdashline

\text{Commit or not} & \text{true} & \text{false} \ \hdashline

\text{EC-op} & l & 0 \ \hdashline

\end{array} $$

如果觉得在R1CS约束系统中优势不够明显，没关系，我们把它放在支持customer gate的Plonk约束系统中优势就会变得相当明显了：

$$ \def\arraystretch{1.5} \begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \ \hline

#\text{error term} & d - 1 & d + 1 \ \hdashline

\text{Is error vector} & \text{true} & \text{false} \ \hdashline

\text{Commit or not} & \text{true} & \text{false} \ \hdashline

\text{EC-op} & (d - 1)l & 0 \ \hdashline

\end{array} $$

其中$d$ 代表gate 的degree，不压缩的话，pover需要对$d−1$个error term vector 做commit，就会有 $(d−1)l$个椭圆曲线的scalar mul 运算；如果压缩的话，error term 是一个scalar，不需要做commit。因此，压缩后省掉了GATE 约束fold 产生的error term vector，其commit 带来的 $(d−1)l$个椭圆曲线的scalar mul 运算。

天下没有免费的午餐，那么压缩的成本在哪里呢？需要验证这$2\sqrt{l} - 2$ 个power of beta值$\beta_a, \beta_b' \text{ } \forall a,b \in [1, \sqrt{l} - 1]$ 满足下面的等式约束，这个校验也叫压缩过程的验证：

$$ \begin{aligned}

& \beta_1 \overset{?} = \beta \

& \beta{a + 1} \overset{?} = \beta{a} * \beta, \forall a \in [1, \sqrt{l} - 2] \

& \beta1' \overset{?} = \beta{\sqrt{l} - 1} * \beta \

& \beta{b + 1}' \overset{?} = \beta{b}' * \beta_1', \forall b \in [1, \sqrt{l} - 2] \

\end{aligned} $$

验证通过后才能对GATE 约束进行验证：

$$ \sum{a = 0}^{\sqrt{l} - 1} \sum{b = 0}^{\sqrt{l} - 1} \textcolor{red} {\beta{a}} * \textcolor{red} {\beta{b}'} * (\textcolor{green} {\mu} C{a + b\sqrt{l}} \textcolor{red} {z} - A{a + b\sqrt{l}} \textcolor{red} {z} \circ B_{a + b\sqrt{l}} \textcolor{red} {z} ) \overset{?} = \textcolor{green} {e} \ $$

用绿色标出来的是scalar 不需要commit，用红色标出来的是vector 需要commit。

在IVC电路中，压缩过程的验证同GATE约束的验证一样，也需要delay 到最后，中间过程只需要把这两个验证过程的proof进行fold，这也是自20年开始folding scheme的标准做法，具体细节可以参考这篇文章，其中有详尽的security 证明。

两个压缩过程的proof 实例在fold的过程中会产生的error term vector，为什么又出现了一个error term vector，error term vector 不是已经通过power of beta 压缩成一个scalar 了吗？这里可能有些绕，原始paper 在这里也是一句话带过，没关系，我们具象化一下看看：

假定$l=9$，一个由$2\sqrt{l} - 2$ 个power of beta组成的向量$\beta_{\text{acc}, i} \forall i \in [0, 2\sqrt{l} - 3]$ 作为R1CS 约束系统的witness ，上述的$2\sqrt{l} - 2$ 个degree为2的等式验证相当于$2\sqrt{l} - 2$ 个gate，因此我们可以构造出这么一个running R1CS 实例出来：

$$ \begin{bmatrix}

1 & 0 & 0 & 0 & 0 & 0 \

0 & 1 & 0 & 0 & 0 & 0 \

0 & 0 & 1 & 0 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \

\beta_{\text{acc}, 1} \

\beta_{\text{acc}, 2} \

\beta_{\text{acc}, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\text{acc}}}\

\end{bmatrix}

\circ

\begin{bmatrix}

0 & 0 & 0 & 0 & 1 & 0 \

0 & 0 & 0 & 0 & 0 & 1 \

0 & 0 & 1 & 0 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \

\beta_{\text{acc}, 1} \

\beta_{\text{acc}, 2} \

\beta_{\text{acc}, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\text{acc}}}\

\end{bmatrix}

\mu_{\text{acc}}'

\begin{bmatrix}

0 & 0 & 0 & 0 & 0 & 1 \

0 & 1 & 0 & 0 & 0 & 0 \

0 & 0 & 1 & 0 & 0 & 0 \

0 & 0 & 0 & 1 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\text{acc}, 0} \

\beta_{\text{acc}, 1} \

\beta_{\text{acc}, 2} \

\beta_{\text{acc}, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\text{acc}}}\

\end{bmatrix}

\begin{bmatrix}

e_{\text{acc}, 0}' \

e_{\text{acc}, 1}' \

e_{\text{acc}, 2}' \

e_{\text{acc}, 3}' \

e_{\text{acc}, 4}' \

e_{\text{acc}, 5}' \

\end{bmatrix} $$

其中绿色标记的是public variable。

同样的，我们也可以构造出一个incremental R1CS 实例出来：

$$ \begin{bmatrix}

1 & 0 & 0 & 0 & 0 & 0 \

0 & 1 & 0 & 0 & 0 & 0 \

0 & 0 & 1 & 0 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \

\beta_{\pi, 1} \

\beta_{\pi, 2} \

\beta_{\pi, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\pi}}\

\end{bmatrix}

\circ

\begin{bmatrix}

0 & 0 & 0 & 0 & 1 & 0 \

0 & 0 & 0 & 0 & 0 & 1 \

0 & 0 & 1 & 0 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \

\beta_{\pi, 1} \

\beta_{\pi, 2} \

\beta_{\pi, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\pi}}\

\end{bmatrix}

\begin{bmatrix}

0 & 0 & 0 & 0 & 0 & 1 \

0 & 1 & 0 & 0 & 0 & 0 \

0 & 0 & 1 & 0 & 0 & 0 \

0 & 0 & 0 & 1 & 0 & 0 \

\end{bmatrix}

\begin{bmatrix}

\beta_{\pi, 0} \

\beta_{\pi, 1} \

\beta_{\pi, 2} \

\beta_{\pi, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\pi}}\

\end{bmatrix}

把两个proof 进行fold，令：

$$ z_{\text{acc}}' =

\begin{bmatrix}

\beta_{\text{acc}, 0} \

\beta_{\text{acc}, 1} \

\beta_{\text{acc}, 2} \

\beta_{\text{acc}, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\text{acc}}}\

\end{bmatrix},

z_{\pi}' =

\begin{bmatrix}

\beta_{\pi, 0} \

\beta_{\pi 1} \

\beta_{\pi, 2} \

\beta_{\pi, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\pi}}\

\end{bmatrix} $$

则：

$$ \begin{aligned}

&\mu{\text{acc}}' C' z{\text{acc}}' - A' z{\text{acc}}' \circ B' z{\text{acc}}' = \bold{e_{\text{acc}}'} \

&C' z{\pi}' - A' z{\pi}' \circ B' z_{\pi}' = 0 \

\end{aligned} $$

fold的过程当然会产生cross/error term vector了，我们会很自然地计算得到相应的error term vector：

$$ \begin{aligned}

&(\mu{\text{acc}}' + r) C' (z{\text{acc}}' + r z{\pi}') - A' (z{\text{acc}}' + r z{\pi}') \circ B' (z{\text{acc}}' + r z_{\pi}') \

&= (\mu{\text{acc}}' C' z{\text{acc}}' - A' z{\text{acc}}' \circ B' z{\text{acc}}') + r \boxed{(\mu{\text{acc}}' z{\pi}' + z{\text{acc}}' - A' z{\pi}' B' z{\text{acc}}' - A' z{\text{acc}}' B' z_{\pi}')} \

&= e{\text{acc}}' + r \boxed{(\mu{\text{acc}}' z{\pi}' + z{\text{acc}}' - A' z{\pi}' B' z{\text{acc}}' - A' z{\text{acc}}' B' z{\pi}')} \

\end{aligned} $$

只是这个长度不再是$l$ 而是$2\sqrt{l} - 2$，已经不在一个量级上了！因为是另外一套R1CS实例了，所以需要额外的一个电路来验证压缩过程。

加上压缩verification 带来的成本，我们先看一下R1CS约束系统的对比数据：

$$ \def\arraystretch{1.5} \begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \ \hline

#\text{commitment} & 2 & 3 \ \hdashline

#\text{EC-op for commitment} & m+ l & m + (2\sqrt{l} - 2) * 2 \ \hdashline

#\text{F-op for error term} & 0 & 2 \

\end{array} $$

压缩前有两个commitment，一个是$z$ 向量中的witness 部分，一个是error term vector $e$，长度分别为$m$ 和$l$；压缩后，除了$z$ 向量中的witness 部分需要commitment，还有两个长度均为$2\sqrt{l} - 2$ 的power of beta 和其相应的error term vector $e′$。

如果觉得在R1CS约束系统中优势不够明显，没关系，我们再看看支持customer gate的Plonk约束系统的对比数据：

$$ \def\arraystretch{1.5} \begin{array}{c:c:c}

& \text{before compressed} & \text{after compressed} \ \hline

#\text{commitment} & d & (d -1) + 2 \ \hdashline

#\text{EC-op for commitment} & m + \textcolor{red} {(d - 1)l} & m + \textcolor{green} {2 * (2\sqrt{l} - 2)} \ \hdashline

#\text{F-op for error term} & 0 & d \

\end{array} $$

可以很明显地看到，椭圆曲线的运算量不是跟约束的数量$l$ 成线性关系，而是与 $2\sqrt{l} - 2$ 成正比；而且跟gate 的degree $d$ 无关。鉴于$d−1$ 个error term vector已经被压缩成了$d−1$个scalar 值，原本的$d$ 个commitment 加法变成了$d$ 个scalar 值的加法。scalar 的加法相比EC的加法不是要便宜太多？

最后，我们把压缩技术放在IVC 的SPS 协议里看看整个流程长什么样子。

Updated Protocol

我们仍然基于R1CS约束系统来detail 整个协议的过程：

Accumulation Prover

step 1: 初始化两个R1CS实例

一个是为Compress Verification用的$(A′,B′,C′)$，另外一个是Accumulation 用的$(A,B,C)$。

step 2: 计算Compress Verification error term

基于：

$$ \mu{\text{acc}}', z{\text{acc}}' =

\begin{bmatrix}

\beta_{\text{acc}, 0} \

\beta_{\text{acc}, 1} \

\beta_{\text{acc}, 2} \

\beta_{\text{acc}, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\text{acc}}}\

\end{bmatrix},

z_{\pi}' =

\begin{bmatrix}

\beta_{\pi, 0} \

\beta_{\pi 1} \

\beta_{\pi, 2} \

\beta_{\pi, 3} \

\textcolor{green} {1} \

\textcolor{green} {\beta_{\pi}}\

\end{bmatrix},

(A', B', C') $$

计算得到压缩proof 生成的error term $e′$：

$$ \begin{aligned}

&(\mu{\text{acc}}' + r) C' (z{\text{acc}}' + r z{\pi}') - A' (z{\text{acc}}' + r z{\pi}') \circ B' (z{\text{acc}}' + r z_{\pi}') \

&= e{\text{acc}}' + r \boxed{(\mu{\text{acc}}' z{\pi}' + z{\text{acc}}' - A' z{\pi}' B' z{\text{acc}}' - A' z{\text{acc}}' B' z{\pi}')} \

e' &= (\mu{\text{acc}}' z{\pi}' + z{\text{acc}}' - A' z{\pi}' B' z{\text{acc}}' - A' z{\text{acc}}' B' z_{\pi}')

\end{aligned} $$

因为本身就是degree 为2的check，所以error term就是一个长度为$2\sqrt{l} - 2$ 的向量。

step 3: 生成error term 相应的commitment

对compressed verification error term vector $e′$ 进行commit:

$$ \widetilde{e'} =\text{commit}(e') $$

对power of beta vector $\beta_{\pi}$ 本身进行commit：

$$ \widetilde{\boldsymbol{\beta}{\pi}} = \text{commit}(\boldsymbol{\beta}{\pi}) $$

step 4: 计算Accumulation error term

基于：

$$ \mu{\text{acc}}、z{\text{acc}}、z_{\pi}、{A, B, C} $$

计算Accumulation error term：

$$ \begin{aligned}

&\sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (\beta{\text{acc}, a} + r \beta{\pi, a}) (\beta{\text{acc}, b}' + r \beta{\pi, b}') [(\mu{\text{acc}} + r) C{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi}) - A{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi}) \circ B{a + b\sqrt{l}} (z{\text{acc}} + r z{\pi})] \

&= \sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (\beta{\text{acc}, a} + r \beta{\pi, a}) * (\beta{\text{acc}, b}' + r \beta{\pi, b}') \

&= \sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (e{\text{acc}, a + b\sqrt{l}} +\boxed{ (\beta{\pi, a} \beta{\pi, b}' T) } r^3 + \boxed{ (\beta{\pi, a} \beta{\pi, b}' K + \beta{\pi, a} \beta{\text{acc}, b}' T + \beta{\text{acc}, a} \beta{\pi, b}' T) } r^2 + \boxed{ (\beta{\pi, a} \beta{\text{acc, b}}' K + \beta{\text{acc}, a} \beta{\pi, b}' K + \beta{\text{acc}, a} \beta_{\text{acc, b}}' T) } r^1) \

e1 &= \sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (\beta{\pi, a} \beta{\text{acc, b}}' K + \beta{\text{acc}, a} \beta{\pi, b}' K + \beta{\text{acc}, a} \beta_{\text{acc, b}}' T) \

e2 &= \sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (\beta{\pi, a} \beta{\pi, b}' K + \beta{\pi, a} \beta{\text{acc}, b}' T + \beta{\text{acc}, a} \beta_{\pi, b}' T) \

e3 &= \sum{a = 0}^{\sqrt{l} -1} \sum{b = 0}^{\sqrt{l} -1} (\beta{\pi, a} \beta_{\pi, b}' T) \

\end{aligned} $$

其中：

$$ \begin{aligned}

&K = \mu{\text{acc}} C{a + b\sqrt{l}} z{\text{acc}} - A{a + b\sqrt{l}} z{\text{acc}} \circ B{a + b\sqrt{l}} z_{\text{acc}} \

\end{aligned} $$

经过了压缩处理，已经变成了3个scalar 值。

step 5: fold R1CS witness

$$ \begin{aligned}

& \boldsymbol{\beta}{\text{acc}}^{*} \leftarrow \boldsymbol{\beta}{\text{acc}} \oplus r \boldsymbol{\beta}_{\pi} \

& e{\text{acc}}'^{*} \leftarrow e{\text{acc}}' \oplus r e' \

&w{\text{acc}}^{*} \leftarrow w{\text{acc}} \oplus r w_{\pi} \

\end{aligned} $$

step 6: fold R1CS intance

$$ \begin{aligned}

& \textcolor{red} {\widetilde{\boldsymbol{\beta}{\text{acc}}^{*}}} \leftarrow \widetilde{\boldsymbol{\beta}{\text{acc}}} \oplus r \widetilde{\boldsymbol{\beta}_{\pi}} \

& \textcolor{red} {\widetilde{e{\text{acc}}'^{*}}} \leftarrow \widetilde{e{\text{acc}}'} \oplus r \widetilde{e'} \

& \textcolor{red} {\widetilde{w{\text{acc}}^{*}}} \leftarrow \widetilde{w{\text{acc}}} \oplus r \widetilde{w_{\pi}} \

& \textcolor{red} {e} \leftarrow e_{\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \

\end{aligned} $$

Accumulation Verifier

step 1: fold R1CS instance

基于Accumulation Prover提供的四个accumuation error term scalar 值$e_{\text{acc}}、e_1 、e_2、e3$，accumulation witness 对应的commitment $\widetilde{w{\text{acc}}}、\widetilde{w{\pi}}$，compress verification error term 对应的commitment $\widetilde{e{\text{acc}}'} 、\widetilde{e'} $，以及power of beta vector $\widetilde{\beta{\text{acc}}}、\widetilde{\beta{\pi}}$，进行instance的fold任务：

$$ \begin{aligned}

& \textcolor{green} {\widetilde{\boldsymbol{\beta}{\text{acc}}^{*}}} \leftarrow \widetilde{\boldsymbol{\beta}{\text{acc}}} \oplus r \widetilde{\boldsymbol{\beta}_{\pi}} \

& \textcolor{green} {\widetilde{e{\text{acc}}'^{*}}} \leftarrow \widetilde{e{\text{acc}}'} \oplus r \widetilde{e'} \

& \textcolor{green} {\widetilde{w{\text{acc}}^{*}}} \leftarrow \widetilde{w{\text{acc}}} \oplus r \widetilde{w_{\pi}} \

& \textcolor{green} {e} \leftarrow e_{\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \

\end{aligned} $$

step 2: consistancy check

在基于cycle curves 的实现方案中，这部分校验工作是在IVC的下一个step 完成的。关于cycle curves 更多的细节，感兴趣的可以参考Nova from scratch 和 CycleFold based Nova。

参考资料

【1】ProtoStar 论文：https\://eprint.iacr.org/2023/620.pdf

Cycle curves 实现相关资料：

【1】Revisiting Nova论文: https\://eprint.iacr.org/2023/969.pd

【2】CycleFold 论文：https\://eprint.iacr.org/2023/1192.pdf

【3】Nova from scratch ： https\://learnblockchain.cn/article/6429

【4】CycleFold base Nova: https\://learnblockchain.cn/article/6452

原创
学分: 6
分类: 零知识证明
标签: folding Nova protostar

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

【上篇】ProtoStar from scratch

Thanks

写在前面的

Compress Verification Degree

ROUND ONE

ROUND TWO

ROUND THREE

Deserve it or not

Compressed Verification in Accumulation

Overhead for Compressed Verification

Updated Protocol