halo2_axiom/poly/ipa/multiopen/
prover.rs

1use super::{construct_intermediate_sets, ChallengeX1, ChallengeX2, ChallengeX3, ChallengeX4};
2use crate::arithmetic::{eval_polynomial, kate_division, CurveAffine};
3use crate::poly::commitment::ParamsProver;
4use crate::poly::commitment::{Blind, Prover};
5use crate::poly::ipa::commitment::{self, IPACommitmentScheme, ParamsIPA};
6use crate::poly::query::ProverQuery;
7use crate::poly::{Coeff, Polynomial};
8use crate::transcript::{EncodedChallenge, TranscriptWrite};
9
10use ff::Field;
11use group::Curve;
12use rand_core::RngCore;
13use std::io;
14use std::marker::PhantomData;
15
16/// IPA multi-open prover
17#[derive(Debug)]
18pub struct ProverIPA<'params, C: CurveAffine> {
19    pub(crate) params: &'params ParamsIPA<C>,
20}
21
22impl<'params, C: CurveAffine> Prover<'params, IPACommitmentScheme<C>> for ProverIPA<'params, C> {
23    const QUERY_INSTANCE: bool = true;
24
25    fn new(params: &'params ParamsIPA<C>) -> Self {
26        Self { params }
27    }
28
29    /// Create a multi-opening proof
30    fn create_proof<'com, Z: EncodedChallenge<C>, T: TranscriptWrite<C, Z>, R, I>(
31        &self,
32        mut rng: R,
33        transcript: &mut T,
34        queries: I,
35    ) -> io::Result<()>
36    where
37        I: IntoIterator<Item = ProverQuery<'com, C>> + Clone,
38        R: RngCore,
39    {
40        let x_1: ChallengeX1<_> = transcript.squeeze_challenge_scalar();
41        let x_2: ChallengeX2<_> = transcript.squeeze_challenge_scalar();
42
43        let (poly_map, point_sets) = construct_intermediate_sets(queries).ok_or_else(|| {
44            io::Error::new(
45                io::ErrorKind::InvalidInput,
46                "queries iterator contains mismatching evaluations",
47            )
48        })?;
49
50        // Collapse openings at same point sets together into single openings using
51        // x_1 challenge.
52        let mut q_polys: Vec<Option<Polynomial<C::Scalar, Coeff>>> = vec![None; point_sets.len()];
53        let mut q_blinds = vec![Blind(C::Scalar::ZERO); point_sets.len()];
54
55        {
56            let mut accumulate = |set_idx: usize,
57                                  new_poly: &Polynomial<C::Scalar, Coeff>,
58                                  blind: Blind<C::Scalar>| {
59                if let Some(poly) = &q_polys[set_idx] {
60                    q_polys[set_idx] = Some(poly.clone() * *x_1 + new_poly);
61                } else {
62                    q_polys[set_idx] = Some(new_poly.clone());
63                }
64                q_blinds[set_idx] *= *x_1;
65                q_blinds[set_idx] += blind;
66            };
67
68            for commitment_data in poly_map.into_iter() {
69                accumulate(
70                    commitment_data.set_index,        // set_idx,
71                    commitment_data.commitment.poly,  // poly,
72                    commitment_data.commitment.blind, // blind,
73                );
74            }
75        }
76
77        let q_prime_poly = point_sets
78            .iter()
79            .zip(q_polys.iter())
80            .fold(None, |q_prime_poly, (points, poly)| {
81                let mut poly = points
82                    .iter()
83                    .fold(poly.clone().unwrap().values, |poly, point| {
84                        kate_division(&poly, *point)
85                    });
86                poly.resize(self.params.n as usize, C::Scalar::ZERO);
87                let poly = Polynomial {
88                    values: poly,
89                    _marker: PhantomData,
90                };
91
92                if q_prime_poly.is_none() {
93                    Some(poly)
94                } else {
95                    q_prime_poly.map(|q_prime_poly| q_prime_poly * *x_2 + &poly)
96                }
97            })
98            .unwrap();
99
100        let q_prime_blind = Blind(C::Scalar::random(&mut rng));
101        let q_prime_commitment = self.params.commit(&q_prime_poly, q_prime_blind).to_affine();
102
103        transcript.write_point(q_prime_commitment)?;
104
105        let x_3: ChallengeX3<_> = transcript.squeeze_challenge_scalar();
106
107        // Prover sends u_i for all i, which correspond to the evaluation
108        // of each Q polynomial commitment at x_3.
109        for q_i_poly in &q_polys {
110            transcript.write_scalar(eval_polynomial(q_i_poly.as_ref().unwrap(), *x_3))?;
111        }
112
113        let x_4: ChallengeX4<_> = transcript.squeeze_challenge_scalar();
114
115        let (p_poly, p_poly_blind) = q_polys.into_iter().zip(q_blinds).fold(
116            (q_prime_poly, q_prime_blind),
117            |(q_prime_poly, q_prime_blind), (poly, blind)| {
118                (
119                    q_prime_poly * *x_4 + &poly.unwrap(),
120                    Blind((q_prime_blind.0 * &(*x_4)) + &blind.0),
121                )
122            },
123        );
124
125        commitment::create_proof(self.params, rng, transcript, &p_poly, p_poly_blind, *x_3)
126    }
127}
halo2_axiom/poly/ipa/multiopen/prover.rs

halo2_axiom/poly/ipa/multiopen/
prover.rs
