在前一章中，我们展示了将向量 $\mathbf{a}$ 和 $\mathbf{G}$ 的元素之和相乘，可以计算出外积项的总和，即 $\sum \mathbf{a}\otimes\mathbf{G}=\sum\mathbf{a}\sum\mathbf{G}$。我们还展示了外积在其主对角线上“包含”了内积。

为了“提取”内积 $\langle\mathbf{a},\mathbf{G}\rangle$，必须从外积中减去所有不属于内积的项，即下方紫色阴影区域：

这样的项有 $\mathcal{O}(n^2)$ 个，因此直接这样做的效率并不高。

然而，请注意，我们可以按照下方动画所示的方式“填满外积”：

在上面的动画中，证明者在发送非对角线项后，将 $\mathbf{G}$ 和 $\mathbf{a}$ 都进行了折叠（fold），使其长度减半。

最后，在我们将 $\mathbf{a}$ 和 $\mathbf{G}$ 折叠 $\log n$ 次之后，向量的大小变为 1。当 $n=1$ 时，外积等于内积，我们只需直接揭示这两个向量即可，它们的大小是常数级别的。

回顾——以及它与上一章算法的关联

此前，我们展示了如何证明我们知道承诺 $P$ 的打开方式（opening），同时只发送 $n/2$ 个元素而不是 $n$ 个。作为回顾：

证明者将向量 $\mathbf{a}$ 承诺为 $P$，即 $P = \langle\mathbf{a},\mathbf{G}\rangle$。然后证明者发送非对角线项 $L=a_1G_2 + a_3G_4 + \dots a_{n-1}G_n$ 和 $R = a_2G_1 + a_4G_3 + \dots a_nG_{n-1}$。验证者回复 $u$，证明者使用 $u$ 对向量 $\mathbf{a}$ 进行折叠，得到 $\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)=[a_1u+a_2u^{-1}, a_3u+a_4u^{-1}, \dots, a_{n-1}u+a_nu^{-1}]$，并将 $\mathbf{a}'$ 发送给验证者。由于 $\mathbf{a}'$ 的长度为 $n/2$，我们将需要传输的数据大小减少了一半。

然后验证者检查 $\langle\mathsf{fold}(\mathbf{G},u^{-1}),\mathbf{a}'\rangle\stackrel{?}=Lu^2+P+Ru^{-2}$

该算法的最初意图是，通过展示我们知道内积 $P$ 与非对角线项 $L$ 和 $R$ 的总和等于 $\mathbf{a}$ 和 $\mathbf{G}$ 成对划分的外积元素之和，来证明我们知道承诺 $P$。

如果我们递归应用这个算法，就会得到本章开头描述的 $\log n$ 算法。

然而，我们也可以将此过程解释为：我们在证明自己知道承诺 $P'$（其中 $P'=(Lu^2+P+Ru^{-2})$）关于长度为 $n'=n/2$ 的基向量 $\mathsf{fold}(\mathbf{G},u^{-1})$ 的打开方式。我们可以用一种朴素的方法来证明我们知道 $P'$ 的打开方式：发送 $\mathbf{a}'$，然后让验证者检查 $P'\stackrel{?}=\langle\mathbf{a'},\mathsf{fold}(\mathbf{G},u^{-1})\rangle$。

但是，与其通过发送 $\mathbf{a}'$ 来证明我们知道 $P'$ 的打开方式，不如递归应用该算法，通过发送大小为 $n/4$ 的向量 $\mathbf{a}{\prime\prime}$ 来证明我们知道 $P'$ 的打开方式。事实上，我们可以不断递归，直到 $a^{\prime\dots\prime}$ 的大小变为 $n=1$。

下方的动画直观地展示了这一过程。下一节将详细描述该动画。

为了使该算法生效，向量的长度必须是 2 的幂。不过，如果长度不是 2 的幂，我们可以用零填充向量，直到长度变为 2 的幂。

使用 $\mathcal{O}(\log n)$ 数据证明我们知道 $P$ 的打开方式

算法

证明者和验证者约定一个长度为 $n$ 的基向量 $\mathbf{G}$。证明者向验证者发送 $P$，即 $\langle\mathbf{a},\mathbf{G}\rangle$。证明者希望在仅发送对数规模数据的情况下，使验证者确信其知道 $P$ 的打开方式。

证明者和验证者随后执行下方的算法。符号 | 后面的参数表示它们仅为证明者所知。

在下方的算法描述中，$n$ 是输入中向量的长度，所有向量的长度都相同。

\texttt{prove_commitments_log}(P, \mathbf{G}, | \mathbf{a})

情况 1：$n = 1$

1. 证明者发送 $a$，验证者检查 $aG \stackrel{?}= P$，算法结束。

情况 2：$n > 1$

1. 证明者计算并向验证者发送 $(L, R)$，其中：
   
   $$\begin{align*} L &= a_1G_2 + a_3G_4 + \dots a_{n-1}G_n\\ R &= a_2G_1 + a_4G_3 + \dots a_nG_{n-1} \end{align*}$$
2. 验证者发送随机数 $u$
3. 证明者和验证者双方共同计算：
   
   $$\begin{align*} \mathbf{G}'&=\mathsf{fold}(\mathbf{G},u^{-1})\\ P' &= Lu^2+P+Ru^{-2} \end{align*}$$
4. 证明者计算：
   
   $$\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)$$
5. \texttt{prove_commitments_log}(P', \mathbf{G}', \mathbf{a}')

算法点评

证明者在递归地证明，在给定 $P$ 和 $\mathbf{G}$ 的情况下，他们知道 $\mathbf{a}$ 使得 $P=\langle\mathbf{a},\mathbf{G}\rangle$。双方递归地折叠 $\mathbf{G}$ 直至其成为单个点，证明者递归地折叠 $\mathbf{a}$ 直至其成为单个点。

证明者在每次迭代中传输常数数量的数据，且递归最多运行 $\log n$ 次，因此证明者发送的数据量为 $\mathcal{O}(\log n)$。

我们要强调的是，该算法并非零知识的，因为在 $n=1$ 的情况下，验证者会获知整个向量。验证者也可以发送非随机的 $u$ 值，试图了解关于 $\mathbf{a}$ 的信息。

然而，回顾一下，我们设计这个算法的动机是为了减小检查 $t_u=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ 的规模，而且 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 本来就不是秘密。

事实上，我们还没有展示如何使用对数规模的数据来证明我们知道内积，我们只是展示了我们知道如何用对数规模的数据打开一个承诺。不过，更新我们的算法以证明我们知道两个向量的内积是非常直接的，正如我们将在本文后面所做的那样。

运行时间

验证者执行了 $\log n$ 次 $\mathbf{G}' = \mathsf{fold}(\mathbf{G}, u^{-1})$ 计算，而第一次 $\mathsf{fold}$ 需要 $\mathcal{O}(n)$ 的时间。乍看之下，验证者的运行时间似乎是 $\mathcal{O}(n \log n)$。然而请注意，在每次迭代中，$n$ 都会减半，从而导致运行时间为 $n + \frac{n}{2} + \frac{n}{4} + ... + 1 = 2n$，因此验证者的整体运行时间为 $\mathcal{O}(n)$。

证明我们知道内积 $\langle\mathbf{a},\mathbf{b}\rangle=v$

现在我们调整上述算法，以证明我们对两个标量向量执行了内积，而不是对一个域元素向量和一个椭圆曲线点向量执行内积。

具体来说，我们必须证明 $P$ 包含了对内积 $\langle\mathbf{a},\mathbf{b}\rangle$ 的承诺。该内积是一个标量，因此我们执行的是普通的 Pedersen commitment，而不是向量承诺。为此，我们使用一个随机的椭圆曲线点（具有未知的离散对数）$Q$。因此，$P = \langle\mathbf{a},\mathbf{b}\rangle Q$。

但是，我们不能简单地重用之前的算法，因为证明者可以为 $P$ 提供多种打开方式。例如，如果 $\mathbf{a} = [1,2]$ 且 $\mathbf{b} = [3,4]$，证明者同样也可以使用向量 $\mathbf{a}' = [3,2]$ 和 $\mathbf{b}' = [1, 4]$ 来打开。

为了创建一个关于内积知识的安全证明，证明者还必须计算并发送关于 $\mathbf{a}$ 和 $\mathbf{b}$ 的承诺。

朴素的解决方案是运行承诺算法两次。前两次是为了证明 $\mathbf{a}$ 和 $\mathbf{b}$ 被正确承诺为 $P_1 = \langle\mathbf{a},\mathbf{G}\rangle$ 和 $P_2 =\langle\mathbf{b},\mathbf{H}\rangle$，第三次则是为了展示 $\langle\mathbf{a},\mathbf{b}\rangle Q=P_3$ 被正确计算。在下一节中，我们将展示当两个向量都是域元素时，如何修改我们的算法来计算内积。

将标量内积转换为标量-点内积

设 $\mathbf{Q}^n$ 为由 $n$ 个点 $Q$ 的副本组成的向量，即

因此，

请注意，$\langle\mathbf{a},\mathbf{b}\rangle Q$ 等于 $\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}^n\rangle$。

也就是说，我们可以将 $\mathbf{b}$ 的每个元素都乘以 $Q$，然后将该向量与 $\mathbf{a}$ 取内积，结果将与 $\langle\mathbf{a},\mathbf{b}\rangle Q$ 相同。例如，如果 $\mathbf{a} = [1,2]$ 且 $\mathbf{b} = [3,4]$，则 $\langle[1,2],[3,4]\rangle Q=(1\cdot 3+2\cdot 4)Q= \langle[1,2],[3Q,4Q]\rangle=1\cdot 3Q+2\cdot 4Q=11Q$。

由此，我们可以证明以下内容：

1. $P_1 =\langle\mathbf{a},\mathbf{G}\rangle$
2. $P_2 =\langle\mathbf{b},\mathbf{H}\rangle$
3. $P_3 =\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}\rangle$

用一个证明代替三个证明

我们可以做得更好，而无需发送三个承诺并运行该算法三次。

由于 $\mathbf{G}$、$\mathbf{H}$ 和 $Q$ 中的点具有未知的离散对数关系，因此它们可以被组合成一个单一的承诺 $P = \langle\mathbf{a},\mathbf{G}\rangle +\langle\mathbf{b},\mathbf{H}\rangle + \langle\mathbf{a},\mathbf{b}\rangle Q = P_1 + P_2 + P_3$。

我们稍微对承诺 $P = \langle\mathbf{a},\mathbf{G}\rangle +\langle\mathbf{b},\mathbf{H}\rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$ 进行重新排列，写成 $P = \langle\mathbf{a},\mathbf{G}\rangle+\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}^n\rangle +\langle\mathbf{b},\mathbf{H}\rangle$，以使下一个技巧更加明显。

为了一次性证明整个承诺（而不是证明三个内积），请观察：

其中 $\oplus$ 表示向量拼接。

实际上，我们正在证明我们将向量 $\mathbf{a}\oplus\mathbf{a}\oplus\mathbf{b}$ 承诺给了椭圆曲线向量基 $\mathbf{G}\oplus\mathbf{Q}^n\oplus\mathbf{H}$。

在实际操作中，我们并不会真正拼接这些向量，因为总长度通常不会是 2 的幂。相反，我们分别计算 $\mathbf{G}$、$\mathbf{H}$ 和 $\mathbf{b}\circ\mathbf{Q}^n$ 组分，但计算 $L$ 和 $R$ 时则如同它们被拼接在一起一样。

我们在下方的动画中展示了该算法：

算法

给定 $v = \langle\mathbf{a},\mathbf{b}\rangle$ 以及承诺 $P = vQ+\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle$，我们希望证明 $P$ 是如我们所声明的那样被承诺的。即 $v$、$\mathbf{a}$ 和 $\mathbf{b}$ 被承诺于 $P$，且 $\langle\mathbf{a},\mathbf{b}\rangle=v$。

\texttt{prove_commitments_log}(P, \mathbf{G}, \mathbf{H},Q, |\mathbf{a}, \mathbf{b})

情况 1：$n = 1$

1. 证明者发送 $(a,b)$，验证者检查 $P \stackrel{?}= aG + bH + abQ$。算法结束。

情况 2：$n > 1$

1. 证明者计算并向验证者发送 $(L, R)$，它们实际上就是所有向量拼接在一起后的非对角线项（参见上方动画）：
   
   $$\begin{align*} L &= (a_1b_2 + a_3b_4 + \dots a_{n-1}b_n)Q+(a_1G_2 + a_3G_4 + \dots a_{n-1}G_n)+(b_2H_1 + b_4H_3 + \dots b_nH_{n-1})\\ R &= (a_2b_1 + a_4b_3 + \dots a_nb_{n-1})Q+(a_2G_1 + a_4G_3 + \dots a_nG_{n-1})+(b_1H_2 + b_3H_4 + \dots b_{n-1}H_n) \end{align*}$$
2. 验证者发送随机数 $u$。
3. 证明者和验证者双方共同计算：
   
   $$\begin{align*} P' &= Lu^2+P+Ru^{-2}\\ \mathbf{G}'&=\mathsf{fold}(\mathbf{G}, u^{-1})\\ \mathbf{H}'&=\mathsf{fold}(\mathbf{H}, u)\\\\ \end{align*}$$
4. 证明者计算：
   
   $$\begin{align*} \mathbf{a}'&=\mathsf{fold}(\mathbf{a},u)\\ \mathbf{b}'&=\mathsf{fold}(\mathbf{b},u^{-1}) \end{align*}$$
5. \texttt{prove_commitments_log}(P', G', H', \mathbf{a}', \mathbf{b}')

以下练习可以在我们的 ZK Bulletproofs GitHub Repo 中找到：

练习 1： 填写下方缺失的代码，以实现证明 $\mathbf{a}$ 被承诺到 $\mathbf{G}$ 以生成点 $P$ 的算法：

Copy
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_vec = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

# return a folded vector of length n/2 for scalars
def fold(scalar_vec, u):
    pass

# return a folded vector of length n/2 for points
def fold_points(point_vec, u):
    pass

# return (L, R)
def compute_secondary_diagonal(G_vec, a):
    pass

a = [4,2,42,420]

P = vector_commit(G_vec, a)

L1, R1 = compute_secondary_diagonal(G_vec, a)
u1 = random_element()
aprime = fold(a, u1)
Gprime = fold_points(G_vec, pow(u1, -1, p))

L2, R2 = compute_secondary_diagonal(Gprime, aprime)
u2 = random_element()
aprimeprime = fold(aprime, u2)
Gprimeprime = fold_points(Gprime, pow(u2, -1, p))

assert len(Gprimeprime) == 1 and len(aprimeprime) == 1, "final vector must be len 1"
assert eq(vector_commit(Gprimeprime, aprimeprime), add_points(multiply(L2, pow(u2, 2, p)), multiply(L1, pow(u1, 2, p)), P, multiply(R1, pow(u1, -2, p)), multiply(R2, pow(u2, -2, p)))), "invalid proof"

练习 2： 修改上方代码以实现该算法，证明 $P$ 包含了对 $\mathbf{a}$、$\mathbf{b}$ 和 $v$ 的承诺，且 $\langle\mathbf{a},\mathbf{b}\rangle=v$。对 $\mathbf{H}$ 和椭圆曲线点 $Q$ 使用以下基向量：

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

Q = (FQ(11573005146564785208103371178835230411907837176583832948426162169859927052980), FQ(895714868375763218941449355207566659176623507506487912740163487331762446439))

本教程是关于 Bulletproof ZKP 系列的一部分。