公开输入和一

如果无法根据验证者的输入检查证明,那么证明的可用性将会受到限制,例如,知道证明者在不知道结果和 / 或值是什么的情况下将两个值相乘。虽然可以在证明密钥中「硬编码」要检查的值(例如,乘法的结果必须始终为 12),但这就需要为每个所需的「验证者的输入」生成单独的密钥对。

译者注:这样会严重限制实用性,电路需要支持参数。

因此,如果可以由验证者而不是证明者为计算指定一些值(输入或 / 和输出),包括 \(v_{one}\),就可以变得更加通用了。

首先,让我们考虑证明值 \(\color{ForestGreen}{g^{L(s)}}, \color{blue}{g^{R(s)}}, \color{red}{g^{O(s)}}\)。由于我们使用的是同态加密,所以可以增加这些值,例如,我们可以添加另一个加密多项式求值 \(g^{L(s)} \cdot g^{l_v(s)} = g^{L(s) + l_v(s)}\),这意味着验证者可以将其他变量多项式添加到已经提供的多项式中。因此,如果我们可以从证明者可用的变量多项式中排除必要的变量多项式,验证者将能够在这些变量上设置他的值,而计算检查应该仍然能够匹配。

这很容易实现,因为验证者已经在选择多项式时限制了证明者,他可以使用 \(\alpha\)-移位。因此,这些变量多项式可以从证明密钥移动到验证密钥,同时消除在 \(\alpha\) 和 \(\beta\) 校验和中的对应项。

必要的协议更新:

  • 设置
    • \(\ldots\) 将所有 \(n\) 变量多项式分成两组:
      • 验证者的 \(m + 1\): $$L_v(x) = l_0(x) + l_1(x) + \ldots + l_m,R_v(x) \ 和 \ O_v(x) \ 同理$$ 其中索引 \(0\) 为 \(v_{one} = 1\) 的值保留
      • 证明者的 \(n - m\): $$L_p(x) = l_{m+1}(x) + \ldots+ l_n(x),R_p(x) \ 和 \ O_p(x) \ 同理$$
    • 生成证明密钥: $$\left( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)}, g_l^{\alpha_l l_i(s)}, g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)}, g_l^{\beta l_i(s)} \cdot g_r^{\beta r_i(s)} \cdot g_o^{\beta o_i(s)} \right\}_{i \in \{m + 1, \ldots, n\}} \right)$$
    • 添加到验证密钥: $$\left( \ldots, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, m\}} \right)$$
  • 证明
    • \(\ldots\) 根据验证者的多项式计算 \(h(x)\):\(\displaystyle h(x) = \frac{L(x)\cdot R(x) - O(x)}{t(x)}\),其中 \(L(x) = L_v(x) + L_p(x)\),\(R(x), O(x)\) 同理
    • 提供证明: $$\left( g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g_l^{\alpha_l L_p(s)}, g_r^{\alpha_r R_p(s)}, g_o^{\alpha_o O_p(s)}, g^{Z(s)}, g^{h(s)} \right)$$
  • 验证
    • 为验证者的变量多项式赋值并与 1 相加: $$g_l^{L_v(s)} = g_l^{l_0(s)} \cdot \prod_{i=1}^m \left( g_l^{l_i(s)} \right)^{v_i},g_r^{R_v(s)} \ 和 \ g_o^{O_v(s)} \ 同理$$
    • 检查变量多项式限制: $$e\left( g_l^{L_p}, g^{\alpha_l} \right) = e\left( g_l^{L'_p}, g \right),g_r^{R_p} \ 和 \ g_o^{O_p} \ 同理$$
    • 检查变量值一致性: $$e\left( g_l^{L_p} g_r^{R_p} g_o^{O_p}, g^{\beta \gamma} \right) = e\left( g^{Z}, g^{\gamma} \right)$$
    • 检查运算的有效性: $$e\left( g_l^{L_v(s)} g_l^{L_p}, g_r^{R_v(s)} g_r^{R_p} \right) = e\left( g_o^{t}, g^{h} \right) \cdot e\left( g_o^{O_v(s)} g_o^{O_p}, g \right)$$

注:根据协议属性(4.6.1 节),由多项式 \(l_0(x), r_0(x), o_0(x)\) 表示的 \(1\) 在相应的运算中已经具有了适当的值,因此不需要再赋值。

注:验证者将不得不在验证步骤中做额外的工作,这与他赋值的变量数量成正比。

实际上,这将证明者的一些变量交到了验证者的手中,同时仍然保持等式的平衡。因此,运算的有效性检查应该仍然成立,但前提是证明者使用的值与验证者用于输入的值相同。

\(1\) 这个值是必不可少的,它允许通过乘以常数项来派生任何数字(在所选的有限域中),例如,将 \(a\) 乘以 \(123\):

$$\color{ForestGreen}{1 \cdot a}\quad \times \quad\color{blue}{123 \cdot v_{one}}\quad = \quad\color{red}{1 \cdot r}$$

译者注:这里将原本由证明者赋值的一些变量改为由验证者赋值,使得证明者不得不与验证者保持相同的输入。这不仅解决了验证者参数输入的问题,也间接解决了常数赋值的问题。