通过随机线性组合减少等式检查（约束）的数量

随机线性组合是在零知识证明算法中常用的技巧，它可以通过一次等式检查以概率方式验证 m 个等式检查。假设我们有 m 个内积需要证明。我们不需要生成 m 个证明，而是创建等式的随机线性组合并证明它。

Pedersen承诺的等式

首先，让我们考虑如何证明多个 Pedersen 承诺的等式。

如果我们有椭圆曲线点 G 和 B，且其离散对数未知，以及随机术语 α 和 β，我们可以构造 Pedersen commitments L 和 R，其中

$L = aG + \alpha B$ $R = bG + \beta B$

如果证明者提供了随机术语的差值，则验证者可以检查 a=b。验证者不能简单地检查 L=R，因为随机术语通常不会相等，即 α≠β。

如果证明者想让验证者相信 a 和 b 分别与 L 和 R 相关联，但不揭示 a 和 b，证明者可以计算

$\pi = \alpha – \beta$

并将 π 交给验证者。验证者计算

$L \stackrel{?}{=} R + \pi B$

在底层，这会展开为

$(aG + \alpha B) = (bG + \beta B) + (\alpha – \beta) B$

所有随机术语会相互抵消，留下 aG=?bG。

但假设证明者希望建立多个承诺的等式，即 L1=L2,L2=R2,…,Lm=Rm。简单的方法是发送 m 个随机术语 π1,…,πm，验证者将进行 m 次等式检查。这将需要发送 m 个域元素 (π1,…,πm)，验证者的算法将在 O(m) 时间内运行。

为什么证明者不能简单地将所有承诺相加

假设我们有 l1,l2,r1,r2 及对应的承诺 L1,L2,R1,R2。假设证明者还想在不揭示它们的情况下证明 l1=r1 和 l2=r2。

以下检查是不安全的：

$$L_1 + L_2 = R_1 + R_2 + \pi B$$

其中 π 是随机术语的差值。作为一个反例，考虑 l1=1,r1=2,l2=2,r2=1 的情况。和是平衡的，但原始声明不正确。

随机线性组合

然而，如果要求证明者证明

$$L_1 + L_2z = R_1 + R_2z + \pi B$$...