Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 代码解析

1. 引言

Bayer和Groth 2013年论文《Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists》，发表于EuroCrypt 2013。

相应的代码实现参见：

• https://github.com/lovesh/bg_poly_eval

2. polynomial evaluation argument

相应代码实现参见：https://github.com/lovesh/bg_poly_eval/blob/master/src/univar_poly_eval_arg.rs：

	#[test]
    fn test_prove_evaluation() {
        let comm_key = CommitmentKey::new("test".as_bytes());

        for degree in vec![1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] {
            let poly = UnivarPolynomial::random(degree);
            let u = FieldElement::random();
            let v = poly.eval(&u);

            let start_prover = Instant::now();

            let protocol = UnivarPolyEvalArgProtocol::init(&poly, u, v, &comm_key); //计算c_u,c_v，以及 c_1,...,c_d; c_{f_1},...,c_{f_d}; c_{\delta_0},...,c_{\delta_d}; c_{f_{u_0}},...,c_{f_{u_{d-1}}}
            let c_0 = protocol.comm_variable().clone();
            let c_v = protocol.comm_evaluation().clone();

            let challenge_by_prover = FieldElement::from_msg_hash(&protocol.get_bytes_for_challenge(&poly, &comm_key));

            let zk_argument = protocol.respond(&challenge_by_prover);

            let prover_time = start_prover.elapsed();

            let start_verifier = Instant::now();

            let challenge_by_verifier = FieldElement::from_msg_hash(&zk_argument.get_bytes_for_challenge(&poly, &c_0, &c_v, &comm_key));

            assert_eq!(challenge_by_prover, challenge_by_verifier);

            assert!(zk_argument.verify(&challenge_by_verifier, &poly, &c_0, &c_v, &comm_key));

            let verifier_time = start_verifier.elapsed();

            println!("For degree {}, proving time is {:?} and verification time is {:?}", degree, prover_time, verifier_time);
        }
    }

其中的 eval() 函数中使用了Honer’s method（霍纳法则），详细参见 https://github.com/lovesh/amcl_rust_wrapper/blob/master/src/univar_poly.rs：

	// Evaluate polynomial at given `x`
    pub fn eval(&self, x: &FieldElement) -> FieldElement {
        if x.is_zero() {
            self[0].clone()
        } else {
            // Use Horner's method https://en.wikipedia.org/wiki/Horner%27s_method
            // p(x) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + a_4*x^4 + ...
            // p(x) = a_0 + x*(a_1 + x*(a_2 + x*(a_3 + x*(a_4 + ... x*(a_{n-1} + x*a_n))))..
            // Reading coefficients from higher to lower degrees.
            let mut res = self.0[self.0.len() - 1].clone(); // a_n
            for i in (0..=self.0.len() - 2).rev() {
                // in each iteration, multiply `res` with `x` and add the coefficient for ith degree, a_i
                res = &self.0[i] + &(&res * x);
            }
            res
        }
    }

polynomial evaluation argument协议中相应的结构体设计为：

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct UnivarPolyEvalArgProtocol {
    /// `u` is the variable at which the polynomial is evaluated
    u: FieldElement,
    /// Blinding used when committing to u.
    r_0: FieldElement,
    /// Commitment to `u`
    comm_u: G1,
    /// `v` is the result of evaluating the polynomial
    v: FieldElement,
    /// Blinding used when committing to v.
    t: FieldElement,
    /// Commitment to `v`
    comm_v: G1,
    /// Even powers of u. [u^{2^1}, u^{2^2}, u^{2^3}, ...u^{2^d}]
    even_powers_u: Vec,
    /// Blindings used when committing to even powers of u.
    r: Vec,
    /// commitments to even power of u
    comm_even_powers_u: Vec,
    /// `f` is the additive blinding of powers of u in Q(x)
    f: Vec,
    /// `s` is the blinding used to commit `f`
    s: Vec,
    /// commitments to `f`
    comm_f: Vec,
    blindings_delta: Vec,
    /// commitments to `delta`
    comm_delta: Vec,
    xi: Vec,
    /// commitments to `f_j^{u^{2^j}}`
    comm_f_times_u_power: Vec
}

/// This serves as the proof that evaluating polynomial at u gives v. Commitments to u and v are
/// intentionally omitted as the verifier should receive them independently of the prover.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct UnivarPolyEvalArg {
    /// commitments to even power of u
    comm_even_powers_u: Vec,
    /// commitments to `f`
    comm_f: Vec,
    /// commitments to `delta`
    comm_delta: Vec,
    /// commitments to `f_j^{u^{2^j}}`
    comm_f_times_u_power: Vec,
    f_bar: Vec,
    r_bar: Vec,
    t_bar: FieldElement,
    xi_bar: Vec,
}

init() 函数返回的为：

		UnivarPolyEvalArgProtocol {
            u: variable, r_0: blinding_variable, comm_u: comm_variable,
            v: evaluation, t: blinding_evaluation, comm_v: comm_evaluation,
            even_powers_u, r: blindings_even_powers_u, comm_even_powers_u,
            f, s, comm_f, blindings_delta, comm_delta,
            xi: blindings_f_times_u,
            comm_f_times_u_power
        }

respond() 函数返回的为：

		UnivarPolyEvalArg {
            comm_even_powers_u: self.comm_even_powers_u,
            comm_f: self.comm_f,
            comm_delta: self.comm_delta,
            comm_f_times_u_power: self.comm_f_times_u_power,
            f_bar, r_bar, t_bar, xi_bar
        }

相应的 verify() 函数实现为：

	pub fn verify(&self, challenge: &FieldElement, poly: &UnivarPolynomial, comm_variable: &G1, comm_evaluation: &G1, comm_key: &CommitmentKey) -> bool {
        // The paper denotes the challenge by `x`

        let d = UnivarPolyEvalArgProtocol::check_poly_degree_and_return_log_degree(&poly);

        // TODO: Check the size of each list of commitments and responses to ensure that they are of appropriate size

        // TODO: Parallelize the following code with rayon

        // The need for these 2 is explained below
        // TODO: Since these are 2 are used several times in multi-scalar multiplication, its better
        // to compute lookup tables for them once.
        let g_inv = comm_key.g.negation();
        let h_inv = comm_key.h.negation();

        let mut comm_u_raised_to_powers_of_2 = vec![comm_variable];
        for i in 0..d {
            comm_u_raised_to_powers_of_2.push(&self.comm_even_powers_u[i as usize])
        }

        // check {c_j}^x * c_{f_j} == commitment({f_bar}_j; {r_bar}_j) = g^{{f_bar}_j} * h^{{r_bar}_j}
        // to use multi-scalar multi-exp, i can check {c_j}^x * c_{f_j} * g^{-{f_bar}_j} * h^{-{r_bar}_j} == 1
        // Now rather than negating each exponent, its better to invert g and h once, so that the
        // check becomes {c_j}^x * c_{f_j} * {1/g}^{{f_bar}_j} * {1/h}^{{r_bar}_j} == 1
        // check {c_j}^x * c_{f_j} * {1/g}^{{f_bar}_j} * {1/h}^{{r_bar}_j} == 1 for j in [0, d]
        for j in 0..=d as usize {
            if !G1Vector::multi_scalar_mul_var_time_without_precomputation(
                iter::once(comm_u_raised_to_powers_of_2[j]).
                    chain(iter::once(&self.comm_f[j])).
                    chain(iter::once(&g_inv)).
                    chain(iter::once(&h_inv)),
                iter::once(challenge).
                    chain(iter::once(&FieldElement::one())).
                    chain(iter::once(&self.f_bar[j])).
                    chain(iter::once(&self.r_bar[j]))
            ).unwrap().is_identity() {
                return false
            }
        }

        // check {c_{j+1}}^x * c_j^{-{{f_bar}_j}} * c_{f_{u_j}} == commitment(0; {xi_bar}_j) = g^0 * h^{{xi_bar}_j}
        // to use multi-scalar multi-exp, i can check {c_{j+1}}^x * c_j^{-{{f_bar}_j}} * c_{f_{u_j}} * h^{-{xi_bar}_j} == 1
        // Rather than negating each exponent, its better to use inverted h, so that the check
        // becomes {c_{j+1}}^x * c_j^{-{{f_bar}_j}} * c_{f_{u_j}} * {1/h}^{-{xi_bar}_j} == 1

        // check {c_{j+1}}^x * c_j^{-{{f_bar}_j}} * c_{f_{u_j}} * {1/h}^{-{xi_bar}_j} == 1 for j in [0, d)
        for j in 0..d as usize {
            if !G1Vector::multi_scalar_mul_var_time_without_precomputation(
                iter::once(comm_u_raised_to_powers_of_2[j +1]).
                    chain(iter::once(comm_u_raised_to_powers_of_2[j])).
                    chain(iter::once(&self.comm_f_times_u_power[j])).
                    chain(iter::once(&h_inv)),
                iter::once(challenge).
                    chain(iter::once(&(-&self.f_bar[j]))).
                    chain(iter::once(&FieldElement::one())).
                    chain(iter::once(&self.xi_bar[j]))
            ).unwrap().is_identity() {
                return false
            }
        }

        // check {c_v}^{x^{d+1}} * { {c_{delta_j}}^{x^j} for all j in [0, d] } == commitment(delta_bar, t_bar)
        // which is same as checking {c_v}^{x^{d+1}} * { {c_{delta_j}}^{x^j} for all j in [0, d] } * {1/g}^delta_bar * {1/h}^t_bar == 1

        let delta_bar = Self::calculate_delta_bar(&poly, d as usize, challenge, &self.f_bar);
        // x_powers is [1, x, x^2, x^3, ...., x^{d+1}]
        let x_powers = FieldElementVector::new_vandermonde_vector(challenge, d as usize + 2);

        // Prepare for multi-exp
        // group_elems is [c_delta_0, c_delta_1, c_delta_2, ..., c_delta_d, c_v, 1/g, 1/h]
        let group_elems = self.comm_delta.iter().
            chain(iter::once(comm_evaluation)).
            chain(iter::once(&g_inv)).
            chain(iter::once(&h_inv));

        // field_elems is [1, x, x^2, x^3, ...., x^{d+1}, delta_bar, t_bar]
        let field_elems = x_powers.iter().
            chain(iter::once(&delta_bar)).
            chain(iter::once(&self.t_bar));

        if !G1Vector::multi_scalar_mul_var_time_without_precomputation(group_elems, field_elems).unwrap().is_identity() {
            return false
        }

        true
    }

3. Non-membership argument

实际针对的场景为：

• public info：commitment c v c_v cv​
• witness： v , r v,r v,r
• relation： c v = g v h r c_v=g^vh^r cv​=gvhr且 v ≠ 0 v\neq 0 v​=0

核心思想为： 若 v ≠ 0 v\neq 0 v​=0，则 v − 1 v^{-1} v−1 值存在。

证明思路为：

• Prover：选择random y , z y,z y,z，计算 t = c v y h − z t=c_v^yh^{-z} t=cvy​h−z，将 t t t发送给Verifier；
• Verifier：发送challenge x x x；
• Prover：计算 s 1 = y + x ⋅ v − 1 , s 2 = z + v − 1 ⋅ x ⋅ r s_1=y+x\cdot v^{-1}, s_2=z+v^{-1}\cdot x\cdot r s1​=y+x⋅v−1,s2​=z+v−1⋅x⋅r，将 s 1 , s 2 s_1,s_2 s1​,s2​发送给Verifier；
• Verifier：验证 c v s 1 = t ⋅ g x ⋅ h s 2 c_v^{s_1}=t\cdot g^x\cdot h^{s_2} cvs1​​=t⋅gx⋅hs2​ 即可。

详细的代码实现参见https://github.com/lovesh/bg_poly_eval/blob/master/src/membership_arg.rs中：

	#[test]
    fn test_prove_set_non_membership() {
        let mut rng = rand::thread_rng();
        let comm_key = CommitmentKey::new("test".as_bytes());

        for set_size in vec![2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] {
            let set: Vec = FieldElementVector::random(set_size).into();
            // pick random element and ensure its not member of the set
            let mut non_member = FieldElement::random();
            while set.contains(&non_member) {
                non_member = FieldElement::random();
            }

            // Commit to non_member. In practice, this commitment (with blinding) will come from another protocol
            let blinding_non_member = FieldElement::random();
            let comm_non_member = comm_key.commit(&non_member, &blinding_non_member);

            let start_prover = Instant::now();

            let protocol = SetNonMembershipProtocol::init(&set, non_member, blinding_non_member, comm_non_member.clone(), &comm_key);
            let challenge_by_prover = FieldElement::from_msg_hash(&protocol.get_bytes_for_challenge(&comm_key));
            let zk_argument = protocol.respond(&challenge_by_prover);

            let prover_time = start_prover.elapsed();

            let start_verifier = Instant::now();

            let challenge_by_verifier = FieldElement::from_msg_hash(&zk_argument.get_bytes_for_challenge(&set, &comm_non_member, &comm_key));
            assert_eq!(challenge_by_prover, challenge_by_verifier);
            assert!(zk_argument.verify(&challenge_by_verifier, &set, &comm_non_member, &comm_key));

            let verifier_time = start_verifier.elapsed();

            let start_verifier = Instant::now();

            // Construct a polynomial with roots as the elements of the set. The polynomial can be constructed
            // once for both `get_bytes_for_challenge_with_poly_constructed` and `verify_with_poly_constructed`
            let poly = construct_polynomial_for_set(&set);
            let challenge_by_verifier = FieldElement::from_msg_hash(&zk_argument.get_bytes_for_challenge_with_poly_constructed(&poly, &comm_non_member, &comm_key));

            assert_eq!(challenge_by_prover, challenge_by_verifier);
            assert!(zk_argument.verify_with_poly_constructed(&challenge_by_verifier, &poly, &comm_non_member, &comm_key));

            let verifier_time_with_poly_construction_once = start_verifier.elapsed();

            println!("For set size {}, proving time is {:?}, naive verification time is {:?}, verification time with polynomial computed only once is {:?}", set_size, prover_time, verifier_time, verifier_time_with_poly_construction_once);
        }
    }

其中的 init() 函数内容为：

	/// Initialize protocol to prove that element `non_member` is not part of the set `set` and is committed in `comm_non_member` with blinding `blinding_non_member`
    pub fn init(set: &[FieldElement], non_member: FieldElement, blinding_non_member: FieldElement, comm_non_member: G1, comm_key: &CommitmentKey) -> Self {
        let poly = construct_polynomial_for_set(set);

        // The polynomial evaluates to `evaluation` at `non_member`
        let evaluation = poly.eval(&non_member);
        // Commit to the evaluation
        let blinding_evaluation = FieldElement::random();
        let comm_evaluation = comm_key.commit(&evaluation, &blinding_evaluation);

        // Prove comm_evaluation is a commitment to a non-zero value implying `evaluation` != 0.
        // `evaluation` != 0 implies `evaluation`^-1 exists in the field
        let y = FieldElement::random();
        let z = FieldElement::random();
        // t = comm_evaluation^y * h^-z
        let t = G1Vector::multi_scalar_mul_const_time_without_precomputation(
            iter::once(&comm_evaluation).chain(iter::once(&comm_key.h)),
            iter::once(&y).chain(iter::once(&(-&z)))
        ).unwrap();

        let poly_eval_arg_protocol = UnivarPolyEvalArgProtocol::init_with_given_commitments(&poly, non_member, evaluation, blinding_non_member, blinding_evaluation, comm_non_member, comm_evaluation, comm_key);

        Self { poly, poly_eval_arg_protocol, y, z, t}
    }

fn construct_polynomial_for_set(set: &[FieldElement]) -> UnivarPolynomial {
    assert!(set.len().is_power_of_two());
    // Construct a polynomial with roots as the elements of the set
    UnivarPolynomial::new_with_roots(set)
}

	/// Create a polynomial with given roots in `roots`
    /// i.e. (x-roots[0])*(x-roots[1])*(x-roots[2])...(x-roots[last]) given `roots`
    pub fn new_with_roots(roots: &[FieldElement]) -> Self {
        // vector of [(x-roots[0]), (x-roots[1]), (x-roots[2]), ...]
        let x_i = roots
            .par_iter()
            .map(|i| {
                let mut v = FieldElementVector::with_capacity(2);
                v.push(-i);
                v.push(FieldElement::one());
                UnivarPolynomial(v)
            })
            .collect::();

        // Polynomial (x-roots[0])*(x-roots[1])*(x-roots[2])...(x-roots[last])
        x_i.par_iter().cloned().reduce(
            || Self::new_constant(FieldElement::one()),
            |a, b| UnivarPolynomial::multiply(&a, &b),
        )
    }

init() 函数的返回值为：

Self { poly, poly_eval_arg_protocol, y, z, t}

相应的respond() 函数内容为：

	pub fn respond(self, challenge: &FieldElement) -> SetNonMembershipArg {
        let comm_evaluation = self.poly_eval_arg_protocol.comm_evaluation().clone();

        // {v^-1}
        let eval_inverse = self.poly_eval_arg_protocol.evaluation().inverse();

        // challenge*{v^-1}
        let chal_v_inv = challenge * &eval_inverse;
        // s_1 = y + challenge*{v^-1}
        let s_1 = &self.y + &chal_v_inv;
        // s_2 = z + challenge*{v^-1}*{blinding for v}
        let s_2 = &self.z + &(&chal_v_inv * self.poly_eval_arg_protocol.blinding_evaluation());

        // response for Polynomial evaluation argument
        let poly_eval_arg = self.poly_eval_arg_protocol.respond(&challenge);

        SetNonMembershipArg {poly_eval_arg, comm_evaluation, t: self.t, s_1, s_2}
    }

相应的 verify 见 verify_with_poly_constructed() 函数：

	pub fn verify_with_poly_constructed(&self, challenge: &FieldElement, poly: &UnivarPolynomial, comm_variable: &G1, comm_key: &CommitmentKey) -> bool {
        // check that t * g^challenge * h^s_2 == comm_evaluation^s_1
        // which is equivalent to the check t * g^challenge * h^s_2 * comm_evaluation^{-s_1} == 1
        if !G1Vector::multi_scalar_mul_var_time_without_precomputation(
            iter::once(&self.t).chain(iter::once(&comm_key.g)).chain(iter::once(&comm_key.h)).chain(iter::once(&self.comm_evaluation)),
            iter::once(&FieldElement::one()).chain(iter::once(challenge)).chain(iter::once(&self.s_2)).chain(iter::once(&(-&self.s_1)))
        ).unwrap().is_identity() {
            return false
        }

        // verify polynomial evaluation argument
        self.poly_eval_arg.verify(challenge, poly, comm_variable, &self.comm_evaluation, comm_key)
    }

4. membership argument

基本场景为：

• Public info: P ( X ) = ∏ i = 1 D ( X − λ i ) P(X)=\prod_{i=1}^{D}(X-\lambda_i) P(X)=∏i=1D​(X−λi​)，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​和commitment c v c_v cv​
• private info： u , v u,v u,v
• relation： P ( u ) = v P(u)=v P(u)=v 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u) 且 c v = C o m ( v ) = C o m ( 0 ) c_v=Com(v)=Com(0) cv​=Com(v)=Com(0)

详细的代码实现参见https://github.com/lovesh/bg_poly_eval/blob/master/src/membership_arg.rs中：

#[test]
    fn test_prove_set_membership() {
        let mut rng = rand::thread_rng();
        let comm_key = CommitmentKey::new("test".as_bytes());

        for set_size in vec![2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] {
            let set: Vec = FieldElementVector::random(set_size).into();
            // pick random member of the set to prove membership
            let member_idx = rng.gen_range(0, set_size);
            let member = set[member_idx].clone();

            // Commit to member. In practice, this commitment (with blinding) will come from another protocol
            let blinding_member = FieldElement::random();
            let comm_member = comm_key.commit(&member, &blinding_member);

            let start_prover = Instant::now();

            let protocol = SetMembershipProtocol::init(&set, member, blinding_member, comm_member.clone(), &comm_key);
            let challenge_by_prover = FieldElement::from_msg_hash(&protocol.get_bytes_for_challenge(&comm_key));
            let zk_argument = protocol.respond(&challenge_by_prover);

            let prover_time = start_prover.elapsed();

            let start_verifier = Instant::now();

            let challenge_by_verifier = FieldElement::from_msg_hash(&zk_argument.get_bytes_for_challenge(&set, &comm_member, &comm_key));
            assert_eq!(challenge_by_prover, challenge_by_verifier);
            assert!(zk_argument.verify(&challenge_by_verifier, &set, &comm_member, &comm_key));

            let verifier_time = start_verifier.elapsed();

            let start_verifier = Instant::now();

            // Construct a polynomial with roots as the elements of the set. The polynomial can be constructed
            // once for both `get_bytes_for_challenge_with_poly_constructed` and `verify_with_poly_constructed`
            let poly = construct_polynomial_for_set(&set);
            let challenge_by_verifier = FieldElement::from_msg_hash(&zk_argument.get_bytes_for_challenge_with_poly_constructed(&poly, &comm_member, &comm_key));
            assert_eq!(challenge_by_prover, challenge_by_verifier);
            assert!(zk_argument.verify_with_poly_constructed(&challenge_by_verifier, &poly, &comm_member, &comm_key));

            let verifier_time_with_poly_construction_once = start_verifier.elapsed();

            println!("For set size {}, proving time is {:?}, naive verification time is {:?}, verification time with polynomial computed only once is {:?}", set_size, prover_time, verifier_time, verifier_time_with_poly_construction_once);
        }
    }

 	/// Initialize protocol to prove that element `member` is part of the set `set` and is committed in `comm_member` with blinding `blinding_member`
    pub fn init(set: &[FieldElement], member: FieldElement, blinding_member: FieldElement, comm_member: G1, comm_key: &CommitmentKey) -> Self {
        let poly = construct_polynomial_for_set(set);
        // To prove comm_evaluation is a commitment to 0, it is sufficient to prove that comm_evaluation
        // is of the form {comm_key.h}^blinding_evaluation which can be done with Schnorr's
        // identification protocol.
        let z = FieldElement::random();
        let t = &comm_key.h * &z;

        // Prove that the polynomial evaluates to 0 at `member`
        let evaluation = FieldElement::zero();
        let blinding_evaluation = FieldElement::random();
        let comm_evaluation = comm_key.commit(&evaluation, &blinding_evaluation);

        let poly_eval_arg_protocol = UnivarPolyEvalArgProtocol::init_with_given_commitments(&poly, member, evaluation, blinding_member, blinding_evaluation, comm_member, comm_evaluation, comm_key);

        Self {poly, poly_eval_arg_protocol, z, t}
    }

 	pub fn respond(self, challenge: &FieldElement) -> SetMembershipArg {
        let comm_evaluation = self.poly_eval_arg_protocol.comm_evaluation().clone();
        // response for Schnorr's Id protocol for proving commitment to evaluation is a commitment to 0
        let s = &self.z + &(challenge * self.poly_eval_arg_protocol.blinding_evaluation());

        // response for Polynomial evaluation argument
        let poly_eval_arg = self.poly_eval_arg_protocol.respond(&challenge);

        SetMembershipArg {poly_eval_arg, comm_evaluation, t: self.t, s}
    }

 	pub fn verify_with_poly_constructed(&self, challenge: &FieldElement, poly: &UnivarPolynomial, comm_variable: &G1, comm_key: &CommitmentKey) -> bool {
        // check that self.comm_evaluation is a commitment to 0 i.e. check h^s == t * {comm_evaluation}^challenge
        // which is equivalent to the check t * {comm_evaluation}^challenge * {1/h}^s == 1
        if !G1Vector::multi_scalar_mul_var_time_without_precomputation(
            iter::once(&self.t).chain(iter::once(&self.comm_evaluation)).chain(iter::once(&(-&comm_key.h))),
            iter::once(&FieldElement::one()).chain(iter::once(challenge)).chain(iter::once(&self.s))
        ).unwrap().is_identity() {
            return false
        }

        // verify polynomial evaluation argument
        self.poly_eval_arg.verify(challenge, poly, comm_variable, &self.comm_evaluation, comm_key)
    }