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

零知识证明（ZKP）是密码学皇冠上的明珠，允许一方在不泄露任何秘密信息的情况下向另一方证明某个陈述为真。Groth16 是目前最高效的 zk-SNARK 协议之一，被 Zcash、Tornado Cash 等广泛采用。

一、从 R1CS 到 QAP

任何计算问题都可以转化为 R1CS（Rank-1 Constraint System）约束系统。每个约束形如 (a·s) × (b·s) = (c·s)，其中 s 是包含所有变量的向量。然后通过多项式插值将 R1CS 转化为 QAP（Quadratic Arithmetic Program）。

use ark_ff::PrimeField;
use ark_poly::univariate::DensePolynomial;

struct R1CS {
    a: Vec>,  // 每个约束的 a 向量
    b: Vec>,  // 每个约束的 b 向量
    c: Vec>,  // 每个约束的 c 向量
    num_variables: usize,
    num_constraints: usize,
}

fn r1cs_to_qap(r1cs: &R1CS) -> (Vec>, Vec>, Vec>) {
    let domain: Vec = (0..r1cs.num_constraints).map(|i| F::from(i as u64)).collect();
    let mut a_polys = vec![DensePolynomial::zero(); r1cs.num_variables];
    let mut b_polys = vec![DensePolynomial::zero(); r1cs.num_variables];
    let mut c_polys = vec![DensePolynomial::zero(); r1cs.num_variables];

    for i in 0..r1cs.num_variables {
        let a_evals: Vec = r1cs.a.iter().map(|row| row[i]).collect();
        a_polys[i] = DensePolynomial::from_coefficients_vec(
            lagrange_interpolation(&domain, &a_evals)
        );
        // 同理处理 b 和 c...
    }
    (a_polys, b_polys, c_polys)
}

二、可信设置（Trusted Setup）

Groth16 需要一次性的可信设置，生成公共参考字符串（CRS）。设置过程产生有毒废料（toxic waste），必须安全销毁。使用椭圆曲线上的双线性配对（如 BN254、BLS12-381）。

use ark_bn254::{Bn254, Fr, G1Projective, G2Projective};
use ark_ec::pairing::Pairing;

struct ProvingKey {
    alpha_g1: E::G1,
    beta_g2: E::G2,
    gamma_g2: E::G2,
    delta_g2: E::G2,
    // 每个变量的多项式在秘密点 tau 的评估值
    a_query: Vec,
    b_query: Vec,
    h_query: Vec,
    l_query: Vec,
}

fn setup(r1cs: &R1CS) -> (ProvingKey, VerifyingKey) {
    let tau = E::ScalarField::rand(&mut rng);
    let alpha = E::ScalarField::rand(&mut rng);
    let beta = E::ScalarField::rand(&mut rng);
    let gamma = E::ScalarField::rand(&mut rng);
    let delta = E::ScalarField::rand(&mut rng);
    // 计算各多项式在 tau 处的评估值并编码到椭圆曲线点...
    todo!()
}

三、证明生成（Prover）

Prover 使用证明密钥和 witness（秘密输入），计算三个椭圆曲线点 (A, B, C) 作为证明。证明大小仅 3 个群元素（约 128 字节），验证时间常数级。

struct Proof {
    a: E::G1,
    b: E::G2,
    c: E::G1,
}

fn prove(
    pk: &ProvingKey,
    public_inputs: &[E::ScalarField],
    witness: &[E::ScalarField],
) -> Proof {
    let r = E::ScalarField::rand(&mut rng);
    let s = E::ScalarField::rand(&mut rng);

    // A = alpha + sum(witness_i * a_i(tau)) + r * delta
    let a = pk.alpha_g1 + msm(&pk.a_query, witness) + pk.delta_g1.mul(r);

    // B = beta + sum(witness_i * b_i(tau)) + s * delta
    let b = pk.beta_g2 + msm_g2(&pk.b_query, witness) + pk.delta_g2.mul(s);

    // C = sum(witness_i * (beta*a_i + alpha*b_i + c_i)(tau)) / delta + A*s + B*r - r*s*delta
    let c = /* 复杂计算 */;

    Proof { a, b, c }
}

四、验证（Verifier）

Verifier 只需执行一次双线性配对检查：e(A, B) = e(alpha, beta) · e(public_inputs_commitment, gamma) · e(C, delta)。验证时间与电路规模无关，仅需约 3ms。

fn verify(
    vk: &VerifyingKey,
    public_inputs: &[E::ScalarField],
    proof: &Proof,
) -> bool {
    let pub_commitment = msm(&vk.gamma_abc_g1[1..], public_inputs)
        + vk.gamma_abc_g1[0];

    // 检查配对等式
    E::multi_pairing([
        (proof.a, proof.b.into()),
        (pub_commitment, vk.gamma_g2.into()),
        (proof.c, vk.delta_g2.into()),
        (vk.alpha_g1, vk.beta_g2.into()),
    ]).is_zero()
}

五、应用场景

Groth16 广泛应用于隐私交易（Zcash）、匿名投票、去中心化身份验证、Layer 2 扩容（zkRollup）等场景。其极小的证明大小和常数级验证时间使其成为区块链隐私保护的理想选择。

零知识证明正在从理论走向大规模应用，掌握其原理是进入 Web3 隐私赛道的必备技能。