halo2_axiom/poly/ipa/multiopen/
verifier.rs

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

halo2_axiom/poly/ipa/multiopen/
verifier.rs
