通过随机线性组合减少等式检查（约束）的数量
- RareSkills
- 发布于 2024-11-05 16:18
- 阅读 831
本文深入探讨了如何在零知识证明算法中利用随机线性组合来有效地检查多个等式的相等性。通过实例展示了Pedersen承诺的等式验证过程，并提出了一种减少通信开销的方法。这种技术能够实现对多个内积同时进行验证，从而提高效率。
随机线性组合是在零知识证明算法中常用的技巧，它可以通过一次等式检查以概率方式验证 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$$...
- 学分: 0
- 分类: 密码学
- 标签: 零知识证明 Pedersen承诺 随机线性组合 内积 安全性分析 Bulletproofs
