2.2 非交互式零知识知识论证 (Non-interactive zero-knowledge arguments of knowledge)

设 $\mathcal{R}$ 是一个关系生成器 (relation generator)，给定一个安全参数 $\lambda$ (以一元形式)，返回一个可在多项式时间内判定的二元关系 $R$。 对于属于 $R$ 的配对 (pairs) ($\varphi$, $w$)，我们称 $\varphi$ 为陈述 (statement)， $w$ 为证据 (witness)。 我们定义 ${\mathcal{R}}_{\lambda }$ 为关系生成器在给定 $1^{\lambda }$ 时的可能输出的集合。 在下面的内容中，为了符号的简洁性，我们假设 $\lambda$ 可以从 $\mathcal{R}$ 的描述中推断出来。 关系生成器也可能输出一些辅助信息 (side information) $z$，该信息将被提供给敌手。 一个高效的公开可验证的非交互式论证 (publicly verifiable non-interactive argument) $\mathcal{R}$ 是一个概率多项式时间算法四元组 (Setup, Prove, Vfy, Sim)，满足以下条件：

• ($\sigma$, $\tau$) ← Setup($\mathcal{R}$): Setup 算法产生一个公共参考字符串 (common reference string) $\sigma$ 和关系 $\mathcal{R}$ 的一个模拟陷门 (simulation trapdoor) $\tau$。

• $\pi$ ← Prove($\mathcal{R}$, $\sigma$, $\varphi$, $w$): Prover 算法以公共参考字符串 $\sigma$ 和 ($R$, $\varphi$, $w$) ∈ $R$ 作为输入，并返回一个论证 (argument) $\pi$。

• 0/1 ← Vfy($\mathcal{R}$, $\sigma$, $\varphi$, $\pi$): Verification 算法以公共参考字符串 $\sigma$、一个陈述 $\varphi$ 和一个论证 $\pi$ 作为输入，并返回 0 (拒绝) 或 1 (接受)。

• $\pi$ ← Sim($\mathcal{R}$, $\tau$, $\varphi$): Simulator 算法以一个模拟陷门 $\tau$ 和陈述 $\varphi$ 作为输入，并返回一个论证 $\pi$。

定义 1. 我们称 (Setup, Prove, Vfy) 是 $\mathcal{R}$ 的一个非交互式论证 (non-interactive argument)，如果它具有完美完备性 (perfect completeness) 和计算可靠性 (computational soundness)，定义如下。

定义 2. 我们称 (Setup, Prove, Vfy, Sim) 是 $\mathcal{R}$ 的一个非交互式零知识知识论证 (perfect non-interactive zero-knowledge argument of knowledge)，如果它具有完美完备性 (perfect completeness)，完美零知识性 (perfect zero-knowledge) 和计算知识可靠性 (computational knowledge soundness)，定义如下。

完美完备性 (Perfect Completeness)

完备性表示，给定任何正确的陈述，一个诚实的 Prover 应该能够说服一个诚实的 Verifier。 对于所有 $\lambda$ ∈ $\mathbb{N}$, $R$ ∈ ${\mathcal{R}}_{\lambda }$, ($\varphi$, $w$) ∈ $R$:

$$\mathrm{Pr}\left[(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});\pi \leftarrow \text{Prove}(\mathcal{R},\sigma ,\varphi ,w):\text{Vfy}(\mathcal{R},\sigma ,\varphi ,\pi )=1\right]=1.$$

完美零知识性 (Perfect Zero-Knowledge)

一个论证是零知识的，如果它不泄露关于陈述真实性的任何信息。 我们说 (Setup, Prove, Vfy, Sim) 是完美零知识的 (perfect zero-knowledge)，如果对于所有 $\lambda$ ∈ $\mathbb{N}$, ($R$, $z$) ← $\mathcal{R}(1^{\lambda })$, ($\varphi$, $w$) ∈ $R$ 和所有敌手 $\mathcal{A}$:

$$\mathrm{Pr}\left[(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});\pi \leftarrow \text{Prove}(\mathcal{R},\sigma ,\varphi ,w):\mathcal{A}(R,z,\sigma ,\tau ,\pi )=1\right]=\mathrm{Pr}\left[(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});\pi \leftarrow \text{Sim}(\mathcal{R},\tau ,\varphi ):\mathcal{A}(R,z,\sigma ,\tau ,\pi )=1\right].$$

计算可靠性 (Computational Soundness)

我们说 (Setup, Prove, Vfy, Sim) 是可靠的 (sound)，如果不可能证明一个错误的陈述，也就是说，说服 Verifier 在没有证据存在的情况下。 设 $L_R$ 是 $R$ 中存在匹配证据的陈述的语言。 形式上，我们要求对于所有非一致性多项式时间敌手 $\mathcal{A}$:

$$\mathrm{Pr}\left[(R,z)\leftarrow \mathcal{R}(1^{\lambda });(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});(\varphi ,\pi )\leftarrow \mathcal{A}(R,z,\sigma ):\varphi \notin L_R\text{ and }\text{Vfy}(\mathcal{R},\sigma ,\varphi ,\pi )=1\right]\approx 0.$$

计算知识可靠性 (Computational Knowledge Soundness)

加强可靠性的概念，我们称 (Setup, Prove, Vfy, Sim) 是一个知识论证 (argument of knowledge)，如果存在一个提取器 (extractor)，每当敌手产生一个有效的论证，该提取器就可以计算出一个证据。 该提取器可以完全访问敌手的状态，包括任何随机硬币。 形式上，我们要求对于所有非一致性多项式时间敌手 $\mathcal{A}$，存在一个非一致性多项式时间提取器 (extractor) ${\mathcal{X}}_A$，使得:

$$\mathrm{Pr}\left[(R,z)\leftarrow \mathcal{R}(1^{\lambda });(\sigma ,\tau )\leftarrow \text{Setup}(\mathcal{R});((\varphi ,\pi );w)\leftarrow (\mathcal{A}||{\mathcal{X}}_A)(R,z,\sigma ):(\varphi ,w)\notin R\text{ and }\text{Vfy}(\mathcal{R},\sigma ,\varphi ,\pi )=1\right]\approx 0.$$

---

密码学概念解释：

• 关系生成器 (Relation Generator) $\mathcal{R}$: 一个算法，它生成一个关系 $R$，该关系定义了要证明的陈述和对应的证据之间的联系。 例如，如果我们要证明一个数是合数，那么关系 $R$ 就是 “($\varphi$, $w$)：$\varphi$ 是一个合数，且 $w$ 是 $\varphi$ 的一个非平凡因子”。 关系生成器可以确保关系的复杂性在一个可控的范围内。

• 陈述 (Statement) $\varphi$: 需要证明其真实性的断言。

• 证据 (Witness) $w$: 证明陈述 $\varphi$ 为真的信息。 只有拥有证据的人才能生成有效的论证。

• 公共参考字符串 (Common Reference String, CRS) $\sigma$: 一段公开的信息，用于建立证明系统。 CRS 由 Setup 算法生成，并被 Prover 和 Verifier 共享。

• 模拟陷门 (Simulation Trapdoor) $\tau$: Setup 算法生成的秘密信息，只有 Simulator 知道。 它允许 Simulator 在不知道证据的情况下生成有效的证明，从而实现零知识性。

• Prover: 试图说服 Verifier 某个陈述是真实的实体。

• Verifier: 验证 Prover 提供的论证，判断陈述是否真实的实体。

• Simulator: 一个算法，它可以在不知道证据的情况下模拟 Prover 的行为，生成看似真实的证明。 Simulator 的存在是零知识性的关键。

• 完备性 (Completeness): 如果陈述是真实的，一个诚实的 Prover 总是能够说服一个诚实的 Verifier。

• 可靠性 (Soundness): 如果陈述是错误的，任何 Prover (即使是恶意的) 都无法说服 Verifier。

• 零知识性 (Zero-Knowledge): Verifier 从 Prover 处获得的唯一信息是陈述的真实性。 Verifier 不会获得关于证据的任何其他信息。

• 知识论证 (Argument of Knowledge): 如果 Prover 能够提供一个有效的论证，那么它必须“知道”对应的证据。 知识可靠性保证了这一点。

• 提取器 (Extractor): 一个算法，它可以从成功生成论证的 Prover 中提取出证据。

公开可验证性和指定验证者证明 (Public Verifiability and Designated Verifier Proofs)。 我们可以通过将 $\sigma$ 分成两个部分 ${\sigma }_P$ 和 ${\sigma }_V$ （分别由 Prover 和 Verifier 使用）来自然地泛化非交互式论证的定义。 当 ${\sigma }_V$ 可以从 ${\sigma }_P$ 推导出来时，我们说非交互式论证是公开可验证的 (publicly verifiable)。 否则，我们称其为指定验证者论证 (designated verifier argument)。 对于指定验证者论证，可以放宽可靠性和知识可靠性，使得敌手只能看到 ${\sigma }_P$，而不能看到 ${\sigma }_V$。

SNARG 和 SNARK (SNARGs and SNARKs)

一个 Verifier 在多项式时间 $\lambda +|\varphi |$ 内运行，并且证明大小在 $\lambda$ 中是多项式的非交互式论证，被称为预处理简洁非交互式论证 (preprocessing succinct non-interactive argument, SNARG)。 如果它是可靠的，则被称为 SNARG；如果它是知识可靠的，则被称为预处理简洁知识论证 (preprocessing succinct argument of knowledge, SNARK)。 如果我们还限制公共参考字符串在 $\lambda$ 中是多项式的，那么我们说这个非交互式论证是一个完全简洁的 SNARG 或 SNARK (fully succinct SNARG or SNARK)。 Bitansky 等人 [BCCT13] 表明，预处理 SNARK 可以被组合以产生完全简洁的 SNARK。 本文的重点是预处理 SNARK，其中公共参考字符串可能很长。

良性关系生成器 (Benign Relation Generators)

Bitansky 等人 [BCPR14] 表明，不可区分性混淆 (indistinguishability obfuscation) 意味着对于每个候选 SNARK，都存在辅助输出分布，使得敌手能够创建一个有效的证明，而不可能提取证据。 假设也存在公共硬币差异输入混淆和其他密码学假设，Boyle 和 Pass [BP15] 加强了这种不可能性，表明存在一个辅助输出分布，可以阻止所有候选 SNARK 的证据提取。 然而，这些反例依赖于特定的辅助输入分布。 因此，在下文中，我们将假设关系生成器是良性的 (benign)，即关系和辅助输入以一种方式分布，使得我们构建的 SNARK 可以是知识可靠的。

---

密码学概念解释：

• 公开可验证性 (Public Verifiability): 任何人都可以验证证明的有效性，而无需额外的秘密信息。 Verifier 只需要公共参考字符串（CRS）即可。

• 指定验证者证明 (Designated Verifier Proof): 只有指定的 Verifier 才能验证证明的有效性。 这种类型的证明需要 Verifier 持有秘密信息（例如，${\sigma }_V$）。 这可以用于隐私保护，因为只有指定的 Verifier 才能确信陈述是真实的。

• SNARG (Succinct Non-interactive ARgument): 一种非交互式论证系统，其中证明的大小非常小（通常是亚线性级别的）。 Verifier 的验证时间也应该比朴素验证方法更快。SNARG 可以用于降低验证的计算开销。

• SNARK (Succinct Non-interactive Argument of Knowledge): 一种特殊的 SNARG，它不仅提供简洁性，还提供知识可靠性。 这意味着，如果 Prover 能够生成一个有效的 SNARK 证明，那么它必须“知道”对应的证据。

• 预处理 SNARG/SNARK (Preprocessing SNARG/SNARK): 一种 SNARG/SNARK，需要在证明之前进行一些预处理步骤。 这些预处理步骤可能涉及生成公共参考字符串（CRS）或其他辅助信息。

• 完全简洁的 SNARG/SNARK (Fully Succinct SNARG/SNARK): 一种 SNARG/SNARK，其中证明的大小和公共参考字符串的大小都很小。

• 不可区分性混淆 (Indistinguishability Obfuscation, iO): 一种密码学技术，允许将一个程序混淆成另一个程序，使得即使知道混淆后的程序，也无法区分它和原始程序。 iO 是一种非常强大的工具，可以用于构建各种密码学方案。

• 良性关系生成器 (Benign Relation Generator): 一种关系生成器，它以一种“良好”的方式生成关系和辅助信息，使得可以构建知识可靠的 SNARK。 这通常意味着，关系和辅助信息的分布不会导致证据提取变得容易。

2.3 二次算术程序 (Quadratic arithmetic programs)

考虑一个由有限域 $\mathbb{F}$ 上的加法和乘法门组成的算术电路。 我们可以指定一些输入/输出线作为指定陈述，并使用电路的其余部分来定义一个证据。 这给出了一个二元关系 (binary relation) $R$，它由满足算术电路的线路值 (wire values) 和满足指定输入/输出线的证据线路 (witness wires) 组成，即，使其与指定的输入/输出线路一致。

推广算术电路，我们可能对由变量集合上的方程描述的关系感兴趣。 一些变量对应于陈述；其余变量对应于证据。 该关系由满足所有方程的陈述和证据组成。 方程将在 $a_0=1$ 和变量 $a_1,...,a_m\in \mathbb{F}$ 上，并且形式如下：

$$\sum _i{a}_i{u}_{i,q}\cdot \sum _i{a}_i{v}_{i,q}=\sum _i{a}_i{w}_{i,q}$$

其中 $u_{i,q},v_{i,q},w_{i,q}$ 是 $\mathbb{F}$ 中的常量，用于指定第 $q$ 个方程。

我们观察到，加法门和乘法门是这些方程的特例。 因此，这种算术约束系统确实推广了算术电路。 例如，乘法门可以被描述为 $a_i\cdot a_j=a_k$ (使用 $u_i=1,v_j=1$ 和 $w_k=1$，并将其余常量设置为 0)。 加法门以类似的方式处理（在定义方程的求和中可以自由处理 $a_l$，即，如果 $a_i+a_j=a_k$ 且 $a_k$ 乘以 $a_l$，我们可以简单地写作 $(a_i+a_j)\cdot a_l$，并跳过 $a_k$ 的计算）。

遵循 Gennaro, Gentry, Parno 和 Raykova [GGPR13]，我们可以将一组算术约束重构为一个二次算术程序 (quadratic arithmetic program, QAP)，假设 $\mathbb{F}$ 足够大。 给定 $n$ 个方程，我们选择任意不同的 $r_1,...,r_n\in \mathbb{F}$，并定义 $t(x)={\prod }_{q=1}^n(x-r_q)$。 此外，设 $u_i(x),v_i(x),w_i(x)$ 是 $n-1$ 阶多项式，使得对于 $i=0,...,m$, $q=1,...,n$，有 $u_i(r_q)=u_{i,q},v_i(r_q)=v_{i,q},w_i(r_q)=w_{i,q}$。

我们现在有 $a_0=1$，变量 $a_1,...,a_m\in \mathbb{F}$ 当且仅当在每个点 $r_1,...,r_q$ 中满足 $n$ 个方程：

$$\sum _{i=0}^m{a}_i{u}_i(r_q)\cdot \sum _{i=0}^m{a}_i{v}_i(r_q)=\sum _{i=0}^m{a}_i{w}_i(r_q).$$
主要也就是说有$n$个方程，然后m个变量（不包括常数1）
形式上，我们将使用具有以下描述的二次算术程序 (quadratic arithmetic programs) $\mathcal{R}$：

R=(F,aux,l,{ui(X),vi(X),wi(X)}i=0m,t(X)), \mathcal{R} = (\mathbb{F}, \text{aux}, l, \{u_i(X), v_i(X), w_i(X)\}_{i=0}^{m}, t(X)), R=(F,aux,l,{ui​(X),vi​(X),wi​(X)}i=0m​,t(X)),

其中 $\mathbb{F}$ 描述了一个有限域，aux 是一些辅助信息，$1\le l\le m$，且 $u_i(X),v_i(X),w_i(X),t(X)\in \mathbb{F}[X]$，并且 $u_i(X),v_i(X),w_i(X)$ 的阶严格低于 $n$， $t(X)$ 的阶为 $n$。 具有这种描述的二次算术程序定义了以下二元关系，其中我们定义 $a_0=1$：

$$R=\left\{(\varphi ,w)\mid \begin{array}{rl}& \varphi =(a_1,...,a_l)\in {\mathbb{F}}^l\\ & w=(a_{l+1},...,a_m)\in {\mathbb{F}}^{m-l}\\ & \sum _{i=0}^m{a}_i{u}_i(X)\cdot \sum _{i=0}^m{a}_i{v}_i(X)\equiv \sum _{i=0}^m{a}_i{w}_i(X)\mathrm{mod}t(X)\end{array}\right\}.$$

我们说 $\mathcal{R}$ 是一个二次算术程序生成器 (quadratic arithmetic program generator)，如果它生成上述形式的关系，且字段大小大于 $2^{\lambda -1}$。

关系可以以多种不同的方式在实践中产生。 关系生成器可以是确定性的，也可以是随机化的。 可能是首先生成字段 $\mathbb{F}$，然后其余关系建立在该字段之上。 或者，可能是首先指定多项式，然后选择一个随机字段。 为了使我们的定义对于字段和关系的生成方式具有不可知性，不同的选项都可以通过适当选择关系生成器来建模。

展望未来，在我们基于配对的 NIZK 论证中，让辅助信息 aux 指定一个双线性群。 使双线性群成为关系生成器的一部分可能看起来有点令人惊讶，但这提供了一个更好的设置模型，其中关系建立在已经存在的双线性群之上。 同样，在这种选择中没有普遍性的损失，人们可以认为这是一种传统的设置，在这种设置中，首先随机选择关系，然后选择双线性群，作为关系生成器分两步工作的一种特殊情况：首先选择关系，然后选择一个随机双线性群。 当然，让关系生成器选择双线性群是我们需要假设它是良性的另一个好理由；适当选择双线性群对于安全至关重要。

---

密码学概念解释：

• 算术电路 (Arithmetic Circuit): 一种计算模型，由加法门和乘法门组成。 电路的输入和输出是有限域中的元素。 算术电路可以用于表示各种计算问题。

• 二次算术程序 (Quadratic Arithmetic Program, QAP): 一种将算术电路转换为多项式方程组的方法。 QAP 是构建简洁证明的关键技术。 一个 QAP 实例由一组多项式 ($u_i(x)$, $v_i(x)$, $w_i(x)$) 和一个目标多项式 $t(x)$ 组成。 目标是找到一组系数 $a_i$，使得满足多项式方程。

• 线路值 (Wire Values): 算术电路中每条线路的值。

• 证据线路 (Witness Wires): 对应于证据的线路。

• 关系 (Relation): 描述了陈述和证据之间的关系。

• 有限域 (Finite Field): 一个包含有限个元素的集合，其中可以进行加法、减法、乘法和除法运算，并且满足通常的代数规则。 有限域在密码学中被广泛使用。

• 多项式 (Polynomial): 一个由变量、系数和运算符组成的表达式。 多项式在 QAP 中被用于表示算术电路的约束。

• 良性关系生成器 (Benign Relation Generator): 与之前定义相同，生成关系的方式不会导致证据提取变得容易。