跨操作数的变量一致性

对于任何变量 \(v_i\)，我们必须将其值赋给每个对应操作数的变量多项式，即 \(\left(g^{l_i(s)}\right)^{v_i}, \left(g^{r_i(s)}\right)^{v_i}, \left(g^{o_i(s)}\right)^{v_i}\)。因为每个操作数多项式的有效性都是单独检查的，所以没有强制要求在相应的变量多项式中使用相同的变量值。这意味着左操作数中变量 \(v_i\) 的值可能与右操作数或输出中变量 \(v_i\) 的值不同。

我们可以使用已经熟悉的限制多项式的方法来强制跨操作数的变量值相等（就像我们对变量多项式所做的那样）。如果我们可以在所有操作数上创建一个「移位校验和」变量多项式，就可以限制证明者只能赋相同的值。验证者可以将每个变量的多项式组合成一个，例如 \(g^{l_i(s) + r_i(s) + o_i(s)}\)，并将其移位一些另外的随机值 \(\beta\)，即 \(g^{\beta\left(l_i(s) + r_i(s) + o_i(s)\right)}\)。这个移位的多项式会被提供给证明者，来将变量与变量多项式一起赋值：

$$\left(g^{l_i(s)}\right)^{v_{L,i}}, \left(g^{r_i(s)}\right)^{v_{R,i}}, \left(g^{o_i(s)}\right)^{v_{O,i}}, \left(g^{\beta(l_i(s) + r_i(s) + o_i(s))}\right)^{v_{\beta,i}}$$

接着 \(\beta\) 被加密为 \(g^\beta\) 并添加到验证密钥中。现在，如果所有 \(v_i\) 的值都相同（即 \(v_{L,i} = v_{R,i} = v_{O,i} = v_{\beta,i}\)，其中 \(i \in \{1, \ldots, n\}\)），则下面的等式应成立：

$$e\left( g^{v_{L,i} \cdot l_i(s)} \cdot g^{v_{R,i} \cdot r_i(s)} \cdot g^{v_{O,i} \cdot o_i(s)}, g^\beta \right) = e\left( g^{v_{\beta,i} \cdot \beta(l_i(s) + r_i(s) + o_i(s))}, g \right)$$

尽管这个一致性校验很有用，但由于 \(l(s), r(s), o(s)\) 中的至少两个可能具有相同的计算值、一个多项式可被另一个整除等等发生的概率不可忽略，这将允许证明者将值 \(v_{L,i}, v_{R,i}, v_{O,i}, v_{\beta,i}\) 分解为至少其中两个不相等但保持等式成立，从而使检查无效：

$$\left(v_{L,i} \cdot l_i(s) + v_{R,i} \cdot r_i(s) + v_{O,i} \cdot o_i(s)\right) \cdot \beta = v_{\beta,i} \cdot \beta\cdot\left(l_i(s) + r_i(s) + o_i(s)\right)$$

例如，让我们考虑一个单一运算，其中 \(l(x) = r(x)\)。我们把这两个的值表示为 \(w = l(s) = r(s)\) 和 \(y = o(x)\)。等式将如下所示：

$$\beta (v_{L}\ w + v_{R}\ w + v_{O}\ y) = v_{\beta} \cdot \beta (w + w + y)$$

对于任意的 \(v_{R}\) 和 \(v_{O}\)，这种形式允许令 \(v_{\beta} = v_{O}\)，\(v_{L} = 2 v_{O} - v_{R}\)，此时转化为：

$$\beta (2 v_O\ w - v_{R}\ w + v_{R}\ w + v_{O}\ y) = v_O \cdot \beta (2w + y)$$

因此，这种一致性策略是无效的。缓解这种情况的一种方法是对每个操作数使用不同的 \(\beta\)，确保操作数的变量多项式具有不可预测的值。以下是协议的修改：

• 设置
  • \(\ldots\) 选择随机值 \(\beta_{l}, \beta_{r}, \beta_{o}\)
  • 计算、加密变量一致性多项式并添加到证明密钥： $$\left\{ g^{\beta_{l} l_i(s) + \beta_{r} r_i(s) + \beta_{o} o_i(s)} \right\}_{i \in \{1,\ldots,n\}}$$
  • 加密 \(\beta\) 并添加到验证密钥：\(\left( g^{\beta_{l}}, g^{\beta_{r}}, g^{\beta_{o}} \right)\)
• 证明
  • \(\ldots\) 将变量值赋给变量一致性多项式： $$g^{z_i(s)} = \left( g^{\beta_{l} l_i(s) + \beta_{r} r_i(s) + \beta_{o} o_i(s)} \right)^{v_i}\quad 其中 \ i \in \{1,\ldots,n\}$$
  • 在加密空间中添加赋值的多项式： $$g^{Z(s)} = \prod_{i=1}^n g^{z_i(s)} = g^{\beta_{l} L(s) + \beta_{r} R(s) + \beta_{o} O(s)}$$
  • 添加到证明中：\(g^{Z(s)}\)
• 验证
  • \(\ldots\) 检查提供的操作数多项式和「校验和」多项式之间的一致性： $$e\left( g^{L}, g^{\beta_{l}} \right) \cdot e\left( g^{R}, g^{\beta_{r}} \right) \cdot e\left( g^{O}, g^{\beta_{o}} \right) = e\left( g^{Z}, g \right)$$ 这相当于： $${e\left( g,g \right)}^{\beta_{l} L + \beta_{r} R + \beta_{o} O} = {e\left( g,g \right)}^{Z}$$

使用相同的变量值来中和的技术将在这种结构中失败，因为不同的 \(\beta\) 使相同的多项式不适合操纵。然而，还有一个类似于备注 4.1 的缺陷，具体来说，由于 \(g^{\beta_l}, g^{\beta_r}, g^{\beta_o}\) 项是公开可用的，所以对手可以修改任何变量多项式的零指数系数，因为它不依赖于 \(s\)，即 \(g^{\beta_l s^0} = g^{\beta_l}\)。

译者注：上文我们通过在设置阶段设置数学表达式的约束关系解决了一些问题，但这里似乎又引入了新问题：如何保证证明者构造的证明是遵循这些约束关系计算出来的呢？

KEA 其实已经解决了这个问题，但似乎并不完美，这就是下面要讨论的变量延展性问题。