zk-SNARK：简洁非交互式论证

zk-SNARK（零知识简洁非交互式知识论证）是一种证明，它：(1) 具备零知识性；(2) 简洁（证明很小，无论计算规模多大，验证都很快）；(3) 非交互式（只有一个证明字符串）。

西格玛协议适用于简单陈述（知晓离散对数）。对于复杂计算——“我已在私有输入上正确运行了此函数”——我们需要通用证明系统。SNARK 能够以 O(1) 的验证时间证明任意计算。

计算首先表示为算术电路：由有限域上的加法门和乘法门构成的有向无环图。例如，证明您知道满足 x^3 + x + 5 = 35 的 x，而不泄露 x=3。该电路约有 5 个门。

算术电路会被转换为 R1CS：一组约束 (A*z)*(B*z) = C*z，其中 z 是所有线路值组成的向量。每个乘法门都会变成一个约束。证明者必须找到满足所有约束的 z，同时不泄露私有线路值。

R1CS 会被转换为 QAP：多项式 A(x)、B(x)、C(x)，使得 A(x)*B(x)-C(x) 可被目标多项式 t(x) 整除，当且仅当约束得到满足。证明者证明自己知道多项式商 H(x)，但不泄露见证。

Groth16（2016）是效率最高的通用 SNARK。在可信设置（CRS 生成）之后，证明者输出一个由 3 个群元素组成的证明（BLS12-381 约 192 字节）。验证需要进行 3 次配对运算。无论电路大小，证明大小都保持不变。

Groth16 要求每个电路都进行一次可信设置：采样有毒废料（随机秘密），计算公共参考字符串，然后销毁有毒废料。如果废料留存，攻击者就能伪造证明。多方仪式（Powers of Tau）可以分散信任。

PLONK（2019）使用通用可信设置：一次仪式适用于所有不超过某个大小上限的电路。无需针对每个电路单独设置。权衡是：证明比 Groth16 略大。用于 zkEVM 实现（Polygon Hermez、zkSync Era）。

STARK（可扩展透明知识论证）无需可信设置，并使用哈希函数（具备后量子安全性）。权衡是：证明更大（几十 KB，而非 200 字节）。用于 StarkWare/StarkNet 和 Cairo 语言。SNARK 更小；STARK 抗量子。

Groth16 使用双线性配对：e: G1 × G2 → GT，其中 e(a*P, b*Q) = e(P,Q)^{ab}。这使得无需泄露数值即可在指数中检查多项式恒等式。BLS12-381 曲线针对高效 Groth16 配对进行了优化。

对于包含 10^6 个门的电路，Groth16 的证明生成时间约为 10 秒（在现代 CPU 上）。验证约需 1 毫秒。这种不对称性是有意设计的：证明者（执行繁重计算的一方）承担工作；验证者（区块链节点）几乎无需工作。

与 PLONK 相比，Groth16 的主要缺点是什么？

zk-SNARK 能够以固定大小的证明证明任意计算。流程：计算 → 算术电路 → R1CS → QAP → SNARK 证明。Groth16 效率最高（每个电路都需可信设置）；PLONK 使用通用设置。下一步：区块链中的 ZKP 应用。