内积的零知识证明

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

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

如果我们多项式的系数是向量而不是标量，那么我们可以证明我们正确地计算了向量的内积。我们现在介绍 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)$ 的系数和内积承诺 $V$
• 用于盲化项的椭圆曲线点 $B$

证明者

证明者生成盲化项 $\alpha$、$\beta$、$\gamma$、$\tau_1$ 和 $\tau_2$ 并计算：

$$ \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 &= vG + \gamma B \\ T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle )G + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle G + \tau_2B \end{align} $$

请注意这次线性系数 $\mathbf{s}_L$ 和 $\mathbf{s}_R$ 是向量而不是标量。证明者将$(A, S, V, T_1, T_2)$传递给验证者。在验证者用随机 $u$ 响应后，证明者在 $u$ 处评估 $\mathbf{l}(x)$、$\mathbf{r}(x)$ 及其内积 $\mathbf{t}(x)$。

$$ \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 &= 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} $$

最终验证步骤

首先，验证者检查 $t_u$ 是否为 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 在 $u$ 处的内积求值。

$$ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle $$

如果证明者是诚实的，这是真的，因为在 $u$ 处求值的多项式的内积与在 $x = u$ 处评估的向量多项式 $\mathbf{l}_x$ 和 $\mathbf{r}_x$ 的内积是相同的。

其次，验证者检查 $A$ 和 $S$ 是否分别是 $\mathbf{l}$ 和 $\mathbf{r}$ 的常数项和线性项的承诺。

$$ A + Su \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}u, \mathbf{H} \rangle + \pi{lr} B $$

回想一下 $A$ 和 $S$ 是 $\mathbf{l}$ 和 $\mathbf{r}$ 的常数项和线性项的承诺，$\pi_{lr}$ 是 $A$ 和 $S$ 中盲化项 $\alpha$ 和 $\beta$ 的和。

最后，验证者检查 $t_u$ 是否为承诺 $V, T_1, T_2$ 的二次多项式的求值：

$$ t_uG + \pi_tB \stackrel{?}{=} V + T_1 u + T_2 u^2 $$

改善证明大小

当证明者发送 $(\mathbf{l}, \mathbf{r}, t, T_1, T_2, \pi)$ 时，证明者发送了 $2n$ 个元素（向量的长度为 $\mathbf{l}$ 和 $\mathbf{r}$），这不是简洁的。

在接下来的章节中，我们将学习如何减少证明的大小。我们可以创建一个大小为 $\log n$ 的正确内积的证明。也就是说，如果我们想证明计算了两个长度为 $n$ 的向量的内积，那么证明的大小仅为 $\log n$——呈指数级减少。

具体而言，我们将通过发送对 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺而不是实际向量及其内积为 $t_u$ 的大小为 $\log n$ 的证明来优化步骤 $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$。

总结

我们描述了一个协议，证明 $A$ 是对 $\mathbf{a}$ 和 $\mathbf{b}$ 的承诺，$V$ 是对 $v$ 的承诺，并且 $\langle \mathbf{a}, \mathbf{b} \rangle = v$，而不揭示 $\mathbf{a}$、$\mathbf{b}$ 或 $v$。然而，证明的大小是线性的，因为在 $(\mathbf{l}_u, \mathbf{r}_u, t, T_1, T2, \pi{lr},\pi_t)$ 中的每个 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的大小为 $n$。

练习： 填补缺失的代码以实现本讲座中的算法。证明你知道内积计算，对于一个 $n=4$ 的向量而不揭示它。请注意，numpy 数组允许逐元素加法和乘法。例如：

import numpy as np
a = np.array([1,2,3,4])
b = np.array([2,2,2,2])

print(a + b) # np.array([3,4,5,6])
print(a * b) # np.array([2,4,6,8])
print(numpy.inner(a, b)) # 20

## 将 numpy 数组转换为 numpy 不会做任何事情
print(np.array(a) + b) # np.array([3,4,5,6])

填补以下代码：

from py_ecc.bn128 import G1, multiply, add, FQ, eq, Z1
from py_ecc.bn128 import curve_order as p
import numpy as np
from functools import reduce
import random

def random_element():
    return random.randint(0, p)

def add_points(*points):
    return reduce(add, points, Z1)

## 如果 points = G1, G2, G3, G4 而 scalars = a,b,c,d 则 vector_commit 返回
## aG1 + bG2 + cG3 + dG4
def vector_commit(points, scalars):
    return reduce(add, [multiply(P, i) for P, i in zip(points, scalars)], Z1)

## 这些 EC 点的离散对数未知：
G = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

H = [(FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919)),
    (FQ(17471368056527239558513938898018115153923978020864896155502359766132274520000), FQ(4119036649831316606545646423655922855925839689145200049841234351186746829602)),
    (FQ(8730867317615040501447514540731627986093652356953339319572790273814347116534), FQ(14893717982647482203420298569283769907955720318948910457352917488298566832491)),
    (FQ(419294495583131907906527833396935901898733653748716080944177732964425683442), FQ(14467906227467164575975695599962977164932514254303603096093942297417329342836))]

B = (FQ(12848606535045587128788889317230751518392478691112375569775390095112330602489), FQ(18818936887558347291494629972517132071247847502517774285883500818572856935411))

## 标量乘法示例：multiply(G, 42)
## EC 加法示例：add(multiply(G, 42), multiply(G, 100))

## 请记得对 p 进行所有的模运算
def commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2):
    pass
    # return (A, S, V, T1, T2)

def evaluate(f_0, f_1, f_2, u):
    return (f_0 + f_1 * u + f_2 * u**2) % p

def prove(blinding_0, blinding_1, blinding_2, u):
    # 填写此部分
    # return pi
    pass

### 第0步：证明者与验证者就 G 和 B 达成一致

### 第1步：证明者创建承诺
a = np.array([89,15,90,22])
b = np.array([16,18,54,12])
sL = ...
sR = ...
t1 = ...
t2 = ...

#### 盲化项
alpha = ...
beta = ...
gamma = ...
tau_1 = ...
tau_2 = ...

A, S, V, T1, T2 = commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2)

### 第2步：验证者选择 u
u = ...

### 第3步：证明者评估 l(u)、r(u)、t(u) 并创建评估证明
l_u = evaluate(a, sL, 0, u)
r_u = evaluate(b, sR, 0, u)
t_u = evaluate(np.inner(a, b), t1, t2, u)

pi_lr = prove(alpha, beta, 0, u)
pi_t = prove(gamma, tau_1, tau_2, u)

### 第4步：验证者接受或拒绝
assert t_u == np.mod(np.inner(np.array(l_u), np.array(r_u)), p), "tu !=〈lu, ru〉"
assert eq(add(A, commit(S, u)), add_points(vector_commit(G, l_u), vector_commit(H, r_u), multiply(B, pi_lr))), "l_u 或 r_u 评估不正确"
assert eq(add(multiply(G, t_u), multiply(B, pi_t)), add_points(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u 评估不正确"

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

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