内积证明

原文链接： Inner Product Arguments

翻译：Star.LI @ Trapdoor Tech

介绍

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

$$\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 ², 其中多个打开的线性成本可以被聚合。

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

但是，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 ↩ ↩