Groth16：从 QAP 到配对检验方程

2025-12-06 约 2506 字预计阅读 6 分钟

Scope: 从 QAP 系数、CRS query 到 Groth16 pairing equation 的符号对应。

Groth16 proof 只有三个群元素。要解释这项压缩，需要写清三个元素的指数、public instance 的 verifier query，以及 pairing equation 如何展开回 QAP identity。

前两篇已经把接口准备好了。第 4 篇给出

\[ A_{\mathbf{w}}(X)B_{\mathbf{w}}(X) - C_{\mathbf{w}}(X) = H(X)Z(X), \]

第 5 篇已经说明多项式关系可以在秘密点 $\tau$ 上编码并用 pairing 检查。Groth16 将该方法应用到 QAP satisfiability relation，并用额外 trapdoors 约束 witness 编码与随机化空间。¹ ²

本文展开以下推导链：

\[ \text{QAP relation} \longrightarrow \text{CRS at secret point} \longrightarrow \text{proof tuple } (A,B,C) \longrightarrow \text{pairing product equation}. \]

Groth16 消费的对象是什么

Groth16 处理已经算术化完成的 QAP instance。设 QAP 为三族多项式

\[ \{u_i(X),v_i(X),w_i(X)\}_{i=0}^{m}, \]

witness 系数写成

\[ \mathbf{a}=(a_0,a_1,\ldots,a_m),\qquad a_0=1. \]

定义

\[ U(X)=\sum_{i=0}^{m}a_i u_i(X),\quad V(X)=\sum_{i=0}^{m}a_i v_i(X),\quad W(X)=\sum_{i=0}^{m}a_i w_i(X). \]

QAP satisfiability 写成

\[ U(X)V(X)-W(X)=h(X)t(X), \]

其中 $t(X)$ 是约束点集合的 vanishing polynomial，$h(X)$ 是 quotient polynomial。若 witness 满足全部约束，左边在每个约束点为零，因而被 $t(X)$ 整除。

Instance, Witness, And Public Inputs

取 $a_1,\ldots,a_\ell$ 为 public instance，$a_{\ell+1},\ldots,a_m$ 为 private witness：

\[ \mathbf{x}=(a_1,\ldots,a_\ell),\qquad \mathbf{w}=(a_{\ell+1},\ldots,a_m). \]

Groth16 instance 是：对固定 $\mathbf{x}$，prover 知道 $\mathbf{w}$，使上述 QAP identity 成立。verifier 不接收 private coefficients，但会显式计算 public-input query。

CRS 中的五个 Trapdoors 与两类 Query

Groth16 CRS 在秘密点上编码 QAP 多项式，并注入用于分离 public/private query 与随机化空间的 trapdoors。

The Role Of $\tau$

第一层 trapdoor 是

\[ \tau. \]

它的角色和上一篇 KZG 里的秘密点评估一样：把多项式关系固定在某个隐藏点上检查。因为若

\[ U(X)V(X)-W(X)=h(X)t(X), \]

作为多项式恒等式成立，那么在 $X=\tau$ 处也有

\[ U(\tau)V(\tau)-W(\tau)=h(\tau)t(\tau). \]

Groth16 的 CRS 会给出一系列元素，使 prover 能在不知道 $\tau$ 的情况下，仍然构造这些多项式在 $\tau$ 上的群编码。

Alpha, Beta, Gamma, Delta

完整符号还需要四个 trapdoors：

\[ \alpha,\ \beta,\ \gamma,\ \delta. \]

定义组合多项式

\[ K_i(X)=\beta u_i(X)+\alpha v_i(X)+w_i(X). \]

$\alpha,\beta$ 锚定 proof 中两组主线性组合；$\gamma$ 缩放 public-input query；$\delta$ 缩放 private witness、quotient 与 prover randomization。public 与 private coefficients 因而进入不同 CRS 分区。

Verifying Key 与 Proving Key

使用加法记号 $[x]_1=xG_1$、$[x]_2=xG_2$。verifying key 至少包含

\[ [\alpha]_1,\quad[\beta]_2,\quad[\gamma]_2,\quad[\delta]_2, \]

以及 public query

\[ \left\{\left[\frac{K_i(\tau)}{\gamma}\right]_1\right\}_{i=0}^{\ell}. \]

proving key 还包含用于构造 $A,B$ 的 $u_i(\tau),v_i(\tau)$ 群编码、private query

\[ \left\{\left[\frac{K_i(\tau)}{\delta}\right]_1\right\}_{i=\ell+1}^{m}, \]

以及 quotient query

\[ \left\{\left[\frac{\tau^j t(\tau)}{\delta}\right]_1\right\}_{j}. \]

verifier 只能线性组合 public query；prover 使用 private 与 quotient query，但无法把 private coefficient 搬进 $\gamma$ 分区。

Toxic Waste And Ceremony Intuition

toxic waste 指 $(\tau,\alpha,\beta,\gamma,\delta)$ 及足以重建相同结构的信息。

若 setup 方保留足够多的 trapdoor 信息，它可能直接构造满足 verifier pairing equation 的群元素。该风险来自 CRS 表示可伪造，并非 pairing 群本身失效。

trusted setup ceremony 需要确保：

有人知道参数如何生成
但没有任何单一方保留完整 toxic waste

这也是 Powers of Tau 类 ceremony 存在的原因。

Proof 三元组在编码什么

Groth16 proof 通常写成三个群元素：

\[ \pi = (A, B, C), \]

其中 $A$ 落在 $G_1$，$B$ 落在 $G_2$，$C$ 落在 $G_1$。如果只记住“只有三个元素”，还是没有回答它们分别带了什么信息。

A And B Elements

令

\[ A_{\mathrm{exp}}=\alpha+U(\tau)+r\delta, \]\[ B_{\mathrm{exp}}=\beta+V(\tau)+s\delta, \]

其中 $r,s\xleftarrow{\$}\mathbb{F}$ 由 prover 采样。proof 的前两个元素为

\[ A=[A_{\mathrm{exp}}]_1,\qquad B=[B_{\mathrm{exp}}]_2. \]

proving key 也提供构造 $[B_{\mathrm{exp}}]_1$ 所需的 G1 query；它只在 $C$ 的计算中使用，不会作为第四个 proof 元素发送。

The C Element

先定义 private contribution

\[ K_{\mathrm{priv}}(\tau)=\sum_{i=\ell+1}^{m}a_iK_i(\tau). \]

第三个 proof 元素的指数是

\[ \begin{aligned} C_{\mathrm{exp}} &=\frac{K_{\mathrm{priv}}(\tau)+h(\tau)t(\tau)}{\delta}\\ &\quad+sA_{\mathrm{exp}}+rB_{\mathrm{exp}}-rs\delta, \end{aligned} \]

并发送

\[ C=[C_{\mathrm{exp}}]_1. \]

第一项由 private 与 quotient queries 构造；后三项补偿 $A$、$B$ 中的随机化交叉项。这个公式给出了 $C$ 的全部职责，无需再用“剩余部分”描述。

Why Three Group Elements Are Enough

三个元素足够的原因可以分成四步：

QAP 已经把 many constraints 压成一条 divisibility relation
CRS 已经把多项式族固定在秘密点上
$\alpha,\beta,\gamma,\delta$ 将 public/private query 与随机化限制在不同 algebraic subspaces
pairing 可以在乘法层面同时检查多个编码关系

所以最后 verifier 不需要看很多开点证明，也不需要看完整 witness commitment，只需要看三个 carefully structured group elements。

Key Observation. QAP reduction、structured CRS 与 pairing bilinearity 共同减少了 verifier 必须显式接收的对象数量。

从 quotient polynomial 到 pairing 方程

下面直接展开 pairing product equation。

Evaluate The QAP Identity At The Secret Point

若 witness 正确，则

\[ U(X)V(X)-W(X)=h(X)t(X). \]

在 $X=\tau$ 上评估：

\[ U(\tau)V(\tau)-W(\tau)=h(\tau)t(\tau). \]

verifier 不知道 $\tau$，因此只处理这些标量的群编码。

Move To Pairing Space

pairing 的双线性让我们可以把标量乘法转成群元素之间的可检验关系：

\[ e([a]_1,[b]_2)=e(G_1,G_2)^{ab}. \]

令 public-input accumulation 为

\[ \mathsf{vk}_{\mathbf{x}}=\sum_{i=0}^{\ell}a_i\left[\frac{K_i(\tau)}{\gamma}\right]_1. \]

pairing $e(\mathsf{vk}_{\mathbf{x}},[\gamma]_2)$ 的目标群指数正好是 public contribution $\sum_{i=0}^{\ell}a_iK_i(\tau)$。

The Pairing Product Check

verifier 检查

\[ \begin{aligned} e(A,B) &=e([\alpha]_1,[\beta]_2) \cdot e(\mathsf{vk}_{\mathbf{x}},[\gamma]_2) \cdot e(C,[\delta]_2). \end{aligned} \]

左边的目标群指数是 $A_{\mathrm{exp}}B_{\mathrm{exp}}$。右边指数可逐行展开。记

\[ K_{\mathrm{pub}}(\tau)=\sum_{i=0}^{\ell}a_iK_i(\tau), \]

则

\[ \begin{aligned} \alpha\beta+K_{\mathrm{pub}}(\tau)+\delta C_{\mathrm{exp}} &=\alpha\beta+\sum_{i=0}^{m}a_iK_i(\tau)+h(\tau)t(\tau)\\ &\quad+s\delta A_{\mathrm{exp}}+r\delta B_{\mathrm{exp}}-rs\delta^2\\ &=\alpha\beta+\beta U(\tau)+\alpha V(\tau)+W(\tau)\\ &\quad+U(\tau)V(\tau)-W(\tau)\\ &\quad+s\delta A_{\mathrm{exp}}+r\delta B_{\mathrm{exp}}-rs\delta^2\\ &=(\alpha+U(\tau)+r\delta)(\beta+V(\tau)+s\delta)\\ &=A_{\mathrm{exp}}B_{\mathrm{exp}}. \end{aligned} \]

第二个等号使用 $\sum_i a_iK_i=\beta U+\alpha V+W$，第三个等号使用 QAP identity $h t=UV-W$。这给出了 proof 三元组、public instance 与最终 pairing equation 的完整符号对应。

Completeness Intuition

上面的等式链已经给出 completeness：诚实 prover 使用满足 QAP 的 $\mathbf{a}$ 和任意 $r,s$ 构造 $A,B,C$，两边指数相等，双线性映射因而返回相同目标群元素。KZG 与 Groth16 都在秘密点评估 polynomial identity；Groth16 另外分离 public/private query，并把 witness randomization 纳入同一验证式。

Knowledge Soundness 与 Trusted Setup 边界

Groth16 的安全性目标是 knowledge soundness。

Knowledge Soundness Assumptions

其知识可靠性依赖 pairing-friendly groups 上的代数假设，以及从成功 prover 提取 witness 的模型。

若有人能构造通过 verifier pairing check 的 proof，则在相应代数假设和知识模型下，extractor 应能恢复满足 QAP relation 的 witness。

这里的 knowledge 由 extractor 定义。

What Toxic Waste Leakage Breaks

toxic waste 泄露后，攻击者可能绕过 witness relation 直接构造满足 pairing equation 的代数对象。

setup 正确销毁 trapdoors 时，CRS 的代数分区支撑知识可靠性；trapdoors 泄露时，伪造空间重新打开。

这也解释了为什么 Groth16 虽然非常实用，但 ceremony 边界永远是它架构的一部分，而不是部署细节。

Summary

Groth16 若从结果往回看，会像一个只有三个群元素的神秘 SNARK；但若从 QAP 往前推，它的结构其实很连贯。

第一步，QAP 把电路满足性写成