halo2_proofs/plonk/vanishing/
prover.rs

Help
1use std::iter;
2
3use ff::Field;
4use group::Curve;
5use rand_core::RngCore;
6
7use super::Argument;
8use crate::{
9    arithmetic::{eval_polynomial, CurveAffine, FieldExt},
10    plonk::{ChallengeX, ChallengeY, Error},
11    poly::{
12        self,
13        commitment::{Blind, Params},
14        multiopen::ProverQuery,
15        Coeff, EvaluationDomain, ExtendedLagrangeCoeff, Polynomial,
16    },
17    transcript::{EncodedChallenge, TranscriptWrite},
18};
19
20pub(in crate::plonk) struct Committed<C: CurveAffine> {
21    random_poly: Polynomial<C::Scalar, Coeff>,
22    random_blind: Blind<C::Scalar>,
23}
24
25pub(in crate::plonk) struct Constructed<C: CurveAffine> {
26    h_pieces: Vec<Polynomial<C::Scalar, Coeff>>,
27    h_blinds: Vec<Blind<C::Scalar>>,
28    committed: Committed<C>,
29}
30
31pub(in crate::plonk) struct Evaluated<C: CurveAffine> {
32    h_poly: Polynomial<C::Scalar, Coeff>,
33    h_blind: Blind<C::Scalar>,
34    committed: Committed<C>,
35}
36
37impl<C: CurveAffine> Argument<C> {
38    pub(in crate::plonk) fn commit<E: EncodedChallenge<C>, R: RngCore, T: TranscriptWrite<C, E>>(
39        params: &Params<C>,
40        domain: &EvaluationDomain<C::Scalar>,
41        mut rng: R,
42        transcript: &mut T,
43    ) -> Result<Committed<C>, Error> {
44        // Sample a random polynomial of degree n - 1
45        let mut random_poly = domain.empty_coeff();
46        for coeff in random_poly.iter_mut() {
47            *coeff = C::Scalar::random(&mut rng);
48        }
49        // Sample a random blinding factor
50        let random_blind = Blind(C::Scalar::random(rng));
51
52        // Commit
53        let c = params.commit(&random_poly, random_blind).to_affine();
54        transcript.write_point(c)?;
55
56        Ok(Committed {
57            random_poly,
58            random_blind,
59        })
60    }
61}
62
63impl<C: CurveAffine> Committed<C> {
64    pub(in crate::plonk) fn construct<
65        E: EncodedChallenge<C>,
66        Ev: Copy + Send + Sync,
67        R: RngCore,
68        T: TranscriptWrite<C, E>,
69    >(
70        self,
71        params: &Params<C>,
72        domain: &EvaluationDomain<C::Scalar>,
73        evaluator: poly::Evaluator<Ev, C::Scalar, ExtendedLagrangeCoeff>,
74        expressions: impl Iterator<Item = poly::Ast<Ev, C::Scalar, ExtendedLagrangeCoeff>>,
75        y: ChallengeY<C>,
76        mut rng: R,
77        transcript: &mut T,
78    ) -> Result<Constructed<C>, Error> {
79        // Evaluate the h(X) polynomial's constraint system expressions for the constraints provided
80        let h_poly = poly::Ast::distribute_powers(expressions, *y); // Fold the gates together with the y challenge
81        let h_poly = evaluator.evaluate(&h_poly, domain); // Evaluate the h(X) polynomial
82
83        // Divide by t(X) = X^{params.n} - 1.
84        let h_poly = domain.divide_by_vanishing_poly(h_poly);
85
86        // Obtain final h(X) polynomial
87        let h_poly = domain.extended_to_coeff(h_poly);
88
89        // Split h(X) up into pieces
90        let h_pieces = h_poly
91            .chunks_exact(params.n as usize)
92            .map(|v| domain.coeff_from_vec(v.to_vec()))
93            .collect::<Vec<_>>();
94        drop(h_poly);
95        let h_blinds: Vec<_> = h_pieces
96            .iter()
97            .map(|_| Blind(C::Scalar::random(&mut rng)))
98            .collect();
99
100        // Compute commitments to each h(X) piece
101        let h_commitments_projective: Vec<_> = h_pieces
102            .iter()
103            .zip(h_blinds.iter())
104            .map(|(h_piece, blind)| params.commit(h_piece, *blind))
105            .collect();
106        let mut h_commitments = vec![C::identity(); h_commitments_projective.len()];
107        C::Curve::batch_normalize(&h_commitments_projective, &mut h_commitments);
108        let h_commitments = h_commitments;
109
110        // Hash each h(X) piece
111        for c in h_commitments.iter() {
112            transcript.write_point(*c)?;
113        }
114
115        Ok(Constructed {
116            h_pieces,
117            h_blinds,
118            committed: self,
119        })
120    }
121}
122
123impl<C: CurveAffine> Constructed<C> {
124    pub(in crate::plonk) fn evaluate<E: EncodedChallenge<C>, T: TranscriptWrite<C, E>>(
125        self,
126        x: ChallengeX<C>,
127        xn: C::Scalar,
128        domain: &EvaluationDomain<C::Scalar>,
129        transcript: &mut T,
130    ) -> Result<Evaluated<C>, Error> {
131        let h_poly = self
132            .h_pieces
133            .iter()
134            .rev()
135            .fold(domain.empty_coeff(), |acc, eval| acc * xn + eval);
136
137        let h_blind = self
138            .h_blinds
139            .iter()
140            .rev()
141            .fold(Blind(C::Scalar::zero()), |acc, eval| {
142                acc * Blind(xn) + *eval
143            });
144
145        let random_eval = eval_polynomial(&self.committed.random_poly, *x);
146        transcript.write_scalar(random_eval)?;
147
148        Ok(Evaluated {
149            h_poly,
150            h_blind,
151            committed: self.committed,
152        })
153    }
154}
155
156impl<C: CurveAffine> Evaluated<C> {
157    pub(in crate::plonk) fn open(
158        &self,
159        x: ChallengeX<C>,
160    ) -> impl Iterator<Item = ProverQuery<'_, C>> + Clone {
161        iter::empty()
162            .chain(Some(ProverQuery {
163                point: *x,
164                poly: &self.h_poly,
165                blind: self.h_blind,
166            }))
167            .chain(Some(ProverQuery {
168                point: *x,
169                poly: &self.committed.random_poly,
170                blind: self.committed.random_blind,
171            }))
172    }
173}
halo2_proofs/plonk/vanishing/prover.rs

halo2_proofs/plonk/vanishing/
prover.rs
