halo2_proofs/poly/multiopen/
prover.rs

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

halo2_proofs/poly/multiopen/
prover.rs
