halo2_proofs/poly/multiopen/
verifier.rs

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

halo2_proofs/poly/multiopen/
verifier.rs
