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

随机线性组合是在零知识证明算法中常用的技巧，它可以通过一次等式检查以概率方式验证 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$$

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

具体而言，证明者和验证者执行以下算法：

随机化的等式证明

设置

证明者和验证者就椭圆曲线点 G 和 B 达成一致，这些点的离散对数是未知的。

证明者发送承诺

证明者生成随机术语 α1,α2,β1,β2，并创建 Pedersen 承诺

$L1 = l{1}G + \alpha_1 B$ \ $R1 = r{1}G + \beta_1 B$ \ $L2 = l{2}G + \alpha_2 B$ \ $R2 = r{2}G + \beta_2 B$

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

验证者选择随机 z

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

证明者计算随机术语的差值

证明者计算 $π=α_1+α_2⋅z−β_1−β_2⋅z$，并将 π 发送给验证者。

最终验证检查

验证者检查

L1+L2z=?R1+R2z+πB

安全分析

如果 l1=r1 和 l2=r2，那么无论选择 z 如何，该方程在两边都会保持平衡，前提是证明者正确计算了 π。

现在假设 l1≠r1 或 l2≠r2。证明者仍然无法生成有效的 π，因为这样做需要解决 G 和 B 的离散对数。

推广到 m 次检查

如果我们有 m 次等式检查 L1=R1,L2=R2,…,Lm=Rm，验证者可以发送 m 个随机元素 z1,…,zm，证明者可以提供 π，使得

$L_1 + L_2z_1 + L_3z_2 + … Lmz{m-1} \stackrel{?}{=}R_1 + R_2z_1+R_3z_2+\dots+Rmz{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$

安全分析

左侧和右侧都是次数为 m−1 的多项式。如果它们不相等，那么根据 Schwartz Zippel Lemma，它们最多在 m−1 点相交。如果 m≪p，其中 p 是有限域的阶数，那么 z 成为交点的概率也是微不足道的。

内积的随机线性组合

我们可以将上述技巧推广到将多个内积结合在一起。

假设我们有两个内积

$\langle \mathbf{a}_L, \mathbf{a}_R\rangle = v_1$ and $\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) 的角度来看，这并不安全，因为有可能 ⟨aL,aR⟩≠v1 和 ⟨aL,aW⟩≠v2，但 ⟨aL,aR+aW⟩=v1+v2。

正如预期的那样，我们可以通过使用随机线性组合来解决此问题。

⟨aL,aR⟩=v1 // 第一个内积
z⟨aL,aW⟩=z⋅v2 // 第二个内积
⟨aL,z⋅aW⟩=z⋅v2 // 将 z 置于内部
⟨aL,aR+z⋅aW⟩=v1+z⋅v2 // 合并为一个内积

我们只需为单个内积创建一次内积证明，而不是两次。关键在于证明者在发送相关承诺后获得 z，但我们将详细信息留到下一章，当我们看到使用此技术的算法示例：区间证明。

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

• 原文链接： rareskills.io/post/rando...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～