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\\ \en...