运算证明

现在我们来修改一下最新协议，使它支持单个乘法计算的证明。回想一下，我们已经有多项式 \(p(x)\) 的知识证明了，但现在要处理三个多项式 \(l(x), r(x), o(x)\)。虽然我们可以定义 \(p(x) = l(x) \times r(x) - o(x)\)，但这里存在两个争议点。首先，在我们的协议中证明阶段是不能做加密值乘法计算的（即 \(l(s) \times r(s)\)），因为配对只能使用一次，要用在多项式限制的检查上。第二，这里给证明者留下了一个可以修改多项式结构但依然保留有效辅因子 \(t(x)\) 的机会，例如可以令 \(p(x) = l(x)\) 或者 \(p(x) = l(x) - r(x)\) 甚至是 \(p(x) = l(x) \times r(x) + o(x)\)，只要这里的 \(p(x)\) 还保留着根 \(a\) 就可以。这种修改本质上是让证明的内容变成了别的陈述，这当然是我们不希望发生的。

所以证明者必须要分别提供多项式 \(l(s)\)、\(r(s)\)、\(o(s)\) 的求值。这意味着必须调整多项式的知识。本质上，验证者需要在加密空间中检查的是 \(l(s) \times r(s) - o(s) = t(s) h(s)\)。虽然验证者可以使用密码学配对执行乘法，但减法（\(-o(x)\)）是一项昂贵的操作（需要找到 \(g^{o(s)}\) 的逆元），这就是我们要将 \(o(x)\) 移到等式右侧的原因：\(l(x) r(x) = t(x) h(x) + o(x)\)。在加密空间中，验证者的检查就可以转换为：

$$e\left(g^{l(s)}, g^{r(s)}\right) = e\left(g^{t(s)}, g^{h(s)}\right) \cdot e\left(g^{o(s)}, g\right)$$

$$e(g, g)^{l(s) r(s)} = e(g,g)^{t(s)h(s)} \cdot e(g,g)^{o(s)}$$

$$e(g, g)^{l(s) r(s)} = e(g,g)^{t(s)h(s) + o(s)}$$

注：回想一下，密码学配对的结果是支持通过乘法实现加密值加法的，参见 3.6.1 节。

保持设置阶段不变，协议更新为：

• 证明
  • 将相应的系数赋值给 \(l(x)\)、\(r(x)\)、\(o(x)\)
  • 求多项式 \(h(x) = \frac{l(x) \times r(x) - o(x)}{t(x)}\)
  • 代入 \(\left\lbrace g^{s^i} \right\rbrace_{i \in [d]}\) 计算多项式 \(g^{l(s)}\)、\(g^{r(s)}\)、\(g^{o(s)}\) 和 \(g^{h(s)}\) 的值
  • 代入 \(\left\lbrace g^{\alpha s^i} \right\rbrace_{i \in \{0, \ldots, d\}}\) 计算移位多项式 \(g^{\alpha l(s)}\)、\(g^{\alpha r(s)}\)、\(g^{\alpha o(s)}\) 的值
  • 构造证明 \(\pi = \left( g^{l(s)}, g^{r(s)}, g^{o(s)}, g^{h(s)}, g^{\alpha l(s)}, g^{\alpha r(s)}, g^{\alpha o(s)} \right)\)
• 验证
  • 将证明 \(\pi\) 解析为 \(\left( g^l, g^r, g^o, g^h, g^{l'}, g^{r'}, g^{o'} \right)\)
  • 检查多项式限制： $$e(g^{l'}, g) = e(g^{l}, g^\alpha)$$ $$e(g^{r'}, g) = e(g^{r}, g^\alpha)$$ $$e(g^{o'}, g) = e(g^{o}, g^\alpha)$$
  • 检查运算的有效性：\(e\left(g^{l}, g^{r}\right) = e\left(g^{t(s)}, g^{h}\right) \cdot e\left(g^{o}, g\right)\)

这样的协议就能证明两个值相乘的结果是正确计算的了。

你可能会注意到，在更新后的协议中我们放弃了零知识组件。这样做是为了让过渡更加简单。我们将在后面的部分将它添加回协议中。