范围证明

范围证明在内积论证中的背景下是一个证明，表明标量 $v$ 已承诺于 $V$，并且 $v$ 小于 $2^n$，对于某个非负整数 n。

本文展示了 Bulletproofs 论文如何构建这样的证明。高层的想法是，如果我们能证明一个向量 $a_L$ 仅包含 0 和 1，并且 $a_L$ 是 v 的二进制表示，那么 v 必须小于 $2^n$。这类似于说一个可以放入 8 位无符号整数的数字必须小于 256。

使用 Bulletproofs 进行范围证明的优点在于，范围证明可以直接构造，而无需算术电路。

Monero 使用 Bulletproof 范围证明（此处呈现的算法）来确保交易的总和不为负（在一个有限域中，负数是大于 $p/2$ 的元素，因为它们是小于或等于 $p/2$ 的元素的加法逆元，其中 p 是域的阶）。

本文是系列文章中的一部分，讨论ZK Bulletproofs。

记号（Notation）

$\mathbf{0}^n$ 是一个全为零的 $n$ 维向量。

$\mathbf{1}^n$ 是一个全为一的 $n$ 维向量。

$\mathbf{2}^n$ 是一个 n 维向量$ [1,2,4,8,…,2^{n−1}]$

$\mathbf{y}^n$ 是一个 n 维向量$ [1,y,y^2,y^3,…,y^{n−1}]$

$\mathbf{y}^ {-n}$ 是一个 n 维向量$ [1,y^{−1},y^{−2},…,y^{−(n−1)}]$

注意，$\mathbf{2}^n$∘$\mathbf{y}^ {-n}$ =$\mathbf{1}^n$。

范围证明概述

证明 $V$ 是一个值小于 $2^n$ 的承诺需要证明以下内容：

1. $a_L$ 是二进制的（仅取 0 和 1 的值）。
2. 内积 $ ⟨aL,2^n⟩=v$。

第二点容易证明，我们做一个普通的内积证明，然后揭示 $2^n$ 是承诺中的一个向量——或者让验证者自己构造 $2^n$ 的承诺。然而，没有算术电路来证明 $a_L$ 是二进制的，需要几个代数技巧。

四个有用的技巧

Bulletproofs 论文隐含地使用了四个代数技巧，最好在直接查看范围证明算法之前明确教授这些技巧。

1. 证明 $a_L$ 是二进制的

声明 $2_L$ 是二进制的等同于以下两个声明：

$$ \mathbf{a}_R = \mathbf{a}_L-\mathbf{1}^n $$

$$ \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n $$

例如，如果 $a_L=[1,0,0,1]$，那么$ a_R=[0,−1,−1,0]$。

在这种情况下，$2_L∘a_R=0^n$，因为

$$ [1,0,0,1] \circ [0,-1,-1,0] = [0,0,0,0] = \mathbf{0}^n $$

现在考虑 $a_L$ 不是二进制的情况，例如 $[2,1,0,0]$。a_R 将是 $[1,0,−1,−1]$。 $a_L$ 和 $a_R$ 的 Hadama_Rd 积将是 $[2,0,0,0]≠0^n$。

更一般地，如果 $a_L$ 有一个非二进制条目，那么该条目将被减去 1，而 $a_R$ 中的相应条目将是非零的。当计算 Hadama_Rd 积时，在该特定索引，$a_L$ 和 $a_R$ 都是非零的，乘积将是非零的，意味着 $a_L∘a_R≠0^n$。

然而，如果 $a_L$ 中的某个条目是 1，那么在该索引，$a_R$ 将是 0，因此该索引的 Hadama_Rd 积也将为零。

最后，如果 $a_L$ 中的某个条目为 0，那么 $a_R$ 在该索引为 −1，而它们元素间的乘积在该索引仍将是零。

因此，如果 $a_L$ 是二进制的并且 $a_R$ 被计算为 $a_R=a_L−1$，那么 $a_L∘a_R=0^n$。

2. 证明一个向量全为零

假设我们希望证明 Pedersen 承诺 A 持有一个零向量。我们创建 Pedersen 承诺 A=⟨a,G⟩+αB，并希望向验证者证明 a=0^n。

这似乎只需简单地发送盲化项 α，但为了使我们的解决方案更具可组合性，我们不想揭示盲化项，因为这可能会影响我们创建的其他承诺。

相反，证明者将 A 发送给验证者，验证者回应一个满是随机值的向量 r。证明者现在必须证明

$⟨a,r⟩=0$

请注意，这是一项概率测试。存在极小的概率，$⟨a,r⟩=0$ 对于 $a≠0^n$，但证明者无法伪造出这样的 a，因为他们不事先知道 r 的值。

然而，传输 r 需要 $O(n)$ 的通信开销，因此验证者只发送一个随机元素 y，证明者计算 $y^n$ 并将 $y^n$ 作为随机向量使用。

然后，证明者证明 $⟨a,y^n⟩=0$。

3. 证明一个内积的形式为 ⟨a_L,a_R∘y^n⟩ 其中 y 由验证者选择且证明者计算 $y^n$

我们还没有证明 $a_L∘a_R=0^n$ 的机制，因为那是一个 Hadama_Rd 积，而不是一个内积。然而，声明向量 $a_L∘a_R$ 为零与声明 $⟨a_L∘a_R,y^n⟩=0$ 是相同的。根据内积规则，我们可以将 $a_R 移动到内积的另一侧，现在我们有 $⟨a_L,a_R∘y^n⟩=0$。

验证者将接收到对 $a_L$ 和 $a_R$ 的承诺，而不是 $a_R∘y^n$。验证者将负责构造对 $a_R∘y^n$ 的承诺，因此他们被说服证明者将 $a_R∘y^n$ 作为内积中的第二个向量。

我们依赖的关键技巧是，证明者使用基向量 G 和 H 来承诺他们的向量，但验证者使用 $G$ 和$H∘y^{-n}$。

当证明者发送评估 $r_u$ 时，证明者必须确保 $y^n$ 项将与验证者基向量 $y^{-n}∘H$ 中的 $y^{-n}$ 进行抵消。

具体来说，证明者构造承诺

$$ \begin{align} A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B \end{align} $$

并将 (A,S) 发送给验证者。这里无需承诺并发送 V，因为在这种情况下它是零。

证明者的多项式将是

$$ \begin{align} \mathbf{l}(x)&=\mathbf{a}_L + \mathbf{s}_Lx\ \mathbf{r}(x)&=\mathbf{a}_R\circ\mathbf{y}^n + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align} $$

至关重要的是，证明者使用 $y^n$ 与 $s_R$ 进行了 Hadama_Rd 乘法。以前，$r(x)$ 计算为 $r(x)=a_R∘y^n+s_Rx$（没有 $y^n∘s_R$）。这将使在验证者计算承诺 $⟨r_u,y^{-n}∘H⟩$ 时所有 $y^n$ 项都被抵消。在后台，$r_u$ 是 $(a_R+s_Ru)∘y^n$，因此 $y^n$ 在验证者计算 $⟨(a_R+s_Ru)∘y^n,y^{-n}∘H⟩$ 时将抵消，即

$$ \begin{align} &\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{y}^n\circ\mathbf{y}^{-n}\circ\mathbf{H}\rangle\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{1}^n\circ\mathbf{H}\rangle\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{H}\rangle \end{align} $$

然而，由于验证者尚未发送 $y$，因此证明者无法立即计算$ l(x) $或 $r(x)$。因此，在接收到 $(A,S)$ 后，验证者发送 $y$，证明者计算 $y^n$ 并计算多项式$ t(x)$：

$$ t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle=\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle+t_1x+t_2x^2 $$

其中

$$ \begin{align} t_1&=\langle\mathbf{a}_L,\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align} $$

证明者承诺系数 t1 和 t2 为

$$ \begin{align} T_1&=t_1G+\tau_1B\ T_2&=t_2G+\tau_2B \end{align} $$

并将 (T1,T2) 发送给验证者。验证者回应一个随机值 u，证明者评估向量多项式 l(x) 和 r(x)：

$$ \begin{align} \mathbf{l}_u&= \mathbf{a}_L\circ\mathbf{y}^n+(\mathbf{s}_L\circ\mathbf{y}^n)u\ \mathbf{r}_u&= \mathbf{a}_R+\mathbf{s}_Ru\ t_u&=\langle\mathbf{l}_u,\mathbf{r}u\rangle\ \pi{lr}&=\alpha + \beta u\ \pi_t&=\tau_1u+\tau_2u^2 \end{align} $$

注意，πt 仅包括 t1 和 t2 的盲化项。在之前的实现中，πt 计算为 γ+τ1u+τ2u2，其中 γ 是 V 的盲化项，它也是多项式 t(x) 的常数项。

由于没有对 V 的盲化项 γ，因此将 V 设为 0，即 v 不是秘密——它是 0。证明者发送 (lu,r_u,tu,πlr,πt)，验证者检查：

$$ \begin{align} 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{y}^{-n}\circ\mathbf{H}\rangle+\pi{lr}B\ t_uG&\stackrel{?}{=} T_1 u + T_2 u^2 – \pi_t B\ \end{align} $$

第一个关键区别是对 r_u 的承诺是与基向量 $y^{-n}∘H$ 而不是 H 有关，原因在于之前的讨论。

第二个，$t_uG\stackrel{?}{=} T_1 u + T_2 u^2 + \pi_t B$ 没有常数承诺。通常，方程是 tuG=?V+T1u+T2u2+πtB，但在这种情况下 V 是对 0 的承诺。

一般来说，如果 V 包含验证者已知的值，验证者就可以进行对 V 的承诺，就像我们在下一节中展示的那样。

4. 在涉及加法公共常数时证明一个内积

正如上面部分提到的，如果验证者知道底层向量，则验证者可以重构承诺。

例如，假设我们证明

$$ \langle\mathbf{a}_L + \mathbf{j},\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}\rangle=vz $$

其中 j 和 k 是验证者已知的向量，z 是验证者事先已知的标量。与 y^n 不同，这些向量和标量是在证明开始之前已知的。注意，k 在该示例中没有与 y^n 进行 Hadama_Rd 乘法。

证明者仍然仅对秘密值 aL、a_R 和 v 进行承诺，如往常：

$$ \begin{align} A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\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 \end{align} $$

通常，多项式 $l(x)$和 $r(x)$ 使得常数项是原始内积的向量，而线性项是 $s_L$ 和 $s_R$。在从验证者接收到 y 后，证明者计算 $y^n$ 并构建但不评估 $l(x)$ 和 $r(x)$：

$$ \begin{align} \mathbf{l}(x)&=\underbrace{\mathbf{a}L + \mathbf{j}}\text{left vector} + \mathbf{s}_Lx\ \mathbf{r}(x)&=\underbrace{\mathbf{a}R\circ\mathbf{y}^n + \mathbf{k}}\text{right vector} + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align} $$

注意，$k$ 没有与 $y^n$ 进行 Hadama_Rd 乘法，但线性项 $s_R$ 仍然是。我们稍后将显示验证者如何处理这个。

现在，我们将 $t(x)$ 计算为

$$ t(x)=vz+t_1x+t_2x^2 $$

其中

$$ \begin{align} t_1&=\langle\mathbf{a}_L+\mathbf{j},\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}\rangle\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align} $$

请注意，t(x) 中的常数项是 vz 而不是 v。承诺为

$$ \begin{align} T_1 &= t_1G+\tau_1B\ T_2 &= t_2G+\tau_2B\ \end{align} $$

并发送给验证者，然后验证者发送随机值 u。

证明者计算：

$$ \begin{align} \mathbf{l}_u&= \mathbf{a}_L\circ\mathbf{y}^n+\mathbf{j}+(\mathbf{s}_L\circ\mathbf{y}^n)u\ \mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}+\mathbf{s}_Ru\ t_u&=\langle\mathbf{l}_u,\mathbf{r}u\rangle\ \pi{lr}&=\alpha + \beta u\ \pi_t&=vz+\tau_1u+\tau_2u^2 \end{align} $$

注意，$π_t$ 的常数项是 $γz$。证明者发送 $(\mathbf{l}_u,\mathbf{r}_u,tu,\pi{lr},\pi_t)$。最后，验证者计算：

$$ \begin{align} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}u\rangle\ A+Su+\underbrace{\langle\mathbf{j,\mathbf{G}}\rangle}{\text{commitment to } \mathbf{j} \text{ in } \mathbf{l}(x)}+\underbrace{\langle\mathbf{k},\mathbf{y}^{-n}\circ\mathbf{H}\rangle}_{\text{commitment to } \mathbf{k} \text{ in } \mathbf{r}(x)}&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi{lr}B\ t_uG&\stackrel{?}{=} Vz+ T_1 u + T_2 u^2 – \pi_t B\ \end{align} $$

$l_u$ 和 $r_u$ 分别包含 $j$ 和 $k$，但 A 和 S 不包含。因此，验证者计算这些向量的承诺并将其添加到证明者提供的秘密向量的承诺 A 和 S 中。在 k 的情况下，基向量 $y^{-n}∘H$ 将导致 k 变为 $k∘y^{-n}$，因此承诺必须分别针对 $y^{-n}∘H$ 进行计算。最后，盲化项 $π_t$ 包含 vz，但 V 不包含 z。因此，证明者必须将 V 乘以 z。

通过计算 $⟨j,G⟩, ⟨k,y^n∘H⟩$ 和 $Vz$，验证者可以确定内积计算确实包含了这些项。

范围证明

为了证明 V 是小于 $2^n$ 的值，我们需要证明三件事：

• 内积 $\langle \mathbf{a}_L,\mathbf{2}^n\rangle = V$，即 $\mathbf{a}_L$ 是 v 的二进制表示
• $\mathbf{a}_R=\mathbf{a}_L-\mathbf{1}$
• $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}$

最后两项并不直接呈现为内积的形式。然而，我们可以稍微修改它们来实现这一点。我们真正所说的是向量

• $\mathbf{a}_R – \mathbf{a}_L+\mathbf{1}$
• $\mathbf{a}_L\circ\mathbf{a}_R$

都是 0^n。我们可以使用先前部分中的技巧来证明它们为零。也就是说，证明者需要建立

$$ \langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0} $$

和 $$ \langle \mathbf{a}_R – \mathbf{a}_L+\mathbf{1},\mathbf{y}^n\rangle=\mathbf{0} $$

其中 $y^n$ 是从验证者发送的 y 值派生的随机向量。

原始 Bulletproofs 论文稍微修改了第一个声明，以便我们可以利用之前部分的第三个技巧：

$$ \langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0} $$

因此，证明者需要建立三个内积：

1. $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}$
2. $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}^n$
3. $\langle\mathbf{a}_L -\mathbf{1}^n- \mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}^n$

将三个内积结合为一个

可以通过一个随机线性组合将三个内积组合成一个，随机性 z 由验证者提供。

$$ z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z^1 \cdot \langle \mathbf{a_L} – \mathbf{1}^n – \mathbf{a_R}, \mathbf{y}^n \rangle + z^0\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v + z^1\cdot\mathbf{0}^n+z^0\cdot\mathbf{0}^n $$

$$ z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z \cdot \langle \mathbf{a_L} – \mathbf{1}^n – \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v $$

通过一些非常复杂的内积代数，我们可以对所有内积进行如下组合。我们在附录中展示了导出过程。

$$ \left\langle \mathbf{a_L} – z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + (z – z^2) \cdot \langle \mathbf{1}^n, y^n \rangle – z^3 \langle \mathbf{1}^n, 2^n \rangle $$

下面框中的项包含验证者已知的值，因此我们将构造我们的验证算法来明确检查这些值。也就是说，验证者将计算对框中项值的承诺，而不是证明者：

$$ \left\langle \mathbf{a_L} – \boxed{z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{(z – z^2) \cdot \langle \mathbf{1}^n, y^n \rangle – z^3 \langle \mathbf{1}^n, 2^n \rangle} $$

为了节省空间，Bulletproofs 论文将项 $(z – z^2) \cdot \langle \mathbf{1}^n, y^n \rangle – z^3 \langle \mathbf{1}^n, 2^n \rangle$ 称为 $δ(y,z)$，因此可以将内积写为

$$ \left\langle \mathbf{a_L} – z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z) $$

注意 $δ(y,z)$ 是验证者可以计算的值。

范围证明算法

证明者选择 $v$ 及其二进制表示 $\mathbf{a}_L$，这样计算 $ \mathbf{a}_R = \mathbf{a}_L – \mathbf{1} $。

然后，证明者随机选择盲化项 α，并使用基向量 G 和 H 计算 $a_L$ 和 $a_R$ 的组合承诺为

$$ A = \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B $$

然后，证明者选择即将创建的向量多项式 l(x) 和 r(x) 的线性项 s_L 和 s_R，并对它们进行承诺

$$ S = \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B $$

证明者将内积对 V 的承诺计算为关于未知离散对数的 G：

$$ V = vG+\gamma B $$

证明者将 $(A, S, V)$ 发送给验证者。

验证者以随机值 $(y,z)$ 响应，证明者将使用这些值将三个内积组合成一个。

$$ \left\langle \mathbf{a_L} – z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z) $$

内积的左侧 $\mathbf{a}_L-z\cdot\mathbf{1}$ 将是 l(x) 的常数项，而 $\mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 将是 $r(x)$ 的常数项。

因此，我们构造 $l(x)$ 为

$$ \mathbf{l}(x)=\underbrace{\mathbf{a}L-z\cdot\mathbf{1}}\text{constant term}+\mathbf{s}_Lx $$

我们将 $r(x) $ 构造为

$$ \mathbf{r}(x)=\underbrace{\mathbf{y}^n\circ(\mathbf{a}R+z\cdot\mathbf{1})+z^2\mathbf{2}^n}\text{constant term}+\mathbf{y}^n\circ\mathbf{s}_Rx $$

请注意，我们将 s_Rx 与 y^n 按元素相乘，正如我们在上述前提部分第 3 节中讨论的那样。

现在证明者可以构造 $t(x) = \langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ ，其常数系数为 $t_0$，线性系数为 $t_1$，二次系数为 $t_2$，如下所示：

$$ \begin{align} t_0 &= \left\langle \mathbf{a_L} – z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align} $$

其中 $t(x) = t_0 + t_1x + t_2x^2$

证明者将对 $t_1$ 和 $t_2$ 的承诺为

$$ \begin{align} T_1 &= t_1G+\tau_1B\ T_2 &= t_2G+\tau_2B \end{align} $$

无需对 $t_0$ 进行承诺——请注意，它恰好是我们尝试证明的内积，所以验证者已经拥有承诺 V。

验证者发送随机性 u，证明者计算

$$ \begin{align} \mathbf{l}_u &= \mathbf{l}(u) \ \mathbf{r}_u &= \mathbf{r}(u) \ tu &= \mathbf{t}(u)\ \pi{lr} &=\alpha+\beta u\ \pi_t &= z^2\gamma + \tau_1u + \tau_2u^2\ \end{align} $$

注意，$π_t$ 的常数项乘以 $z^2$，以反映原始内积的 $z^2⋅v$ 项。

验证者然后计算新的基向量 $\mathbf{H}_{\mathbf{y}^{-1}}=\mathbf{y}^{-n}\circ\mathbf{H}$，并运行以下检查：

$$ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle $$

$$ A + Su + \boxed{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \boxed{\langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}u, \mathbf{H}{y^{-1}} \rangle + \pi_{lr} B $$

$$ t_uG+\pi_tB=V\boxed{z^2}+\boxed{\delta(y,z)}\cdot G+T_1u+T_2u^2 $$

请记住，证明者未承诺他们用于内积左右两侧的整个向量，只承诺了 $a_L$ 和 $b_L$。其余向量是验证者已知的公共向量，因此验证者通过构造对常数项的承诺并将其添加到证明者提供的秘密向量承诺中重构了这些向量的承诺。

为了提醒一下，以下是验证者已知的数值框住的原始内积：

$$ \left\langle \mathbf{a_L} + \boxed{-z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{\delta(y,z)} $$

鼓励读者验证原始乘积中的框中项（验证者已知的值）在上述相等检测中被验证者重构。

通过复制证明者计算的一部分，验证者断言证明者确实按声明进行计算。

验证算法的正确性

我们现在将显示最终的验证检查在证明者诚实时是完全正确的。

下面我们显示确切的代数，但直观上，验证者正在“重构”内积中的左向量 $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$、右向量 $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 以及输出 $z^2v+\delta(y,z)$。

对证明者来说，验证者并未得到对 $\mathbf{a_L} – z \cdot \mathbf{1}^n$ 和 $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 的承诺，而是对 $a_L$ 和 $a_R$。同样，验证者不是得到对输出 $z^2v + \delta(y,z)$ 的承诺，而仅对 $v$。

加法项和按元素乘以 $y^n$ 的项必须由验证者重构。

$t_u = \mathbf{t}(u)$ 的正确性

对于 $t_u\stackrel{?} =\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ 检查，这个是由定义而真，因为这就是证明者如何计算 $t_u$。

关于 A 和 S 的承诺的 $l(x)$ 和 $r(x)$ 的正确性

对于 $A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}u, \mathbf{H}{y^{-1}} \rangle + \pi_{lr} B$

我们做以下替换：

$$ \underbrace{\langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B}_A + \underbrace{(\langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)}Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \underbrace{\mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}Lu}{\mathbf{l}_u}, \mathbf{G} \rangle + \langle \underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}Rx}{\mathbf{r}u}, \mathbf{H}{y^{-1}} \rangle + \underbrace{(\alpha+\beta u)}{\pi{lr}} B $$

所有 G 项如下所示抵消：

$$ \cancel{\langle\mathbf{a}_L,\mathbf{G}\rangle}+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\cancel{\langle\mathbf{s}_L,\mathbf{G}\rangle}+\langle\mathbf{s}R,\mathbf{H}\rangle+\beta B)u + \cancel{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_L u, \mathbf{G} \rangle} + \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}R x, \mathbf{H}{y^{-1}} \rangle + (\alpha+\beta u) B $$

$$ \langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\langle\mathbf{s}R,\mathbf{H}\rangle+\beta B)u + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}R x, \mathbf{H}{y^{-1}} \rangle + (\alpha+\beta u) B $$

与 B 相关的盲化项如下所示抵消： $$ \langle\mathbf{a}_R,\mathbf{H}\rangle+\cancel{\alpha B} + (\langle\mathbf{s}R,\mathbf{H}\rangle+\cancel{\beta B)u} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}R x, \mathbf{H}{y^{-1}} \rangle + \cancel{(\alpha+\beta u) B} $$

$$ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}R u, \mathbf{H}{y^{-1}} \rangle $$

$H_y−1$ 与 $y^n$ 项抵消：

$$ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}R+z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle $$

将内积进行分割：

$$ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}R,\mathbf{H}\rangle+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle $$

抵消方程两侧都出现的项：

$$ \cancel{\langle\mathbf{a}_R,\mathbf{H}\rangle} + (\langle\mathbf{s}R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}R,\mathbf{H}\rangle}+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle $$

$$ \cancel{(\langle\mathbf{s}R,\mathbf{H}\rangle u)} + \langle z\cdot\mathbf{y}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\cancel{\langle\mathbf{s}_R u, \mathbf{H} \rangle} $$

$$ \langle z\cdot\mathbf{y}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle} \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle} $$

$$ \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle $$

将 $y^n$ 移到另一侧： $$ \langle z\cdot\mathbf{1},\mathbf{H}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle $$

$$ \cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} \stackrel{?}{=}\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} $$

$t(u)$ 计算的正确性

为了解释

$$ t_uG+\pi_tB=Vz^2+\delta(y,z)G+T_1u+T_2u^2 $$

的正确性，我们可以如下替换项： $$ \underbrace{\langle \mathbf{l}_u, \mathbf{r}u \rangle}{t_u}G+\underbrace{(z^2\gamma + \tau_1u + \tau2u^2)}{\pit}B=\underbrace{(vG+\gamma B)}{V}z^2+\delta(y,z)G+\underbrace{(t_1G+\tau1B}{T_1})u+\underbrace{(t_2G+\tau2B)}{T_2}u^2 $$

使用的 $l_u$, $r_u$, $t_1$, $t_2$: $$ \begin{align} \mathbf{l}_u &= \mathbf{a_L} – z \cdot \mathbf{1}^n\ \mathbf{r}_u &= \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align} $$

然而，这种代数会非常麻烦。相反，我们注意到 $z^2v+\delta(y,z)G$ 是 $⟨l(x),r(x)⟩$ 的向量多项式内积的常数项。要抵消 V 中的盲化项 $\gamma B$，请注意 $π_t$ 包含 $z^2γ$，因此这将与 $Vz^2 = (vG + \gamma B)z^2$ 中的 gamma 项抵消。

由于 Pedersen 承诺是加法同态，验证者可以简单计算并将 $\delta(y,z)G$ 加到 $Vz^2$，以计算多项式 $t(x)$ 的常数项承诺。

对数大小的范围证明

我们可以通过发送对 l_u 和 r_u 的承诺 C，并证明承诺的向量具有内积 tu 的使用对数大小的证明，从而减少数据传输的大小，然后验证

$$ A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}{\mathbf{y}^{-1}}\rangle-\pi{lr}B\stackrel{?}{=} C $$

和

$$ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle $$

涉及基向量 $G$ 和 $\mathbf{H}_{\mathbf{y}^{-1}}$。

将范围证明算法用于子集和问题

子集和问题 问道：“给定一组数字，是否存在一个子集（可能包括整个集合）和为 k？例如，如果 k=16 并且集合是 ${3,5,7,11}$，答案是肯定的，因为 $5+11=16$。但是如果 $k=13$ ，则答案是否定的。

子集和问题是 NP 完全的，这意味着，类似于布尔电路或算术电路，它可以表示 NP 中的任何问题。即，任何 NP 中的问题都可以重写（技术词是“约简）为子集和实例。

通过将 $2^n$ 替换为 $[3,5,7,11]$，我们可以证明我们知道子集和的解决方案而不揭示答案。具体来说，如果 $k=16$，证明者将知道 $a_L=[0,1,0,1]$。一般来说，$a_L$ 中的一个条目表示我们包括该元素在子集中，而 0 则表示该元素不包含在子集中。

因此，Bulletproofs 能够证明对 NP 中任何问题的任何见证的知识。

附录：将三个内积结合为一个的推导

从三个内积开始

$$ z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a_L} – \mathbf{1}^n – \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v $$

我们展示如何导出最终结果 $$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle $$

使用我们之前学习的内积代数。

1. 中间项可以分成单独的内积：

$$ z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + \boxed{z \cdot \langle \mathbf{a_L} – \mathbf{1}^n – \mathbf{a_R}, \mathbf{y}^n \rangle} + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v $$

$$ z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle+\boxed{z\cdot\langle\mathbf{a}_L,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{1}^n,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{a}_R,\mathbf{y}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle=z^2\cdot v $$

2. 我们可以将常量 z 项移入内积内： $$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v $$

3. 将已知验证者的值移动到右侧： $$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v $$

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle} $$

4. 将 a_R 项都转换为 a_R∘y^n： $$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-\mathbf{a}_R\circ\mathbf{y}^n,z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\boxed{\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

5. 将 $a_R∘y^n$ 项合并为一个：

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\underbrace{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle} = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

6. 将左边的两个 $a_L$ 项合并：

$$ \langle \boxed{\mathbf{a_L}}, z^2\cdot\mathbf{2}^n \rangle+\langle\boxed{\mathbf{a}_L},z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

7. 将最后一个左侧项拆分为两个内积： $$ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

8. 合并 $a_L$ 项： $$ \langle \boxed{\mathbf{a_L}}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n, \boxed{\mathbf{a}_L}\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

$$ \langle \mathbf{a_L}, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle $$

9. 我们可以使用规则 $\langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{y}\rangle = v \rightarrow \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle$ 来合并包含 $\mathbf{a}_R\circ\mathbf{y}^n$ 的项。这里 b 是 $\mathbf{a}_R\circ\mathbf{y}^n$，c 是 $z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n$ ，y 是 $-z\cdot\mathbf{1}^n$ 。

$$ \langle \underbrace{\mathbf{aL}}\mathbf{x}, \underbrace{\mathbf{a}R\circ\mathbf{y}^n}\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle+\langle\underbrace{\mathbf{a}R\circ\mathbf{y}^n}\mathbf{b},\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y}\rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v $$

$$ \langle \underbrace{\mathbf{aL}}\mathbf{x}-\underbrace{z\cdot\mathbf{1}^n}_\mathbf{y}, \underbrace{\mathbf{a}R\circ\mathbf{y}^n}\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}v+\langle\underbrace{-z\cdot\mathbf{1}^n}\mathbf{y},\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c}\rangle $$

$$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n\rangle $$

10. 现在将右侧的项分开：

$$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z^2\cdot\mathbf{2}^n\rangle $$

11. 将右侧内积中的标量提出来：

$$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+z\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^2\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle $$

12. 提取 $\langle\mathbf{1}^n,\mathbf{y}^n\rangle$：

$$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle $$

因为 $\delta(y,z)=(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle$，我们有：

$$ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+\delta(y,z) $$

这完成了推导。 ◼

• 原文链接： ra_Reskills.io/post/range...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
• 公式由登链社区编辑校对