halo2_axiom/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, parallelize, CurveAffine},
10    plonk::{ChallengeX, Error},
11    poly::{
12        commitment::{Blind, ParamsProver},
13        Coeff, EvaluationDomain, ExtendedLagrangeCoeff, Polynomial, ProverQuery,
14    },
15    transcript::{EncodedChallenge, TranscriptWrite},
16};
17
18pub(in crate::plonk) struct Committed<C: CurveAffine> {
19    random_poly: Polynomial<C::Scalar, Coeff>,
20    random_blind: Blind<C::Scalar>,
21}
22
23pub(in crate::plonk) struct Constructed<C: CurveAffine> {
24    h_pieces: Vec<Polynomial<C::Scalar, Coeff>>,
25    h_blinds: Vec<Blind<C::Scalar>>,
26    committed: Committed<C>,
27}
28
29pub(in crate::plonk) struct Evaluated<C: CurveAffine> {
30    h_poly: Polynomial<C::Scalar, Coeff>,
31    h_blind: Blind<C::Scalar>,
32    committed: Committed<C>,
33}
34
35impl<C: CurveAffine> Argument<C> {
36    pub(in crate::plonk) fn commit<
37        'params,
38        P: ParamsProver<'params, C>,
39        E: EncodedChallenge<C>,
40        R: RngCore, // + Sync + Clone,
41        T: TranscriptWrite<C, E>,
42    >(
43        params: &P,
44        domain: &EvaluationDomain<C::Scalar>,
45        rng: R,
46        transcript: &mut T,
47    ) -> Result<Committed<C>, Error> {
48        // Sample a random polynomial of degree n - 1
49        let mut random_poly = domain.empty_coeff();
50        parallelize(&mut random_poly, |random_poly, _| {
51            let mut rng = rand::thread_rng();
52            for coeff in random_poly.iter_mut() {
53                *coeff = C::Scalar::random(&mut rng);
54            }
55        });
56        // Sample a random blinding factor
57        let random_blind = Blind(C::Scalar::random(rng));
58
59        // Commit
60        let c = params.commit(&random_poly, random_blind).to_affine();
61        transcript.write_point(c)?;
62
63        Ok(Committed {
64            random_poly,
65            random_blind,
66        })
67    }
68}
69
70impl<C: CurveAffine> Committed<C> {
71    pub(in crate::plonk) fn construct<
72        'params,
73        P: ParamsProver<'params, C>,
74        E: EncodedChallenge<C>,
75        R: RngCore,
76        T: TranscriptWrite<C, E>,
77    >(
78        self,
79        params: &P,
80        domain: &EvaluationDomain<C::Scalar>,
81        h_poly: Polynomial<C::Scalar, ExtendedLagrangeCoeff>,
82        mut rng: R,
83        transcript: &mut T,
84    ) -> Result<Constructed<C>, Error> {
85        // Divide by t(X) = X^{params.n} - 1.
86        let h_poly = domain.divide_by_vanishing_poly(h_poly);
87
88        // Obtain final h(X) polynomial
89        let h_poly = domain.extended_to_coeff(h_poly);
90
91        // Split h(X) up into pieces
92        let h_pieces = h_poly
93            .chunks_exact(params.n() as usize)
94            .map(|v| domain.coeff_from_vec(v.to_vec()))
95            .collect::<Vec<_>>();
96        drop(h_poly);
97        let h_blinds: Vec<_> = h_pieces
98            .iter()
99            .map(|_| Blind(C::Scalar::random(&mut rng)))
100            .collect();
101
102        // Compute commitments to each h(X) piece
103        let h_commitments_projective: Vec<_> = h_pieces
104            .iter()
105            .zip(h_blinds.iter())
106            .map(|(h_piece, blind)| params.commit(h_piece, *blind))
107            .collect();
108        let mut h_commitments = vec![C::identity(); h_commitments_projective.len()];
109        C::Curve::batch_normalize(&h_commitments_projective, &mut h_commitments);
110        let h_commitments = h_commitments;
111
112        // Hash each h(X) piece
113        for c in h_commitments.iter() {
114            transcript.write_point(*c)?;
115        }
116
117        Ok(Constructed {
118            h_pieces,
119            h_blinds,
120            committed: self,
121        })
122    }
123}
124
125impl<C: CurveAffine> Constructed<C> {
126    pub(in crate::plonk) fn evaluate<E: EncodedChallenge<C>, T: TranscriptWrite<C, E>>(
127        self,
128        x: ChallengeX<C>,
129        xn: C::Scalar,
130        domain: &EvaluationDomain<C::Scalar>,
131        transcript: &mut T,
132    ) -> Result<Evaluated<C>, Error> {
133        let h_poly = self
134            .h_pieces
135            .iter()
136            .rev()
137            .fold(domain.empty_coeff(), |acc, eval| acc * xn + eval);
138
139        let h_blind = self
140            .h_blinds
141            .iter()
142            .rev()
143            .fold(Blind(C::Scalar::ZERO), |acc, eval| acc * Blind(xn) + *eval);
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_axiom/plonk/vanishing/prover.rs

halo2_axiom/plonk/vanishing/
prover.rs
