向量承诺的简洁证明

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

在上一章中，我们展示了如何做到这一点而不泄露任何信息。本章中，我们展示了如何在发送少于 $n$ 个元素的情况下证明我们知道开启，但没有零知识属性。

动机

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

在上一章中，我们展示了如何证明我们正确执行内积，但不揭示向量或结果。但是，证明的大小是 $\mathcal{O}(n)$，因为证明者发送 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的步骤。

本文中的子例程将在减少证明大小方面发挥重要作用。本文章不是关注零知识，因为前面讨论的算法具有零知识属性。也就是说，$\mathbf{l}_u$ 和 $\mathbf{r}_u$ 本身并不保密，因此无须对其进行模糊化。

问题陈述

给定一个商定的基向量 $\mathbf{G}=[G_1,\dots,G_n]$，证明者向验证者提供一个 Pedersen 向量承诺 $A$，其中 $A$ 是对 $\mathbf{a}$ 的非盲承诺，即 $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$ 是外积的对角线

我们将利用的第一个见解是内积是 外积 的对角线。换句话说，外积“包含”内积。在一维向量的上下文中，外积是通过将第一个一维向量中的每个元素与第二个向量中的每个其他元素相乘而形成的二维矩阵。例如：

$$ \begin{align} \mathbf{a}=[a_1, a_2],\space \mathbf{b}=[b_1, b_2], \end{align} \space\space \mathbf{a} \otimes \mathbf{b} = \begin{pmatrix} \boxed{a_1 b_1} & a_1 b_2 \ a_2 b_1 & \boxed{a_2 b_2} \ \end{pmatrix} $$

这可能看起来像是朝错误的方向，因为外积需要 $\mathcal{O}(n^2)$ 的步骤来计算。然而，以下见解表明，有可能在 $\mathcal{O}(1)$ 的时间内间接计算外积。

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

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

$$ \sum_{i=1}^{n} ai\sum{i=1}^{n} b_i=\sum\mathbf{a} \otimes \mathbf{b} $$

对于我们向量 $[a_1,a_2]$ 和 $[b_1,b_2]$ 的例子，这将成为

$$ \underbrace{(a_1 + a_2)(b_1 + b2)}{\sum a_i\sum b_i} = \underbrace{a_1b_1 + a_1b_2 + a_2b_1 + a_2b2}{\sum\mathbf{a} \otimes \mathbf{b}} $$

从图形上看，这可以想象成矩形的面积，边长为 $(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$ 的“面积”相同。

$$ \begin{array}{|c|cc|} \hline &a_1+a_2\ \hline b_1&a_1b_1 + a_1b_2\ +b_2& + a_2b_1 + a_2b_2\ \hline \end{array}= \begin{array}{|c|c|c|} \hline &a_1&a_2\ \hline b_1&a_1b_1&a_2b_1\ \hline b_2&a_1b_2&a_2b_2\ \hline \end{array} $$

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

$$ (a_1 + a_2)(G_1 + G_2) = a_1G_1 + a_1G_2 + a_2G_1 + a_2G_2 $$

注意我们的原始 Pedersen 承诺

$$ A = \langle[a_1,a_2],[G_1,G_2]\rangle = a_1G_1 + a_2G_2 $$

嵌入了外积的盒装项中：

$$ (a_1 + a_2)(G_1 + G_2) = \boxed{a_1G_1} + a_1G_2 + a_2G_1 + \boxed{a_2G_2} $$

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

由于内积是外积的对角线，因而我们已经 间接地 通过将向量项的和相乘来计算内积。为了证明我们知道内积，我们需要证明我们也知道外积中不属于内积的项。

对于长度为 2 的向量，我们可以将外积中不属于内积的部分称为 非对角线乘积。

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

$$ \begin{array}{|c|c|c|} \hline &a_1&a_2\ \hline b_1&\blacksquare&\square\ \hline b_2&\square&\blacksquare\ \hline \end{array} $$

我们现在可以正式陈述我们将依赖的关系。如果 $n=2$，则有： $$\sum\mathbf{a}\otimes\mathbf{b}=\langle\mathbf{a},\mathbf{b}\rangle+\mathsf{off\_diagonal}(\mathbf{a},\mathbf{b})$$

如果其中一个向量是椭圆曲线点的向量（即使它们的离散对数未知），该关系也成立。

对于 $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$ 可以如下所示：

$$ \begin{array}{|c|c|c|} \hline &a_1&a_2\ \hline G_1&&R\ \hline G_2&L&\ \hline \end{array} $$

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

$$\underbrace{a’G’}\text{外积和} = \underbrace{A}\text{内积} + \underbrace{L + R}_\text{非对角线项}$$

在展开形式中，上述等式为： $$\underbrace{(a_1 + a_2)(G_1 + G2)}\text{外积} = \underbrace{a_1G_1 + a_2G2}\text{内积} + \underbrace{a_1G_2 + a_2G1}\text{非对角线项}$$

请注意，上述检查等价于之前的关系：

$$\sum\mathbf{a}\otimes\mathbf{G}=\langle\mathbf{a},\mathbf{G}\rangle+\mathsf{off\_diagonal}(\mathbf{a},\mathbf{G})$$

安全漏洞：多个开启

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

$$ R = a’G’ – L $$

为了防止这种情况，我们重用了我们讨论零知识乘法的类似思想——证明者必须在计算中包含验证者提供的随机性 $u$。他们还必须在获取 $u$ 之前 提前 发送 $L$ 和 $R$，以便 $L$ 和 $R$ 无法被“有利地”选择。

证明者必须单独发送 $L$ 和 $R$ 而非发送它们的总和 $L + R$ 的原因是，因为证明者能够在没有限制的情况下在 $L$ 和 $R$ 之间移动值。换句话说，因为

$$L + R = a’G’$$

证明者可以选择某个椭圆曲线点 $S$，并计算出虚假的 $L’$ 和 $R’$ 为

$$\underbrace{(L + S)}{L’} + \underbrace{(R – S)}{R’} = a’G’$$

我们需要强制证明者将 $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’$：

$$a’ = a_1 + a_2u$$

5. 现在持有 $(A, L, R, a’, u)$ 的验证者检查：

$$ L + u A + u^2R \stackrel{?}= a'(u G_1 + G_2) $$

从底层来看，这被写为： $$ \underbrace{a_1G_2}_L + \underbrace{u(a_1G_1 + a_2G2)}{uA} + \underbrace{a_2u G1}{u^2R} = \underbrace{(a_1 + u a2)}{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 的向量。因此，证明者和验证者共同构建了一个长度为 1 的新向量，该向量是给定证明者的向量和验证者的随机性 $u$ 的结果。

由于他们都将原始向量压缩为长度为 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. 验证者检查：

$$L + uA + u^2R \stackrel{?}= a'(uG_1 + G_2)$$

现在让我们看看证明者为什么不能作弊。

证明者在第 3 步的唯一“自由度”是 $a’$。

为了得出满足

$$L + uA + u^2R = a'(uG_1 + G_2)$$

的 $a’$，证明者需要知道 $G_1$ 和 $G_2$ 的离散对数。具体地，他们必须解决

$$a’=\frac{l + ua + u^2r}{ug_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 引理，该方程至多具有两个解。只要域的阶数 $\gg 2$，那么找出 $a’$ 使其成为方程 $L + uA + u^2R = a'(uG_1 + G_2)$ 的交点的概率是微乎其微的。

Bulletproofs 论文对注入随机性的处理

证明者不将 $a_1$ 和 $a_2$ 组合为 $a_1 + a_2u$，而是将它们组合为 $a’ = a_1u + a_2u^{-1}$，验证者则计算 $G’ = u^{-1}G_1 + uG_2$。请注意，两个向量的幂以相反的顺序应用。当我们计算外积时，内积项将具有 $uu^{-1}$ 取消： $$ [a_1u, u^{-1}a_2] \otimes [u^{-1}G_1, uG_2]= \begin{array}{|c| c c|} \hline & ua_1 & u^{-1}a_2 \ \hline G_1u^{-1} & \color{green}{a_1G_1} & a_1G_2u^2 \ G_2u & a_2G_1u^{-2} & \color{green}{a_2G_2} \ \hline \end{array} $$

可以说，这种方法在某种意义上更“干净”，因此我们将继续使用它。

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

在 Bulletproofs 中，计算 $a_1x + a_2x^{-1}$ 的过程如此常见，以至于付出了一个名字，我们称之为 $\mathsf{fold}(\mathbf{a},x)$。第一个参数 $\mathbf{a}$ 是我们要折叠的向量（必须是偶数长度，如果不是，我们用 $0$ 来填充它）。Fold 将长度为 $n$ 的向量 $\mathbf{a}$ 拆分为 $n/2$ 对，并返回长度为 $n/2$ 的向量，形式为：

$$\mathsf{fold}(\mathbf{a}, x)=[a_1x+a_2x^{-1},a_3x+a4x^{-1},\dots,a{n-1}x+a_nx^{-1}]$$

如果我们做 $\mathsf{fold}(\mathbf{a},x^{-1})$，那么意味着：

$$\mathsf{fold}(\mathbf{a}, x^{-1})=[a_1x^{-1}+a_2x,a_3x^{-1}+a4x,\dots,a{n-1}x^{-1}+a_nx]$$

当 $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} $$

假设证明者是诚实的，则最终的检查在底层扩展为：

$$ \begin{align} (a_1G_2)u^2 + (a_1G_1 + a_2G_2) + u^{-2}(a_2G_1) &= (a_1u + a_2u^{-1})(u^{-1} G_1 + uG_2)\ (a_1G_2)u^2 + (a_1G_1 + a_2G_2) + u^{-2}(a_2G_1) &=a_1G_1+a_1u^2G_2+a_2u^{-2}G_1+a_2G_2\ a_1u^2G_2 + a_1G_1 + a_2G_2 + a_2u^{-2}G_1 &=a_1G_1+a_1u^2G_2+a_2u^{-2}G_1+a_2G_2\ a_1G_1 + a_1u^2G_2 + a_2u^{-2}G_1 + a_2G_2 &=a_1G_1+a_1u^2G_2+a_2u^{-2}G_1+a_2G_2\ \end{align} $$

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

假设数组 $\mathbf{a}$ 的长度为偶数（如果不是，我们可以添加零元素使其为偶数长度），我们可以成对分割数组。以下是成对分割的示例：

$$\mathbf{a} = [a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8]=[a_1, a_2] [a_3, a_4] [a_5, a_6] [a_7, a_8]$$

同样，我们可以成对分割 $\mathbf{G}$。

$$\mathbf{G} = [G_1, G_2, G_3, G_4, G_5, G_6, G_7, G_8]=[G_1, G_2] [G_3, G_4] [G_5, G_6] [G_7, G_8]$$

然后，每对子项可以被视为使用之前的 $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)$ 项，即在证明者发送的数据大小上没有效率提升。

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

$$ \begin{align} A_1 &= a_1G_1+a_2G_2\ A_2 &= a_3G_3+a_4G_4\ A_3 &= a_5G_5+a_6G_6\ A_4 &= a_7G_7+a_8G_8\ L_1 &= a_1G_2\ R_1 &= a_2G_1\ L_2 &= a_3G_4\ R_2 &= a_4G_3\ L_3 &= a_5G_6\ R_3 &= a_6G_5\ L_4 &= a_7G_8\ R_4 &= a_8G_7\ \end{align} $$

在图形上，可以如下所示：

$$ \begin{array}{c|c|} &a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8\ \hline G_1&&R_1\ \hline G_2&L_1\ \hline G_3&&&&R_2\ \hline G_4&&&L_2\ \hline G_5&&&&&&R_3\ \hline G_6&&&&&L_3\ \hline G_7&&&&&&&&R_4\ \hline G_8&&&&&&&L_4\ \hline \end{array} $$

作为（关键的！）优化，我们将所有的 $A_i$、$L_i$ 和 $R_i$ 项相加，使之成为单个点 $A$、$L$、$R$。换句话说，证明者仅发送：

$$ \begin{align} A &= A_1 + A_2 + A_3 + A_4\ L &= L_1 + L_2 + L_3 + L_4\ R &= R_1 + R_2 + R_3 + R_4\ \end{align} $$

上述操作如动画所示： https://img.learnblockchain.cn/2025/mp4/outerproduct-anim.mp4

合并所有承诺和副对角线的安全性

当证明者将更多项相加时，最初担心的一个问题是，既然证明者有了更多的机会来隐藏不诚实的计算。

我们现在展示，一旦证明者发送 $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_2, G_3, G_4, G_5, G_6, G_7, G_8)$ 的向量承诺到矩阵 $[a_2, a_4, a_6, a_8]$ 的承诺。Pedersen 向量承诺的安全假设是证明者只能生成一个可能的向量开启。“在他们发送承诺后‘移动值’”意味着证明者能够计算出与 $\langle G_1, G_2 \rangle$ 不同的向量。 但这就违背了我们“仅可生成 Pedersen 承诺有效开启的单一有效向量”的假设。对于 $R$ 邻一样的论据。

$A$ 是四个 Pedersen 承诺的和（即对向量 $[a_1, a_2]$、$[a_3, a_4]$、$[a_5, a_6]$、$[a_7, a_8]$ 的承诺）。然而，从安全性来看，多次将 Pedersen 承诺相加这一事实是无关紧要的。无论是单独计算承诺然后相加，还是将 $A$ 计算为长度为 $n = 8$ 的向量并没有差别。例如：

$$ \begin{align} &\space a_1G_1 + a_2G_2\space + \space a_3G_3 + a_4G_4\space\space + \space\space a_5G_5 + a_6G_6\space + \space a_7G_7 + a_8G_8\ =&(a_1G_1 + a_2G_2) + (a_3G_3 + a_4G_4) + (a_5G_5 + a_6G_6) + (a_7G_7 + a_8G_8)\end{align} $$

例如，证明者可能会“将值”从 $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_3G4 + \dots + a{n-1}G_n$ 和 $R = a_2G_1 + a_4G_3 + \dots + anG{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{G}$ 的原始向量 $\mathbf{a}$ 的承诺。$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)$ 个元素。

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

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]
```## 证明者提交
A = vector_commit(G_vec, a)  
L, R = compute_secondary_diagonal(G_vec, a)  

## 验证者计算随机性
u = random_element()  

## 证明者计算 fold(a)
aprime = fold(a, u)  

## 验证者计算 fold(G)
Gprime = fold_points(G_vec, pow(u, -1, p))  

## 验证检查
assert eq(vector_commit(Gprime, aprime), add_points(multiply(L, pow(u, 2, p)), A, multiply(R, pow(u, -2, p)))), "无效的证明"  
assert len(Gprime) == len(a) // 2 and len(aprime) == len(a) // 2, "证明的大小必须为 n/2"

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