摘要

非交互式证明（Non-interactive arguments）使证明者能够在不进行交互的情况下让验证者相信一个陈述是正确的。近年来，人们在理论和实践上对如何构造高效的非交互式证明取得了很大进展，这些证明具有小规模和低验证复杂度，即所谓的简洁非交互式论证（SNARGs）以及简洁非交互式知识论证（SNARKs）。

许多 SNARGs 的构造依赖于基于配对的密码学。在这些构造中，一个证明由若干群元素组成，而验证过程则是检查若干配对积等式。本文要解决的问题是：基于配对的高效 SNARGs 可以做到多高效？

我们的第一个贡献是提出了一种基于配对的（预处理的）SNARK，用于算术电路的可满足性问题，这是一个 NP 完全问题。在我们的 SNARK 中，我们使用不对称配对来提高效率，一个证明仅包含 3 个群元素，而验证则是通过 3 次配对运算来检查单个配对积等式。总体上，我们的 SNARK 具备零知识性，并且不会泄露证明者用于生成证明的见证的任何信息。

作为第二个贡献，我们回答了 Bitansky、Chiesa、Ishai、Ostrovsky 和 Paneth（TCC 2013）提出的一个公开问题，他们展示了 2 移动线性交互式证明具有线性判定过程。由此可见，在 SNARGs 中，如果证明者和验证者使用一般的非对称双线性群运算，那么证明就不能由单个群元素构成。这给出了基于配对的 SNARGs 的第一个下界。是否能将下界扩展到 2 个群元素的 SNARGs 仍然是一个有趣的开放问题，这样的话就能证明我们的 3 元素构造的最优性。

关键词：
SNARKs、非交互式零知识证明、线性交互式证明、二次算术程序、双线性群

1 引言

Goldwasser、Micali 和 Rackoff (GMR89) 引入了零知识证明，这类证明使得证明者能够在不泄露任何额外信息的情况下，让验证者相信某个陈述为真。它们有三个核心性质：

完备性（Completeness）： 给定一个陈述和见证，证明者可以说服验证者。

可靠性（Soundness）： 一个恶意的证明者不能说服验证者接受一个错误的陈述。

零知识性（Zero-knowledge）： 证明不会泄露除陈述真实性以外的任何信息，特别是不会泄露证明者的见证。

通信量是零知识证明的一个重要性能参数。Kilian (Kil92) 给出了第一个次线性通信的零知识论证，所需的通信量比待证明语句的规模要小。Micali (Mic00) 提出了子线性规模的证明，其方式是让证明者以计算效率高的方式发送简短的论证，验证者则通过加密函数来完成检查。正如 Kilian (Kil95) 所指出的，当交互式论证在 CRS 模型下变为公开的时，这一思路就会导向非交互式零知识证明。

Groth、Ostrovsky 和 Sahai (GOS12, Gro06, GS12) 引入了基于配对的 NIZK 证明，首次在标准假设下实现了线性规模的证明。Groth (Gro10) 将这些技术与交互式零知识论证的思想结合起来，提出了第一个常数规模的 NIZK 论证。Lipmaa (Lip12) 使用一种基于无进程集合的替代构造，来减少 CRS 的大小。

Groth 的常数规模 NIZK 论证基于多项式方程的集合，并利用配对来高效地验证这些方程。Gennaro、Gentry、Parno 和 Raykova (GGPR13) 找到了一种巧妙的构造方法，可以基于 Lagrange 插值多项式得到配对基础上的 NIZK 论证，其 CRS 大小与语句和见证的规模成比例。他们提出了多种多项式方程：用于布尔电路可满足性的二次跨度程序、用于算术电路可满足性的二次算术程序。Lipmaa (Lip13) 提出了更高效的二次跨度程序，Danezis、Fournet、Groth 和 Kohlweiss (DFGK14) 进一步改进了跨度程序，给出了由 4 个群元素构成的布尔电路可满足性 NIZK 论证。
…

1.1 贡献 (Our contribution)

简洁的 NIZK。
我们构造了一个用于算术电路可满足性的 NIZK 论证，其中一个证明仅包含 3 个群元素。除了规模小之外，证明也非常容易验证。验证者只需要计算少量的指数运算，生成一个与语句规模成正比的指数数，并检查一个单一的配对积等式，这个等式只涉及 3 次配对运算。我们的构造可以在任何类型的配对下实现，并特别适用于 Type III 配对，这是效率最高的一类配对。

该论证具备完美的完备性和完美的零知识性。为了保证可靠性（soundness），我们在通用双线性群模型下采取了强有力的立场 [Sho97, Nec94]，以获得最优性能。这一立场部分受到 Gentry 和 Wichs [GW11] 的启发，他们指出基于标准可验证假设的 SNARGs 必须是不可伪造的。尽管如此，遵循 Abe、Groth、Ohkubo 和 Tibouchi [AGOT14] 的做法，我们通过在对称配对环境下提供一个备选构造来防御密码分析攻击。为了获得最佳效率，我们的 NIZK 论证自然适用于不对称配对环境。但即使在对称配对环境下，通过在源群中保持一定程度的结构保密性，我们依然可以获得较强的安全性。因此我们提出了一个统一的 NIZK 论证，它可以在任何类型的配对下实现，同时结合了最佳效率和通用双线性群的抗性。

性能对比

我们在 表 1 中给出了布尔电路可满足性的性能对比，在 表 2 中给出了算术电路可满足性的性能对比。对比内容包括：公共参考串 (CRS) 的大小、证明的大小、证明者的计算量、验证者的计算量，以及验证所需的配对积等式数量。我们的方案在所有效率参数上表现更优。
(这个地方翻译有点乱，待全文看完后再回来修改下）
在这两个表中，当电路的门数 $m$ 超过输出线的数量时（典型情况），我们只展示了这种常见场景。在这种情况下，输出线数 $n$ 可以视为相对于 $m$ 和 $n+m$ 很小的量。

---

表 1

布尔电路可满足性比较：电路规模为 $m$ 个门，$n$ 条输入线，门为 2 输入逻辑门。

（符号解释：$G$ 表示群元素数量，$M$ 表示乘法，$E$ 表示指数运算，$P$ 表示配对）

---

表 2

算术电路可满足性比较：电路规模为 $m$ 个门，$n$ 条输入线，输出为 1。

---

补充说明

在布尔电路可满足性场景下，我们考虑任意输入数目的逻辑门。在算术电路可满足性中，我们考虑 2 输入的乘法门，每个输入可能是加权的和。每个乘法门的计算只依赖于固定数量的输入线；否则验证关系的代价可能远大于后续证明生成的代价。

我们注意到 [PHGR13] 使用对称双线性群 $G_1=G_2$，这使得 CRS 的大小更大，而我们的方案在不对称群下效率更高。实现时（例如 Pinocchio 系统），会采用不对称配对以获得最佳效率。

规模问题（Size Matters）
虽然证明规模减少到了 3 个群元素已经是很大改进，但仅仅减少验证时间并不够，我们希望进一步降低 CRS 大小，因为这在组合 SNARKs 时非常关键。[BCCT13, BCTV14] 表明带有大 CRS 的预处理 SNARK 可以组合成简洁的后置 SNARK，但需要较大的 CRS。我们的方案通过简化结构，把验证集中在单个配对等式上，大大降低了 prover 的计算量和 CRS 大小。
好的 👍 我来帮你把这一页的内容翻译成中文，并保持与前文连贯的学术风格。

---

文献中所有基于配对的 SNARKs 都遵循一个共同的范式：证明者通过通用群运算生成若干群元素，验证者则通过检查若干配对积等式来验证证明。Bitansky 等人 [BCI+13] 通过线性交互式证明 (LIP) 的定义形式化了这一范式。一个线性交互式证明在有限域上进行，证明者与验证者的消息由域元素向量构成。它进一步要求证明者在整个证明过程中只使用线性运算来计算消息。一旦我们有了合适的 2 移动 (2-move) LIP，就可以通过“在指数中”执行这些等式，将其编译为基于配对密码学的 SNARK。

我们的效率提升来源之一是：在算术电路的 LIP 系统中，证明者只需发送 3 个域元素，而现有方法 [GGPR13, PHGR13] 的二次算术程序对应的 LIP 需要证明者发送 4 个域元素。

第二个效率提升来源于：相比之前的工作，我们采用了更激进的 LIP 编译方式。Bitansky 等人 [BCI+13] 在对称双线性群环境中提出了一种转换方法，其中每个域元素被编译成两个群元素。然后，他们利用指数知识假设来证明证明者确实知道相关域元素。一个更保守的选择是将每个域元素编译成一个群元素。这样做虽然提升了效率，但只能在安全性模型 [Sho97, BBC05] 下获得较弱的安全性，因为此时我们不能再利用指数知识假设。

在这两种极端之间，还可以采取中间的折衷。例如，Parno 等人 [PHGR13] 提供了一个包含 4 个域元素的 LIP，其被编译为 7 个群元素。在本文中，我们选择了最大化效率的方式：把 LIP 中的每个域元素编译成单个群元素，并在通用群模型下证明安全性。

我们更倾向于使用不对称双线性群，因为它们比对称群效率更高。这意味着，LIP 中证明者发送的域元素数量并不是唯一的考量点，编译方式的优化程度同样重要。在不对称双线性群中，一个域元素可以作为第一个源群的指数、第二个源群的指数，或者两者皆是。我们的 LIP 被精心设计，使得每个域元素都可以编译到单个源群元素中，从而把证明规模减少到仅 3 个群元素。

---

下界 (Lower bounds).
在追求更高效的非交互式论证时，一个自然的问题是：最小的证明规模是多少？
我们将证明，基于配对的 SNARGs 不可能存在仅用 单个群元素 的证明。

这个结果回答了 Bitansky 等人 [BCI+13] 提出的一个开放问题：是否存在一种 LIP，其验证器具有线性判定过程？如果存在，这样的线性判定过程会非常有用，例如它能使基于 ElGamal 加密的 SNARGs 构造成为可能。

我们对这一问题给出了否定答案。我们的结果表明，任何基于配对的 SNARG 都必须至少包含两个配对群元素，否则验证过程会变成二次复杂度而不是线性，无法保持高效。因此，在非对称双线性组上工作，我们必须在两个源组中都有元素才能进行这种配对。这排除了1组元素的存在，无论它是零知识是否为零，并且表明我们的NIZK参数接近最佳证明大小。通过构造一个源于每个源组G1和G2的一个元素，或者排除这种SNARG的存在，可以完全缩小差距，这仍然是一个有趣的开放问题。

2.预备知识

给定两个函数 f, g: N -> [0,1]，f(λ) ≈ g(λ) 当 |f(λ) - g(λ)| = λ^-ω(1)。我们说 f 是可忽略的 (negligible)，当 f(λ) ≈ 0 时；而 f 是压倒性的 (overwhelming)，当 f(λ) ≈ 1 时。 我们将使用 λ 来表示安全参数 (security parameter)，其直觉是，当 λ 增长时，我们期望更强的安全性。
我们写作 y = A(x; r)，表示算法 A 在输入 x 和随机数 r 上的输出 y。 我们写作 y ← A(x)，表示算法 A 在输入 x 上随机挑选 r 并设置 y = A(x; r)。 我们也写作 y ← S，表示从集合 S 中均匀随机抽样 y。 我们假设可以从集合（例如 Z_p）中均匀地抽样。
遵循 Abe 和 Fehr [AF07] 的记法，我们写作 (y; z) ← (A || X_A)(x)，表示算法 A 在输入 x（包括随机硬币）上的输出 y 和 X_A上的输出 z。（一个相同的输入，不同函数上的输出）

2.1 双线性群 (Bilinear Groups)

我们将在具有以下属性的双线性群 (p, G₁, G₂, G_T, e, g, h) 上进行研究：
G₁, G₂, G_T 是素数阶 p 的群。
配对 (Pairing) e: G₁ x G₂ -> G_T 是一个双线性映射。
g 是 G₁ 的生成元，h 是 G₂ 的生成元，且 e(g, h) 是 G_T 的生成元。
存在高效的算法来计算群操作，评估双线性映射，决定群元素的成员资格，决定群元素的相等性，以及抽样群的生成元。我们将这些称为通用群操作 (generic group operations)。
有许多方法来建立双线性群，包括对称双线性群（其中 G₁ = G₂）和非对称双线性群（其中 G₁ ≠ G₂）。 Galbraith, Paterson 和 Smart [GPS08] 将双线性群分为 Type I（其中存在可以高效计算的非平凡同态 φ: G₂ -> G₁），Type II（其中不存在可以高效计算的同态 φ: G₂ -> G₁），和 Type III。 Type III 双线性群是最有效率的双线性群，因此也是实际应用中最相关的。 我们给出了在 Type III 双线性群中基于 SNARG 的配对。我们的结构可以在所有三种类型的双线性群中实例化。
使用一种用离散对数表示群元素的记法将会很有用。 我们强调离散对数很难计算，这种记法仅用于表示目的。 我们写作 [a]₁ 表示 g^a, [b]₂ 表示 h^b, 以及 [c]_T 表示 e(g, h)^c。 使用这种记法，g = [1]₁, h = [1]₂，以及 e(g, h) = [1]_T，而中性元素（单位元，其它元素与此元素运算，则不会发生变化，比如加加法中的0，乘法中1）是 [0]₁, [0]₂ 和 [0]_T。 在群中使用离散对数表示法时，在所有群中使用加法记法是很自然的，例如，[a]_T + [b]_T = [a + b]_T。一个群元素的向量将会被表示成 [a]_i。我们的记法允许我们使用标准的线性代数记法，所以 [a]_i + [b]_i = [a + b]_i，假设 a 和 b 有相同的维度，并且也假设适当的维度。我们定义 A[b]_i = [Ab]_i。 给定两个包含 n 个群元素的向量 [a]₁ 和 [b]₂，我们定义它们的点积为 [a]₁ · [b]₂ = e([a · b]_T)，它可以被使用配对 e 高效地计算出来。
我们说一个算法是通用的 (generic)，如果它只使用通用的群操作来创建和操作群元素。 Shoup [Sho97] 将通用群模型形式化，通过考虑随机单射编码 [·]_i 来代替实群元素。 通用群操作然后通过访问一个预言机来处理，例如，它可以返回 [a + b]_i 给定 [a]_i 和 [b]_i。 由于编码的随机性，通用群预言机只能通过有意义的操作来返回元素。 一个含义是，如果它有输入 [a]₁ 并且返回元素 [b]，我们可以通过检查加法查询，有效地推导出 G₁ 中的一个矩阵 M，使得 b = Ma。 同样的情况也适用于 G₂，而在 G_T 中，也可能存在由配对运算产生的元素，但我们仍然可以将任何输出元素写成输入中显式二次多项式。