从算术电路到 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。¹ ² ³

R1cs on As it was

从算术电路到 R1CS、QAP 与 AIR