随机线性组合（Random linear combinations）是零知识证明算法中常见的技巧，它能将 $m$ 个相等性检查以概率的形式合并为单次相等性检查。假设我们有 $m$ 个需要证明的内积（inner products）。我们不需要创建 $m$ 个证明，而是可以创建这些等式的随机线性组合并对其进行证明。

Pedersen 承诺的相等性

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

如果我们有离散对数未知的椭圆曲线点 $G$ 和 $B$，以及盲化因子（blinding terms）$\alpha$ 和 $\beta$，我们可以构造 Pedersen committments $L$ 和 $R$，其中

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

如果证明者提供了盲化因子的差值，验证者就可以检查 $a = b$ 是否成立。验证者不能简单地检查 $L = R$，因为盲化因子通常彼此不相等，即 $\alpha \neq \beta$。

如果证明者希望让验证者相信 $L$ 和 $R$ 分别是 $a$ 和 $b$ 的承诺，但不泄露 $a$ 和 $b$，证明者可以计算

$\pi = \alpha - \beta$

并将 $\pi$ 发送给验证者。验证者计算

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

在底层，这可以展开为

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

所有的盲化因子都会抵消，剩下 $aG \stackrel{?}{=} bG$。

但假设证明者希望建立几个承诺的相等性，即 $L_1 = L_2, L_2 = R_2, ..., L_m = R_m$。朴素的解决方案是发送 $m$ 个盲化因子 $\pi_1,...,\pi_m$，然后验证者将运行 $m$ 次相等性检查。这将需要发送 $m$ 个域元素（$\pi_1,...,\pi_m$），并且验证者的算法运行时间将为 $\mathcal{O}(m)$。

为什么证明者不能直接将所有承诺相加

假设我们有 $l_1, l_2, r_1, r_2$，它们对应的承诺分别为 $L_1, L_2, R_1, R_2$。同时假设证明者想要在不泄露它们的情况下证明 $l_1 = r_1$ 且 $l_2 = r_2$。

以下检查是不安全的：

其中 $\pi$ 是盲化因子的差值。作为一个反例，考虑 $l_1 = 1, r_1 = 2, l_2 = 2, r_2 = 1$ 的情况。它们的和是相等的，但最初的声明是不正确的。

随机线性组合

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

对于一个他们无法预测的随机值 $z$ 也成立，那么该方案就是安全的。

具体来说，证明者和验证者执行以下算法：

随机化相等性证明

设置

证明者和验证者就椭圆曲线点 $G$ 和 $B$ 达成共识，其中离散对数是未知的。

证明者发送承诺

证明者生成盲化因子 $\alpha_1, \alpha_2, \beta_1, \beta_2$ 并创建 Pedersen 承诺

$L_1 = l_{1}G + \alpha_1 B$
$R_1 = r_{1}G + \beta_1 B$
$L_2 = l_{2}G + \alpha_2 B$
$R_2 = r_{2}G + \beta_2 B$

并将 $(L_1, L_2, R_1, R_2)$ 发送给验证者。

验证者选取随机数 $z$

验证者选择一个随机域元素 $z$ 并将其发送给证明者。

证明者计算盲化因子的差值

证明者计算 $\pi = \alpha_1+\alpha_2\cdot z-\beta_1-\beta_2\cdot z$ 并将 $\pi$ 发送给验证者。

最终验证检查

验证者检查以下等式是否成立：

安全性分析

如果 $l_1 = r_1$ 且 $l_2 = r_2$，那么无论 $z$ 的选择如何，假设证明者正确计算了 $\pi$，该等式都将保持平衡。

现在假设 $l_1\neq r_1$ 或 $l_2 \neq r_2$。证明者仍然无法生成有效的 $\pi$，因为这样做将需要求解 $G$ 和 $B$ 的离散对数。

推广到 $m$ 个检查

如果我们有 $m$ 个相等性检查，即 $L_1 = R_1, L_2 = R_2, ..., L_m = R_m$，验证者可以发送 $m$ 个随机元素 $z_1,\dots,z_m$，且证明者可以提供 $\pi$，使得：

$L_1 + L_2z_1 + L_3z_2 + ... L_mz_{m-1} \stackrel{?}{=}R_1 + R_2z_1+R_3z_2+\dots+R_mz_{m-1} + \pi B$

然而，这需要验证者发送 $m$ 个元素，从而导致线性的通信开销。如果验证者只发送 $z$，并且证明者和验证者用 $z$ 的连续幂次将承诺隔开，通信开销可以降低到常数级别：

$L_1 + L_2z + L_3z^2 + ... L_mz^{m-1} \stackrel{?}{=}R_1+R_2z+R_3z^2\dots+R_mz^{m-1} + \pi B$

安全性分析

左侧（left-hand-side）和右侧（right-hand-side）都是次数为 $m-1$ 的多项式。如果它们彼此不相等，那么根据 Schwartz Zippel Lemma（施瓦茨-齐佩尔引理），它们最多在 $m-1$ 个点处相交。如果 $m\ll p$（其中 $p$ 是有限域的阶），那么 $z$ 成为交点的概率依然可以忽略不计。

内积的随机线性组合

我们可以将上述技术推广，从而将多个内积组合在一起。

假设我们有两个内积

$\langle \mathbf{a}_L, \mathbf{a}_R\rangle = v_1$ 且 $\langle \mathbf{a}_L, \mathbf{a}_W\rangle=v_2$

因为这两个内积共享一个公共项，在代数上可以将它们组合如下：

$\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$

然而，从可靠性（soundness）的角度来看，这是不安全的，因为可能存在 $\langle \mathbf{a}_L, \mathbf{a}_R\rangle \neq v_1$ 且 $\langle \mathbf{a}_L, \mathbf{a}_W\rangle\neq v_2$，但 $\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$ 的情况。

果然不出所料，我们可以通过使用随机线性组合来解决这个问题。

我们只需为一个内积创建内积证明，而不需要为两个内积分别创建。至关重要的是，证明者必须在发送相关承诺之后才接收到 $z$，但我们将具体细节留到下一章，届时我们将看到一个使用此技术的算法示例：范围证明（range proofs）。

本教程是 ZK Bulletproofs 系列的一部分。