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);
44
45        // Collapse openings at same point sets together into single openings using
46        // x_1 challenge.
47        let mut q_polys: Vec<Option<Polynomial<C::Scalar, Coeff>>> = vec![None; point_sets.len()];
48        let mut q_blinds = vec![Blind(C::Scalar::ZERO); point_sets.len()];
49
50        {
51            let mut accumulate = |set_idx: usize,
52                                  new_poly: &Polynomial<C::Scalar, Coeff>,
53                                  blind: Blind<C::Scalar>| {
54                if let Some(poly) = &q_polys[set_idx] {
55                    q_polys[set_idx] = Some(poly.clone() * *x_1 + new_poly);
56                } else {
57                    q_polys[set_idx] = Some(new_poly.clone());
58                }
59                q_blinds[set_idx] *= *x_1;
60                q_blinds[set_idx] += blind;
61            };
62
63            for commitment_data in poly_map.into_iter() {
64                accumulate(
65                    commitment_data.set_index,        // set_idx,
66                    commitment_data.commitment.poly,  // poly,
67                    commitment_data.commitment.blind, // blind,
68                );
69            }
70        }
71
72        let q_prime_poly = point_sets
73            .iter()
74            .zip(q_polys.iter())
75            .fold(None, |q_prime_poly, (points, poly)| {
76                let mut poly = points
77                    .iter()
78                    .fold(poly.clone().unwrap().values, |poly, point| {
79                        kate_division(&poly, *point)
80                    });
81                poly.resize(self.params.n as usize, C::Scalar::ZERO);
82                let poly = Polynomial {
83                    values: poly,
84                    _marker: PhantomData,
85                };
86
87                if q_prime_poly.is_none() {
88                    Some(poly)
89                } else {
90                    q_prime_poly.map(|q_prime_poly| q_prime_poly * *x_2 + &poly)
91                }
92            })
93            .unwrap();
94
95        let q_prime_blind = Blind(C::Scalar::random(&mut rng));
96        let q_prime_commitment = self.params.commit(&q_prime_poly, q_prime_blind).to_affine();
97
98        transcript.write_point(q_prime_commitment)?;
99
100        let x_3: ChallengeX3<_> = transcript.squeeze_challenge_scalar();
101
102        // Prover sends u_i for all i, which correspond to the evaluation
103        // of each Q polynomial commitment at x_3.
104        for q_i_poly in &q_polys {
105            transcript.write_scalar(eval_polynomial(q_i_poly.as_ref().unwrap(), *x_3))?;
106        }
107
108        let x_4: ChallengeX4<_> = transcript.squeeze_challenge_scalar();
109
110        let (p_poly, p_poly_blind) = q_polys.into_iter().zip(q_blinds).fold(
111            (q_prime_poly, q_prime_blind),
112            |(q_prime_poly, q_prime_blind), (poly, blind)| {
113                (
114                    q_prime_poly * *x_4 + &poly.unwrap(),
115                    Blind((q_prime_blind.0 * &(*x_4)) + &blind.0),
116                )
117            },
118        );
119
120        commitment::create_proof(self.params, rng, transcript, &p_poly, p_poly_blind, *x_3)
121    }
122}