Thanks十分感谢@AntalphaLabs上月底提供的线下hackerhouse,有机会亲历并学习SecbitLabs@郭宇老师、@even做zkresearch的思路和方法,并讨论了很多foldingscheme相关的问题非常感谢参加hackerhouse一起交流
<br />
<br />
ProtoStar 论文中非常经典的一张图:
<br />
<br />
<br />
<br />
<br />
在R1CS约束系统里面只有一种约束,就是GATE的约束,Witness 是z 向量。电路的描述,也就是A、B、C三个矩阵,在setup 阶段就已经完成,矩阵的每一行对应一个gate。SPS prover 要做的就是根据业务计算逻辑填充这个z 向量,SPS verifier 拿着这个z 向量验证是否满足所有GATE的约束:
$$ Cz - Az \circ Bz \overset{?}= \bold{0} $$
<br />
但是这里有个问题,这个等式的左右两边是一个长度为$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} $$
有没有可能把它压缩成一个等式?
<br />
引入一个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} $$
<br />
最后变成一个等式:
$$ \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 $$
<br />
所以放在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} $$
<br />
$$β$$ 向量的每个元素都要校验,这里要校验$$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 $$
<br />
由于增加了一个变量$\beta_i$,所以等式的degree变成了3。
为什么要校验$$\beta$$ 向量?
如果不校验$$β$$ 向量,prover 随便给定一个不满足R1CS约束的$$z$$ 向量,然后再给一组可以满足上面等式的$β$ 向量(比如$\bold{0}$ 向量),这样就很容易骗过verifier。
<br />
这里的问题是,prover 发送的message $β$ 向量长度$l$ 不可控,verifier 验证的复杂度$O(l)$ 也不可控,有可能很大。有没有可能再压缩一下?
<br />
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} $$
<br />
然后,原压缩后的等式变成了:
$$ \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。
<br />
同样,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的等式。
<br />
到这里,在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) $$
<br />
可能在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) $$
<br />
所以当gate 的个数$l$ ,gate的degree $d$,都变得很大时,这里压缩的优势就变得相当明显。它计算的复杂度由$O(ld)$ 变成了 $O((d+2)+4\sqrt{l} - 4)$ ,直接降了一个数量级,所以答案是Deserve it!
<br />
经过压缩后,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} $$
<br />
而是$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} $$
<br />
在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} $$
<br />
我们将这两个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} $$
<br />
我们对比一下压缩之前的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 $$
<br />
其中$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}} $$
<br />
更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} $$
<br />
如果觉得在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} $$
<br />
其中$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} $$
<br />
验证通过后才能对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 证明。
<br />
两个压缩过程的proof 实例在fold的过程中会产生的error term vector,为什么又出现了一个error term vector,error term vector 不是已经通过power of beta 压缩成一个scalar 了吗?这里可能有些绕,原始paper 在这里也是一句话带过,没关系,我们具象化一下看看:
<br />
假定$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 \
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 & 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。
<br />
同样的,我们也可以构造出一个incremental R1CS 实例出来:
$$ \begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 \
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 & 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}
$$
<br />
把两个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} $$
<br />
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′$。
<br />
如果觉得在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} $$
<br />
可以很明显地看到,椭圆曲线的运算量不是跟约束的数量$l$ 成线性关系,而是与 $2\sqrt{l} - 2$ 成正比;而且跟gate 的degree $d$ 无关。鉴于$d−1$ 个error term vector已经被压缩成了$d−1$个scalar 值,原本的$d$ 个commitment 加法变成了$d$ 个scalar 值的加法。scalar 的加法相比EC的加法不是要便宜太多?
<br />
最后,我们把压缩技术放在IVC 的SPS 协议里看看整个流程长什么样子。
我们仍然基于R1CS约束系统来detail 整个协议的过程:
一个是为Compress Verification用的$(A′,B′,C′)$,另外一个是Accumulation 用的$(A,B,C)$。
<br />
基于:
$$ \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') $$
<br />
计算得到压缩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}') \
&= (\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}')} \
\
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$ 的向量。
对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}) $$
基于:
$$ \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}') \
&*[(\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}})] \
\
&= \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} $$
<br />
其中:
$$ \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} $$
经过了压缩处理,已经变成了3个scalar 值。
<br />
$$ \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} $$
$$ \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 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} $$
验证accumulation prover fold的正确性,或者校验accumuation verifier 与 accumulation prover fold的一致性。也就是,比较上面红色标记的部分是否与绿色标记的部分相等。
<br />
在基于cycle curves 的实现方案中,这部分校验工作是在IVC的下一个step 完成的。关于cycle curves 更多的细节,感兴趣的可以参考Nova from scratch 和 CycleFold based Nova。
【1】ProtoStar 论文:https\://eprint.iacr.org/2023/620.pdf
【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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!