内积代数

在这篇文章中，我们提供了一些对于内积的有用代数技巧，这些技巧将在后面推导范围证明（以及将电路编码为内积）时非常有用。每条规则将附带一个简单的证明。

记号

加粗变量，如 $\mathbf{a}$，表示一个向量。未加粗的变量，如 $v$，表示一个标量。操作符 $\circ$ 是两个向量的 Hadamard 乘积（逐元素相乘），即 $[a_1, \dots, a_n]\circ[b_1, \dots, b_n] = [a_1b_1, \dots, a_nb_n]$。我们使用简写“lhs”和“rhs”分别表示一个方程的“左侧”和“右侧”。“加数”是加法中的一个元素，例如如果 $a + b = c$，那么 $a$ 和 $b$ 被称为加数。$\mathbf{1}$ 向量是一个全为 1 的向量，即 $[1, 1, \dots, 1]$。除非另有说明，所有向量隐含为相同的长度 $n$。

规则 1：一个向量是向量之和的内积可以展开

假设我们正在计算一个内积，其中一个向量是两个向量的和——例如 $\langle\mathbf{a} + \mathbf{b}, \mathbf{c}\rangle$。我们可以将其拆分为两个内积的和：$\langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle$

证明：lhs 可以写成 $$ \sum_{i=1}^n(a_i+b_i)c_i $$

rhs 可以写成

$$ \begin{align} \sum_{i=1}^na_ici+\sum{i=1}^nc_ibi &=\sum{i=1}^n(a_ic_i+c_ibi) \\ &=\sum{i=1}^n(a_i+b_i)c_i \end{align} $$

规则 2：具有共同项的内积可以合并

下面 lhs 的两个内积有一个共同向量 $\mathbf{c}$。因此，它们可以合并： $$ \langle \mathbf{a}, \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{c} \rangle = \langle \mathbf{a} + \mathbf{b}, \mathbf{c} \rangle $$

这实际上是规则 1，仅左右两侧互换。

证明与规则 1 相同。

规则 3：将向量移到内积的另一侧

内积可以重写为 $\mathbf{1}$ 向量与原始向量的 Hadamard 乘积： $$ \langle \mathbf{a}, \mathbf{b} \rangle= \langle \mathbf{1}, \mathbf{a\circ b} \rangle $$

证明：

$$ \begin{align} \langle \mathbf{a}, \mathbf{b} \rangle&=\sum_{i=1}^na_ibi \\ \langle \mathbf{1}, \mathbf{a\circ b} \rangle&=\sum{i=1}^n1(a_ibi)\\ \sum{i=1}^na_ibi &= \sum{i=1}^n1(a_ib_i)\\ \end{align} $$

规则 4：我们可以向内积的一个项添加向量，以迫使两个内积具有共同项

假设我们在添加内积 $\langle\mathbf{x}, \mathbf{b}+\mathbf{c}\rangle$ 和内积 $\langle\mathbf{y}, \mathbf{b}\rangle$，并且内积的和为 $v$。注意它们有不同的分量，因此我们不能用规则 2 将它们相加。然而，以下等式

$$ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle = v $$

可以写为

$$ \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle $$

在上面的场景中，我们可以向两侧添加 $\langle\mathbf{y},\mathbf{c}\rangle$。

$$ \begin{align} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}&= v + \boxed{\langle\mathbf{y},\mathbf{c}\rangle}\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle + \langle\mathbf{y},\mathbf{c}\rangle&= v + \langle\mathbf{y},\mathbf{c}\rangle \end{align} $$

现在我们有了共同的 $\mathbf{y}$ 项，我们可以使用规则 2 合并：

$$ \begin{align} \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{\fbox{y}}, \mathbf{b}\rangle + \langle\mathbf{\fbox{y}},\mathbf{c}\rangle&= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{\fbox{y}}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \end{align} $$

现在我们迫使这两个内积在 lhs 上具有共同项 $\langle \mathbf{b} + \mathbf{c} \rangle$，我们可以再次使用规则 2 将它们合并成一个向量：

$$ \begin{align} \langle \mathbf{x}, \boxed{\mathbf{b} + \mathbf{c}}\rangle + \langle \mathbf{y}, \boxed{\mathbf{b} + \mathbf{c}}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x} + \mathbf{y}, \boxed{\mathbf{b} + \mathbf{c}}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle &= v + \langle\mathbf{y},\mathbf{c}\rangle\\ \end{align} $$

因此，

$$ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{y}, \mathbf{b}\rangle = v $$

可以重写为

$$ \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle $$

规则 5：添加两个无关向量的内积

我们可以将 $\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle$（没有共同的向量）相加，并得到：

$$ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1+\mathbf{b}_2\rangle-\langle\mathbf{a_1},\mathbf{b_2}\rangle-\langle\mathbf{a_2},\mathbf{b_1}\rangle $$

证明：

$$ \begin{align} \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&&\text{将 }\langle\mathbf{a}_1,\mathbf{b}_2\rangle \text{ 添加到两侧}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle&&\text{合并 }\mathbf{b}_2 \text{ 项}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&=\langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&&\text{将 }\langle\mathbf{a}_2,\mathbf{b}_1\rangle\text{ 添加到两侧}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle+\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle&=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1\rangle+\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_2\rangle&&\text{合并右侧}\\ \langle\mathbf{a}_1,\mathbf{b}_1\rangle+\langle\mathbf{a}_2,\mathbf{b}_2\rangle&=\langle\mathbf{a}_1+\mathbf{a}_2,\mathbf{b}_1+\mathbf{b}_2\rangle-\langle\mathbf{a}_1,\mathbf{b}_2\rangle-\langle\mathbf{a}_2,\mathbf{b}_1\rangle&&\text{减去 }\langle\mathbf{a}_1,\mathbf{b}_2\rangle+\langle\mathbf{a}_2,\mathbf{b}_1\rangle \end{align} $$

证明说明有时找到要添加到方程两侧的内积可能是有用的。

规则 6：标量可以在内积内外移动

$z\cdot\langle\mathbf{a},\mathbf{b}\rangle = \langle z\cdot\mathbf{a},\mathbf{b}\rangle = \langle\mathbf{a},z\cdot\mathbf{b}\rangle$

这个陈述的证明留给读者作为练习。作为提示，常数项可以在求和内外移动。

本教程是我们关于 ZK Bulletproofs 系列的一部分。

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