零知识证明工程实战：从 zk-SNARK 到 zk-STARK 的电路构造与证明生成链路

引言：零知识的数学奇迹

零知识证明（Zero-Knowledge Proof, ZKP）允许证明者向验证者证明某个陈述为真，却不泄露任何额外信息。这一看似矛盾的概念由 Goldwasser、Micali 和 Rackoff 在1985年提出，如今已成为区块链扩容（ZK-Rollup）、隐私计算和身份认证的核心基础设施。本文从数论出发，系统梳理 zk-SNARK 和 zk-STARK 的代数构造、电路编写和证明生成全链路。

第一部分：从交互式证明到非交互式证明

1.1 IP 与 PCP：理论基石

交互式证明（Interactive Proof, IP）中，验证者 V 发送挑战（challenge），证明者 P 回应。关键结论：IP = PCP[O(log n), O(1)] = NEXP —— 任何可验证的计算都可以转化为对概率可检查证明（Probabilistically Checkable Proof）的常数比特查询。

1.2 Fiat-Shamir 变换

将交互式 Σ-protocol 转化为非交互式证明的标准技术：用哈希函数 H(transcript) 替代验证者的随机挑战，使证明可被任何人验证。安全性依赖于随机预言机模型（Random Oracle Model）下哈希函数的伪随机性。

1.3 Trusted Setup 与结构化参考串

SRS（Structured Reference String）是一组提前生成的公共参数，通常通过多方计算仪式（MPC Ceremony）生成。若 SRS 的陷门信息泄露（toxic waste），攻击者可伪造证明。通用且可更新的 SRS（如 KZG 承诺使用的 SRS）是 PLONK 和 Marlin 等新一代协议的核心。

第二部分：zk-SNARK 代数构造

2.1 R1CS 约束系统

Rank-1 Constraint System（R1CS）是描述算术电路的标准形式，由三元组向量 (a, b, c) 表示每个乘法门：

⟨a, z⟩ × ⟨b, z⟩ = ⟨c, z⟩

其中 z = (1, w, x₁, x₂, ...) 为实例向量，w 为见证（witness）。每个 R1CS 约束对应电路中一个乘法门的线性组合关系。

2.2 二次算术程序（QAP）：从 R1CS 到多项式

通过拉格朗日插值将 m 个 R1CS 约束转化为 m 1 次多项式 A(x)、B(x)、C(x)，使得 A(i)·B(i) = C(i) 对所有 i ∈ {1,...,m} 成立。等价地，存在目标多项式 t(x) = ∏(x - i) 使得：

A(x)·B(x) - C(x) = H(x)·t(x)

Groth16 的验证方程基于配对等式 e(g^α, g^β) · e(g^L, g^R) = e(g^H, g^Z) · e(g^C, g)，可在 O(1) 配对（每次约 1ms）内完成验证。

2.3 PLONK：通用 SRS 与置换论证

PLONK 用复制约束（copy constraint）替代 R1CS 约束描述布线关系。其核心创新是置换多项式 σ(X) 和如下约束等式：

(a(X) β·X γ)(b(X) β·k₁·X γ)(c(X) β·k₂·X γ) = (a(X) β·σ₁(X) γ)(b(X) β·σ₂(X) γ)(c(X) β·σ₃(X) γ)

该等式保证每个门的输出线连接到下一个门的输入线（线路连接验证）。PLONK 使用 KZG 承诺（Kate commitment）实现通用 SRS，单证明大小约 400 字节，验证时间 O(1)。

2.4 Groth16 vs PLONK vs Marlin

第三部分：zk-STARK——透明且量子安全的替代方案

3.1 FRI 协议：低度测试

STARK 基于 Fast Reed-Solomon IOPP（FRI, Fast Reed-Solomon IOPP of Proximity）：证明某个函数 f 是低度（