如果我们有一个包含对向量 $\mathbf{a}$ 的承诺的 Pedersen vector commitment $A$（即 $A = a_1G_1 + a_2G_2+\dots + a_nG_n$），我们可以通过将 $\mathbf{a}$ 发送给验证者来证明我们知道该承诺的打开（opening），验证者将检查 $A \stackrel{?}= a_1G_1 + \dots + a_nG_n$。这需要向验证者发送 $n$ 个元素（假设 $\mathbf{a}$ 的长度为 $n$）。

在上一章中，我们展示了如何在零知识的情况下做到这一点。在本章中，我们将展示如何通过发送少于 $n$ 个元素来证明对承诺打开的知识，但不具备零知识属性。

动机

我们在此开发的技术将成为一个重要的基础模块，用于证明内积的有效计算，其证明大小为 $\log n$，其中 $n$ 是向量的长度。

在上一章中，我们展示了如何证明我们正确执行了内积计算，而无需泄露向量或结果。然而，由于证明者发送 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的步骤，该证明的大小为 $\mathcal{O}(n)$。

本文中的子程序对于减小证明的大小将非常重要。本文不涉及零知识，因为之前讨论的算法本身就具备零知识属性。也就是说，$\mathbf{l}_u$ 和 $\mathbf{r}_u$ 一开始并不是秘密，因此没有必要对它们进行混淆。

问题陈述

给定一个商定的基向量 $\mathbf{G}=[G_1,\dots,G_n]$，证明者向验证者提供一个 Pedersen 向量承诺 $A$，其中 $A$ 是对 $\mathbf{a}$ 的非盲化（non-blinding）承诺，即 $A = \langle[a_1,\dots,a_n],[G_1,\dots,G_n]\rangle$，并希望在发送少于 $n$ 个项（即不发送整个向量 $[a_1,\dots,a_n]$）的情况下，证明他们知道该承诺的打开。

小于 $n$ 的证明

缩小证明大小依赖于三个洞见：

洞见 1：内积 $\langle \mathbf{a},\mathbf{b}\rangle$ 是外积的对角线

我们要利用的第一个洞见是，内积是外积的对角线。换句话说，从某种意义上说，外积“包含”了内积。在一维向量的语境中，外积是一个二维矩阵，由第一个一维向量中的每个元素与第二个向量中的每个元素相乘形成。例如：

这似乎是朝着错误方向迈出的一步，因为外积需要 $\mathcal{O}(n^2)$ 个步骤来计算。然而，接下来的洞见表明，可以在 $\mathcal{O}(1)$ 的时间里间接地计算外积。

洞见 2：外积的和等于原向量和的乘积

第二个观察结果是，外积各项的和等于各个向量和的乘积。也就是说，

对于我们向量 $[a_1,a_2]$ 和 $[b_1,b_2]$ 的例子，这等同于：

在图形上，这可以直观地理解为一个尺寸为 $(a_1 + a_2) \times (b_1 + b_2)$ 的矩形的面积，与 $a_1 \times b_1 + a_1 \times b_2 + a_2 \times b_1 + a_2 \times b_2$ 的“面积”相同：

在我们的例子中，$\mathbf{b}$ 向量实际上是椭圆曲线点的基向量，所以我们的意思是：

请注意，我们最初的 Pedersen 承诺

被嵌入到了外积中带框的项里：

因此，通过将向量各项的和相乘，我们也计算了外积的和。

既然内积是外积的对角线，我们就通过将向量各项的和相乘，间接地计算了内积。为了证明我们知道内积，我们需要证明我们同样知道外积中不属于内积的那些项。

对于长度为 $2$ 的向量，我们将外积中不属于内积的部分称为非对角乘积（off-diagonal product）。

在下方，我们用 $\square$ 标记构成非对角乘积的项，用 $\blacksquare$ 标记构成内积的项：

我们现在可以正式声明我们在后续将要依赖的恒等式。如果 $n=2$，那么：

如果其中一个向量是椭圆曲线点的向量（即使它们的离散对数是未知的），这个恒等式同样成立。

对于 $n > 2$ 的情况，证明内积的知识意味着证明者需要使验证者相信他们知道下方紫色阴影区域的“面积”。

在 $n > 2$ 时简洁地传达这一信息比较棘手，因此我们稍后会再来讨论。

在 $n = 2$ 的情况下，该面积仅仅就是那些非对角元素。

洞见 3：如果 $n = 1$，那么内积等于外积

一个重要的边缘情况是当我们有一个长度为 $1$ 的向量时。在这种情况下，证明者只需将 $\mathbf{a}$（其长度为 $1$）发送给验证者，验证者只需将 $\mathbf{a}$ 的唯一元素与 $\mathbf{G}$ 的唯一元素相乘即可。

算法草图

现在，我们可以为 $n=2$ 的情况制定算法的初稿，该算法能够证明我们已经计算了 $\mathbf{a}$ 和 $\mathbf{G}$ 的内积，这等同于展示我们知道承诺 $A$。

证明者与验证者之间的交互如下：

1. 证明者将其承诺 $A = a_1G_1 + a_2G_2$ 发送给验证者。
2. 证明者将 $\mathbf{a}$ 中的所有项相加，并作为 $a' = a_1 + a_2$ 发送给验证者（请注意，向量各分量的和是一个标量，因此对 $\mathbf{a}$ 的元素求和会得到标量 $a'$）。此外，证明者计算 $\mathbf{a} \otimes \mathbf{G}$ 的非对角项（即 $R = a_2G_1$，$L = a_1G_2$），并将 $L$ 和 $R$ 发送给验证者。

在图形上，$L$ 和 $R$ 可以表示如下：

3. 验证者通过计算 $a'G'$（其中 $G' = G_1 + G_2$）间接计算出 $\mathbf{a} \otimes \mathbf{G}$，并检查：

展开形式下，上述方程为：

请注意，上述检查等价于早前给出的恒等式：

安全漏洞：多重打开（multiple openings）

然而，存在一个安全问题——证明者可以为同一个承诺找到多个证明。例如，证明者可以随机选择 $L$，然后计算

为了防止这种情况，我们重新借用在讨论零知识乘法时一个类似的想法——证明者必须在其计算中包含验证者提供的随机数 $u$。他们还必须在获得 $u$ 之前 发送 $L$ 和 $R$，这样就无法“投机地”选择 $L$ 和 $R$。

证明者之所以必须单独发送 $L$ 和 $R$，而不是发送总和 $L + R$，是因为证明者能够通过在 $L$ 和 $R$ 之间无限制地转移数值来破坏协议。也就是说，由于

证明者可以选择某个椭圆曲线点 $S$，并由此计算出伪造的 $L'$ 和 $R'$：

我们需要强制证明者保持 $L$ 和 $R$ 分离。

这是修正此漏洞后的更新算法：

1. 证明者和验证者商定一个基向量 $[G_1, G_2]$，其中的点是随机选择的，并且它们的离散对数是未知的。

2. 证明者计算并向验证者发送 $(A, L, R)$：
   

   $$\begin{align*} A &= a_1G_1 + a_2G_2 && \text{// 我们要证明其知识的向量承诺}\\ L &= a_1G_2 && \text{// 左侧对角项}\\ R &= a_2G_1 && \text{// 右侧对角项}\\ \end{align*}$$

3. 验证者回复一个随机标量 $u$。

4. 证明者计算并发送 $a'$：

5. 验证者现在拥有了 $(A, L, R, a', u)$，接着检查：
   
   $$L + u A + u^2R \stackrel{?}= a'(u G_1 + G_2)$$

其背后的底层展开是：

如果证明者正确计算了 $a'$、$L$ 和 $R$，这个等式是恒等成立的。

请注意，验证者将 $u$ 作用于 $G_2$，而证明者将 $u$ 作用于 $a_1$。这导致原始内积的各项成为结果多项式的一次（线性）系数。

由于 $L$ 和 $R$ 之间被由验证者控制的 $u^2$ 分隔开，这防止了恶意证明者执行前面描述的攻击。也就是说，证明者不能将数值从 $R$ 转移到 $L$，因为转移的数值必然会被 $u^2$ 缩放，而证明者又必须在收到 $u$ 之前就发送 $L$ 和 $R$。

算法的另一种解释：将 $n$ 的维度减半

验证者只进行了一次乘法，即 $a'$ 乘以 $(uG_1 + G_2)$。即使我们从长度为 $2$ 的向量开始，验证者也只需执行 $n/2=1$ 次点乘。

$a_1 + a_2u$ 的操作将长度为 $2$ 的向量 $\mathbf{a}$ 变成了长度为 $1$ 的向量。因此，在给定证明者的向量和验证者的随机数 $u$ 的情况下，证明者和验证者双方正在共同构造一个新的长度为 $1$ 的向量。

因为他们都已将原始向量压缩为一个长度为 $1$ 的向量，所以验证者可以在 $n = 1$ 的情况下使用恒等式 $\langle\mathbf{a}',\mathbf{G}'\rangle=\mathbf{a}'\otimes\mathbf{G}'$。在此，$\mathbf{a}' = a_1 + a_2u$ 且 $\mathbf{G'} = G_1u + G_2$。

算法的安全性

算法总结

作为对该算法的快速总结，

1. 证明者向验证者发送 $(A, L, R)$。
2. 验证者回复 $u$。
3. 证明者计算并发送 $a'$。
4. 验证者检查：

现在让我们看看为什么证明者无法作弊。

在步骤 3 中，证明者拥有的唯一“自由度”是 $a'$。

要想给出一个满足

的 $a'$，证明者需要知道 $G_1$ 和 $G_2$ 的离散对数。具体而言，他们必须解出

其中

• $l$ 和 $r$ 分别是 $L$ 和 $R$ 的离散对数
• $g_1$ 和 $g_2$ 分别是 $G_1$ 和 $G_2$ 的离散对数，$a$ 是 $A$ 的离散对数。
• $l$ 和 $r$ 是证明者已知的，因为证明者在步骤 1 中生成了 $L$ 和 $R$。

然而，证明者并不知道离散对数 $g_1$ 和 $g_2$，因此他们无法计算出 $a'$。

变量 $a'$ 只有两个有效解

对于满足 $L + uA + u^2R = a'(uG_1 + G_2)$ 的 $a'$，只有两个有效值。请注意，方程左侧的 $L + uA + u^2R$ 构成了一个关于变量 $u$ 的二次多项式，而右侧的 $a'(uG_1+G_2)$ 构成了一个一次多项式。根据 Schwartz-Zippel Lemma（Schwartz-Zippel 引理），该方程最多有两个解。只要域的阶（order） $\gg 2$，那么证明者恰好找到能够使 $L + uA + u^2R = a'(uG_1 + G_2)$ 相交于一点的 $a'$ 的概率就可以忽略不计。

Bulletproofs 论文中注入随机数的方法

在 Bulletproofs 论文中，证明者并不是将 $a_1$ 和 $a_2$ 组合为 $a_1 + a_2u$，而是将它们组合成 $a' = a_1u + a_2u^{-1}$，验证者则计算 $G' = u^{-1}G_1 + u G_2$。请注意，这两个向量的幂次是按相反顺序应用的。当我们计算外积时，内积项中的 $uu^{-1}$ 将相互抵消：

可以说，这种方法“更干净”，所以我们将在后续采用这种方法。

引入 $\mathsf{fold}(\mathbf{a},x)$

$a_1x + a_2x^{-1}$ 这种计算在 Bulletproofs 中非常频繁，因此给它起个名字会很方便，我们称之为 $\mathsf{fold}(\mathbf{a},x)$。第一个参数 $\mathbf{a}$ 是我们正在折叠的向量（其长度必须为偶数，如果不是，我们用 $0$ 进行填充）。Fold 操作将长度为 $n$ 的向量 $\mathbf{a}$ 分割为 $n/2$ 对，并返回如下长度为 $n/2$ 的向量：

如果我们执行 $\mathsf{fold}(\mathbf{a},x^{-1})$，我们的意思是：

当 $n=2$ 时，$\mathsf{fold}(\mathbf{a},x)$ 仅仅是 $a_1x+a_2x^{-1}$，而 $\mathsf{fold}(\mathbf{a},x^{-1})=a_1x^{-1}+a_2x$。

带有 $\mathsf{fold}$ 的算法描述

我们现在使用 Bulletproofs 论文中处理随机数的方法重新陈述该算法：

1. 证明者向验证者发送他们对 $\mathbf{a}$ 的承诺 $A = a_1G_1 + a_2G_2$，以及计算得到的 $L$ 和 $R$：
   
   $$\begin{align*} L &= a_1G_2 \\ R &= a_2G_1 \\ \end{align*}$$
2. 验证者回复一个随机标量 $u$。
3. 证明者计算并发送 $a'$：
   
   $$a' = \mathsf{fold}(\mathbf{a},u) = a_1u + a_2u^{-1}$$
4. 验证者计算：
   
   $$\begin{align*} P &= a'\cdot\mathsf{fold}(\mathbf{G},u^{-1})= a'\cdot(u^{-1} G_1 + uG_2)\\ P &\stackrel{?} = Lu^2 + A + u^{-2}R \end{align*}$$

假设证明者是诚实的，最后的检查底层可展开为：

如何处理 $n > 2$ 的情况

假设数组 $\mathbf{a}$ 具有偶数长度（如果不是，我们可以添加一个零元素使其长度变为偶数），我们可以对该数组进行成对划分（pairwise-partition）。下面是一个成对划分的示例：

类似地，我们也可以对 $\mathbf{G}$ 进行成对划分。

然后，每个子对都可以视为计算内积的一个实例，直接使用前面讲过的 $n=2$ 情况：

接着，我们可以证明我们知道这四个 $n=2$ 承诺 $a_1G_1 + a_2G_2$、$a_3G_3 + a_4G_4$、$a_5G_5 + a_6G_6$ 和 $a_7G_7 + a_8G_8$，这就等价于证明我们知道原承诺的打开。

然而，这会为我们所证明的每个对额外产生四组 $(L, R)$ 项——也就是说，在证明者传输的数据大小方面没有任何效率提升。

一种朴素的解决方案是证明者承诺并发送：

在图形上，这可以表示如下：

作为一个（关键的！）优化，我们将每一对中的所有 $A_i$、$L_i$ 和 $R_i$ 项相加，变成单独的点 $A$、$L$ 和 $R$。换言之，证明者只需发送：

上述操作如下方动画所示：

将所有承诺和非对角项加在一起的安全性

对于这种优化，最初的担忧是：由于证明者将更多的项加在了一起，就有了更多的机会来隐藏不诚实的计算。

现在我们来证明：一旦证明者发送了 $A$（以及 $L$ 和 $R$），他们就只能创建出唯一的证明来表明自己知道 $A$ 的打开。

观察到 $L$ 的计算方式为 $L = a_1G_2 + a_3G_4 +a_5G_6+a_7G_8$，$R$ 的计算方式为 $R = a_2G_1 + a_4G_3 +a_6G_5+a_8G_7$。它们不包含任何共同的椭圆曲线点。因此，证明者无法将数值从 $L$ “转移” 到 $R$，因为他们不知道任何这些点的离散对数。实际上，$L$ 是向基向量 $[G_1, G_3, G_5, G_7]$ 作出的关于 $[a_2, a_4, a_6, a_8]$ 的 Pedersen 向量承诺。Pedersen 向量承诺的安全假设是证明者只能生成一种可能的向量打开。在发送承诺后还要“转移数值”，将意味着证明者能够计算出与 $[a_2, a_4, a_6, a_8]$ 不同的另一个向量，且产生相同的承诺。但这违背了我们的假设，即对于一个 Pedersen 承诺，证明者只能产生唯一一个有效的向量。对于 $R$ 也可以进行类似的论证。

$A$ 是四个 Pedersen 承诺（分别对向量 $[a_1, a_2]$、$[a_3, a_4]$、$[a_5, a_6]$、$[a_7, a_8]$ 的承诺）的和。然而，从安全性的角度来看，多个 Pedersen 承诺相加这一事实是无关紧要的。无论这些承诺是单独计算再相加，还是直接将 $A$ 作为 $n = 8$ 的向量进行计算，并没有任何区别。请考虑：

例如，证明者可能会将数值从 $a_1G_1$ “转移”到 $a_2G_1$。

剩下的唯一担忧是，证明者可能会将数值从 $A$ 中的 $a_1G_1$ 转移到 $L$ 中的 $a_2G_1$，因为它们共享同一个椭圆曲线点。然而，如前所述，这会被来自验证者的随机数 $u$ 所阻止。

因此，一旦证明者发送了以本节所描述方式计算的 $(A, L, R)$，他们就只能创建一种可能的打开，从而也就只能创建出一种可能的证明。

证明我们知道 $A$ 的打开，同时只发送 $n/2$ 的数据

1. 证明者向验证者发送 $A = \langle\mathbf{a},\mathbf{G}\rangle$。证明者还发送 $L = a_1G_2 + a_3G_4 + ... a_{n-1}G_n$ 和 $R = a_2G_1 + a_4G_3 + ... + a_nG_{n-1}$。
2. 验证者发送一个随机数 $u$。
3. 证明者计算 $\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)$ 并将 $\mathbf{a}'$ 发送给验证者。
4. 验证者检查 $Lu^2 + A + Ru^{-2} \stackrel{?}=\langle\mathbf{a}',\mathsf{fold}(\mathbf{G},u^{-1})\rangle$。

我们将其作为一个练习留给读者：推导一个例子来检验在证明者诚实的情况下，最终的验证检查在代数上是否等价。我们建议使用一个小的例子，例如 $n=4$。

对 $\mathsf{fold}$ 的另一种解释

$P$ 是原始向量 $\mathbf{a}$ 关于基向量 $\mathbf{G}$ 的承诺。$L$ 是成对外积中由左侧非对角线分量组成的向量承诺，$R$ 是成对外积中由右侧非对角线分量组成的向量承诺。

总和 $Lu^2 + P + Ru^{-2}$ 本身就是向量 $\mathsf{fold}(\mathbf{a},u)$ 相对基底 $\mathsf{fold}(\mathbf{G}, u^{-1})$ 的向量承诺，其大小为 $n/2$。

我们在下面以图形方式展示这一关系：

要证明我们知道一个大小为 $n/2$ 的承诺的打开，我们只需发送该大小为 $n/2$ 的向量即可，在本例中为 $\mathsf{fold}(\mathbf{a},u)$。

使用这种解释，该算法正在执行以下操作：

1. 证明者发送 $A = \langle\mathbf{a},\mathbf{G}\rangle$、$L$ 和 $R$。
2. 验证者发送 $u$。
3. 现在验证者拥有了一个相对基向量 $\mathsf{fold}(\mathbf{G},u^{-1})$ 的承诺 $A' = Lu^2 + A + Ru^{-2}$。
4. 证明者通过发送 $\mathbf{a}' =\mathsf{fold}(\mathbf{a}, u)$ 来证明他们知道 $A'$ 的打开。

验证速度的限制

因为验证者需要计算 $\mathsf{fold}(\mathbf{G}, u^{-1})$，这将要求遍历整个 $\mathbf{G}$ 向量，这将花费 $\mathcal{O}(n)$ 的时间。尽管证明大小可以小于原始向量，但验证该证明仍将花费线性时间。

总结

我们展示了证明者如何能够在仅发送 $n/2$ 个元素（折叠后的 $\mathbf{a}$）的情况下，展示他们知道 Pedersen 向量承诺 $A$ 的打开。

在下一章中，我们将展示如何递归地应用这个算法，从而使证明者仅需发送 $\mathcal{O}(\log n)$ 个元素。

练习： 实现本章描述的算法。使用以下代码作为起点：

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
    # your code here

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

# return L, R as a tuple
def compute_secondary_diagonal(G_vec, a):
    pass
    # your code here

a = [9,45,23,42]

# prover commits
A = vector_commit(G_vec, a)
L, R = compute_secondary_diagonal(G_vec, a)

# verifier computes randomness
u = random_element()

# prover computes fold(a)
aprime = fold(a, u)

# verifier computes fold(G)
Gprime = fold_points(G_vec, pow(u, -1, p))

# verification check
assert eq(vector_commit(Gprime, aprime), add_points(multiply(L, pow(u, 2, p)), A, multiply(R, pow(u, -2, p)))), "invalid proof"
assert len(Gprime) == len(a) // 2 and len(aprime) == len(a) // 2, "proof must be size n/2"