针对内积的零知识证明

Last updated on Nov 13, 2024

内积论证（inner product argument）是一种证明，用于证明证明者正确执行了内积计算。本章将展示如何为内积论证构造零知识证明。

在上一章中，我们展示了如何以零知识的方式将两个标量相乘：我们对两个一阶多项式进行承诺（commit），并证明我们正确计算了它们的乘积，然后证明一阶多项式的常数项是我们所乘的秘密因子的承诺。

如果我们多项式的系数是向量而不是标量，那么我们就可以证明我们正确计算了向量的内积。现在我们引入向量多项式（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 product，即逐元素乘积，用 $\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}

换句话说，将两个向量多项式相乘然后对乘积在某点求值，与分别对向量多项式求值然后对所得向量取阿达马乘积是等价的。

向量多项式的内积

为了计算两个向量多项式的内积，我们按照上述方法将它们相乘，然后将向量中的各项相加，使结果变为一个标量。我们将此操作表示为 $\langle \mathbf{l}(x), \mathbf{r}(x) \rangle$ 。我们也可以通过在将向量系数相乘时使用内积而不是阿达马乘积来实现相同的结果。

对于上面那两个例子中的多项式，计算过程将是：

\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$ 。

为什么这在通常情况下成立

假设我们以“常规”方式将向量多项式相乘——即对系数取逐元素乘积（阿达马乘积）而不是内积。每个系数的内积实际上就是每个系数的阿达马乘积各项的总和。

因此我们可以说，如果我们有两个向量多项式 $\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$ 。

设置

证明者和验证者就以下参数达成一致：

证明者用于承诺向量的基向量（basis vectors） $\mathbf{G}$ 和 $\mathbf{H}$
椭圆曲线点 $G$ （独立于 $\mathbf{G}$ ），将用于对 $t(x)$ 的系数以及承诺给 $V$ 的内积进行承诺
用于盲化项（blinding terms）的椭圆曲线点 $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$ 处求值的内积等于向量多项式 $\mathbf{l}_x$ 和 $\mathbf{r}_x$ 在 $x = u$ 处求值的内积。

其次，验证者检查 $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}$ 的长度），这并不够简洁（succinct）。

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

具体而言，我们将通过发送对 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺（而不是实际的向量），同时附带一个对数大小的证明来表明该承诺包含内积为 $t_u$ 的向量，从而优化 $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, T_2, \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

# casting a numpy array to numpy doesn't do anything
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)

# if points = G1, G2, G3, G4 and scalars = a,b,c,d vector_commit returns
# aG1 + bG2 + cG3 + dG4
def vector_commit(points, scalars):
    return reduce(add, [multiply(P, i) for P, i in zip(points, scalars)], Z1)


# these EC points have unknown discrete logs:
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))

# scalar multiplication example: multiply(G, 42)
# EC addition example: add(multiply(G, 42), multiply(G, 100))

# remember to do all arithmetic modulo 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):
    # fill this in
    # return pi
    pass

## step 0: Prover and verifier agree on G and B

## step 1: Prover creates the commitments
a = np.array([89,15,90,22])
b = np.array([16,18,54,12])
sL = ...
sR = ...
t1 = ...
t2 = ...

### blinding terms
alpha = ...
beta = ...
gamma = ...
tau_1 = ...
tau_2 = ...

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

## step 2: Verifier picks u
u = ...

## step 3: Prover evaluates l(u), r(u), t(u) and creates evaluation proofs
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)

## step 4: Verifier accepts or rejects
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 or r_u not evaluated correctly"
assert eq(add(multiply(G, t_u), multiply(B, pi_t)), add_points(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u not evaluated correctly"

本教程是 ZK Bulletproofs 系列的一部分。