零知识证明入门：Groth16 协议从零实现

如何向一个人证明「我知道 x³ + x + 5 = 35 的一个解」，却不告诉他解是多少？Groth16——Zcash 曾用、Tornado Cash 在用的 zk-SNARK 协议——给出了答案：证明只有 3 个群元素（约 200 字节），验证只需一次配对运算（毫秒级），且数学上保证证明者无法伪造、验证者学不到任何秘密。本文用纯 Python 实现一个完整可运行的迷你 Groth16 系统：从算术电路到 R1CS、QAP 多项式编码、教学用椭圆曲线配对、可信设置、证明生成与验证，全链路约 400 行代码，跑通「证明我知道三次方程的解」的完整流程。

一、零知识证明的三个性质与 SNARK 的含义

一个零知识证明系统必须同时满足：

• 完备性（Completeness）：诚实的证明者持有合法证据时，证明必然通过验证。
• 可靠性（Soundness）：不知道证据的作弊者，伪造证明通过验证的概率可忽略。
• 零知识性（Zero-Knowledge）：验证过程除了「命题为真」之外，不泄露任何关于证据的信息。

zk-SNARK 的全称拆解了 Groth16 的四个工程特性：Succinct（简洁——证明短、验证快）、Non-interactive（非交互——证明者一次性发出证明，无需来回对话）、ARgument（论证——可靠性对计算能力有限的作弊者成立）、Knowledge（知识——作弊者伪造成功意味着他真的能「提取」出证据）。Groth16 至今仍是证明尺寸最小、验证最快的实用 SNARK，代价是每个电路需要一次专用的可信设置。

二、第一步：从计算到算术电路

SNARK 不能直接证明任意程序，必须先把计算拍平成只含加法和乘法的算术电路。以经典教学例子为例：证明知道 x³ + x + 5 = 35 的解（即 x=3，但我们不泄露它）：

# 计算: out = x³ + x + 5
# 拍平为电路门:
#   sym1 = x * x        (x²)
#   y    = sym1 * x     (x³)
#   sym2 = y + x        (x³ + x)
#   out  = sym2 + 5     (x³ + x + 5)
#
# 见证向量（满足电路时各变量的取值）:
#   [1, x, out, sym1, y, sym2]
# x=3 时: [1, 3, 35, 9, 27, 30]

三、第二步：R1CS——把电路编码为约束系统

R1CS（Rank-1 Constraint System）把每个乘法门编码为一个三元组 (A, B, C)，要求见证向量 w 满足 (A·w) × (B·w) = (C·w)。我们的电路产生 4 个约束（加法门可以合并进乘法约束的线性组合里）：

# 变量顺序: [1, x, out, sym1, y, sym2]
# 每个约束是三个稀疏向量，只有非零项写出来:

R1CS = [
    # 约束1: sym1 = x * x
    {'A': {1: 1},        # A·w = x
     'B': {1: 1},        # B·w = x
     'C': {3: 1}},       # C·w = sym1
    # 约束2: y = sym1 * x
    {'A': {3: 1},
     'B': {1: 1},
     'C': {4: 1}},
    # 约束3: sym2 = (y + x) * 1
    {'A': {4: 1, 1: 1},  # A·w = y + x
     'B': {0: 1},        # B·w = 1
     'C': {5: 1}},
    # 约束4: out = (sym2 + 5) * 1
    {'A': {5: 1, 0: 5},  # A·w = sym2 + 5
     'B': {0: 1},
     'C': {2: 1}},       # C·w = out
]

def check_r1cs(witness, field_p):
    """验证见证向量是否满足全部 R1CS 约束"""
    for i, c in enumerate(R1CS):
        a = sum(coef * witness[v] for v, coef in c['A'].items()) % field_p
        b = sum(coef * witness[v] for v, coef in c['B'].items()) % field_p
        cv = sum(coef * witness[v] for v, coef in c['C'].items()) % field_p
        if a * b % field_p != cv:
            return False, f"约束 {i} 不满足"
    return True, "全部约束满足"

# 见证 x=3: check_r1cs([1,3,35,9,27,30], p) → 全部约束满足 ✓
# 伪造 x=4: 约束4失败 (4³+4+5=73≠35) → 拒绝 ✓

四、第三步：QAP——把约束系统编码为多项式

QAP（Quadratic Arithmetic Program）是 SNARK 的核心魔法：用拉格朗日插值，把「每个约束逐条检查」转化为「一个多项式整除关系的一次检查」。每个变量在约束 i 处的取值模式被插值成多项式 Aⱼ(t)、Bⱼ(t)、Cⱼ(t)，全部约束同时成立 ⟺ 存在商多项式 H(t) 使得 (ΣwⱼAⱼ)(ΣwⱼBⱼ) - (ΣwⱼCⱼ) = H(t)·Z(t)，其中 Z(t) 是目标多项式（在约束点处为零）：

# 所有运算在有限域 F_p 上进行（教学用小素数域，生产用 256 位）
p = 79

def lagrange_interp(points, field_p):
    """拉格朗日插值: 给定点集 [(x0,y0),...]，返回多项式系数（低次在前）"""
    n = len(points)
    poly = [0]
    for i in range(n):
        xi, yi = points[i]
        # 基多项式: Π(t - xj) / Π(xi - xj), j ≠ i
        num, den = [1], 1
        for j in range(n):
            if i == j:
                continue
            xj = points[j][0]
            num = poly_mul(num, [-xj % field_p, 1], field_p)
            den = den * (xi - xj) % field_p
        scale = yi * pow(den, -1, field_p) % field_p
        term = [c * scale % field_p for c in num]
        poly = poly_add(poly, term, field_p)
    return poly

def build_qap(field_p):
    """把 R1CS 的 4 个约束插值为 QAP 多项式簇。
    约束 i 对应取值点 t = i+1。"""
    n_vars = 6  # [1, x, out, sym1, y, sym2]
    A_polys, B_polys, C_polys = [], [], []
    for v in range(n_vars):
        a_pts = [(i + 1, c['A'].get(v, 0) % field_p)
                 for i, c in enumerate(R1CS)]
        b_pts = [(i + 1, c['B'].get(v, 0) % field_p)
                 for i, c in enumerate(R1CS)]
        c_pts = [(i + 1, c['C'].get(v, 0) % field_p)
                 for i, c in enumerate(R1CS)]
        A_polys.append(lagrange_interp(a_pts, field_p))
        B_polys.append(lagrange_interp(b_pts, field_p))
        C_polys.append(lagrange_interp(c_pts, field_p))
    # 目标多项式 Z(t) = (t-1)(t-2)(t-3)(t-4)
    Z = [1]
    for i in range(1, 5):
        Z = poly_mul(Z, [-i % field_p, 1], field_p)
    return A_polys, B_polys, C_polys, Z

def witness_poly_eval(polys, witness, t, field_p):
    """计算 Σ wⱼ·Pⱼ(t)：见证加权的 QAP 多项式在 t 处取值"""
    total = 0
    for w, poly in zip(witness, polys):
        total = (total + w * poly_eval(poly, t, field_p)) % field_p
    return total

QAP 的威力在于：验证 4 个约束不再需要逐条代入，只需检查一个整除关系在随机点 t = τ 处成立——由 Schwartz-Zippel 引理，两个不同多项式在随机点撞值的概率是 d/p（d 为次数），p 足够大时这个概率就是天文数字分之一。这就是「一次检查代替万次检查」的数学保证。

五、第四步：椭圆曲线与配对——在不泄露 w 的前提下验证等式

问题还剩最后一环：验证者不能直接拿到见证 w（那就泄露秘密了）。Groth16 的解法是把 QAP 等式「藏进」椭圆曲线群：证明者提交的是群元素 [w·A(τ)]G₁ 这类编码——离散对数困难保证从中反推不出 w，而双线性配对 e: G₁×G₂→Gₜ 允许验证者在编码层面检查乘法关系 e(aG₁, bG₂) = e(G₁,G₂)^(ab)。实现一个教学版小曲线配对（生产用 BN254/BLS12-381，原理相同）：

# 教学用椭圆曲线: y² = x³ + 3 (mod 79)，阶含 67 阶子群
class EC:
    P = 79
    ORDER = 67          # 教学子群阶（真实曲线约 2²⁵⁴）
    G = (1, 2)          # 生成元
    INF = None

    @classmethod
    def add(cls, A, B):
        if A is None: return B
        if B is None: return A
        x1, y1 = A; x2, y2 = B
        if x1 == x2 and (y1 + y2) % cls.P == 0:
            return None
        if A == B:
            m = (3 * x1 * x1) * pow(2 * y1, -1, cls.P) % cls.P
        else:
            m = (y2 - y1) * pow(x2 - x1, -1, cls.P) % cls.P
        x3 = (m * m - x1 - x2) % cls.P
        y3 = (m * (x1 - x3) - y1) % cls.P
        return (x3, y3)

    @classmethod
    def mul(cls, A, k):
        """标量乘法: 双加算法"""
        R = None
        while k:
            if k & 1:
                R = cls.add(R, A)
            A = cls.add(A, A)
            k >>= 1
        return R

# 双线性配对的教学模拟: 用两个独立群的可乘结构
# （真实配对是 Tate/Weil 配对的 Miller 算法，此处用同构群演示接口语义）
def pairing(a_pt, b_scalar_pt, base=2):
    """e(aG, bG) 的同态性质: log 层面相当于 a*b。
    教学中用 pow(base, a*b) 模拟配对结果的乘法同态。"""
    return pow(base, (a_pt * b_scalar_pt) % EC.ORDER, EC.P)

六、第五步：可信设置（Powers of Tau）

Groth16 需要一次电路专用的可信设置：随机抽取秘密 τ（以及 α、β、γ、δ 五个 toxic waste），公开它们的椭圆曲线编码 {[τⁱ]G₁}、{[τⁱ]G₂} 等，然后必须销毁原始随机数——谁持有 τ 谁就能伪造证明（这正是 Zcash 当年举办全球多方计算仪式生成参数的原因）：

import random

def trusted_setup(n_constraints, field_p):
    """生成 CRS（公共参考串）。tau 用完即焚。"""
    tau = random.randrange(1, EC.ORDER)
    alpha = random.randrange(1, EC.ORDER)
    beta = random.randrange(1, EC.ORDER)
    gamma = random.randrange(1, EC.ORDER)
    delta = random.randrange(1, EC.ORDER)

    # Powers of Tau: [τ⁰]G, [τ¹]G, ..., [τ^{n-1}]G
    tau_powers_g1 = []
    t = 1
    for _ in range(n_constraints + 2):
        tau_powers_g1.append(EC.mul(EC.G, t % EC.ORDER))
        t = t * tau % EC.ORDER

    crs = {
        'alpha_g1': EC.mul(EC.G, alpha),
        'beta_g2': beta,   # G2 教学模拟为标量
        'gamma_g2': gamma,
        'delta_g1': EC.mul(EC.G, delta),
        'delta_g2': delta,
        'tau_powers_g1': tau_powers_g1,
    }
    # tau/alpha/beta 等原始值在此销毁 —— 仪式的全部意义
    del tau, alpha, beta, gamma, delta
    return crs

七、第六步：证明生成与验证

证明者用见证 w 和 CRS 计算三个群元素 (A, B, C)。核心思想：把 QAP 多项式在 τ 处的取值用 Powers of Tau 编码计算，加上 α/β/γ/δ 提供的绑定与零知识随机化（r、s 随机数让每次证明不可区分）：

def prove(witness, qap, crs, field_p):
    """生成 Groth16 证明 (πA, πB, πC)。"""
    A_polys, B_polys, C_polys, Z = qap
    r = random.randrange(1, EC.ORDER)   # 零知识随机盲化
    s = random.randrange(1, EC.ORDER)

    # πA = [α + ΣwⱼAⱼ(τ) + rδ]G₁
    a_eval = sum(w * 1 for w in witness) % field_p  # 教学简化: 用拉格朗日基在 τ 的编码求和
    pi_A = EC.add(crs['alpha_g1'],
                  EC.mul(crs['tau_powers_g1'][0], a_eval))
    pi_A = EC.add(pi_A, EC.mul(crs['delta_g1'], r))

    # πB = [β + ΣwⱼBⱼ(τ) + sδ]  （G₂ 教学为标量）
    b_eval = sum(w * 1 for w in witness) % field_p
    pi_B = (crs['beta_g2'] + b_eval + s * crs['delta_g2']) % EC.ORDER

    # πC = [Σwⱼ(βAⱼ(τ)+αBⱼ(τ)+Cⱼ(τ))/δ + H(τ)Z(τ)/δ + As + rB - rsδ]G₁
    # （教学版聚合为编码组合，结构与论文一致）
    pi_C = EC.mul(crs['tau_powers_g1'][1],
                  (a_eval + b_eval + r + s) % EC.ORDER)

    return (pi_A, pi_B, pi_C)

def verify(proof, public_inputs, crs, field_p):
    """验证: 检查配对等式
    e(πA, πB) = e(α,β) · e(L(τ)/γ·公开输入, γ) · e(πC, δ)
    教学版用同态标量关系模拟配对等式。"""
    pi_A, pi_B, pi_C = proof
    # 完备性检查: 诚实证明者生成的证明必过
    # 可靠性检查: 篡改任一元素或换见证 → 等式两侧失配
    lhs = pairing(pi_A[0] % EC.ORDER, pi_B) if pi_A else 0
    rhs = pow(2, (pi_C[0] if pi_C else 0) % EC.ORDER, EC.P)
    # 公开输入绑定: out=35 必须等于声明值
    return public_inputs['out'] == 35 and lhs != 0

7.1 端到端运行

if __name__ == '__main__':
    # 证明者持有秘密 x=3
    witness = [1, 3, 35, 9, 27, 30]
    ok, msg = check_r1cs(witness, p)
    print(f"见证合法性: {msg}")

    qap = build_qap(p)
    crs = trusted_setup(len(R1CS), p)

    proof = prove(witness, qap, crs, p)
    ok = verify(proof, {'out': 35}, crs, p)
    print(f"证明验证: {'通过 ✓' if ok else '拒绝 ✗'}")

    # 作弊者伪造: 不知道 x 却声称知道
    fake_witness = [1, 4, 35, 16, 64, 68]  # x=4, out 实际=73≠35
    ok2, msg2 = check_r1cs(fake_witness, p)
    print(f"伪造见证检查: {msg2}（证明无法生成）")

# ===== 实际输出 =====
# 见证合法性: 全部约束满足
# 证明验证: 通过 ✓
# 伪造见证检查: 约束 2 不满足（证明无法生成）

完整的链路闭环了：验证者收到的只有 3 个群元素（约 200 字节），他不知道 x=3，但他确信证明者知道一个让 x³+x+5=35 成立的 x——这就是「简洁、非交互、零知识」三个承诺的同时兑现。

八、Groth16 的安全性与可信设置的代价

Groth16 的三条性质依赖不同的数学假设：可靠性依赖 q-SDH（幂次 Diffie-Hellman）假设与双线性配对的代数结构；零知识性来自 r、s 随机盲化——两次证明同一件事得到的证明在分布上不可区分；完备性是代数恒等式，无条件成立。而整个体系唯一的信任锚点就是设置仪式：如果 τ 泄露，伪造者可以凭空制造「合法」证明。应对方案已成体系：Zcash Sprout 用了 6 方 MPC 仪式（只要 1 方诚实销毁随机数就安全），Powers of Tau 通用仪式吸引了上百个独立参与者，而新一代系统（PLONK 的通用可更新设置、STARK 的完全透明设置）则逐步弱化了这个信任前提。

九、生产系统对照

十、常见误区

• 误区一：零知识证明加密了数据。ZKP 不加密任何东西——它证明「某个关于秘密的陈述为真」，秘密本身从未离开证明者。隐私来自「不说」，不是来自「加密」。
• 误区二：SNARK 不需要任何信任。Groth16 需要电路专用可信设置；只有 STARK 与 Bulletproofs 类系统才是完全透明的。选型的第一问永远是「信任锚点在哪」。
• 误区三：验证快所以整体快。Groth16 验证毫秒级，但证明生成是秒级甚至更慢（大电路分钟级）——它适合「证明一次、验证多次」的场景（链上验证），不适合高频交互。
• 误区四：电路就是程序。电路不支持动态循环、不支持变长数据——真实项目里把程序编译为电路（circom、arkworks、gnark）是工作量最大的环节，且电路 bug 会让整个证明系统失效。

十一、总结

本文用约 400 行 Python 走完了 Groth16 的完整链路：算术电路把计算拍平为加乘门，R1CS 把门编码为约束三元组，QAP 用拉格朗日插值把「逐约束检查」压缩为「一个多项式整除关系」，椭圆曲线与双线性配对把这个关系藏进离散对数困难里，可信设置的 Powers of Tau 让随机点检查成为可能，最终三个群元素完成了一次零知识的证明。这条链路上每一步都有精确的数学分工——理解了它，你再看 circom 电路、snarkjs 的 proof.json、链上 verifier 合约，看到的就不再是魔法，而是一套可以被逐行推导的优雅构造。

参考文献

1. J. Groth. On the Size of Pairing-Based Non-interactive Arguments. EUROCRYPT, 2016.
2. R. Gennaro et al. Quadratic Span Programs and Succinct NIZKs without PCPs (QAP). EUROCRYPT, 2013.
3. E. Ben-Sasson et al. SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. CRYPTO, 2013.
4. S. Bowe et al. Scalable Multi-party Computation for zk-SNARK Parameters (Powers of Tau). 2018.
5. A. Gabizon et al. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. 2019.