可验证计算协议

我们对多项式知识协议（3.7 节）做了许多重要的修改来让它更具有通用性，让我们看看它现在是如何定义的。假设函数 \(f(*)\) 的计算结果是证明的主体，运算的数量为 \(d\)，变量的数量为 \(n\)，对应的系数为 \(\left\{ c_{L,i,j}, c_{R,i,j}, c_{O,i,j} \right\}_{i \in \{1, \ldots, n\}, j \in \{1, \ldots, d\}}\)：

  • 设置
    • 为左操作数 \(\left\{ l_i(x) \right\}_{i \in \{1, \ldots, n\}}\) 构造变量多项式，使得对于 \(j \in \{1, \ldots, d\}\) 的所有运算都求值为相应的系数，即 \(l_i(j) = c_{L,i,j}\)，右操作数和输出同理
    • 选择随机值 \(s, \alpha\)
    • 计算 \(t(x) = (x-1)(x-2)\ldots(x-d)\) 以及 \(g^{t(s)}\)
    • 计算证明密钥：\(\left( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ g^{l_i(s)}, g^{r_i(s)}, g^{o_i(s)}, g^{\alpha l_i(s)}, g^{\alpha r_i(s)}, g^{\alpha o_i(s)} \right\}_{i \in \{1,\ldots,n\}} \right)\)
    • 计算验证密钥：\(\left(g^{t(s)}, g^{\alpha}\right)\)
  • 证明
    • 计算函数 \(f(*)\) 和相应的变量值 \(\left\{ v_i \right\}_{i \in \{1,\ldots,n\}}\)
    • 计算 \(h(x) = \frac{L(x) \times R(x) - O(x)}{t(x)}\)，其中 \(L(x) = \sum_{i=1}^n v_i \cdot l_i(x)\)，\(R(x), O(x)\) 同理
    • 给变量赋值并求和来得到操作数多项式： $$g^{L(s)} = \left(g^{l_1(s)}\right)^{v_1} \cdots \left(g^{l_n(s)}\right)^{v_n},\ g^{R(s)} = \prod_{i=1}^{n} \left(g^{r_i(s)}\right)^{v_i},\ g^{O(s)} = \prod_{i=1}^{n} \left(g^{o_i(s)}\right)^{v_i}$$
    • 将变量值赋给移位的多项式： $$g^{\alpha L(s)} = \prod_{i=1}^{n} \left(g^{\alpha l_i(s)}\right)^{v_i},\ g^{\alpha R(s)} = \prod_{i=1}^{n} \left(g^{\alpha r_i(s)}\right)^{v_i},\ g^{\alpha O(s)} = \prod_{i=1}^{n} \left(g^{\alpha o_i(s)}\right)^{v_i}$$
    • 使用提供的 \(s\) 的幂计算加密值 \(g^{h(s)}\)：\(\left\{ g^{s^k} \right\}_{k \in [d]}\)
    • 构造证明：\(\left( g^{L(s)}, g^{R(s)}, g^{O(s)}, g^{\alpha L(s)}, g^{\alpha R(s)}, g^{\alpha O(s)}, g^{h(s)} \right)\)
  • 验证
    • 将证明解析为：\(\left( g^L, g^R, g^O, g^{L'}, g^{R'}, g^{O'}, g^h \right)\)
    • 检查变量多项式限制： $$e(g^{L}, g^\alpha) = e(g^{L'}, g),\quad e(g^{R}, g^\alpha) = e(g^{R'}, g), \quad e(g^{O}, g^\alpha) = e(g^{O'}, g)$$
    • 检查运算的有效性： $$e(g^{L}, g^{R}) = e(g^{t}, g^{h}) \cdot e(g^{O}, g)$$

注：使用符号 \(\prod\) 可以简洁地表达多个元素的乘积，即 \(\prod_{i=1}^n v_i = v_1 \cdot v_2 \cdot \ldots \cdot v_n\)。

所有变量多项式 \(\{l_i(x), r_i(x), o_i(x)\}_{i \in \{1, \ldots, n\}}\) 和目标多项式 \(t(x)\) 的集合被称为二次算术程序（Quadratic Arithmetic Program，QAP，参见 [Gen+12]）。

虽然这个协议足够健壮，可以进行一般计算验证，但还有两个必须要解决的安全问题。