Plonky3 “竖着卷” 的好处和适用场景是什么？

[keroro520]

例子： 如何使用 FRI 批量证明三个多项式 $M_0$ , $M_1$ , $M_2$ ，其中 $deg(M_0) = 8, deg(M_1) = 4, deg(M_2) = 2$ ?

方法一：将三个多项式线性组合成一个多项式，然后进入 FRI 折叠证明过程：

$$ \begin{aligned} \text{compress multi poly into one poly: } \quad & p_0(x) = M_0(x) + \beta \cdot M_1(x) + \beta^2 \cdot M_2(x) \ \\ \text{divide poly into two parts: } \quad & p_i(x) = p_{i_{even}}(x^2) + x \cdot p_{i_{odd}}(x^2) \ \\ \text{compress two parts into one: } \quad & p_{i+1}(x) = p_{i_{even}}(x) + \gamma \cdot p_{i_{odd}}(x) \ \\ \end{aligned} $$

方法二：Plonky 设计出 FRI “竖着卷” 的方式，在 FRI 开始时，设 $p_0$ 为最高阶的 trace polynomial，然后在 FRI 折叠的过程中，不断地将小阶 trace polynomial 加入到折叠过程：

$$ \begin{aligned} \text{Set } p_0 \text{as the poly with largest degree, } M_1 \text{ : } \quad & p_0 = M_0(x) \ \\ \text{divide poly into two parts: } \quad & p_0(x) = p_{0_{even}}(x^2) + x \cdot p_{0_{odd}}(x^2) \ \\ \text{compress two parts into one and mix with M1: }\quad & p_1(x) = M_1(x) + p_{0_{even}}(x^2) + \gamma \cdot p_{0_{odd}}(x^2) \ \\ \text{divide poly into two parts: } \quad & p_1(x) = p_{1_{even}}(x^2) + x \cdot p_{1_{odd}}(x^2) \ \\ \text{compress two parts into one and mix with M2: } \quad & p_2(x) = M_2(x) + p_{1_{even}}(x^2) + \gamma \cdot p_{1_{odd}}(x^2) \ \\ \end{aligned} $$

我的问题是，我们可以通过 random linear combination 的技术可以将多个多项式压缩成一个 CP 后，为什么 Plonky3 还要设计出 “竖着卷” 的机制呢？ Plonky3 的 “竖着卷” 的好处和适用场景是什么呢？

[keroro520]

"竖着卷“ 在 Fast RS-IOP Multivariate Polynomial Commitments and Verifiable Secret Sharing | USENIX 里称为 Rolling Batch。

在这里例子中，方法一要执行 8 * 3 次 evaluation，而方法二 Rolling Batch 只需要 8 + 4 + 2 次 evaluations，能节省 evaluation 的次数，从而加快生成证明的速度。