内积的零知识证明

一个内积论证是一个证明，证明者正确地进行了内积计算。本章展示了如何为内积论证构造零知识证明。

在前一章中，我们展示了如何以零知识的方式相乘两个标量：我们承诺两个度为一的多项式，并证明我们正确地计算了它们的乘积，然后显示这两个度为一的多项式的常数项是我们要相乘的秘密因子的承诺。

如果我们多项式的系数是向量而不是标量，那么我们可以证明我们正确地计算了向量的内积。我们现在介绍 vector polynomial。

向量多项式：以向量为系数的多项式

以下是两个带有向量系数的多项式：

$$ \begin{align} \mathbf{l}(x) &= \begin{bmatrix} 1 \ 2 \end {bmatrix} x + \begin{bmatrix} 3 \ 4 \end{bmatrix} \ \mathbf{r}(x) &= \begin{bmatrix} 2 \ 3 \end{bmatrix} x +\begin{bmatrix} 7 \ 2 \end{bmatrix} \end{align} $$

对向量多项式的求值会产生另一个向量。例如，$\mathbf{l}(2)$ 的结果是：

$$ \begin{align} \mathbf{l}(2) &= \begin{bmatrix} 1 \ 2 \end{bmatrix} (2) + \begin{bmatrix} 3 \ 4 \end{bmatrix} \ &= \begin{bmatrix} 2 \ 4 \end{bmatrix} + \begin{bmatrix} 3 \ 4 \end{bmatrix} \ &= \begin{bmatrix} 5 \ 8 \end{bmatrix} \end{align} $$

并且对 $\mathbf{r}$ 进行 2 的求值返回：

$$ \begin{align} \mathbf{r}(2) &= \begin{bmatrix} 2 \ 3 \end{bmatrix} (2) + \begin{bmatrix} 7 \ 2 \end{bmatrix} \ &= \begin{bmatrix} 4 \ 6 \end{bmatrix} + \begin{bmatrix} 7 \ 2 \end{bmatrix} \ &= \begin{bmatrix} 11 \ 8 \end{bmatrix} \end{align} $$

$\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 采用粗体字书写，因为它们在某个标量 $x$ 的求值时产生向量。

乘法向量多项式

向量多项式可以像标量多项式一样相乘。例如，乘法得出 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 为：

$$ \begin{align} \mathbf{l}(x)\mathbf{r}(x) &= (\begin{bmatrix} 1\ 2 \end{bmatrix}x + \begin{bmatrix} 3\ 4 \end{bmatrix})( \begin{bmatrix} 2 \ 3 \end{bmatrix}x + \begin{bmatrix} 7\ 2 \end{bmatrix} ) \ &= \begin{bmatrix} 1 \ 2 \end{bmatrix}\circ \begin{bmatrix} 2 \ 3 \end{bmatrix}x^2 + \begin{bmatrix} 1 \ 2 \end{bmatrix}\circ \begin{bmatrix} 7 \ 2 \end{bmatrix}x + \begin{bmatrix} 3 \ 4 \end{bmatrix}\circ \begin{bmatrix} 2 \ 3 \end{bmatrix}x + \begin{bmatrix} 3 \ 4 \end{bmatrix}\circ \begin{bmatrix} 7 \ 2 \end{bmatrix} \ &= \begin{bmatrix} 2 \ 6 \end{bmatrix}x^2 + \begin{bmatrix} 7 \ 4 \end{bmatrix}x + \begin{bmatrix} 6 \ 12 \end{bmatrix}x + \begin{bmatrix} 21 \ 8 \end{bmatrix} \ &= \begin{bmatrix} 2 \ 6 \end{bmatrix}x^2 + \begin{bmatrix} 13 \ 16 \end{bmatrix}x + \begin{bmatrix} 21 \ 8 \end{bmatrix} \end{align} $$

当我们将每个向量相乘时，我们采用Hadamard积（逐元素乘积，用 $\circ$ 表示）。

请注意，如果我们将 $x = 2$ 代入结果向量多项式，我们将得到以下结果：

$$ \begin{bmatrix} 2 \ 6 \end{bmatrix}(2)^2 + \begin{bmatrix} 13 \ 16 \end{bmatrix}(2) + \begin{bmatrix} 21 \ 8 \end{bmatrix}= \begin{bmatrix} 55 \ 64 \end{bmatrix} $$

这与我们计算时得到的结果是相同的：

$$ \mathbf{l}(2)\circ\mathbf{r}(2) = \begin{bmatrix}5\8\end{bmatrix}\circ\begin{bmatrix}11\8\end{bmatrix}=\begin{bmatrix}55\64\end{bmatrix} $$

换句话说，将两个向量多项式相乘，然后在某个点处求值，与分别对这两个向量多项式求值然后对得到的向量进行Hadamard积是相同的。

向量多项式的内积

为了计算两个向量多项式的内积，我们像上面的介绍那样将它们相乘，但随后总结向量项以使结果成为标量。我们将此操作表示为 $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$。我们可以通过使用内积而不是Hadamard积来实现相同的结果，当我们将向量系数相乘时。

对于上述两个示例多项式，这是：

$$ \langle \mathbf{l}(x), \mathbf{r}(x) \rangle = \langle \begin{align}\end{align} \begin{bmatrix} 1 \ 2 \end{bmatrix} x +\begin{bmatrix} 3 \ 4 \end{bmatrix},\begin{bmatrix} 2 \ 3 \end{bmatrix}x+\begin{bmatrix} 7 \ 2 \end{bmatrix}\rangle $$

$$ =\langle \begin{bmatrix} 1 \ 2 \end{bmatrix},\begin{bmatrix} 2 \ 3 \end{bmatrix}\rangle x^2 + \langle \begin{bmatrix} 3 \ 4 \end{bmatrix},\begin{bmatrix} 2 \ 3 \end{bmatrix}\rangle x + \langle \begin{bmatrix} 1 \ 2 \end{bmatrix},\begin{bmatrix} 7 \ 2 \end{bmatrix}\rangle x+\langle \begin{bmatrix} 3 \ 4 \end{bmatrix},\begin{bmatrix} 7 \ 2 \end{bmatrix}\rangle $$

$$ =(1\cdot2+2\cdot3)x^2+(3\cdot2+4\cdot3)x + (1\cdot7+2\cdot2) x + (3\cdot7+4\cdot2) $$

$$=8x^2 + 18x + 11x + 29$$

$$=8x^2 + 29x + 29$$

请注意，$\langle\mathbf{l}(2), \mathbf{r}(2)\rangle$ 等于 $\langle \mathbf{l}(x), \mathbf{r}(x)\rangle$ 在 $x = 2$ 的求值。也就是说，$\langle [5, 8], [11, 8]\rangle = 119$ 且 $8(2)^2 + 29(2) + 29 = 119$。

为什么这在一般情况下有效

假设我们用“正常”的方式来乘法向量多项式——即，我们对系数的逐元素乘积（Hadamard积）进行处理。每个系数的内积就是每个系数的Hadamard积的项之和。

因此，我们可以说，如果我们有两个向量多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$，并且我们以 $\mathbf{t}(x)=\mathbf{l}(x)\mathbf{r}(x)$ 的方式相乘，那么内积 $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ 等于 $\mathbf{t}$ 的系数的逐元素和。请注意，两向量多项式的乘积结果是一个向量多项式，但两向量多项式的内积结果是所有系数为标量的多项式。

零知识内积证明

在前一章关于零知识乘法的内容中，我们证明了我们有一个有效的乘法，方法是通过证明两个线性多项式的常数项乘积等于多项式乘积中的常数项。

为了证明内积的计算正确，我们用向量多项式替换多项式，并用向量多项式的内积替换标量多项式的乘法。

其他一切保持不变。

算法

目标是让证明者说服验证者 $A$ 是一个对 $\mathbf{a}$ 和 $\mathbf{b}$ 的承诺，$V$ 是一个对 $v$ 的承诺，并且 $\langle \mathbf{a}, \mathbf{b} \rangle = v$，而不揭示 $\mathbf{a}$、$\mathbf{b}$ 或 $v$。

设置

证明者和验证者达成一致：

• 基向量 $\mathbf{G}$ 和 $\mathbf{H}$，证明者可以用这些向量来承诺向量
• 椭圆曲线点 $G$（与 $\mathbf{G}$ 不同），将用于承诺 $t(x)$ 的系数和内积承诺...