【上篇】ProtoStar from scratch

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

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

Thanks

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

<br />

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

<br />

写在前面的

ProtoStar 论文中非常经典的一张图: image.png

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

<br />

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

<br />

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

<br />

Compress Verification Degree

<br />

ROUND ONE

<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 />

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} $$

<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 />

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} $$

<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 />

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) $$

<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 />

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} $$

<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 />

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 $$

<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 协议里看看整个流程长什么样子。

Updated Protocol

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

Accumulation Prover

step 1: 初始化两个R1CS实例

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

<br />

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') $$

<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$​ 的向量。​

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}') \

&*[(\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 />

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

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

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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
白菜
白菜
0x6b50...a615
crypto