{"content":{"title":"【上篇】ProtoStar from scratch","body":"# Thanks\r\n\r\n\r\n- 十分感谢@AntalphaLabs 上月底提供的线下hackerhouse ，有机会亲历并学习SecbitLabs @郭宇 老师、@even 做zk research 的思路和方法，并讨论了很多folding scheme相关的问题\r\n\r\n
\r\n\r\n- 非常感谢参加hackerhouse 一起交流讨论过protostar的小伙伴们 @yingfei、 @Harry L 、@周洋、 @CJ 、@hhh，尽管当时对protostar的认识还比较肤浅，还没摸到它的门框儿，但至少有一个初步的overview 概念 -)\r\n\r\n
\r\n\r\n# 写在前面的\r\n\r\nProtoStar 论文中非常经典的一张图：\r\n\r\n\r\n- ProtoStar 论文中最核心、最具创新的应该就是3.5 章节，其它部分基本都是对整个folding scheme 的抽象，如果读完还是不知道3.5 章节的compress verification tech在整个协议中怎么用，建议反复研究上面这张图(论图的重要性)\r\n\r\n
\r\n\r\n- 为了方便描述，我们以最简单的R1CS约束系统为base来讨论，更容易感知到Protostar 的intuition，适当的时候会拓展到plonkish约束系统，以便有更全局的sense\r\n\r\n
\r\n\r\n- 本文旨在厘清3.5章节的compress verification tech 在整个folding scheme中应用，IVC部分基本可以参考 revisiting Nova 的cycle curves方案。本文的tag是\"上篇\"，“下篇”将会整合plonkish 的三大约束GATE 约束、Wiring 约束、Lookup约束系统地串一下ProtoStar 协议\r\n\r\n
\r\n\r\n# Compress Verification Degree\r\n\r\n
\r\n\r\n## ROUND ONE\r\n\r\n
\r\n\r\n在R1CS约束系统里面只有一种约束，就是GATE的约束，Witness 是z 向量。电路的描述，也就是A、B、C三个矩阵，在setup 阶段就已经完成，矩阵的每一行对应一个gate。SPS prover 要做的就是根据业务计算逻辑填充这个z 向量，SPS verifier 拿着这个z 向量验证是否满足所有GATE的约束：\r\n\r\n$$\r\nCz - Az \\circ Bz \\overset{?}= \\bold{0}\r\n$$\r\n\r\n
\r\n\r\n但是这里有个问题，这个等式的左右两边是一个长度为$l$ 的向量，$l$ 代表的是GATE的个数。也就是说，在R1CS约束系统中，SPS verifier 需要校验$l$ 个degree 为2的等式：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&C_0 z - A_0 z \\circ B_0 z \\overset{?} = 0 \\\\\r\n\r\n&C_1 z - A_1 z \\circ B_1 z \\overset{?} = 0 \\\\\r\n\r\n&... \\\\\r\n\r\n&C_{l - 1} z - A_{l - 1} z \\circ B_{l - 1} z \\overset{?} = 0 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n有没有可能把它压缩成一个等式？\r\n\r\n
\r\n\r\n## ROUND TWO\r\n引入一个public 的变量，fold factor $$\\beta$$：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&C_0 z - A_0 z \\circ B_0 z \\overset{?} = 0 \\\\\r\n\r\n&\\beta^1* (C_1 z - A_1 z \\circ B_1 z) \\overset{?} = 0 \\\\\r\n\r\n&... \\\\\r\n\r\n&\\beta^{l - 1} * (C_{l - 1} z - A_{l - 1} z \\circ B_{l - 1} z) \\overset{?} = 0 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n最后变成一个等式：\r\n\r\n\r\n$$\r\n\\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\r\n$$\r\n\r\n
\r\n\r\n所以放在SPS 协议里，prover 除了向verifier 发送message $$z$$ 向量，还需要发送另外一个message $$β$$ 向量 $\\begin{bmatrix}\\beta^0 \\\\\\beta^1 \\\\... \\\\\\beta^{l - 1} \\\\\\end{bmatrix}$ ，verifier 拿着这两个向量验证上面的等式是否成立就行了，对吗？还漏掉了一件事儿，需要验证message $$β$$ 向量的合法性(正确性)，需要满足：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\beta_0 \\overset{?} = 1 \\\\\r\n\r\n&\\beta_{i + 1} \\overset{?} = \\beta_{i} * \\beta, \\forall i \\in [0, l - 2] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n$$β$$ 向量的每个元素都要校验，这里要校验$$l$$ 个degree 为2的等式。另外还要校验压缩后的等式：\r\n\r\n\r\n$$\r\n\\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\r\n$$\r\n\r\n
\r\n\r\n由于增加了一个变量$\\beta_i$，所以等式的degree变成了3。\r\n\r\n> 为什么要校验$$\\beta$$ 向量？\r\n> \r\n> \r\n> 如果不校验$$β$$ 向量，prover 随便给定一个不满足R1CS约束的$$z$$ 向量，然后再给一组可以满足上面等式的$β$ 向量(比如$\\bold{0}$ 向量)，这样就很容易骗过verifier。\r\n\r\n
\r\n\r\n这里的问题是，prover 发送的message $β$ 向量长度$l$ 不可控，verifier 验证的复杂度$O(l)$ 也不可控，有可能很大。有没有可能再压缩一下？\r\n\r\n
\r\n\r\n## ROUND THREE\r\nprover 发送这么一个message，由两个向量组成：\r\n\r\n\r\n$$\r\n\\beta = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta^0 \\\\\r\n\r\n\\beta^1 \\\\\r\n\r\n\\beta^2 \\\\\r\n\r\n... \\\\\r\n\r\n\\beta^{\\sqrt{l} - 1}\r\n\r\n\\end{bmatrix}\r\n\r\n, \r\n\r\n\\beta' = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta^{0 * \\sqrt{l}} \\\\\r\n\r\n\\beta^{1 * \\sqrt{l}} \\\\\r\n\r\n\\beta^{2 * \\sqrt{l}} \\\\\r\n\r\n... \\\\\r\n\r\n\\beta^{(\\sqrt{l} - 1)\\sqrt{l}}\r\n\r\n\\end{bmatrix}\r\n$$\r\n\r\n
\r\n\r\n然后，原压缩后的等式变成了：\r\n\r\n\r\n$$\r\n\\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\r\n$$\r\n\r\n等式的degree 增加了2，变成了4。\r\n\r\n
\r\n\r\n同样，verifier 需要验证这个新增加的message 的合法性：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\textcircled {1} \\beta_1 \\overset{?} = \\beta \\\\\r\n\r\n&\\textcircled {2} \\beta_{i + 1} \\overset{?} = \\beta_{i} * \\beta, \\forall i \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n&\\textcircled {3} \\beta_1' \\overset{?} = \\beta_{\\sqrt{l} - 1} * \\beta \\\\\r\n\r\n&\\textcircled {4} \\beta_{i + 1}' \\overset{?} = \\beta_{i}' * \\beta_1', \\forall i \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n这里需要验证$2\\sqrt{l} - 2$ 个degree 为2的等式。\r\n\r\n
\r\n\r\n## Deserve it or not\r\n\r\n到这里，在R1CS约束系统中，verifier 从原本要验证$l$ 个degree为2的等式，变成了验证1个degree为4的等式加上$2\\sqrt{l} - 2$ 个degree 为2的等式，那么这么做是否值得：\r\n\r\n\r\n$$\r\nl * \\text{deg}(2) \\textcolor{red} {\\overset{?} >} 1 * \\text{deg}(2 + 2) + (2\\sqrt{l} - 2) * \\text{deg}(2)\r\n$$\r\n\r\n
\r\n\r\n可能在R1CS约束系统中优势还不够明显，没关系，在支持customer gate的plonkish 约束系统中，gate的degree就不再是2了，而是自定义的degree-$d$：\r\n\r\n\r\n$$\r\nl * \\text{deg}(d) \\textcolor{red} {\\overset{?} >} 1 * \\text{deg}(d + 2) + (2\\sqrt{l} - 2) * \\text{deg}(2)\r\n$$\r\n\r\n
\r\n\r\n所以当gate 的个数$l$ ，gate的degree $d$，都变得很大时，这里压缩的优势就变得相当明显。它计算的复杂度由$O(ld)$ 变成了 $O((d+2)+4\\sqrt{l} - 4)$ ，直接降了一个数量级，所以答案是Deserve it!\r\n\r\n
\r\n\r\n# Compressed Verification in Accumulation\r\n\r\n经过压缩后，SPS verifier 不再是验证$l$ 个等式：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&C_0 z - A_0 z \\circ B_0 z \\overset{?} = 0 \\\\\r\n\r\n&C_1 z - A_1 z \\circ B_1 z \\overset{?} = 0 \\\\\r\n\r\n&... \\\\\r\n\r\n&C_{l - 1} z - A_{l - 1} z \\circ B_{l - 1} z \\overset{?} = 0 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n而是$1+ (2\\sqrt{l} - 2)$ 个等式：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\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 \\\\\r\n\r\n&\\textcircled {2} \\beta_1 \\overset{?} = \\beta \\\\\r\n\r\n&\\textcircled {3} \\beta_{i + 1} \\overset{?} = \\beta_{i} * \\beta, \\forall i \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n&\\textcircled {4} \\beta_1' \\overset{?} = \\beta_{\\sqrt{l} - 1} * \\beta \\\\\r\n\r\n&\\textcircled {5} \\beta_{i + 1}' \\overset{?} = \\beta_{i}' * \\beta_1', \\forall i \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n在R1CS约束系统中，假设有两个组instance$\\text{acc} = \\{\\beta_\\text{acc}, \\beta_\\text{acc}', z_\\text{acc}\\}$ 和$\\pi = \\{\\beta_\\pi, \\beta_\\pi', z_{\\pi}\\}$，前者为**relaxed instance**，后者为 **incremental instance**：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\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}} \\\\\r\n\r\n&\\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 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n我们将这两个instance 进行fold：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&(\\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})] \\\\\r\n\r\n\\\\\r\n\r\n&= (\\beta_{\\text{acc}, a} + r \\beta_{\\pi, a}) * (\\beta_{\\text{acc}, b}' + r \\beta_{\\pi, b}') \\\\\r\n\r\n&*[(\\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}})] \\\\\r\n\r\n\\\\\r\n\r\n&= 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 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n> 方框内的就是我们最终要计算得到的三个error term，注意这是三个scalar \r\n\r\n其中$T$ 和$K$ 代表的两个多项式：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&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}} \\\\\r\n\r\n&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}} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n# Overhead for Compressed Verification\r\n\r\n我们对比一下压缩之前的R1CS 约束系统：\r\n\r\n\r\n$$\r\n\\begin{rcases}\r\n\r\n\\mu_{\\text{acc}} C z_{\\text{acc}} - A z_{\\text{acc}} \\circ B z_{\\text{acc}} = \\bold{e} \\\\\r\n\r\n C z_{\\pi} - A z_{\\pi} \\circ B z_{\\pi} = \\bold{0} \\\\\r\n\r\n\\end{rcases} \r\n\r\n\\overset{\\text{fold}} \\Longrightarrow\r\n\r\n(\\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\r\n$$\r\n\r\n
\r\n\r\n其中$T$ 代表多项式：\r\n\r\n$$\r\nT = \\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}}\r\n$$\r\n\r\n
\r\n\r\n更intuitive 的数据对比：\r\n\r\n$$\r\n\\def\\arraystretch{1.5}\r\n\\begin{array}{c:c:c}\r\n\r\n& \\text{before compressed} & \\text{after compressed} \\\\ \\hline\r\n\r\n\\#\\text{error term} & 1 & 3 \\\\ \\hdashline\r\n\r\n\\text{Is error vector} & \\text{true} & \\text{false} \\\\ \\hdashline\r\n\r\n\\text{Commit or not} & \\text{true} & \\text{false} \\\\ \\hdashline\r\n\r\n\\text{EC-op} & l & 0 \\\\ \\hdashline\r\n\r\n\\end{array}\r\n$$\r\n\r\n
\r\n\r\n如果觉得在R1CS约束系统中优势不够明显，没关系，我们把它放在支持customer gate的Plonk约束系统中优势就会变得相当明显了：\r\n\r\n\r\n$$\r\n\\def\\arraystretch{1.5}\r\n\\begin{array}{c:c:c}\r\n\r\n& \\text{before compressed} & \\text{after compressed} \\\\ \\hline\r\n\r\n\\#\\text{error term} & d - 1 & d + 1 \\\\ \\hdashline\r\n\r\n\\text{Is error vector} & \\text{true} & \\text{false} \\\\ \\hdashline\r\n\r\n\\text{Commit or not} & \\text{true} & \\text{false} \\\\ \\hdashline\r\n\r\n\\text{EC-op} & (d - 1)l & 0 \\\\ \\hdashline\r\n\r\n\\end{array}\r\n$$\r\n\r\n
\r\n\r\n其中$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 运算。\r\n\r\n-----\r\n\r\n天下没有免费的午餐，那么压缩的成本在哪里呢？需要验证这$2\\sqrt{l} - 2$ 个power of beta值$\\beta_a, \\beta_b' \\text{ } \\forall a,b \\in [1, \\sqrt{l} - 1]$ 满足下面的等式约束，这个校验也叫压缩过程的验证：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\beta_1 \\overset{?} = \\beta \\\\\r\n\r\n& \\beta_{a + 1} \\overset{?} = \\beta_{a} * \\beta, \\forall a \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n& \\beta_1' \\overset{?} = \\beta_{\\sqrt{l} - 1} * \\beta \\\\\r\n\r\n& \\beta_{b + 1}' \\overset{?} = \\beta_{b}' * \\beta_1', \\forall b \\in [1, \\sqrt{l} - 2] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n验证通过后才能对GATE 约束进行验证：\r\n\r\n$$\r\n\\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} \\\\\r\n$$\r\n\r\n> 用绿色标出来的是scalar 不需要commit，用红色标出来的是vector 需要commit。\r\n> \r\n\r\n----\r\n\r\n在IVC电路中，**压缩过程的验证同GATE约束的验证一样，也需要delay 到最后，中间过程只需要把这两个验证过程的proof进行fold**，这也是自20年开始folding scheme的标准做法，具体细节可以参考这篇文章，其中有详尽的security 证明。\r\n\r\n
\r\n\r\n两个压缩过程的proof 实例在fold的过程中会产生的**error term vector**，为什么又出现了一个**error term vector**，error term vector 不是已经通过power of beta 压缩成一个scalar 了吗？这里可能有些绕，原始paper 在这里也是一句话带过，没关系，我们具象化一下看看：\r\n\r\n
\r\n\r\n假定$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 实例出来：\r\n\r\n\r\n$$\r\n\\begin{bmatrix}\r\n\r\n1 & 0 & 0 & 0 & 0 & 0 \\\\\r\n\r\n1 & 0 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 1 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\text{acc}, 0} \\\\\r\n\r\n\\beta_{\\text{acc}, 1} \\\\\r\n\r\n\\beta_{\\text{acc}, 2} \\\\\r\n\r\n\\beta_{\\text{acc}, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\text{acc}}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\circ \r\n\r\n\\begin{bmatrix}\r\n\r\n0 & 0 & 0 & 0 & 1 & 0 \\\\\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\text{acc}, 0} \\\\\r\n\r\n\\beta_{\\text{acc}, 1} \\\\\r\n\r\n\\beta_{\\text{acc}, 2} \\\\\r\n\r\n\\beta_{\\text{acc}, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\text{acc}}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n=\r\n\r\n\\mu_{\\text{acc}}'\r\n\r\n\\begin{bmatrix}\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 1 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 0 & 1 & 0 & 0 \\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\text{acc}, 0} \\\\\r\n\r\n\\beta_{\\text{acc}, 1} \\\\\r\n\r\n\\beta_{\\text{acc}, 2} \\\\\r\n\r\n\\beta_{\\text{acc}, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\text{acc}}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\r\n\r\n+ \r\n\r\n\\begin{bmatrix}\r\n\r\ne_{\\text{acc}, 0}' \\\\\r\n\r\ne_{\\text{acc}, 1}' \\\\\r\n\r\ne_{\\text{acc}, 2}' \\\\\r\n\r\ne_{\\text{acc}, 3}' \\\\\r\n\r\ne_{\\text{acc}, 4}' \\\\\r\n\r\ne_{\\text{acc}, 5}' \\\\\r\n\r\n\\end{bmatrix}\r\n$$\r\n\r\n其中绿色标记的是public variable。\r\n\r\n
\r\n\r\n\r\n同样的，我们也可以构造出一个incremental R1CS 实例出来：\r\n\r\n\r\n$$\r\n\\begin{bmatrix}\r\n\r\n1 & 0 & 0 & 0 & 0 & 0 \\\\\r\n\r\n1 & 0 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 1 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\pi, 0} \\\\\r\n\r\n\\beta_{\\pi, 1} \\\\\r\n\r\n\\beta_{\\pi, 2} \\\\\r\n\r\n\\beta_{\\pi, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\pi}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\circ \r\n\r\n\\begin{bmatrix}\r\n\r\n0 & 0 & 0 & 0 & 1 & 0 \\\\\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\pi, 0} \\\\\r\n\r\n\\beta_{\\pi, 1} \\\\\r\n\r\n\\beta_{\\pi, 2} \\\\\r\n\r\n\\beta_{\\pi, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\pi}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n=\r\n\r\n\\begin{bmatrix}\r\n\r\n0 & 0 & 0 & 0 & 0 & 1 \\\\\r\n\r\n0 & 1 & 0 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 1 & 0 & 0 & 0 \\\\\r\n\r\n0 & 0 & 0 & 1 & 0 & 0 \\\r\n\r\n\\end{bmatrix}\r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\pi, 0} \\\\\r\n\r\n\\beta_{\\pi, 1} \\\\\r\n\r\n\\beta_{\\pi, 2} \\\\\r\n\r\n\\beta_{\\pi, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\pi}}\\\\\r\n\r\n\\end{bmatrix}\r\n\r\n$$\r\n\r\n
\r\n\r\n把两个proof 进行fold，令：\r\n\r\n$$\r\nz_{\\text{acc}}' = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\text{acc}, 0} \\\\\r\n\r\n\\beta_{\\text{acc}, 1} \\\\\r\n\r\n\\beta_{\\text{acc}, 2} \\\\\r\n\r\n\\beta_{\\text{acc}, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\text{acc}}}\\\\\r\n\r\n\\end{bmatrix},\r\n\r\nz_{\\pi}' = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\pi, 0} \\\\\r\n\r\n\\beta_{\\pi 1} \\\\\r\n\r\n\\beta_{\\pi, 2} \\\\\r\n\r\n\\beta_{\\pi, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\pi}}\\\\\r\n\r\n\\end{bmatrix}\r\n$$\r\n\r\n则：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\mu_{\\text{acc}}' C' z_{\\text{acc}}' - A' z_{\\text{acc}}' \\circ B' z_{\\text{acc}}' = \\bold{e_{\\text{acc}}'} \\\\\r\n\r\n&C' z_{\\pi}' - A' z_{\\pi}' \\circ B' z_{\\pi}' = 0 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\nfold的过程当然会产生cross/error term vector了，我们会很自然地计算得到相应的error term vector：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&(\\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}') \\\\\r\n\r\n\r\n&= (\\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}')} \\\\\r\n\r\n&= 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}')} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n只是这个长度不再是$l$ 而是$2\\sqrt{l} - 2$，已经不在一个量级上了！**因为是另外一套R1CS实例了，所以需要额外的一个电路来验证压缩过程**。\r\n\r\n----\r\n\r\n加上压缩verification 带来的成本，我们先看一下R1CS约束系统的对比数据：\r\n\r\n\r\n$$\r\n\\def\\arraystretch{1.5}\r\n\\begin{array}{c:c:c}\r\n\r\n& \\text{before compressed} & \\text{after compressed} \\\\ \\hline\r\n\r\n\\#\\text{commitment} & 2 & 3 \\\\ \\hdashline\r\n\r\n\\#\\text{EC-op for commitment} & m+ l & m + (2\\sqrt{l} - 2) * 2 \\\\ \\hdashline\r\n\r\n\\#\\text{F-op for error term} & 0 & 2 \\\\\r\n\r\n\\end{array}\r\n$$\r\n\r\n压缩前有两个commitment，一个是$z$ 向量中的witness 部分，一个是error term vector $e$，长度分别为$m$ 和$l$；压缩后，除了$z$ 向量中的witness 部分需要commitment，还有两个长度均为$2\\sqrt{l} - 2$ 的power of beta 和 其相应的error term vector $e′$。\r\n\r\n
\r\n\r\n如果觉得在R1CS约束系统中优势不够明显，没关系，我们再看看支持customer gate的Plonk约束系统的对比数据：\r\n\r\n\r\n$$\r\n\\def\\arraystretch{1.5}\r\n\\begin{array}{c:c:c}\r\n\r\n& \\text{before compressed} & \\text{after compressed} \\\\ \\hline\r\n\r\n\\#\\text{commitment} & d & (d -1) + 2 \\\\ \\hdashline\r\n\r\n\\#\\text{EC-op for commitment} & m + \\textcolor{red} {(d - 1)l} & m + \\textcolor{green} {2 * (2\\sqrt{l} - 2)} \\\\ \\hdashline\r\n\r\n\\#\\text{F-op for error term} & 0 & d \\\\\r\n\r\n\\end{array}\r\n$$\r\n\r\n
\r\n\r\n可以很明显地看到，椭圆曲线的运算量不是跟约束的数量$l$ 成线性关系，而是与 $2\\sqrt{l} - 2$ 成正比；而且跟gate 的degree $d$ 无关。鉴于$d−1$ 个error \bterm vector已经被压缩成了$d−1$个scalar 值，原本的$d$ 个commitment 加法变成了$d$ 个scalar 值的加法。scalar 的加法相比EC的加法不是要便宜太多？\r\n\r\n
\r\n\r\n最后，我们把压缩技术放在IVC 的SPS 协议里看看整个流程长什么样子。\r\n\r\n# Updated Protocol\r\n\r\n我们仍然基于R1CS约束系统来detail 整个协议的过程：\r\n\r\n## Accumulation Prover\r\n\r\n\r\n\r\n### step 1: 初始化两个R1CS实例\r\n\r\n\r\n一个是为Compress Verification用的$(A′,B′,C′)$，另外一个是Accumulation 用的$(A,B,C)$。\r\n\r\n
\r\n\r\n### step 2: 计算Compress Verification error term\r\n\r\n\r\n\r\n基于：\r\n\r\n\r\n$$\r\n\\mu_{\\text{acc}}', z_{\\text{acc}}' = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\text{acc}, 0} \\\\\r\n\r\n\\beta_{\\text{acc}, 1} \\\\\r\n\r\n\\beta_{\\text{acc}, 2} \\\\\r\n\r\n\\beta_{\\text{acc}, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\text{acc}}}\\\\\r\n\r\n\\end{bmatrix},\r\n\r\nz_{\\pi}' = \r\n\r\n\\begin{bmatrix}\r\n\r\n\\beta_{\\pi, 0} \\\\\r\n\r\n\\beta_{\\pi 1} \\\\\r\n\r\n\\beta_{\\pi, 2} \\\\\r\n\r\n\\beta_{\\pi, 3} \\\\\r\n\r\n\\textcolor{green} {1} \\\\\r\n\r\n\\textcolor{green} {\\beta_{\\pi}}\\\\\r\n\r\n\\end{bmatrix},\r\n\r\n(A', B', C')\r\n$$\r\n\r\n
\r\n\r\n计算得到压缩proof 生成的error term $e′$：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&(\\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}') \\\\\r\n\r\n\r\n&= (\\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}')} \\\\\r\n\r\n&= 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}')} \\\\\r\n\r\n\\\\\r\n\r\ne' &= (\\mu_{\\text{acc}}' z_{\\pi}' + z_{\\text{acc}}' - A' z_{\\pi}' B' z_{\\text{acc}}' - A' z_{\\text{acc}}' B' z_{\\pi}')\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n因为本身就是degree 为2的check，所以error term就是一个长度为$2\\sqrt{l} - 2$ 的向量。\r\n\r\n### step 3: 生成error term 相应的commitment\r\n对compressed verification error term vector $e′$ 进行commit:\r\n\r\n\r\n$$\r\n\\widetilde{e'} =\\text{commit}(e')\r\n$$\r\n\r\n对power of beta vector $\\beta_{\\pi}$ 本身进行commit：\r\n\r\n\r\n$$\r\n\\widetilde{\\boldsymbol{\\beta}_{\\pi}} = \\text{commit}(\\boldsymbol{\\beta}_{\\pi})\r\n$$\r\n\r\n### step 4: 计算Accumulation error term\r\n基于：\r\n\r\n$$\r\n\\mu_{\\text{acc}}、z_{\\text{acc}}、z_{\\pi}、\\{A, B, C\\}\r\n$$\r\n\r\n计算Accumulation error term：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&\\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})] \\\\\r\n\r\n\\\\\r\n\r\n&= \\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}') \\\\\r\n\r\n&*[(\\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}})] \\\\\r\n\r\n\\\\\r\n\r\n&= \\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) \\\\\r\n\r\n\\\\\r\n\r\ne_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) \\\\\r\n\r\ne_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) \\\\\r\n\r\ne_3 &= \\sum_{a = 0}^{\\sqrt{l} -1} \\sum_{b = 0}^{\\sqrt{l} -1} (\\beta_{\\pi, a} \\beta_{\\pi, b}' T) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n其中：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n&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}} \\\\\r\n\r\n&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}} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n经过了压缩处理，已经变成了3个scalar 值。\r\n\r\n
\r\n\r\n### step 5: fold R1CS witness\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\boldsymbol{\\beta}_{\\text{acc}}^{*} \\leftarrow \\boldsymbol{\\beta}_{\\text{acc}} \\oplus r \\boldsymbol{\\beta}_{\\pi} \\\\\r\n\r\n& e_{\\text{acc}}'^{*} \\leftarrow e_{\\text{acc}}' \\oplus r e' \\\\\r\n\r\n&w_{\\text{acc}}^{*} \\leftarrow w_{\\text{acc}} \\oplus r w_{\\pi} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n### step 6: fold R1CS intance\r\n \r\n \r\n$$\r\n\\begin{aligned}\r\n\r\n& \\textcolor{red} {\\widetilde{\\boldsymbol{\\beta}_{\\text{acc}}^{*}}} \\leftarrow \\widetilde{\\boldsymbol{\\beta}_{\\text{acc}}} \\oplus r \\widetilde{\\boldsymbol{\\beta}_{\\pi}} \\\\\r\n\r\n& \\textcolor{red} {\\widetilde{e_{\\text{acc}}'^{*}}} \\leftarrow \\widetilde{e_{\\text{acc}}'} \\oplus r \\widetilde{e'} \\\\\r\n\r\n& \\textcolor{red} {\\widetilde{w_{\\text{acc}}^{*}}} \\leftarrow \\widetilde{w_{\\text{acc}}} \\oplus r \\widetilde{w_{\\pi}} \\\\\r\n\r\n& \\textcolor{red} {e} \\leftarrow e_{\\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n## Accumulation Verifier\r\n\r\n### step 1: fold R1CS instance\r\n\r\n\r\n\r\n基于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任务：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\textcolor{green} {\\widetilde{\\boldsymbol{\\beta}_{\\text{acc}}^{*}}} \\leftarrow \\widetilde{\\boldsymbol{\\beta}_{\\text{acc}}} \\oplus r \\widetilde{\\boldsymbol{\\beta}_{\\pi}} \\\\\r\n\r\n& \\textcolor{green} {\\widetilde{e_{\\text{acc}}'^{*}}} \\leftarrow \\widetilde{e_{\\text{acc}}'} \\oplus r \\widetilde{e'} \\\\\r\n\r\n& \\textcolor{green} {\\widetilde{w_{\\text{acc}}^{*}}} \\leftarrow \\widetilde{w_{\\text{acc}}} \\oplus r \\widetilde{w_{\\pi}} \\\\\r\n\r\n& \\textcolor{green} {e} \\leftarrow e_{\\text{acc}} + r e_1 + r^2 e_2 +r^3 + e_3 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n### step 2: consistancy check\r\n\r\n\r\n\r\n验证accumulation prover fold的正确性，或者校验accumuation verifier 与 accumulation prover fold的一致性。也就是，比较上面红色标记的部分是否与绿色标记的部分相等。\r\n\r\n
\r\n\r\n在基于cycle curves 的实现方案中，这部分校验工作是在IVC的下一个step 完成的。关于cycle curves 更多的细节，感兴趣的可以参考[Nova from scratch](https://learnblockchain.cn/article/6429) 和 [CycleFold based Nova](https://learnblockchain.cn/article/6452)。\r\n\r\n# 参考资料\r\n\r\n【1】ProtoStar 论文：https\\://eprint.iacr.org/2023/620.pdf\r\n\r\n\r\n# Cycle curves 实现相关资料：\r\n\r\n【1】Revisiting Nova论文: https\\://eprint.iacr.org/2023/969.pd\r\n\r\n【2】CycleFold 论文：https\\://eprint.iacr.org/2023/1192.pdf\r\n\r\n【3】Nova from scratch ： https\\://learnblockchain.cn/article/6429\r\n\r\n【4】CycleFold base Nova: https\\://learnblockchain.cn/article/6452"},"author":{"user":"https://learnblockchain.cn/people/15677","address":null},"history":"QmNWJA6FKR9d9GbfxGHRcEmBZcgxXWbcd3XXFED1QPpE53","timestamp":1694098130,"version":1}