「理解 PLONK（三）：置换证明」引入随机数的目的

[keroro520]

「理解 PLONK（三）：置换证明」中，完整的置换协议引入了三个新的随机数 $\alpha$ 、 $\gamma$ 、 $\beta$ ：

• 连乘证明引入随机数 $\alpha$：

  其中 $\alpha$ 是用来聚合多个多项式约束的随机挑战数。 $L_0(X)\cdot(r(X)-1)+\alpha\cdot(q(X)\cdot r(X)-r(\omega\cdot X))=h(X)\cdot z_H(X)$

• Multiset 等价证明引入随机数 $\gamma$

  我们可以利用 Schwartz-Zippel 定理来进一步地检验：向 Verifier 索要一个随机数 $\gamma$，那么 Prover 就可以通过下面的等式证明两个向量 $\{p_i\}$ 与 $\{q_i\}$ 在多重集合意义上等价： $\prod_{{i\in[n]}}(\gamma-p_i)=\prod_{i\in[n]}(\gamma-q_i)$

• 置换证明引入随机数 $\beta$

  我们再使用一个技巧：再向 Verifier 索取一个随机数 $\beta$，把一个元组「折叠」成一个值：

$$ \begin{array}{|c|c|} a'_i=(a_i+\beta\cdot i) & b_i'=(b + \beta\cdot \sigma(i)) \\ \hline (a_0 + \beta\cdot 0) & (b_0 + \beta\cdot 1) \\ (a_1 + \beta\cdot 1) & (b_1 + \beta\cdot 0) \\ \vdots & \vdots \\ (a_{n-1} + \beta\cdot n-1) & (b_{n-1} + \beta\cdot n) \\ (a_n + \beta\cdot n) & (b_n + \beta\cdot (n-1))\\ \end{array} $$

我的疑惑：

1. 连乘证明在聚合多个多项式约束时，为什么一定要引入随机数 $\alpha$ ？直接聚合 $L_0(X)\cdot(r(X)-1)+ (q(X)\cdot r(X)-r(\omega\cdot X))=h(X)\cdot z_H(X)$ 会有什么问题？以及，为什么文中的第一个式子没有乘上 $\alpha$ （我理解应该是 「 $\alpha \cdot L_0(X)\cdot(r(X)-1)$ 」 ）

2. 置换证明在折叠元组时，为什么一定要引入随机数 $\beta$？直接折叠 $a'_i = (a_i + i) \quad b_i'=(b + \sigma(i))$ 会有什么问题？

3. 上述三个随机数 $\alpha$、 $\gamma$、 $\beta$ 能否都使用同一个数值？

[0xxEric]

分享一下我个人的见解，不一定准备，请其它同学老师指正：
1、没有聚合前，相当于要证两个式子的成立：
式一：L 0(X)(z(X)−1)=h1(x)*zH(x)
式二：q(X)⋅r(X)−r(ω⋅X)=h2(x)*zH(x)
那么，这样的话：Prover要去分别计算两个商多项式h1(x)与h2(x)，并且验证两次是否能整除zH(x)。然后需要Verifer发送两个随机数，ζ1与ζ2，来分别打开2个式子来验证成立。
而如果聚合的后，Verifer虽然也是要发两个随机数（先发α，再发ζ来验证），但这样只用构造一个h(x)，应该是计算量下降了。

而且，假如如果再有不只两个式子，而是n个式子的话，Verifer仍然只需要两个随机数（一个α，一个ζ），而不是n个随机（ζ1，ζ2...ζn）来验证。
因为这n个式子，都可以用（1，α，α^2，...）来聚合。

对于为何要引入随机数α、而不能直接聚合：因为没有随机数，不能实现“极大概率地验证正确性”，例如：
L 0(X)(z(X)−1)=h(x)*zH(x)+1；
q(X)⋅r(X)−r(ω⋅X)=h(x)*zH(x)-1；
二者相加后：L 0(X)(z(X)−1)+q(X)⋅r(X)−r(ω⋅X)=h(x)*zH(x) 能证明其能整除zH(x)
但不能证明，两个式子能分别整除zH(x)。而使用随机数α，使得Prover“偶然蒙对”的概率极低。

2、类同的道理，需要用随机数进行聚合
3、我认为既然是随机数，就是随机给出来的。可能一样可能不一样。不用在意是否是同一个数。