Groth16：从 QAP 到配对检验方程

maocred@gmail.com (Halois) — Sat, 06 Dec 2025 08:00:00 +0800

Reading: Groth16 as a derivation, not a magic trick.

Groth16 最容易被记成一句营销话术：proof 只有三个群元素，验证很快，所以它很强。这个说法不假，但几乎没解释任何东西。真正该理解的是：这三个群元素到底在编码什么；它们为什么足以代表一个 QAP witness；以及最后那条 pairing product equation 为什么不是凭空出现的黑箱检查，而是 QAP identity 在秘密点评估之后的压缩形式。

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

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

第 5 篇解释了 KZG 风格的核心直觉：多项式关系可以通过秘密点 $\tau$ 上的群编码与 pairing check 来验证。Groth16 本质上就是把这条思路做到了 QAP satisfiability relation 上，但它还额外引入了若干 trapdoors，把 witness 可伪造空间压得非常窄，最终只留下三段 proof tuple。¹ ²

所以这篇不打算把 Groth16 写成一个“比别的 SNARK 更短”的结果，而是把这条推导链写出来：

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

从算术电路到 R1CS、QAP 与 AIR

maocred@gmail.com (Halois) — Thu, 04 Dec 2025 08:00:00 +0800

Reading: arithmetization as interface design, not notation churn.

前面三篇一直在准备同一件事：证明系统不会直接消费“某个程序跑对了”这种语义句子。它们消费的是某种 algebraic surface，最好能被承诺、挑战、开点、低度测试或者 pairing equation 直接处理。到了这一篇，主角不再是 transcript skeleton，而是 computation 本身如何被翻译成代数约束。

如果只用一句话概括算术化，它就是把“计算正确”改写成“某个 witness 满足一组 field 上的代数关系”。但这句话还不够，因为后面的证明系统并不直接吃“很多条关系”。它们更喜欢的是：

向量上的 rank-1 constraints
多项式上的恒等式或整除关系
execution trace 上的 transition constraints

所以这一篇真正要写清楚的不是名词，而是两条链：

$$ \text{circuit} \longrightarrow \text{R1CS} \longrightarrow \text{QAP} $$

以及

$$ \text{trace} \longrightarrow \text{AIR}. $$

两条链的共同目标都是同一个：把 computation 变成一个证明系统能消费的 polynomial object。¹ ² ³

Qap on As it was

Groth16：从 QAP 到配对检验方程

从算术电路到 R1CS、QAP 与 AIR