halo2_proofs/poly/multiopen/
verifier.rs

1use ff::Field;
2
3use super::super::{
4    commitment::{Guard, Params, MSM},
5    Error,
6};
7use super::{
8    construct_intermediate_sets, ChallengeX1, ChallengeX2, ChallengeX3, ChallengeX4,
9    CommitmentReference, Query, VerifierQuery,
10};
11use crate::arithmetic::{eval_polynomial, lagrange_interpolate, CurveAffine};
12use crate::transcript::{EncodedChallenge, TranscriptRead};
13
14/// Verify a multi-opening proof
15pub fn verify_proof<
16    'r,
17    'params: 'r,
18    I,
19    C: CurveAffine,
20    E: EncodedChallenge<C>,
21    T: TranscriptRead<C, E>,
22>(
23    params: &'params Params<C>,
24    transcript: &mut T,
25    queries: I,
26    mut msm: MSM<'params, C>,
27) -> Result<Guard<'params, C, E>, Error>
28where
29    I: IntoIterator<Item = VerifierQuery<'r, 'params, C>> + Clone,
30{
31    // Sample x_1 for compressing openings at the same point sets together
32    let x_1: ChallengeX1<_> = transcript.squeeze_challenge_scalar();
33
34    // Sample a challenge x_2 for keeping the multi-point quotient
35    // polynomial terms linearly independent.
36    let x_2: ChallengeX2<_> = transcript.squeeze_challenge_scalar();
37
38    let (commitment_map, point_sets) = construct_intermediate_sets(queries);
39
40    // Compress the commitments and expected evaluations at x together.
41    // using the challenge x_1
42    let mut q_commitments: Vec<_> = vec![
43        (params.empty_msm(), C::Scalar::ONE); // (accumulator, next x_1 power).
44        point_sets.len()];
45
46    // A vec of vecs of evals. The outer vec corresponds to the point set,
47    // while the inner vec corresponds to the points in a particular set.
48    let mut q_eval_sets = Vec::with_capacity(point_sets.len());
49    for point_set in point_sets.iter() {
50        q_eval_sets.push(vec![C::Scalar::ZERO; point_set.len()]);
51    }
52
53    {
54        let mut accumulate = |set_idx: usize, new_commitment, evals: Vec<C::Scalar>| {
55            let (q_commitment, x_1_power) = &mut q_commitments[set_idx];
56            match new_commitment {
57                CommitmentReference::Commitment(c) => {
58                    q_commitment.append_term(*x_1_power, *c);
59                }
60                CommitmentReference::MSM(msm) => {
61                    let mut msm = msm.clone();
62                    msm.scale(*x_1_power);
63                    q_commitment.add_msm(&msm);
64                }
65            }
66            for (eval, set_eval) in evals.iter().zip(q_eval_sets[set_idx].iter_mut()) {
67                *set_eval += (*eval) * (*x_1_power);
68            }
69            *x_1_power *= *x_1;
70        };
71
72        // Each commitment corresponds to evaluations at a set of points.
73        // For each set, we collapse each commitment's evals pointwise.
74        // Run in order of increasing x_1 powers.
75        for commitment_data in commitment_map.into_iter().rev() {
76            accumulate(
77                commitment_data.set_index,  // set_idx,
78                commitment_data.commitment, // commitment,
79                commitment_data.evals,      // evals
80            );
81        }
82    }
83
84    // Obtain the commitment to the multi-point quotient polynomial f(X).
85    let q_prime_commitment = transcript.read_point().map_err(|_| Error::SamplingError)?;
86
87    // Sample a challenge x_3 for checking that f(X) was committed to
88    // correctly.
89    let x_3: ChallengeX3<_> = transcript.squeeze_challenge_scalar();
90
91    // u is a vector containing the evaluations of the Q polynomial
92    // commitments at x_3
93    let mut u = Vec::with_capacity(q_eval_sets.len());
94    for _ in 0..q_eval_sets.len() {
95        u.push(transcript.read_scalar().map_err(|_| Error::SamplingError)?);
96    }
97
98    // We can compute the expected msm_eval at x_3 using the u provided
99    // by the prover and from x_2
100    let msm_eval = point_sets
101        .iter()
102        .zip(q_eval_sets.iter())
103        .zip(u.iter())
104        .fold(
105            C::Scalar::ZERO,
106            |msm_eval, ((points, evals), proof_eval)| {
107                let r_poly = lagrange_interpolate(points, evals);
108                let r_eval = eval_polynomial(&r_poly, *x_3);
109                let eval = points.iter().fold(*proof_eval - &r_eval, |eval, point| {
110                    eval * &(*x_3 - point).invert().unwrap()
111                });
112                msm_eval * &(*x_2) + &eval
113            },
114        );
115
116    // Sample a challenge x_4 that we will use to collapse the openings of
117    // the various remaining polynomials at x_3 together.
118    let x_4: ChallengeX4<_> = transcript.squeeze_challenge_scalar();
119
120    // Compute the final commitment that has to be opened
121    msm.append_term(C::Scalar::ONE, q_prime_commitment);
122    let (msm, v) = q_commitments.into_iter().zip(u.iter()).fold(
123        (msm, msm_eval),
124        |(mut msm, msm_eval), ((q_commitment, _), q_eval)| {
125            msm.scale(*x_4);
126            msm.add_msm(&q_commitment);
127            (msm, msm_eval * &(*x_4) + q_eval)
128        },
129    );
130
131    // Verify the opening proof
132    super::commitment::verify_proof(params, msm, transcript, *x_3, v)
133}
134
135impl<'a, 'b, C: CurveAffine> Query<C::Scalar> for VerifierQuery<'a, 'b, C> {
136    type Commitment = CommitmentReference<'a, 'b, C>;
137    type Eval = C::Scalar;
138
139    fn get_point(&self) -> C::Scalar {
140        self.point
141    }
142    fn get_eval(&self) -> C::Scalar {
143        self.eval
144    }
145    fn get_commitment(&self) -> Self::Commitment {
146        self.commitment
147    }
148}
halo2_proofs/poly/multiopen/verifier.rs

halo2_proofs/poly/multiopen/
verifier.rs
