菲亚特-沙米尔零知识简洁非交互知识论证（Fiat–ShamirzkSNARKs）解析

### 菲亚特 - 沙米尔零知识简洁非交互知识论证（Fiat–Shamir zkSNARKs）解析 #### 1. 可更新回溯式知识可靠性 在相关定义中，树中的每个记录都相对于随机预言机的“本地编程”被接受，但对手输出的证明的验证是相对于未编程的随机预言机进行的。 **可更新回溯式知识可靠性定义**： 设 \(n_1, \ldots, n_{\mu} \in \mathbb{N}\)，\(\Psi_{FS} = (SRS, P, V, Sim)\) 是一个具有可更新 SRS 设置的 \((2\mu + 1)\) 消息的 FS 转换非交互零知识（NIZK）证明系统，用于关系 \(R\)，\(H\) 为随机预言机。要求存在一个期望的概率多项式时间（PPT）树构建器 \(T\)，最终输出 \(T\)，它要么是一个接受记录的 \((n_1, \ldots, n_{\mu})\) 树，要么是 \(\perp\)，以及一个 PPT 提取器 \(Ext_{ks}\)。设对手 \(A_{ks}\) 是一个 PPT 算法，以至少 \(acc\) 的概率输出有效证明，其中： \[acc = \Pr\left[V(srs, x, \pi) = 1 \land (x, \pi) \notin Q \mid r \leftarrow_R(A_{ks}), (x, \pi) \leftarrow A_{ks}^{UpdO, H}(1^{\lambda}; r)\right]\] 若满足以下条件，则称 \(\Psi_{FS}\) 是具有安全损失 \(\varepsilon_{ks}(\lambda, acc, q)\) 的 \((n_1, \ldots, n_{\mu})\) 回溯式知识可靠的： \[\Pr\left[V(srs, x, \pi) = 1, R(x, w) = 0 \mid r \leftarrow_R(A_{ks}), (srs, x, \cdot) \leftarrow A_{ks}^{UpdO, H}(1^{\lambda}; r), T \leftarrow T(srs, A_{ks}, r, Q_{srs}, Q_{H}), w \leftarrow Ext_{ks}(T)\right] \leq \varepsilon_{ks}(\lambda, acc, q)\] 这里，\(srs\) 是最终确定的 SRS，列表 \(Q_{srs}\) 包含所有更新后的 SRS 及其证明 \((srs, \rho)\)，列表 \(Q_{H}\) 包含对手对 \(H\) 的所有查询以及随机预言机的答案，\(\vert Q_{H} \vert \leq q\)。 #### 2. 模拟可提取性 - 一般结果 具备上述定义框架后，我们给出多消息菲亚特 - 沙米尔转换 NIZK 证明系统模拟可提取性的证明。 不失一般性，假设当接受证明包含对随机预言机挑战的响应时，对手会查询该预言机以获取响应。可以将违反此条件的任何对手转换为进行这些额外查询且以相同概率获胜的对手。 证明的核心概念是，\(k\) - 唯一响应和 \(k\) - 可编程无陷门零知识属性共同确保了回溯式知识可靠性树中的第 \(k\) 步挑战是新鲜的，且不来自模拟器。这使得我们在回溯论证中可以消除模拟预言机，并在后续部分使用现有结果。 **定理 1（多消息协议的模拟可提取性）**： 设 \(\Psi_{FS} = (SRS, P, V, Sim)\) 是一个具有可更新 SRS 设置的 \((2\mu + 1)\) 消息的 FS 转换 NIZK 证明系统。若 \(\Psi_{FS}\) 是具有安全损失 \(\varepsilon_{ur}\) 的可更新 \(k\) - 唯一响应协议、可更新 \(k\) - 可编程无陷门零知识协议，以及具有安全损失 \(\varepsilon_{ks}\) 的可更新回溯式知识可靠协议，则 \(\Psi_{FS}\) 是具有安全损失 \(\varepsilon_{se}(\lambda, acc, q) \leq \varepsilon_{ks}(\lambda, acc - \varepsilon_{ur}(\lambda), q)\) 的可更新模拟可提取协议，对抗任何进行最多 \(q\) 次随机预言机查询且以至少 \(acc\) 的概率返回接受证明的 PPT 对手 \(A\)。 **证明思路**： 设 \((x, \pi) \leftarrow A^{UpdO, SimO.H, SimO.P'}(r_A)\) 是 USE 对手。我们展示如何构建一个提取器 \(Ext_{se}(srs, A, r_A, Q, Q_{H}, Q_{srs})\)，以高概率输出满足 \(R(x, w)\) 的见证 \(w\)。为此，我们定义一个针对 \(\Psi_{FS}\) 回溯式知识可靠性的算法 \(A_{ks}^{UpdO, H}(r)\)，它在内部运行 \(A^{UpdO, SimO.H, SimO.P'}(r_A)\)，其中 \(r = (r_{Sim}, r_A)\)，\(r_{Sim}\) 是用于模拟 \(SimO.P'\) 的随机性。 \(A_{ks}^{UpdO, H}(r)\) 的代码对 \(Q\) 进行硬编码，只要按顺序查询语句，就不会对 \(Q\) 中的证明使用任何随机性。在这种情况下，它直接从 \(Q\) 中返回证明 \(\pi_{Sim}\)，但仍会对 \((\tilde{\pi}_{Sim}[0..k], \tilde{\pi}_{Sim}[k].ch)\) 查询 \(SimO.Prog\)，即对第 \(k\) 个挑战进行编程。虽然在不知道 \(Q\) 的情况下很难构造这样的对手，但显然它是存在的，并且 \(Ext_{se}\) 有必要的输入来构造 \(A_{ks}\)。这种硬编码保证了 \(A_{ks}\) 在实验中返回与 \(A\) 相同的 \((x, \pi)\)。最终，\(Ext_{se}\) 使用 \(A_{ks}\) 的树构建器 \(T\) 和提取器 \(Ext_{ks}\) 来提取 \(x\) 的见证。 下面给出保证 \(A_{ks}\) 在 \(A\) 成功时也成功（除了一个小的安全损失，后续会进行界定）的模拟细节： 由于 \(A_{ks}\) 在内部运行 \(A\)，它需要处理 \(A\) 的预言机查询。\(A_{ks}\) 将 \(A\) 对更新预言机 \(UpdO\) 的查询传递给它自己的 \(UpdO\) 预言机，并将结果返回给 \(A\)。\(A_{ks}\) 通过在其磁带的随机性 \(r_{Sim}\) 上运行 \(Sim\) 算法，在内部模拟对模拟器 \(SimO.P'\) 的（非硬编码）查询。\(Sim\) 需要访问预言机 \(SimO.H\) 以诚实地计算挑战，以及 \(SimO.Prog\) 来编程挑战。同样，\(A_{ks}\) 在内部模拟这两个预言机，这次使用 \(A_{ks}\) 的 \(H\) 预言机。注意，\(A\) 对 \(SimO.H\) 的查询不进行编程，而是传递给 \(H\)。 重要的是，模拟证明中直到第 \(k\) 轮的所有挑战也都是诚实地计算的，即 \(\tilde{\pi}[i].ch = H(\tilde{\pi}[0..i])\)，其中 \(i < k\)。 最终，\(A\) 输出一个实例和证明 \((x, \pi)\)。只要 \(\tilde{\pi}[0..i] \notin Q_{prog}\)，\(i \in [1, \mu]\)，\(A_{ks}\) 就返回相同的值。这模拟了 \(A_{ks}\) 输出的证明不能包含任何编程查询，因为这样的证明在 RBKS 实验中与 \(H\) 不一致。如果 \(A\) 输出的证明包含编程挑战，则 \(A_{ks}\) 中止，我们将此事件记为 \(E\)。 **引理 1**：事件 \(E\) 发生的概率上限为 \(\varepsilon_{ur}(\lambda)\)。 **证明**：我们构建一个可以访问随机预言机 \(H\) 和更新预言机 \(UpdO\) 的对手 \(A_{ur}^{UpdO, H}(\lambda; r)\)。\(A_{ur}\) 使用 \(A_{ks}\) 来破坏 \(\Psi_{FS}\) 的 \(k\) - UR 属性。当 \(A_{ks}\) 输出满足 \(E\) 的证明 \(\pi\) 时，\(A_{ur}\) 遍历列表 \(Q\) 和 \(Q_{H}\)，直到找到 \(\tilde{\pi}_{Sim}[0..k]\)，使得 \(\tilde{\pi}[0..k] = \tilde{\pi}_{Sim}[0..k]\) 以及对 \(\tilde{\pi}_{Sim}[0..k]\) 的编程随机预言机查询 \(\tilde{\pi}_{Sim}[k].ch\)。\(A_{ur}\) 返回针对 \(x\) 的两个证明 \(\pi\) 和 \(\pi_{Sim}\)，以及挑战 \(\tilde{\pi}_{Sim}[k].ch = \tilde{\pi}[k].ch\)。重要的是，两个证明都相对于唯一响应验证器。第一个证明是正确计算的模拟证明，根据唯一响应属性定义，在第 \(k\) 步允许任何挑战；第二个证明是对手产生的接受证明。若 \(\pi \neq \pi_{Sim}\)，则 \(A_{ur}\) 破坏了 \(\Psi_{FS}\) 的 \(k\) - UR 属性，这种情况仅以概率 \(\varepsilon_{ur}(\lambda)\) 发生。 我们用 \(\overline{acc}\) 表示 \(A_{ks}\) 输出接受证明的概率。通过“直到坏情况”的推理，\(\overline{acc}\) 与 \(A\) 输出接受证明的概率最多相差 \(\varepsilon_{ur}(\lambda)\)。因此，\(A_{ks}\) 输出接受证明的概率至少为 \(\overline{acc} \geq acc - \varepsilon_{ur}(\lambda)\)。由于 \(\Psi_{FS}\) 是 \(\varepsilon_{ks}(\lambda, \overline{acc}, q)\) 回溯式知识可靠的，存在一个树构建器 \(T\) 和提取器 \(Ext_{ks}\)，它们对 \(A_{ks}\) 进行回溯以获得接受记录的树 \(T\)，并且以最多 \(\varepsilon_{ks}(\lambda, \overline{acc}, q)\) 的概率无法提取见证。提取器 \(Ext_{se}\) 以相同的概率输出见证。 因此，\(\varepsilon_{se}(\lambda, acc, q) = \varepsilon_{ks}(\lambda, \overline{acc}, q) \leq \varepsilon_{ks}(\lambda, acc - \varepsilon_{ur}, q)\)。 **备注**： - 我们的定理不依赖于 \(\varepsilon_{zk}(\lambda)\)，实验中没有真正的证明者算法 \(P\)，只有 TLZK 的 \(k\) - 可编程性才重要。 - 定理没有为树构建器 \(T\) 规定树的形状，有趣的是，在具体结果中 \(T\) 输出一个接受记录的 \((k, *)\) 树。 #### 3. 具体零知识简洁非交互知识论证（SNARKs）预备知识 ##### 3.1 双线性群 双线性群生成器 \(P_{gen}(1^{\lambda})\) 返回公共参数 \(p = (p, G_1, G_2, G_T, \hat{e}, [1]_1, [1]_2)\)，其中 \(G_1\)、\(G_2\) 和 \(G_T\) 是素数阶 \(p = 2^{\Omega(\lambda)}\) 的加法循环群，\([1]_1\) 和 \([1]_2\) 分别是 \(G_1\) 和 \(G_2\) 的生成元，\(\hat{e} : G_1 \times G_2 \to G_T\) 是一个非退化的 PPT 可计算双线性对。我们假设双线性对是 Type - 3，即从 \(G_1\) 到 \(G_2\) 或从 \(G_2\) 到 \(G_1\) 不存在高效同构。我们使用标准的括号表示法，即 \([a]_{\iota}\) 表示 \(a [1]_{\iota}\)，\(\hat{e}([a]_1, [b]_2)\) 表示为 \([a]_1 \bullet [b]_2\)，因此 \([a]_1 \bullet [b]_2 = [ab]_T\)。由于每个算法 \(A\) 都将公共参数作为输入，在描述 \(A\) 的输入时我们省略这些参数，同样，我们不明确说明每个协议都从运行 \(P_{gen}\) 开始。 ##### 3.2 代数群模型 Fuchsbauer、Kiltz 和 Loss 提出的代数群模型（AGM）介于标准和通用双线性群模型之间。在 AGM 中，假设对手 \(A\) 如果通过对作为输入提供给它的群元素应用群操作计算出群元素 \([y] \in G\)，则可以输出该群元素。进一步假设 \(A\) 知道如何从这些元素“构建” \([y]\)。更准确地说，AGM 要求每当 \(A([x])\) 输出群元素 \([y]\) 时，它也输出 \(c\) 使得 \([y] = c^{\top} \cdot [x]\)。Plonk、Sonic 和 Marlin 已被证明在 AG