zk-SNARK 协议

在所有的逐步改进之后，最终的零知识简洁的非交互式知识论证如下（零知识组件是可选的，并以\(\color{Magenta}{不同的颜色}\)突出显示）：

  • 设置
    • 选择一个生成元 \(g\) 和一个密码学配对 \(e\)
    • 对于变量总数为 \(n\) 的函数 \(f(u) = y\)，其中 \(m\) 是输入 / 输出变量，转换为阶数为 \(d\)，大小为 \(n + 1\) 的多项式形式（一个二次算术程序）\(\left( \{l_i(x), r_i(x), o_i(x)\}_{i \in \{0, \ldots, n\}}, t(x) \right)\)
    • 选择随机值 \(s, \rho_l, \rho_r, \alpha_l, \alpha_r, \alpha_o, \beta, \gamma\)
    • 设置 \(\rho_o = \rho_l \cdot \rho_r\) 和操作数生成元 \(g_l = g^{\rho_l}, g_r = g^{\rho_r}, g_o = g^{\rho_o}\)
    • 生成证明密钥： $$\bigg( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, n\}},$$ $$\left\{ 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)} g_r^{\beta r_i(s)} g_o^{\beta o_i(s)} \right\}_{i \in \{m + 1, \ldots, n\}},$$ $$\color{Magenta}{ g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)}, g_r^{\beta t(s)}, g_o^{\beta t(s)} } \bigg)$$
    • 生成验证密钥： $$\left( g^1, g_o^{t(s)}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, m\}}, g^{\alpha_l}, g^{\alpha_r}, g^{\alpha_o}, g^{\gamma}, g^{\beta \gamma} \right)$$
  • 证明
    • 对于输入 \(u\)，执行 \(f(u)\) 的计算，获取所有中间变量的值 \(\{v_i\}_{i \in \{m+1, \dots, n\}}\)
    • 将所有值赋值给未加密的变量多项式 \(L(x) = l_0(x) + \sum_{i = 1}^n v_i \cdot l_i(x)\)，\(R(x), O(x)\) 同理
    • \(\color{Magenta}{选择随机值 \ \delta_l, \delta_r \ 和 \ \delta_o}\)
    • 找到 \(\displaystyle h(x) = \frac{L(x) R(x) - O(x)}{t(x)} \color{Magenta}{\ +\ \delta_r L(x) + \delta_l R(x) + \delta_l \delta_r t(x) - \delta_o }\)
    • 将证明者的变量值赋值给加密的变量多项式 \(\color{Magenta}{并应用零知识 \ \delta\text{-}移位}\) $$\displaystyle g_l^{L_p(s)} = \color{Magenta}{ \left(g_l^{t(s)}\right)^{\delta_l} } \cdot \prod_{i = m+1}^n \left( g_l^{l_i(s)} \right)^{v_i}，g_r^{R_p(s)}, g_o^{O_p(s)} \ 同理$$
    • 为它的 \(\alpha\)-移位的配对赋值 $$\displaystyle g_l^{L'_p(s)} = \color{Magenta}{ \left(g_l^{\alpha_l t(s)}\right)^{\delta_l} } \cdot \prod_{i = m+1}^n \left( g_l^{\alpha_l l_i(s)} \right)^{v_i}，g_r^{R'_p(s)}, g_o^{O'_p(s)} \ 同理$$
    • 为变量值一致性多项式赋值 $$g^{Z(s)} = \color{Magenta}{ \left(g_l^{\beta t(s)}\right)^{\delta_l} \left(g_r^{\beta t(s)}\right)^{\delta_r} \left(g_o^{\beta t(s)}\right)^{\delta_o} } \cdot \prod_{i=m+1}^n \left( g_l^{\beta l_i(s)} g_r^{\beta r_i(s)} g_o^{\beta o_i(s)} \right)^{v_i}$$
    • 计算证明 $$\left( g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g^{h(s)}, g_l^{L'_p(s)}, g_r^{R'_p(s)}, g_o^{O'_p(s)}, g^{Z(s)} \right)$$
  • 验证
    • 将证明解析为 \(\left( g_l^{L_p}, g_r^{R_p}, g_o^{O_p}, g^{h}, g_l^{L'_p}, g_r^{R'_p}, g_o^{O'_p}, g^{Z} \right)\)
    • 将输入 / 输出值赋值给验证者的加密多项式并与 \(1\) 相加： $$\displaystyle 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_p} g_l^{L_v(s)}, g_r^{R_p} g_r^{R_v(s)} \right) = e\left( g_o^{t(s)}, g^{h} \right) \cdot e\left( g_o^{O_p} g_o^{O_v(s)}, g \right)$$