Bulletproofs零知识证明：内积的零知识与简洁证明

Bulletproofs ZKPs 允许证明者以对数大小的证明来证明对内积的知识。Bulletproofs 不需要一个可信的设置。

在前面的章节中，我们展示了如何在不透露向量或内积的情况下证明对内积的知识，尽管这需要一个大小为 $\mathcal{O}(n)$ 的证明，其中 $n$ 是向量的长度。我们还展示了如何使用对数大小的数据来证明对内积的知识，但没有零知识属性。

在本章中，我们将这些算法结合在一起，以演示 Bulletproof ZK 算法。

（此工作是关于 ZK Bulletproofs 系列的一部分。）

问题陈述

证明者和验证者同意两个椭圆曲线基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 的长度为 $n$，以及椭圆曲线点 $Q$ 和 $B$。所有这些点之间的离散对数关系都是未知的。

证明者有向量 $\mathbf{a}$ 和 $\mathbf{b}$，其内积为 $v$。证明者将 $\mathbf{a}$ 和 $\mathbf{b}$ 承诺为 $A$，即 $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$，其中 $\alpha$ 是盲项。证明者承诺 $V = \langle\mathbf{a},\mathbf{b}\rangle Q + \gamma B$。

证明者将 $(A, V)$ 发送给验证者，旨在证明 $\mathbf{a}$ 和 $\mathbf{b}$ 被承诺为 $A$，其内积被承诺为 $V$。验证者不学习向量或内积。

证明的大小必须为 $\mathcal{O}(\log n)$。

Bulletproof ZK 算法

证明者生成随机标量 $\set{\alpha, \beta,\gamma,\tau_1,\tau_2}$ 和随机向量 $\set{\mathbf{s}_L,\mathbf{s}_R}$，并计算承诺

$$ \begin{align} A &= \langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle + \langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\ V &= vQ + \gamma B \\ \end{align} $$

证明者准备（但不发送）向量多项式

$$ \begin{align} \mathbf{l}(x) &= \mathbf{a} + \mathbf{s}_Lx\\ \mathbf{r}(x) &= \mathbf{b} + \mathbf{s}_Rx\\ t(x)&=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle = \langle\mathbf{a},\mathbf{b}\rangle+(\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle) x+(\langle\mathbf{s}_L,\mathbf{s}_R\rangle)x^2 \end{align} $$

$A$ 是对向量多项式的常数项的承诺，$S$ 是对线性项的承诺，$V$ 是对内积的承诺。

证明者为了 $t(x)$ 的系数创建承诺如下

$$ \begin{align} T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)Q + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle Q + \tau_2B \end{align} $$

注意 $V$ 是 $t(x)$ 的常数系数的承诺，$T_1$ 和 $T_2$ 分别是 $t(x)$ 的线性和二次系数的承诺。

证明者将 $(A, S, V, T_1, T_2)$ 发送给验证者。

验证者以随机值 $u$ 进行响应。

然后，证明者在 $u$ 处评估多项式，并创建它们被正确评估的证明：

$$ \begin{align} \mathbf{l}_u &= \mathbf{l}(u) = \mathbf{a} + \mathbf{s}_Lu \\ \mathbf{r}_u &= \mathbf{r}(u) = \mathbf{b} + \mathbf{s}_Ru \\ t_u &= t(u) =v + (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)u + \langle\mathbf{s}_L,\mathbf{s}R\rangle u^2\\ \pi{lr} &=\alpha+\beta u\\ \pi_t &= \gamma + \tau_1u + \tau_2u^2\\ \end{align} $$

之前，证明者传输 $(\mathbf{l}_u, \mathbf{r}_u, tu, \pi{lr}, \pi_t)$，以便验证者可以检查

$$ \begin{align} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A + Su &\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}u, \mathbf{H} \rangle + \pi{lr} B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 – \pi_t B\\ \end{align} $$

但由于向量 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的存在，这将是线性大小的。相反，证明者将 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 承诺为

$$ C=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{H}\rangle $$

并发送 $(C, tu, \pi{lr}, \pi_t)$。

我们可以将前两个验证者检查重新排列如下：

$$ \begin{align} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}u\rangle\\ A + Su -\pi{lr}B&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align} $$

注意，如果我们设定 $P = A + Su -\pi_{lr}B$，那么这与证明 $P$ 向量 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 相对于基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 的承诺，并且 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的内积为 $t_u$ 的问题表述是相同的。因此，我们可以重用对 $P$ 的承诺开启的对数大小证明的知识。

对于这个证明，我们不需要保密，因为 $\mathbf{l}_u$ 和 $\mathbf{r}_u 在之前的算法中已经公开。

现在，验证者拥有所有必要的数据，证明者参与一个交互式证明，以证明 $C$ 保持对 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺，并且它们的内积为 $t_u$：

$$ \{prove_commitments_log}(C + t_uQ, \mathbf{G}, \mathbf{H}, Q, \mathbf{l}_u, \mathbf{r}_u) $$

该子例程将证明 $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ 和 $C\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle$ 而不必发送 $\mathbf{l}_u$ 和 $\mathbf{r}_u$。它还仅发送对数大小的数据。请注意，上一章中递归算法使用承诺 $P = \langle \mathbf{a}, \mathbf{G} \rangle + \langle \mathbf{b}, \mathbf{H} \rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$，因此验证者需要自行添加“$Q$ 部分”。现在验证者可以确保

$$ \begin{align} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ C&\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle\\ \end{align} $$

最后，验证者检查

$$ \begin{align} C&\stackrel{?}=A + Su-\pi_{lr}B\\ t_u Q &\stackrel{?}{=} V + T_1 u + T_2 u^2 – \pi_t B \end{align} $$

请记住，$A$ 和 $S$ 是向量多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 的常数和线性项的承诺。第一个检查确保对 $C$ 的承诺向量是这些多项式在 $u$ 处的评估。

第二个检查确保 $t(u)$ 被正确评估，给定对系数 $V$、$T_1$ 和 $T_2$ 的承诺。

通过 Fiat Shamir 变换实现非交互性

在实践中，通过 Fiat Shamir Transform 使该算法成为非交互式。证明者不是向验证者请求随机性，而是通过将它迄今为止传输的所有数据进行连接并对其进行哈希来生成随机性。然后，验证者重新哈希这些数据，以确保证明者正确生成了随机性。

关键是哈希必须包含所有之前的数据传输，否则实现将具有 冻结心脏漏洞。

下一步

在实践中，实际关注的问题由多个内积组成。例如，一个 Rank 1 Constraint System:

$$ L\mathbf{a}\circ R\mathbf{a} = O\mathbf{a} $$

实际上是 $3n$ 个内积（例如，将 $\mathbf{a}$ 与 $L$ 的 $n$ 行相乘，以此类推对于 $R$ 和 $O$），还有一个 Hadamard 乘积。因此，知道一些将多个内积合并为单个内积的数学技巧将是很有用的，以便我们不必发送 $3n$ 个 Bulletproofs。在即将到来的关于随机线性组合的章节中，我们将学习如何实现这一点。

此外，一些有用的问题可以直接编码为内积，尤其是范围证明或子集和问题。在那些情况下，我们可以跳过将问题编码为 算术电路 的步骤，直接将其编码为内积。为了提高我们的内积表示的灵活性，并为理解随机线性组合奠定基础，我们将在下一章学习一些内积代数。

练习: 结合之前的练习，证明 $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$，其中 $\mathbf{a}$ 和 $\mathbf{b}$ 是长度为 4 的向量。你的证明应该简洁且具有零知识。为了简单起见，创建一个交互式证明。请参考 这个代码库 以获取练习。

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