变量和变量一致性多项式的非延展性

变量多项式的延展性

让我们用以下两个运算作为例子来说明备注 4.1：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{b}$$

$$\color{ForestGreen}{3a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{c}$$

预期结果是 \(b = a\) 和 \(c = 3a\)，有明确的 \(c = 3b\) 的关系。这意味着左操作数的变量多项式的求值为 \(l_a(1) = 1\) 和 \(l_a(2) = 3\)。无论 \(l_a(x)\) 的形式如何，证明者都可以通过提供修改的多项式 \(l'_a(x) = a l_a(x) + 1\) 来不成比例地赋 \(a\) 的值。因此求值将会变成 \(l'_a(1) = a + 1\) 和 \(l'_a(2) = 3a + 1\)，结果 \(b = a + 1\)，\(c = 3a + 1\)，其中 \(c \neq 3b\)，实际上意味着 \(a\) 的值在不同的运算中是不一样的。

因为证明者已知 \(g^{\alpha_l}\) 和 \(g^{\beta_l}\)，所以他可以同时满足正确的操作数多项式和变量值一致性检查：

  • \(\ldots\) 证明
    • 通过不成比例地赋值变量 \(a\) 来构造左操作数多项式： $$L(x) = a \cdot l_a(x) + 1$$
    • 用常规方式构造右操作数和输出多项式： $$R(x) = r_1(x),\ O(x) = b \cdot o_b(x) + c \cdot o_c(x)$$
    • 计算余数 \(h(x) = \frac{L(x)\cdot R(x) - O(x)}{t(x)}\)
    • 计算加密值：\(g^{L(s)} = \left( g^{l_a(s)} \right)^a \cdot g^1\)，用常规方式计算 \(g^{R(s)}, g^{O(s)}\)
    • 计算 \(\alpha\)-移位：\(g^{\alpha L(s)} = \left( g^{\alpha l_a(s)} \right)^a \cdot g^\alpha\)，用常规方式计算 \(g^{\alpha R(s)}, g^{\alpha O(s)}\)
    • 计算变量一致性多项式： $$g^{Z(s)} = \prod_{i \in \{1, a, b, c\}} \left( g^{\beta_l l_i(s) + \beta_r r_i(s) + \beta_o o_i(s)} \right)^i \ \cdot g^{\beta_l} = g^{\beta_l (L(s) + 1) + \beta_r R(s) + \beta_o O(s)}$$ （其中下标 \(_i\) 代表对应变量的符号，指数 \(^i\) 代表变量的值；此外，未定义的变量多项式等于零。）
    • 构造证明：\(\left( g^{L(s)}, g^{R(s)}, g^{O(s)}, g^{\alpha_l L(s)}, g^{\alpha_r R(s)}, g^{\alpha_o O(s)}, g^{Z(s)}, g^{h(s)} \right)\)
  • 验证
    • 检查变量多项式限制： $$e\left( g^{L'}, g \right) = e\left( g^{L}, g^\alpha \right) \ \ \Rightarrow \ \ e\left( g^{\alpha a \cdot l_a(s) + \alpha}, g \right) = e\left( g^{a l_a(s) + 1}, g^\alpha \right)$$ 用常规方式计算 \(g^{R'}, g^{O'}\)
    • 检查变量值一致性 $$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) \Rightarrow$$ $${e\left( g, g \right)}^{(a\cdot l_a + 1) \beta_l + R\beta_r + O\beta_o} = e\left( g, g \right)^{\beta_l (L + 1) + \beta_r R + \beta_o O}$$
    • 检查运算的有效性 \(e(g^{L}, g^{R}) = e(g^{t}, g^{h}) \cdot e(g^{O}, g)\)

变量一致性多项式的延展性

此外，可以使用 \(g^{\beta_l}, g^{\beta_r}, g^{\beta_o}\) 就允许在不同的操作数中使用相同变量的不同值。例如，如果我们有一个运算：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{a}\quad = \quad\color{red}{b}$$

可以用变量多项式表示：

$${\color{ForestGreen}{l_a(x) = x}},\quad {\color{blue}{r_a(x) = x}},\quad {\color{red}{o_a(x) = 0}}$$

$${\color{ForestGreen}{l_b(x) = 0}},\quad {\color{blue}{r_b(x) = 0}},\quad {\color{red}{o_b(x) = x}}$$

虽然我们预期的输出是 \(b = a^2\)，但我们可以设置不同的 \(a\) 值，例如 \({\color{ForestGreen}{a = 2}}\)，\({\color{blue}{a = 5}}\) 如下：

  • 证明
    • \(\ldots\) 用 \(a = 2\) 构造左操作数多项式：\(L(x) = 2 l_a(x) + 10 l_b(x)\)
    • 用 \(a = 5\) 构造右操作数多项式：\(R(x) = 2 r_a(x) + 3 + 10 r_b(x)\)
    • 用 \(b = 10\) 构造输出多项式：\(O(x) = 2 o_a(x) + 10 o_b(x)\)
    • \(\ldots\) 计算加密值： $$g^{L(s)} = \left( g^{l_a(s)} \right)^2 \cdot \left( g^{l_b(s)} \right)^{10} = g^{2l_a(s) + 10 l_b(s)}$$ $$g^{R(s)} = \left( g^{r_a(s)} \right)^2 \cdot (g)^3 \cdot \left( g^{r_b(s)} \right)^{10} = g^{2r_a(s) + 3 + 10 r_b(s)}$$ $$g^{O(s)} = \left( g^{o_a(s)} \right)^2 \cdot \left( g^{o_b(s)} \right)^{10} = g^{2 o_a(s) + 10 o_b(s)}$$
    • 计算变量一致性多项式： $$g^{Z(s)} = \left( g^{\beta_l l_a(s) + \beta_r r_a(s) + \beta_o o_a(s)} \right)^{2} \ \cdot \left( g^{\beta_r} \right)^{3} \cdot \left( g^{\beta_l l_b(s) + \beta_r r_b(s) + \beta_o o_b(s)} \right)^{10} = $$ $$g^{\beta_l \left(2 l_a(s) + 10 l_b(s) \right)\ +\ \beta_r (2 r_a(s) + 3 + 10 r_b(s))\ +\ \beta_o (2 o_a(s) + 10 o_b(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)$$

注：多项式 \(o_a(x), l_b(x), r_b(x)\) 其实可以忽略不计，因为它们对于任何 \(x\) 的计算结果都为 0，但是为了完整性，我们仍然保留它们。

这种能力破坏了证明的可靠性（Soundness）。很明显，不应该将加密的 \(\beta\) 提供给证明者。

非延展性

解决延展性的一种方法是在设置阶段将 \(g^{\beta_l},\ g^{\beta_r},\ g^{\beta_o}\) 在加密空间中乘以随机秘密值 \(\gamma\)（Gamma）来使验证密钥中的 \(g^{\beta_l},\ g^{\beta_r},\ g^{\beta_o}\) 与 \(g^{Z(s)}\) 不兼容：\(g^{\beta_l \gamma},\ g^{\beta_r \gamma},\ g^{\beta_o \gamma}\)。这种屏蔽（Mask）加密不允许用有意义的方式修改 \(g^{Z(s)}\)，因为 \(Z(s)\) 不是 \(\gamma\) 的倍数，即 \(g^{Z(s)} \cdot g^{v'\cdot\beta_l \gamma} = g^{\beta_l (L(s) + \color{yellow}{v' \gamma} ) + \beta_r R(s) + \beta_o O(s)}\)。因为证明者不知道 \(\gamma\)，所以更改将会是随机的。修改要求我们将 \(Z(s)\) 乘以 \(\gamma\) 来平衡协议中的变量值一致性检查方程：

  • 设置
    • 选择随机值 \(\beta_l, \beta_r, \beta_o, \gamma\)
    • 生成验证密钥：\(\left(\ldots, g^{\beta_l \gamma}, g^{\beta_r \gamma}, g^{\beta_o \gamma}, g^{\gamma} \right)\)
  • 证明 \(\ldots\)
  • 验证
    • \(\ldots\) 检查变量值一致性，应满足： $$e\left( g^{L}, g^{\beta_l \gamma} \right) \cdot e\left( g^{R}, g^{\beta_r \gamma} \right) \cdot e\left( g^{O}, g^{\beta_o \gamma} \right) = e\left( g^{Z}, g^\gamma \right)$$

需要注意的是，我们排除了变量多项式为 0 阶的情况（例如 \(l_1(x) = 1x^0\)），否则在任何两个操作数 / 输出为零的情况下，将允许在证明密钥 \(\left\{ g^{\beta_l l_i(s) + \beta_r r_i(s) + \beta_o o_i(s)} \right\}_{i \in \{1,\ldots,n\}}\) 的变量一致性多项式中暴露 \(\beta\) 的加密，例如，对于 \(l_1(x) = 1,\ r_1(s) = 0,\ o_1(s) = 0\)，这将导致 \(g^{\beta_l l_1(s) + \beta_r r_1(s) + \beta_o o_1(s)} = g^{\beta_l}\)。

我们也可以用类似的方法屏蔽 \(\alpha\) 来解决变量多项式的延展性。但这并不是必需的，因为对变量多项式的任何修改都需要被反映在无法修改的变量一致性多项式中。