对数大小的承诺证明

在前面的章节中，我们展示了将向量 $\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)$ 这样的项，因此直接执行这一操作效率不高。

然而，观察到我们可以以下面动画所示的方式“填充外积”：

https://img.learnblockchain.cn/2025/02/27/MatrixFoldingAnimation.mp4

在上面的动画中，当证明者发送非对角线项后，证明者将 $\mathbf{G}$ 和 $\mathbf{a}$ 同时折叠，使得它们的长度减少一半。

最后，当我们对 $\mathbf{a}$ 和 $\mathbf{G}$ 折叠 $\log n$ 次后，向量的大小为 1。 当 $n=1$ 时，外积等于内积，我们只需透露这两个向量，它们将是常数大小。

回顾 — 这与前一章算法的关系

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

证明者将向量 $\mathbf{a}$ 承诺给 $P$，即 $P = \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}$。验证者回应 $u$，证明者将向量 $\mathbf{a}$ 根据 $u$ 折叠为 $\mathbf{a}’=\mathsf{fold}(\mathbf{a},u)=[a_1u+a_2u^{-1}, a_3u+a4u^{-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})$，关于基向量 $\mathsf{fold}(\mathbf{G},u^{-1})$ 的长度为 $n’=n/2$。我们可以幼稚地通过发送 $\mathbf{a}’$ 证明我们知道 $P’$ 的开口，验证者检查 $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$ 是输入向量的长度，这些向量的长度都是一样的。

$$\ {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_3G4 + \dots a{n-1}G_n\ R &= a_2G_1 + a_4G_3 + \dots anG{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. $$\ {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$ 本身从一开始就是不秘密的。

实际上，我们尚未展示如何用对数大小的数据证明我们知道内积，我们仅仅展示了我们用对数大小的数据知道一个承诺的开口。然而，更新我们的算法以展示我们知道两个向量的内积是很简单的，正如我们将在本文后面做的那样。

运行时间

验证者执行计算 $\mathbf{G}’ = \mathsf{fold}(\mathbf{G}, u^{-1})$ $\log n$ 次，并且第一次 $\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承诺，而不是向量承诺。为此，我们使用一个随机的椭圆曲线点（具有未知的离散对数）$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$ 组成的向量，即

$$\mathbf{Q}^n=[\underbrace{Q,\dots, Q}_n]$$

因此，

$$\mathbf{b}\circ\mathbf{Q}^n=[b_1Q, b_2Q,\dots,b_nQ]$$

注意 $\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$ 以使下一个技巧更加明显。

为了同时证明整个承诺，而不是三个内积，注意到

$$P=\langle\mathbf{a},\mathbf{G}\rangle+\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}^n\rangle +\langle\mathbf{b},\mathbf{H}\rangle=\langle\mathbf{a}\oplus\mathbf{a}\oplus\mathbf{b},\mathbf{G}\oplus b\circ\mathbf{Q}^n\oplus\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$。

我们在下面的动画中展示算法：

https://img.learnblockchain.cn/2025/02/27/ThreeWayInnerProduct.mp4

算法

给定 $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$。

$$\ {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_3b4 + \dots a{n-1}b_n)Q+(a_1G_2 + a_3G4 + \dots a{n-1}G_n)+(b_2H_1 + b_4H_3 + \dots bnH{n-1})\ R &= (a_2b_1 + a_4b_3 + \dots anb{n-1})Q+(a_2G_1 + a_4G_3 + \dots anG{n-1})+(b_1H_2 + b_3H4 + \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. $$\ {prove_commitments_log}(P’, G’, H’, \mathbf{a}’, \mathbf{b}’)$$

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

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

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)

## 这些椭圆曲线点具有未知的离散对数：
G_vec = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

## 返回长度为 n/2 的折叠向量
def fold(scalar_vec, u):
    pass

## 返回长度为 n/2 的折叠向量
def fold_points(point_vec, u):
    pass

## 返回 (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$：

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

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

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

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