![[CleanShot 2025-05-25 at
[email protected]]]
> https://eprint.iacr.org/2025/902.pdf
## 摘要
> 本文针对一种构建 SNARG 的通用范式——先在标准模型中通过功能交互式预言证明（FIOP）与功能承诺（FC）框架构造简洁交互式论证，再在随机预言模型（ROM）中通过 Fiat–Shamir 变换获得非交互式 SNARG——填补了此前分析中的关键安全空缺。作者提出并形式化了 **状态恢复安全性**（state‐restoration security）与 **功能绑定**（function binding）两大核心概念，证明只要所用 FIOP 与 FC 满足对应的状态恢复安全性与功能绑定变体，即可确保 Fiat–Shamir 变换后的非交互式论证在 ROM 中的可信性。
> 基于该主定理，文章进一步验证了多种 FC 架构（包括 KZG、多项式承诺等）满足功能绑定性质，并从而*在 ROM 中首次给出了 Plonk SNARG 的 Fiat–Shamir 安全性证明*（依赖可验证 RSA 分解困难性假设 ARSDH）。
## 背景
### SNARG 与 Fiat–Shamir 变换
- **SNARG**（Succinct Non-Interactive Argument of Knowledge）是一种非交互式、论证长度远小于见证大小的零知识论证框架，广泛应用于区块链与可信计算。
- **Fiat–Shamir 变换** 是将公开硬币交互式证明"去交互化"的经典技术，通过哈希（在 ROM 中视为随机 预言）模拟 Verifier 的质询，从而生成非交互式论证。
- **随机预言模型 (ROM)** 假设哈希函数为真正的随机函数，简化安全分析但需谨慎使用。
### 功能承诺与交互式预言证明
- **功能承诺（Functional Commitment）**：委托者可以承诺一个功能，并在后续高效揭示该功能在任意输入处的输出且保持隐私，通用建构包括向量承诺与多项式承诺。
- **交互式预言证明 (Interactive Oracle Proof, IOP)**：结合交互式证明（IP）与可验证随机访问证明（PCP），Verifier 对 Prover 消息具备预言查询能力，兼具 IP 与 PCP 优势。
- **多项式承诺（Polynomial Commitment）**：其中典型方案如 KZG，将待承诺向量视作多项式，通过双线性对实现高效开证明与批量验证。
## Funky 协议概述
Funky 协议定义如下：
1. 使用 FIOP 生成对实例 $x$、见证 $w$ 的 **功能性交互式论证**，允许 Verifier 对 Prover 的预言响应进行少量随机查询；
2. 对 Prover 在不同轮次的输出应用 FC 承诺，每次承诺后进行有限次公币交互；
3. 最后在 ROM 中对所有交互轮次应用 Fiat–Shamir 变换，输出非交互式论证。
## 主要贡献
### 1. 状态恢复安全性与功能绑定定义
- **状态恢复安全性**（State‐Restoration Soundness）：在模拟 Fiat–Shamir 后，若敌手能在限制次数内生成接收器接受的论证，则可通过**重置 Verifier 随机状态**并重复交互抽取有效见证。此性质强于传统公开硬币可靠性。
- **功能绑定**（Function Binding）：FC 的自然安全性变体——当同一承诺针对不同输入可被开证明至不同输出时，需保持所有查询结果一致，否则可解承诺提取冲突见证。此性质推广了 VC 的位置绑定 (position binding)。
### 2. 通用安全性定理
> **定理 1（非正式）**：令 Funky[FIOP, FC] 为基于 FIOP（轮次 $k$, 论证长 $\ell$, 查询数 $q$）及 FC 的 Funky 协议。若 FIOP 满足状态恢复安全性误差 $\varepsilon_{\text{SR-FIOP}}$，FC 满足功能绑定误差 $\varepsilon_{\text{SR-FC}}$，则在 ROM 中，对任何 $m$ 轮交互、时间绑定 $t$ 的 Adversary，其 Fiat–Shamir 后的论证接受概率上界为
$
\varepsilon_{\text{SR-ARG}}(m,t)\;\le\;\varepsilon_{\text{SR-FIOP}}(m+k)\;+\;k\cdot\varepsilon_{\text{SR-FC}}(\dots)\;+\;\text{negl}\,.
$
### 3. 示例：KZG 与 Plonk 安全性
- 文章验证了基于双线性对的 KZG 多项式承诺满足所需功能绑定性质，并给出相应证明。
- 结合 ARSDH 假设，首次在 ROM 中呈现了 Plonk SNARG 的 Fiat–Shamir 安全性证明，填补了实践中 Plonk ROM 安全性空白。
![[CleanShot 2025-05-25 at
[email protected]]]
## 技术细节
### FIOP 与 FC 的组合
在 Funky 协议中，FIOP 定义了一组在交互式论证中对 Prover 消息进行**预言查询**的函数族
$
Q = \{\;\alpha:\Sigma^\ell\to D\;\},
$
其中每个查询 $\alpha\in Q$ 接受 Prover 在第 $i$ 轮发送的消息 $\Pi_i\in\Sigma^{\ell_i}$ 并返回答案 $\alpha(\Pi_i)\in D$ 。
FIOP 本身由 $(P,V)$ 构成，具有 $k_{\text{FIOP}}$ 轮交互，每轮交互后 Verifier 从相应查询类 $Q_i$ 中随机选取若干 $\alpha$ 并获得响应。
功能承诺 (FC) 在此基础上提供对函数 $\alpha$ 及其求值结果 $\beta=\alpha(\cdot)$ 的**承诺**能力。令
$
{\rm pp}_{\rm FC}\leftarrow\mathsf{FC}.\mathsf{Gen}(1^\lambda,\ell)\,,\quad
(\mathit{cm},\mathit{aux})\leftarrow\mathsf{FC}.\mathsf{Commit}({\rm pp}_{\rm FC},\,\alpha)\,,
$
其中 $\mathit{cm}$ 为承诺串，$\mathit{aux}$ 为辅助输出。
关键在于，FC 是**三同态**（triply homomorphic）的：若
$
\mathsf{FC}.\mathsf{Check}(\mathit{pp},\,\mathit{cm},\,\alpha,\,\beta,\,\mathit{pf})=1
\quad\wedge\quad
\mathsf{FC}.\mathsf{Check}(\mathit{pp},\,\mathit{cm}',\,\alpha,\,\beta',\,\mathit{pf}')=1,
$
则必有
$
\mathsf{FC}.\mathsf{Check}\bigl(\mathit{pp},\,\mathit{cm}+\mathit{cm}',\,\alpha,\,\beta+\beta',\,\mathit{pf}+\mathit{pf}'\bigr)=1.
$
![[CleanShot 2025-05-25 at
[email protected]]]
此性质（Definition 8.5）使得在交互式论证中，来自多个 预言查询的承诺与证明可以**线性组合**并批量验证。
在 Funky 协议的每轮中，Prover 对于所选查询 $\alpha_i$ 先生成 FIOP 消息 $\Pi_i$，再计算 $\beta_i=\alpha_i(\Pi_i)$，最后调用
$
(\mathit{cm}_i,\mathit{aux}_i)\leftarrow\mathsf{FC}.\mathsf{Commit}(\mathit{pp},\,\alpha_i)
$
并将 $\beta_i$ 与 $\mathit{aux}_i$ 一并发送给 Verifier，从而实现 FIOP 与 FC 的无缝集成。
### 批量与线性化优化
- **批量消息传递（Batching）**
定义 BatchMsg[FC, s]（Construction 8.6）：对 $s$ 个独立函数 $(\alpha_b)_{b=1}^s$ 同时承诺，得到向量承诺 $cm=(cm_b)_{b=1}^s$ 和原函数数组 $aux=(\alpha_b)_{b=1}^s$ 。
在开证明阶段，Verifier 发送标量挑战 $\gamma\gets F$，Prover 计算
$
pf \;=\; \sum_{b=1}^s \gamma^{b-1}\,\mathsf{FC}.\mathsf{Open}(cm_b,\,\alpha_b,\,\beta_b)\,,
$
并一次性验证：
$
\mathsf{FC}.\mathsf{Check}\Bigl(\mathit{pp},\,\sum_{b=1}^s\gamma^{b-1}cm_b,\,
\sum_{b=1}^s\gamma^{b-1}\beta_b,\,pf\Bigr)=1.
$
![[CleanShot 2025-05-25 at
[email protected]]]
由此 BatchMsg[FC, s] 对查询类 $Q_{\text{BatchMsg}}[Q,s]$ 满足**批量状态恢复函数绑定**（Lemma 8.2）：
$
\epsilon_{\text{SR-}bFC}(\lambda,s\ell,L,s_{\rm FC},m_{\rm FC},t_{bFC})
\;\le\; L\,(m_{\rm FC}+1)\,2^{-\lambda(s-1)}.
$
- **线性化技巧（Linearization）**
对于结构化多项式查询族 $Q_{\rm Struct}$，引入参数 $\tau\in F$，构造 $Lin[BatchMsg[FC,s], m,(h_k)_{k=1}^n]$（见 Lemma 8.3），将 $m\times n$ 个子查询承诺 $(cm_{i,k})$ 和响应 $(\beta_{i,k})$ 线性化为单一承诺与响应：
$
cm_{\rm lin}
= \sum_{i=1}^m\sum_{k=1}^n \tau^{(i-1)n+(k-1)}\,cm_{i,k},\qquad
\beta_{\rm lin}
= \sum_{i=1}^m\sum_{k=1}^n \tau^{(i-1)n+(k-1)}\,\beta_{i,k}.
$
验证时同样仅需一次 $\mathsf{FC}.\mathsf{Check}$ 调用，且满足**线性化状态恢复函数绑定**：
$
\epsilon_{\text{SR-linFC}}(\lambda,(m+n)(D+1),L,s_{\rm FC},m_{\rm FC},t_{\rm linFC})
\;\le\; \epsilon_{\text{SR-}bFC}(\lambda,(m+1)(D+1),L,s_{\rm FC},m_{\rm FC},t_{bFC}).
$
## 性能与效率
在 Funky 协议中，交互式阶段包含 $k_{\rm FIOP}$ 轮交互，每轮 Prover 发送 $\ell$ 位的 FIOP 消息和一个 FC 承诺 。
因此，交互式协议的总通信量为 $k_{\rm FIOP}\cdot(\ell+|\mathit{cm}|)$ 位，其中 $|\mathit{cm}|$ 取决于所用承诺方案（如 KZG 中为单个群元） 。
应用 Fiat–Shamir 变换后，非交互式 SNARG 的证明大小为
$
k_{\rm FIOP}\cdot\ell \;+\; k_{\rm FIOP}\cdot|\mathit{cm}|\;+\;k_{\rm FIOP}\cdot\kappa
$
位，其中附加的 $k_{\rm FIOP}\cdot\kappa$ 部分源于 ROM 中对每轮质询的随机预言响应 。
Verifier 验证过程中，需要进行 $k_{\rm FIOP}$ 次 FIOP 验证和 $k_{\rm FIOP}$ 次 $\mathsf{FC}.\mathsf{Check}$ 调用 。
因此，Verifier 总时间复杂度为
$
O\bigl(k_{\rm FIOP}\cdot(\mathsf{Time}_{\rm FIOP\_V}+\mathsf{Time}_{\rm FC\_V})\bigr)
$
当 $k_{\rm FIOP},\ell,|\mathit{cm}|,\kappa$ 为常数时，上述复杂度仍为常数阶，保持了 SNARG 的“简洁性” 。
## 结论与未来工作
本文建立了 Funky 协议在 ROM 中的 Fiat–Shamir 安全性，填补了此前构造的关键安全空缺 。
证明了状态恢复 soundness 错误 $\epsilon_{\rm SR\text{-}ARG}$ 与 FIOP 及 FC 安全误差之间的精确关系，为后续框架设计提供了理论指导 。
实例分析表明，常用 FC 架构（例如 KZG）和 FIOP 架构（例如 Plonk IOP）可直接套用本框架，并获得 ROM 下的 Fiat–Shamir 安全证明 。
未来可探索将 Funky 协议与递归证明结合，实现多层 SNARG 的高效递归压缩 。
另外，可研究功能绑定在其他承诺方案（如 Bulletproofs 类承诺）中的应用，以进一步优化证明大小和验证开销 。