原文链接： Inner Product Arguments

翻译：Star.LI @ Trapdoor Tech

介绍

你也许听说过“BulletProofs”：它是一种零知识证明算法，不要求可信设置。比如，门罗币（Monero）就用了这个算法。这种证明系统的核心是内积证明1，一个能让证明者向验证者证明“内积“正确性的小技巧。内积，即是计算两个向量中每个分量的乘积和：

\[\begin{align*} \vec a \cdot \vec b = a_0 b_0 + a_1 b_1 + a_2 b_2 + \cdots + a_{n-1} b_{n-1} \end{align*}\]

其中 \(\vec a = (a_0, a_1, \ldots, a_{n-1})\), \(\vec b = (b_0, b_1, \ldots, b_{n-1})\)。

一个比较有趣的例子就是当我们设置向量 \(\vec b\) 为某个 \(z\) 的幂，即 \(\vec b = (1, z, z^2, \ldots, z^{n-1})\)，那么它的内积就变成了多项式

\[\begin{align*} f(X) = \sum_{i=1}^{n-1} a_i X^i \end{align*}\]

在 \(z\) 点的取值。

内积证明采用Pedersen承诺。我之前写过一篇文章介绍KZG承诺，Pedersen承诺与其类似，承诺值也是在椭圆曲线上的，不同的是它不需要可信设置。下面比较这两个多项式承诺方案(PCS)，KZG承诺方案 和 Pedersen承诺与内积证明相结合的方案:

  Pedersen+IPA KZG
安全假设 离散对数 双线性群
可信设置 否 是
承诺大小 1个群元素 1个群元素
证明大小 2 log n个 群元素 1个群元素
验证 O(n) 群运算 1个配对

说到底，和KZG承诺相比，我们这个承诺方案的效率要低一些。证明大小更大（\(O(\log n)\)），不过对数本身还是挺小的，所以不至于太糟。但可惜的是验证者需要做的计算是线性的, 这失去了简洁性。这些局限使得 Pedersen 承诺对于某些应用来说不太现实，但在一些情况下这些缺点可以被规避。

  • 其中一个例子我在之前的文章多重打开中曾经提到过。这里的诀窍是你可以将多个打开聚合成一个。
  • Halo2 2, 其中多个打开的线性成本可以被聚合。

在以上这两个例子中，特点就是多个打开的成本被分摊了。如果你只想打开一个多项式，那就比较困难了，你需要承担整个打开的运算成本。

但是，Pedersen 承诺与内积证明结合的方案，很大的好处是较少的安全假设。也就是，不需要配对，并且不需要可信设置。

Pedersen 承诺

在我们讨论内积证明之前，我们要先看一下依赖的结构：Pedersen承诺。为了使用Pedersen承诺，我们需要一个椭圆曲线 \(G\)。让我们首先回顾一下我们使用椭圆曲线可以做到哪些事情（在这里我会使用加法符号表示，看起来更自然一些）：

  1. 你可以将两个椭圆曲线点 \(g_0 \in G\) 和 \(g_1 \in G\) 相加: \(h = g_0 + g_1\)
  2. 你可以将元素\(g \in G\)与一个标量\(a \in \mathbb F_p\)相乘，其中\(p\)是\(G\)椭圆曲线的阶 (即元素数量): \(h=ag\)

无法计算两个曲线元素的“乘积”：“\(h * h\)”运算是未定义的，所以你没办法计算“\(h * h = a g * a g = a^2 g\)”；与此相反，与标量相乘是很容易计算的，比如 \(2 h = 2 a g\)。

另一个重要的性质就是不存在有效的计算“离散对数”的算法，这意味着对于满足\(h = a g\)的给定的\(h\)和\(g\)，如果你不知道\(a\)，\(a\)是不可计算的，我们称\(a\)为\(h\)对于\(g\)的离散对数。

Pedersen承诺则利用该不可计算性来构造承诺方案。假设有两个点\(g_0\)和\(g_1\)，它们的离散对数(比如存在\(x \in \mathbb F_p\)使得\(g_1 = x g_0\))并不可知，那么我们可以向两个数\(a_0, a_1 \in \mathbb F_p\)提交承诺:

\[\begin{align*} C = a_0 g_0 + a_1 g_1 \end{align*}\]

\(C\)为椭圆曲线\(G\)的一个元素。

为打开一个承诺，证明者给验证者\(a_0\)和\(a_1\)，然后验证者计算\(C\)，如果相等的话就被接受。

承诺方案的中心性质在于它是不是绑定（binding）。给定\(C=a_0 g_0 + a_1 g_1\)，一个试图作弊的证明者是否能够生成\(b_0, b_1 \in \mathbb F_p\)并使验证者接受它们，即同时满足\(C = b_0 g_0 + b_1 g_1\) 且\(b_0, b_1 \not= a_0, a_1\)。

如果有人能做到上述行为的话，那么它们也可以找出离散对数。为什么呢？我们知道\(a_0 g_0 + a_1 g_1 = b_0 g_0 + b_1 g_1\)，整理后可得

\[\begin{align*} (a_0 - b_0) g_0 = (b_1 - a_1) g_1 \end{align*}\]

所以\(a_0 − b_0\)和\(b_1 − a_1\)不可同时为0。假说\(a_0 − b_0\)不为零，我们得到：

\[\begin{align*} g_0 = \frac{b_1 - a_1}{a_0 - b_0} g_1 = x g_1 \end{align*}\]

对于\(x = \frac{b_1 - a_1}{a_0 - b_0}\)。这样我们就找到了\(x\)的值。我们知道该问题是难题，所以在现实中没有攻击者能够做到。

这意味着对于攻击者来说找到另外的\(b_0 , b_1\)来打开承诺\(C\)在计算性上是不可能的。（它们的确存在，只是无法通过计算获得 – 就像哈希碰撞）。

我们可以扩展一个向量的承诺，比如说一个标量列表\(a_0, a_1, \ldots, a_{n-1} \in \mathbb F_p\)。我们只是需要一个“基”，即一个相等数量的互相未知离散对数的群元素，然后我们就可以计算承诺了：

\[\begin{align*} C = a_0 g_0 + a_1 g_1 + a_2 g_2 + \ldots + a_{n-1} g_{n-1} \end{align*}\]

这给了我们一个向量承诺，尽管这个承诺相对复杂：为了打开任意元素，必须打开所有的元素。但这里有一个重要的性质：这个承诺方案是加同态的，这意味着如果我们有另外一个承诺\(D = b_0 g_0 + b_1 g_1 + b_2 g_2 + \ldots + b_{n-1} g_{n-1}\)，那么我们可能可以通过添加两个承诺得到两个向量\(\vec a\) 和 \(\vec b\)的和:

\[\begin{align*} C + D = (a_0 + b_0) g_0 + (a_1 + b_1) g_1 + (a_1 + b_1) g_2 + \ldots + (a_{n-1} + b_{n-1}) g_{n-1} \end{align*}\]

因为有了加同态的性质，这个向量承诺就变得有用了。

内积证明

内积证明的基本策略是“分治法”：将一个问题规约成多个同类型的子问题，而不是试图一步完全解决它。当子问题规约到一定程度的时候，就可以简单解决。

在这当中每一步，问题的大小都会减半。这保证了\(\log n\)步后，问题大小会减少到1，可以通过简单证明解决。

假设我们需要证明的承诺 \(C\) 具有以下形式：

\[\begin{align*} C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q \end{align*}\]

其中 \(\vec g = (g_0, g_1, \ldots, g_{n-1}), \vec h = (h_0, h_1, \ldots, h_{n-1})\) ，且 \(q\) 是我们的“基”，即：它们是群 \(G\) 中的元素，并且它们之间对于任意一方的离散对数都未知。同时介绍一种新的表示方法：\(\vec a \cdot \vec g\)，一个由标量组成的向量（\(\vec a\)）和另一个由群元素组成的向量（\(\vec g\)）的乘积，我们将其定义为

\[\begin{align*} \vec a \cdot \vec g = a_0 g_0 + a_1 g_1 + \cdots + a_{n-1} g_{n-1} \end{align*}\]

也就是说，我们要证明 \(C\) 是以下元素的承诺

  • 基为 \(\vec g\) 的向量 \(\vec a\)
  • 基为 \(\vec h\) 的向量 \(\vec b\)
  • 基为 \(q\) 的内积 \(\vec a \cdot \vec b\) 。

单看本身似乎并不是很有用 – 在大多数应用中我们想让验证者知道 \(\vec a \cdot \vec b\)，而不是仅仅将这个结果藏在一个承诺里。这可以通过我后面要讲到的一个小技巧来解决。

证明

我们想让证明者向验证者证明 \(C\) 的确具有形式 \(C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q\)。就像之前提到的，不是直接证明，而是要把这个问题规约成，如果这一性质对于另一个承诺 \(C′\) 成立，则 \(C\) 也满足该性质。

接下来证明者就要和验证者玩一个小游戏了。证明者提交一些信息，然后验证者发起一个挑战，从而引出下一个承诺 \(C′\)。将它称作一个游戏不代表这个证明必须是交互的：Fiat-Shamir算法允许我们通过将挑战换成一个承诺的抗碰撞哈希值，从而将交互式的证明转化成非交互式的。

证明描述

承诺 \(C\) 符合 \(C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q\) 的形式，并且以\(\vec g, \vec h, q\)为基。我们将符合这样形式的 \(C\) 称为拥有“内积性质”。

规约步骤

假设 \(m = \frac{n}{2}\), 证明者计算

\[\begin{align*} z_L = a_m b_0 + a_{m+1} b_1 + \cdots + a_{n-1} b_{m-1} = \vec a_R \cdot \vec b_L \\ z_R = a_0 b_m + a_{1} b_{m+1} + \cdots + a_{m-1} b_{n-1} = \vec a_L \cdot \vec b_R \end{align*}\]

这里我们定义 \(\vec a_L\) 为向量 \(\vec a\) 的“左半部”，\(\vec a_R\) 为“右半部”，向量 \(\vec b\) 类似。

然后证明者计算如下的承诺：

\[\begin{align*} C_L = \vec a_R \cdot \vec g_L + \vec b_L \cdot \vec h_R + z_L q \\ C_R = \vec a_L \cdot \vec g_R + \vec b_R \cdot \vec h_L + z_R q \end{align*}\]

并发送给验证者。然后验证者发送挑战 \(x \in \mathbb F_p\) (通过使用Fiat-Shamir将它变成非交互式的，这意味着 \(x\) 是 \(C_L\) 和 \(C_R\) 的哈希)。证明者以此来计算更新的向量：

\[\begin{align*} \vec a' = \vec a_L + x \vec a_R \\ \vec b' = \vec b_L + x^{-1} \vec b_R \end{align*}\]

长度为原向量的一半。

现在，验证者计算新的承诺：

\[\begin{align*} C' = x C_L + C + x^{-1} C_R \end{align*}\]

还有更新的基：

\[\begin{align*} \vec g' = \vec g_L + x^{-1} \vec g_R \\ \vec h' = \vec h_L + x \vec h_R \end{align*}\]

现在，如果新的承诺 \(C′\) 符合了 \(C' = \vec a' \cdot \vec g' +\vec b' \cdot \vec h' + \vec a' \cdot \vec b' q\)的形式 - 那么承诺\(C\)就遵从最初的假设，拥有“内积性质”。

所有的向量大小都减半 – 这让我们离成功又近一步。在这里我们替换 \(C:=C'\), \(\vec g := \vec g'\)，\(\vec h := \vec h'\) 并重复以上步骤。

接下来我解释这个方法可行的数学原理，同时推荐你们去看看 Vitalik 所做的一个漂亮的可视化展示 以得到一些直观的感受。

最终步骤

当我们一直重复以上步骤，n每次降低一半。最终我们会到达\(n=1\)，然后就可以停下了。这时证明者发送\(\vec a\)和\(\vec b\)两个向量，事实上就是两个标量，然后验证者就可以非常直观地计算：

\[\begin{align*} D = a g + b h + a b q \end{align*}\]

如果等于 \(C\) 就接受，反之则拒绝。

正确性(correctness) 及合理性(soundness)

在之前我假设 \(C′\) 为我们所需要的形式，然后以此证明 \(C\)也成立。现在我要证明为什么该逻辑成立。我们需要验证以下两点：

  • 正确性 – 即当证明者遵从相应操作的时候，它们可以达到说服验证者该结论为正确的目的；
  • 合理性 – 即试图作弊的证明者不能使用错误的证明通过验证者验证，或者成功率低至可忽略不计。

让我们从正确性证起，假设证明者依照操作进行每一个步骤。既然如此，我们知道给定 \(\vec g, \vec h, q\) 为基，\(C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q\)，同时 \(C'= \vec a' \cdot \vec g' +\vec b' \cdot \vec h' + \vec a' \cdot \vec b' q\)。

验证者计算\(C' = x C_L + C + x^{-1} C_R\)。

\[\begin{eqnarray} C' & = & x C_L + C + x^{-1} C_R \\ & = & x ( \vec a_R \cdot \vec g_L + \vec b_L \cdot \vec h_R + z_L q) \\ & & + \vec a_L \cdot \vec g_L + \vec a_R \cdot \vec g_R + \vec b_L \cdot \vec h_L + \vec b_R \cdot \vec h_R + \vec a \cdot \vec b q \\ & & + x^{-1} (\vec a_L \cdot \vec g_R + \vec b_R \cdot \vec h_L + z_R q) \\ & = & (x \vec a_R + \vec a_L)\cdot(\vec g_L + x^{-1} \vec g_R) \\ & & + (\vec b_L + x^{-1} \vec b_R)\cdot(\vec h_L + x \vec h_R) \\ & & + (x z_L + \vec a \cdot \vec b + x^{-1} z_R) q \\ &=& (x \vec a_R + \vec a_L)\cdot \vec g' + (\vec b_L + x^{-1} \vec b_R)\cdot \vec h' + (x z_L + \vec a \cdot \vec b + x^{-1} z_R) q \end{eqnarray}\]

为了使承诺具有内积属性，我们需要验证 \((x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) = x z_L + \vec a \cdot \vec b + x^{-1} z_R\)。这个等式成立，因为

\[\begin{eqnarray} (x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) & = & x \vec a_R \cdot \vec b_L + \vec a_L \cdot \vec b_L + \vec a_R \cdot \vec b_R + x^{-1} \vec a_L \cdot \vec b_R \\ & = & x z_L + \vec a \cdot \vec b + x^{-1} z_R \end{eqnarray}\]

这样正确性就证明了。为证明合理性，我们需要证明，证明者的初始承诺 \(C\) 不具有内积属性，那么通过规约步骤，是无法产生一个具有内积属性的承诺 \(C'\)。

假设证明者提交了 \(C=\vec a \cdot \vec g + \vec b \cdot \vec h + r q\)，其中 \(r \neq \vec a \cdot \vec b\)。如果我们走一遍如上的规约步骤，我们会得到

\[\begin{align*} C' = (x \vec a_R + \vec a_L)\cdot \vec g' + (\vec b_L + x^{-1} \vec b_R)\cdot \vec h' + (x z_L + r + x^{-1} z_R) q \end{align*}\]

所以现在我们假设证明者成功作弊，那么 \(C′\) 就满足了内积属性，则有：

\[\begin{align*} (x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) = x z_L + r + x^{-1} z_R \end{align*}\]

展开左侧可得

\[\begin{align*} x \vec a_R \cdot \vec b_L + \vec a \cdot \vec b + x^{-1} \vec a_L \cdot \vec b_R = x z_L + r + x^{-1} z_R \end{align*}\]

注意证明者可以自由选择 \(z_L\) 和 \(z_R\)，所以我们不能直接假设它们会遵从以上定义。

同时乘以 \(x\) 并移到同一边，我们得到 \(x\) 的二次方程式：

\[\begin{align*} x^2 ( \vec a_R \cdot \vec b_L - z_L) + x (\vec a \cdot \vec b - r) + (\vec a_L \cdot \vec b_R - z_R ) \end{align*}\]

除非所有项都为零，该等式至多会有两个解 \(x \in \mathbb F_p\)，但是验证者是在证明者已经承诺了他们的 \(r\), \(z_L\) 和 \(z_R\)值后选择 \(x\)值，证明者能够成功作弊的概率非常小；我们通常选择域 \(\mathbb F_p\) 大小约为 \(2^{256}\)。因此，当证明者不按照协议选择正确值时，验证者选择到一个让等式能够成立的 \(x\) 值的概率微乎其微。

这就完成了我们的合理性证明。

仅在最后计算基变化

验证者在每一轮都需要做两件事：计算挑战 \(x\)，并计算更新的基 \(\vec g'\) 和 \(\vec h'\)。但是在每一轮都更新 \(g\) 效率很低，验证者可以简单地保存他们在 \(k\) 轮中遇到的挑战值 \(x_1 , x_2 \dots x_k\)。

假设\(k\)轮后，这些基为 \(\vec g_k, \vec h_k\)。元素\(g_\ell\)和\(h_\ell\)是标量（或者长度为1的向量），因为长度到达1的时候我们会终止协议。通过\(\vec g_0\)计算\(\vec g_\ell\)，是一个长度为n的椭圆曲线上的多标量点乘（MSM）。\(\vec g_0\)的标量因子是下面多项式的系数

\[\begin{align*} f_g(X) = \prod_{j=0}^{k-1} \left(1+x^{-1}_{k-j} X^{2^{j}}\right) \end{align*}\]

且\(\vec h_0\)的标量因子由以下多项式给定

\[\begin{align*} f_h(X) = \prod_{j=0}^{k-1} \left(1+x_{k-j} X^{2^{j}}\right) \end{align*}\]

使用内积证明来验证多项式值

针对我们的主要应用 – 验证 \(f(x) = \sum_{i=1}^{n-1} a_i x^i\)在\(z\)处的取值 – 我们需要对协议做一些小的扩充。

  • 最重要的一点是，我们想要验证 \(f(z) = \vec a \cdot \vec b\) 的结果，而不仅是承诺 \(C\) 拥有“内积属性”。
  • \(\vec b = (1, z, z^2, ..., z^{n-1})\) 对于验证者来说是已知的。因此我们可以把这部分从承诺中移除来简化协议。

如何构造承诺

如果我们想要验证多项式\(f(x) = \sum_{i=1}^{n-1} a_i x^i\)，我们通常需要从承诺\(F = \vec a \cdot \vec g\)开始进行构造。证明者可以将\(y=f(z)\)的计算发送给验证者。

那么貌似验证者可以计算最初的承诺\(C=\vec a \cdot \vec g + \vec b \cdot \vec h + \vec a \cdot \vec b q = F + \vec b \cdot \vec h + f(z) q\)，因为他们已知\(\vec b = (1, z, z^2, ..., z^{n-1})\)，然后开始证明流程。

但稍等一下。大多数情况下，\(F\)是证明者生成的承诺，一个恶意的证明者可以在这里作弊，比如说提交一个\(F = \vec a \cdot \vec g + tq\)。在这种情况下，因为证明者生成的承诺有一个偏移，他们能够证明\(f(z) = y - t\)。

为了避免这种情况，我们需要在证明流程中进行一点改变。 收到承诺\(F\)和计算结果\(y\)后，验证者生成一个向量\(w\)并且重新选择基\(q:=wq\)，之后证明继续。因为证明者不能预判\(w\)的取值，它们就无法成功操控除了\(f(z)\)之外的结果（或者说概率极小）。

注意如果想要得到一个通用的内积，我们还要防止证明者操控向量\(\vec b\) – 但在多项式取值的应用中，\(\vec b\)的部分可以完全去掉不用考虑，因此这里略过细节。

如何去掉第二个向量

注意，如果我们想要进行多项式计算，验证者已知向量\(\vec b = (1, z, z^2, ..., z^{n-1})\)。给定挑战\(x_0, x_1, \ldots, x_\ell\)，他们可以通过在“仅在最终计算基变化”一节中提到的技巧简单地得到\(b_\ell\)。

因此，我们可以从所有承诺中移除第二个向量并且只计算\(b_\ell\)。这意味着验证者必须要能够从初始向量\(\vec b_0 = (1, z, z^2, ..., z^{n-1})\)中计算最终的\(b_\ell\)。因为\(\vec b\)的规约过程与基向量\(\vec g\)相同，线性组合也由之前定义的多项式\(f_g\)的系数定义，也就是说\(b_\ell=f_g(z)\)。

针对点值形式多项式的IPA

目前为止，我们用一个内积证明计算了使用它的系数提交的多项式，即一个由\(f(X) = \sum_{i=0}^{n-1} f_i X^i\)定义的多项式中的\(f_i\)。然而，多数情况下我们想要一个在给定定义域\(x_0, x_1, \ldots, x_{n-1}\)计算值定义的多项式。因为任何阶低于\(n−1\)的多项式都是由\(f(x_0), f(x_1), \ldots, f(x_{n-1})\)的计算结果定义的独一无二的多项式，所以这两者是完全相等的。但是这两者之间的转换在计算上非常费时，如果定义域适用快速傅立叶转换的话需要花费\(O(n \log n)\)次计算，否则就是\(O(n^2)\)次。

为了避免这项开销，我们尝试避免使用多项式系数形式。这可以通过提交多项式值\(f\)的承诺的而不是系数的承诺来实现：

\[\begin{align*} C = f(x_0) g_0 + f(x_1) g_1 + \cdots + f(x_{n-1}) g_{n-1} \end{align*}\]

这表示我们IPA的向量\(\vec a\)形式为\(\vec a = (f(x_0), f(x_1), \ldots, f(x_{n-1}))\)：

重心公式 使我们现在可以计算这个新的承诺多项式的取值，记作：

\[\begin{align*} f(z) = A(z)\sum_{i=0}^{n-1} \frac{f(x_i)}{A'(x_i)} \frac{1}{z-x_i} \end{align*}\]

如果我们选择向量\(\vec b\)

\[\begin{align*} b_i = \frac{A(z)}{A'(x_i)} \frac{1}{z-x_i} \end{align*}\]

我们可以得到\(\vec a \cdot \vec b = f(z)\)，因此采用这种向量的IPA可以被用作证明点值多项式的取值。除了这一点差异之外，其他的证明过程是完全相同的。

  1. Bowe, Grigg, Hopwood: Recursive Proof Composition without a Trusted setup ↩ ↩

  2. Bootle, Cerulli, Chaidos, Groth, Petit: Efficient Zero-Knowledge Arguments forArithmetic Circuits in the Discrete Log Setting ↩ ↩