计算的零知识证明

自从引入通用计算协议（4.4 节运算证明）以来，我们不得不放弃零知识属性来让过渡更加简单。现在，我们已经构建了一个可验证计算协议。

以前为了构造多项式的零知识证明，我们使用了随机 \(\delta\)-移位，这使得证明与随机无法区分（3.5 节）：

$$\delta p(s) = t(s) \cdot \delta h(s)$$

通过计算，我们证明：

$$L(s) \cdot R(s) - O(s) = t(s)h(s)$$

虽然我们可以使用相同的 \(\delta\) 将这种方法应用于多个多项式，即提供随机值 \(\delta L(s), \delta R(s), \delta^2 O(s), \delta^2 h(s)\)，这将通过配对满足运算的有效性检查：

$$e\left(g, g \right)^{\delta^2 L(s) R(s)} = e(g,g)^{\delta^2 \left(t(s) h(s) + O(s) \right)}$$

问题是相同的 \(\delta\) 会妨碍安全性，因为我们在证明中分别提供了这些值：

• 可以很容易地识别两个不同多项式的值是否相同（例如，\(g^{\delta L(s)} = g^{\delta R(s)}\) 等等），也就是可以学习到一些知识
• \(L(s)\) 和 \(R(s)\) 值之间的潜在微小差异可以允许通过暴力破解来分解，例如，如果 \(L(s) = 5R(s)\)，迭代检查 \(g^{L(s)} = \left( g^{R(s)} \right)^i\)，其中 \(i \in \{1 ... N\}\) 只需 5 步即可揭示 \(5\times\) 的差异。可以对加密的加法运算执行相同的暴力破解，例如，\(g^{L(s)} = g^{R(s) + 5}\)
• 可以发现证明中元素之间的其他相关性，例如，如果 \(e(g^{\delta L(s)}, g^{\delta R(s)}) = e(g^{\delta^2 O(s)}, g)\) 则 \(L(x) \cdot R(x) = O(x)\) 等等

注：优化 4.9.4 使此类数据挖掘变得更加困难，但仍然允许发现其中的关系，除了验证者可以用有助于揭示知识的特定方式选择 \(\rho_l, \rho_r\)（只要它不是一种多元化的设置）这一事实。

因此，我们需要让每个多项式的值具有不同的随机性（\(\delta\)），例如：

$$\delta_l L(s) \cdot \delta_r R(s) - \delta_o O(s) = t(s) \cdot (\Delta\ \ \unicode{x003F}\unicode{x2009}\unicode{x20DD}\ h(s))$$

为了解决右侧的不相等，我们修改证明的值 \(h(s)\) 相比更改协议显得更为可取。这里的 Delta（\(\Delta\)）代表我们需要应用到 \(h(s)\) 来抵消等式另一边的随机性的差异，\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD}\) 代表乘法或加法运算（反过来也适应除法和减法）。如果我们选择通过乘法（\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD} = \times\)）应用 \(\Delta\)，这意味着不可能以压倒性的概率找到 \(\Delta\)，因为存在随机性：

$$\Delta = \frac{\delta_l L(s) \cdot \delta_r R(s) - \delta_o O(s)}{t(s) h(s)}$$

我们可以设置 \(\delta_o = \delta_l \cdot \delta_r\)，于是转换为：

$$\Delta = \frac{\delta_l \delta_r( L(s) \cdot R(s) - O(s))}{t(s) h(s)} = \delta_l \delta_r$$

然而，如上文所述，这阻碍了零知识属性，更重要的是，这种结构将不会适应验证者的输入多项式，因为它们必须是相应 \(\delta\) 的倍数，这将需要交互。

我们可以尝试在求值中添加随机性：

$$(L(s) + \delta_l) \cdot (R(s) + \delta_r) - (O(s) + \delta_o) = t(s) \cdot (\Delta \times h(s))$$

$$\Delta = \frac{ \overbrace{L(s) R(s) - O(s)}^{t(s) h(s)} + \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o }{t(s) h(s)} = 1 + \frac{\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o}{t(s) h(s)}$$

但是由于随机性，它是不能被整除的。即使我们通过将每个 \(\delta\) 乘以 \(t(s)h(s)\) 来解决这个问题，由于我们通过 \(h(s)\) 的乘法来应用 \(\Delta\)，并且 \(\Delta\) 将包含加密的求值（即 \(g^{L(s)}\) 等等），如果不使用配对，就不可能计算 \(g^{\Delta h(s)}\)（结果在另一个数字空间中）。同样，通过使用加密幂 \(\left\{ g^{s^i} \right\}_{i \in [d]}\) 对 \(\Delta h(x)\) 进行加密求值是不可能的，因为 \(h(x)\) 和 \(\Delta\) 的阶数是 \(d\)，因此 \(\Delta h(x)\) 的阶数高达 \(2d\)。此外，出于同样的原因，不可能计算这种随机操作数多项式求值 \(g^{L(s) + \delta_l t(s)h(s)}\)。

因此，我们应该尝试通过加法（\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD} = +\)）应用 \(\Delta\)，因为它可以用于同态加密的值。

$$(L(s) + \delta_l) \cdot (R(s) + \delta_r) - (O(s) + \delta_o) = t(s) \cdot (\Delta + h(s))$$

$$\Delta = \frac{ L(s) R(s) - O(s) + \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o - t(s) h(s)}{t(s)} \Rightarrow$$

$$\Delta = \frac{ \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o}{t(s)}$$

分子中的每一项都是 \(\delta\) 的倍数，因此我们可以将每个 \(\delta\) 与 \(t(s)\) 相乘来让它可以被整除：

$$(L(s) + \delta_l t(s)) \cdot (R(s) + \delta_r t(s)) - (O(s) + \delta_o t(s)) = t(s) \cdot (\Delta + h(s))$$

$$\color{yellow}{L(s) R(s) - O(s)} + t(s) (\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o) = t(s) \Delta + \color{yellow}{t(s) h(s)}$$

$$t(s) (\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o) = t(s) \Delta$$

$$\Delta = \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o$$

这样就可以在加密空间中有效地计算了：

$$g^{L(s) + \delta_l t(s)} = g^{L(s)} \cdot \left( g^{t(s)} \right)^{\delta_l} \ ,\quad 等等$$

$$g^\Delta = \left( g^{L(s)} \right)^{\delta_r} \cdot \left( g^{R(s)} \right)^{\delta_l} \cdot \left( g^{t(s)} \right)^{\delta_l \delta_r} g^{-\delta_o}$$

这样既可以通过运算的有效性检查，又可以隐藏加密值。

$${L\cdot R - O} + {\color{magenta}{t(\delta_r L + \delta_l R + \delta_l \delta_r t - \delta_o)}} = t(s) h + {\color{magenta}{t(s) (\delta_r L + \delta_l R + \delta_l \delta_r t - \delta_o)}}$$

由于添加了 \(\delta_l, \delta_r, \delta_o\) 的均匀随机倍数，该结构在统计上是零知识的（参见 [Gen+12] 的定理 13）。

注：这种方法也与验证者的操作数一致，例如 \(g_l^{L_p + \delta_l t} \cdot g_l^{L_v} = g_l^{L_p + L_v + \delta_l t}\)，因此运算的有效性检查仍然成立，但仅当证明者使用验证者的值来构造证明时才成立（即 \(\Delta = \delta_r (L_p + L_v) + \delta_l (R_p + R_v) + \delta_l \delta_r t - \delta_o\)），请参阅下一节了解更多详细信息。

为了使「变量多项式限制」和「变量值一致性」检查与零知识更改一致，有必要将以下参数添加到证明密钥中：

$$g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)}, g_r^{\beta t(s)}, g_o^{\beta t(s)}$$

非常奇怪的是，最初的 Pinocchio 协议 [Par+13] 主要关注可验证计算，很少关注零知识属性，但这只是一个小的修改，几乎是无成本的。

译者注：与前文的零知识方案不同，这里通过相加而不是相乘的方式来确保证明者知识的零知识性。

Pinocchio 协议是针对 [GGPR] 论文的改进，在 3.1 节中也提到了实现零知识只需要沿用 [GGPR] 论文的方法即可，并不是这篇论文的贡献。另外，Pinocchio 协议的论文侧重工程实践，在 2013 年时，零知识证明还没有得到应用，真正的应用还是从匿名币 Zcash 开始的。