jf_plonk/proof_system/
prover.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7use core::ops::Neg;
8
9use super::structs::{
10    eval_merged_lookup_witness, eval_merged_table, Challenges, Oracles, PlookupEvaluations,
11    PlookupOracles, ProofEvaluations, ProvingKey,
12};
13use crate::{
14    constants::domain_size_ratio,
15    errors::{PlonkError, SnarkError::*},
16    lagrange::LagrangeCoeffs,
17    proof_system::structs::CommitKey,
18};
19use ark_ec::pairing::Pairing;
20use ark_ff::{FftField, Field, One, UniformRand, Zero};
21use ark_poly::{
22    univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, GeneralEvaluationDomain,
23    Polynomial, Radix2EvaluationDomain,
24};
25use ark_std::{
26    rand::{CryptoRng, RngCore},
27    string::ToString,
28    vec,
29    vec::Vec,
30};
31use jf_pcs::{
32    prelude::{Commitment, UnivariateKzgPCS},
33    PolynomialCommitmentScheme,
34};
35use jf_relation::{constants::GATE_WIDTH, Arithmetization};
36use jf_utils::par_utils::parallelizable_slice_iter;
37#[cfg(feature = "parallel")]
38use rayon::prelude::*;
39
40type CommitmentsAndPolys<E> = (
41    Vec<Commitment<E>>,
42    Vec<DensePolynomial<<E as Pairing>::ScalarField>>,
43);
44
45/// A Plonk IOP prover.
46pub(crate) struct Prover<E: Pairing> {
47    domain: Radix2EvaluationDomain<E::ScalarField>,
48    quot_domain: GeneralEvaluationDomain<E::ScalarField>,
49}
50
51impl<E: Pairing> Prover<E> {
52    /// Construct a Plonk prover that uses a domain with size `domain_size` and
53    /// quotient polynomial domain with a size that is larger than the degree of
54    /// the quotient polynomial.
55    /// * `num_wire_types` - number of wire types in the corresponding
56    ///   constraint system.
57    pub(crate) fn new(domain_size: usize, num_wire_types: usize) -> Result<Self, PlonkError> {
58        let domain = Radix2EvaluationDomain::<E::ScalarField>::new(domain_size)
59            .ok_or(PlonkError::DomainCreationError)?;
60        let quot_domain = GeneralEvaluationDomain::<E::ScalarField>::new(
61            domain_size * domain_size_ratio(domain_size, num_wire_types),
62        )
63        .ok_or(PlonkError::DomainCreationError)?;
64        Ok(Self {
65            domain,
66            quot_domain,
67        })
68    }
69
70    /// Round 1:
71    ///
72    /// 1. Compute and commit wire witness polynomials.
73    /// 2. Compute public input polynomial.
74    ///
75    /// Return the wire witness polynomials and their commitments,
76    /// also return the public input polynomial.
77    pub(crate) fn run_1st_round<C: Arithmetization<E::ScalarField>, R: CryptoRng + RngCore>(
78        &self,
79        prng: &mut R,
80        ck: &CommitKey<E>,
81        cs: &C,
82    ) -> Result<(CommitmentsAndPolys<E>, DensePolynomial<E::ScalarField>), PlonkError> {
83        let wire_polys: Vec<DensePolynomial<E::ScalarField>> = cs
84            .compute_wire_polynomials()?
85            .into_iter()
86            .map(|poly| self.mask_polynomial(prng, poly, 1))
87            .collect();
88        let wires_poly_comms = UnivariateKzgPCS::batch_commit(ck, &wire_polys)?;
89        let pub_input_poly = cs.compute_pub_input_polynomial()?;
90        Ok(((wires_poly_comms, wire_polys), pub_input_poly))
91    }
92
93    /// Round 1.5 (Plookup): Compute and commit the polynomials that interpolate
94    /// the sorted concatenation of the (merged) lookup table and the
95    /// (merged) witnesses in lookup gates. Return the sorted vector, the
96    /// polynomials and their commitments, as well as the merged lookup table.
97    /// `cs` is guaranteed to support lookup.
98    #[allow(clippy::type_complexity)]
99    pub(crate) fn run_plookup_1st_round<
100        C: Arithmetization<E::ScalarField>,
101        R: CryptoRng + RngCore,
102    >(
103        &self,
104        prng: &mut R,
105        ck: &CommitKey<E>,
106        cs: &C,
107        tau: E::ScalarField,
108    ) -> Result<
109        (
110            CommitmentsAndPolys<E>,
111            Vec<E::ScalarField>,
112            Vec<E::ScalarField>,
113        ),
114        PlonkError,
115    > {
116        let merged_lookup_table = cs.compute_merged_lookup_table(tau)?;
117        let (sorted_vec, h_1_poly, h_2_poly) =
118            cs.compute_lookup_sorted_vec_polynomials(tau, &merged_lookup_table)?;
119        let h_1_poly = self.mask_polynomial(prng, h_1_poly, 2);
120        let h_2_poly = self.mask_polynomial(prng, h_2_poly, 2);
121        let h_polys = vec![h_1_poly, h_2_poly];
122        let h_poly_comms = UnivariateKzgPCS::batch_commit(ck, &h_polys)?;
123        Ok(((h_poly_comms, h_polys), sorted_vec, merged_lookup_table))
124    }
125
126    /// Round 2: Compute and commit the permutation grand product polynomial.
127    /// Return the grand product polynomial and its commitment.
128    pub(crate) fn run_2nd_round<C: Arithmetization<E::ScalarField>, R: CryptoRng + RngCore>(
129        &self,
130        prng: &mut R,
131        ck: &CommitKey<E>,
132        cs: &C,
133        challenges: &Challenges<E::ScalarField>,
134    ) -> Result<(Commitment<E>, DensePolynomial<E::ScalarField>), PlonkError> {
135        let prod_perm_poly = self.mask_polynomial(
136            prng,
137            cs.compute_prod_permutation_polynomial(&challenges.beta, &challenges.gamma)?,
138            2,
139        );
140        let prod_perm_comm = UnivariateKzgPCS::commit(ck, &prod_perm_poly)?;
141        Ok((prod_perm_comm, prod_perm_poly))
142    }
143
144    /// Round 2.5 (Plookup): Compute and commit the Plookup grand product
145    /// polynomial. Return the grand product polynomial and its commitment.
146    /// `cs` is guaranteed to support lookup
147    pub(crate) fn run_plookup_2nd_round<
148        C: Arithmetization<E::ScalarField>,
149        R: CryptoRng + RngCore,
150    >(
151        &self,
152        prng: &mut R,
153        ck: &CommitKey<E>,
154        cs: &C,
155        challenges: &Challenges<E::ScalarField>,
156        merged_lookup_table: Option<&Vec<E::ScalarField>>,
157        sorted_vec: Option<&Vec<E::ScalarField>>,
158    ) -> Result<(Commitment<E>, DensePolynomial<E::ScalarField>), PlonkError> {
159        if sorted_vec.is_none() {
160            return Err(
161                ParameterError("Run Plookup with empty sorted lookup vectors".to_string()).into(),
162            );
163        }
164
165        let prod_lookup_poly = self.mask_polynomial(
166            prng,
167            cs.compute_lookup_prod_polynomial(
168                &challenges.tau.unwrap(),
169                &challenges.beta,
170                &challenges.gamma,
171                merged_lookup_table.unwrap(),
172                sorted_vec.unwrap(),
173            )?,
174            2,
175        );
176        let prod_lookup_comm = UnivariateKzgPCS::commit(ck, &prod_lookup_poly)?;
177        Ok((prod_lookup_comm, prod_lookup_poly))
178    }
179
180    /// Round 3: Return the split quotient polynomials and their commitments.
181    /// Note that the first `num_wire_types`-1 split quotient polynomials
182    /// have degree `domain_size`+1.
183    pub(crate) fn run_3rd_round<R: CryptoRng + RngCore>(
184        &self,
185        prng: &mut R,
186        ck: &CommitKey<E>,
187        pks: &[&ProvingKey<E>],
188        challenges: &Challenges<E::ScalarField>,
189        online_oracles: &[Oracles<E::ScalarField>],
190        num_wire_types: usize,
191    ) -> Result<CommitmentsAndPolys<E>, PlonkError> {
192        let quot_poly =
193            self.compute_quotient_polynomial(challenges, pks, online_oracles, num_wire_types)?;
194        let split_quot_polys = self.split_quotient_polynomial(prng, &quot_poly, num_wire_types)?;
195        let split_quot_poly_comms = UnivariateKzgPCS::batch_commit(ck, &split_quot_polys)?;
196
197        Ok((split_quot_poly_comms, split_quot_polys))
198    }
199
200    /// Round 4: Compute linearization polynomial and evaluate polynomials to be
201    /// opened.
202    ///
203    /// Compute the polynomial evaluations for TurboPlonk.
204    /// Return evaluations of the Plonk proof.
205    pub(crate) fn compute_evaluations(
206        &self,
207        pk: &ProvingKey<E>,
208        challenges: &Challenges<E::ScalarField>,
209        online_oracles: &Oracles<E::ScalarField>,
210        num_wire_types: usize,
211    ) -> ProofEvaluations<E::ScalarField> {
212        let wires_evals: Vec<E::ScalarField> =
213            parallelizable_slice_iter(&online_oracles.wire_polys)
214                .map(|poly| poly.evaluate(&challenges.zeta))
215                .collect();
216        let wire_sigma_evals: Vec<E::ScalarField> = parallelizable_slice_iter(&pk.sigmas)
217            .take(num_wire_types - 1)
218            .map(|poly| poly.evaluate(&challenges.zeta))
219            .collect();
220        let perm_next_eval = online_oracles
221            .prod_perm_poly
222            .evaluate(&(challenges.zeta * self.domain.group_gen));
223
224        ProofEvaluations {
225            wires_evals,
226            wire_sigma_evals,
227            perm_next_eval,
228        }
229    }
230
231    /// Round 4.5 (Plookup): Compute and return evaluations of Plookup-related
232    /// polynomials
233    pub(crate) fn compute_plookup_evaluations(
234        &self,
235        pk: &ProvingKey<E>,
236        challenges: &Challenges<E::ScalarField>,
237        online_oracles: &Oracles<E::ScalarField>,
238    ) -> Result<PlookupEvaluations<E::ScalarField>, PlonkError> {
239        if pk.plookup_pk.is_none() {
240            return Err(ParameterError(
241                "Evaluate Plookup polynomials without supporting lookup".to_string(),
242            )
243            .into());
244        }
245        if online_oracles.plookup_oracles.h_polys.len() != 2 {
246            return Err(ParameterError(
247                "Evaluate Plookup polynomials without updating sorted lookup vector polynomials"
248                    .to_string(),
249            )
250            .into());
251        }
252
253        let range_table_poly_ref = &pk.plookup_pk.as_ref().unwrap().range_table_poly;
254        let key_table_poly_ref = &pk.plookup_pk.as_ref().unwrap().key_table_poly;
255        let table_dom_sep_poly_ref = &pk.plookup_pk.as_ref().unwrap().table_dom_sep_poly;
256        let q_dom_sep_poly_ref = &pk.plookup_pk.as_ref().unwrap().q_dom_sep_poly;
257
258        let range_table_eval = range_table_poly_ref.evaluate(&challenges.zeta);
259        let key_table_eval = key_table_poly_ref.evaluate(&challenges.zeta);
260        let h_1_eval = online_oracles.plookup_oracles.h_polys[0].evaluate(&challenges.zeta);
261        let q_lookup_eval = pk.q_lookup_poly()?.evaluate(&challenges.zeta);
262        let table_dom_sep_eval = table_dom_sep_poly_ref.evaluate(&challenges.zeta);
263        let q_dom_sep_eval = q_dom_sep_poly_ref.evaluate(&challenges.zeta);
264
265        let zeta_mul_g = challenges.zeta * self.domain.group_gen;
266        let prod_next_eval = online_oracles
267            .plookup_oracles
268            .prod_lookup_poly
269            .evaluate(&zeta_mul_g);
270        let range_table_next_eval = range_table_poly_ref.evaluate(&zeta_mul_g);
271        let key_table_next_eval = key_table_poly_ref.evaluate(&zeta_mul_g);
272        let h_1_next_eval = online_oracles.plookup_oracles.h_polys[0].evaluate(&zeta_mul_g);
273        let h_2_next_eval = online_oracles.plookup_oracles.h_polys[1].evaluate(&zeta_mul_g);
274        let q_lookup_next_eval = pk.q_lookup_poly()?.evaluate(&zeta_mul_g);
275        let w_3_next_eval = online_oracles.wire_polys[3].evaluate(&zeta_mul_g);
276        let w_4_next_eval = online_oracles.wire_polys[4].evaluate(&zeta_mul_g);
277        let table_dom_sep_next_eval = table_dom_sep_poly_ref.evaluate(&zeta_mul_g);
278
279        Ok(PlookupEvaluations {
280            range_table_eval,
281            key_table_eval,
282            h_1_eval,
283            q_lookup_eval,
284            prod_next_eval,
285            table_dom_sep_eval,
286            q_dom_sep_eval,
287            range_table_next_eval,
288            key_table_next_eval,
289            h_1_next_eval,
290            h_2_next_eval,
291            q_lookup_next_eval,
292            w_3_next_eval,
293            w_4_next_eval,
294            table_dom_sep_next_eval,
295        })
296    }
297
298    /// Compute linearization polynomial (excluding the quotient part)
299    pub(crate) fn compute_non_quotient_component_for_lin_poly(
300        &self,
301        alpha_base: E::ScalarField,
302        pk: &ProvingKey<E>,
303        challenges: &Challenges<E::ScalarField>,
304        online_oracles: &Oracles<E::ScalarField>,
305        poly_evals: &ProofEvaluations<E::ScalarField>,
306        plookup_evals: Option<&PlookupEvaluations<E::ScalarField>>,
307    ) -> Result<DensePolynomial<E::ScalarField>, PlonkError> {
308        let r_circ = Self::compute_lin_poly_circuit_contribution(pk, &poly_evals.wires_evals);
309        let r_perm = self.compute_lin_poly_copy_constraint_contribution(
310            pk,
311            challenges,
312            poly_evals,
313            &online_oracles.prod_perm_poly,
314        );
315        let mut lin_poly = r_circ + r_perm;
316        // compute Plookup contribution if support lookup
317        let r_lookup = plookup_evals.map(|plookup_evals| {
318            self.compute_lin_poly_plookup_contribution(
319                challenges,
320                &poly_evals.wires_evals,
321                plookup_evals,
322                &online_oracles.plookup_oracles,
323            )
324        });
325        if let Some(lookup_poly) = r_lookup {
326            lin_poly = lin_poly + lookup_poly;
327        }
328
329        lin_poly = Self::mul_poly(&lin_poly, &alpha_base);
330        Ok(lin_poly)
331    }
332
333    // Compute the Quotient part of the linearization polynomial:
334    //
335    // -Z_H(x) * [t1(X) + x^{n+2} * t2(X) + ... + x^{(num_wire_types-1)*(n+2)} *
336    // t_{num_wire_types}(X)]
337    pub(crate) fn compute_quotient_component_for_lin_poly(
338        domain_size: usize,
339        zeta: E::ScalarField,
340        quot_polys: &[DensePolynomial<E::ScalarField>],
341    ) -> Result<DensePolynomial<E::ScalarField>, PlonkError> {
342        let vanish_eval = zeta.pow([domain_size as u64]) - E::ScalarField::one();
343        let zeta_to_n_plus_2 = (vanish_eval + E::ScalarField::one()) * zeta * zeta;
344        let mut r_quot = quot_polys.first().ok_or(PlonkError::IndexError)?.clone();
345        let mut coeff = E::ScalarField::one();
346        for poly in quot_polys.iter().skip(1) {
347            coeff *= zeta_to_n_plus_2;
348            r_quot = r_quot + Self::mul_poly(poly, &coeff);
349        }
350        r_quot = Self::mul_poly(&r_quot, &vanish_eval.neg());
351        Ok(r_quot)
352    }
353
354    /// Compute (aggregated) polynomial opening proofs at point `zeta` and
355    /// `zeta * domain_generator`. TODO: Parallelize the computation.
356    pub(crate) fn compute_opening_proofs(
357        &self,
358        ck: &CommitKey<E>,
359        pks: &[&ProvingKey<E>],
360        zeta: &E::ScalarField,
361        v: &E::ScalarField,
362        online_oracles: &[Oracles<E::ScalarField>],
363        lin_poly: &DensePolynomial<E::ScalarField>,
364    ) -> Result<(Commitment<E>, Commitment<E>), PlonkError> {
365        if pks.is_empty() || pks.len() != online_oracles.len() {
366            return Err(ParameterError(
367                "inconsistent pks/online oracles when computing opening proofs".to_string(),
368            )
369            .into());
370        }
371        // List the polynomials to be opened at point `zeta`.
372        let mut polys_ref = vec![lin_poly];
373        for (pk, oracles) in pks.iter().zip(online_oracles.iter()) {
374            for poly in oracles.wire_polys.iter() {
375                polys_ref.push(poly);
376            }
377            // Note we do not add the last wire sigma polynomial.
378            for poly in pk.sigmas.iter().take(pk.sigmas.len() - 1) {
379                polys_ref.push(poly);
380            }
381
382            // Add Plookup related polynomials if support lookup.
383            let lookup_flag =
384                pk.plookup_pk.is_some() && (oracles.plookup_oracles.h_polys.len() == 2);
385            if lookup_flag {
386                polys_ref.extend(Self::plookup_open_polys_ref(oracles, pk)?);
387            }
388        }
389
390        let opening_proof =
391            Self::compute_batched_witness_polynomial_commitment(ck, &polys_ref, v, zeta)?;
392
393        // List the polynomials to be opened at point `zeta * w`.
394        let mut polys_ref = vec![];
395        for (pk, oracles) in pks.iter().zip(online_oracles.iter()) {
396            polys_ref.push(&oracles.prod_perm_poly);
397            // Add Plookup related polynomials if support lookup
398            let lookup_flag =
399                pk.plookup_pk.is_some() && (oracles.plookup_oracles.h_polys.len() == 2);
400            if lookup_flag {
401                polys_ref.extend(Self::plookup_shifted_open_polys_ref(oracles, pk)?);
402            }
403        }
404
405        let shifted_opening_proof = Self::compute_batched_witness_polynomial_commitment(
406            ck,
407            &polys_ref,
408            v,
409            &(self.domain.group_gen * zeta),
410        )?;
411
412        Ok((opening_proof, shifted_opening_proof))
413    }
414}
415
416/// Private helper methods
417impl<E: Pairing> Prover<E> {
418    /// Return the list of plookup polynomials to be opened at point `zeta`
419    /// The order should be consistent with the verifier side.
420    #[inline]
421    fn plookup_open_polys_ref<'a>(
422        oracles: &'a Oracles<E::ScalarField>,
423        pk: &'a ProvingKey<E>,
424    ) -> Result<Vec<&'a DensePolynomial<E::ScalarField>>, PlonkError> {
425        Ok(vec![
426            &pk.plookup_pk.as_ref().unwrap().range_table_poly,
427            &pk.plookup_pk.as_ref().unwrap().key_table_poly,
428            &oracles.plookup_oracles.h_polys[0],
429            pk.q_lookup_poly()?,
430            &pk.plookup_pk.as_ref().unwrap().table_dom_sep_poly,
431            &pk.plookup_pk.as_ref().unwrap().q_dom_sep_poly,
432        ])
433    }
434
435    /// Return the list of plookup polynomials to be opened at point `zeta * g`
436    /// The order should be consistent with the verifier side.
437    #[inline]
438    fn plookup_shifted_open_polys_ref<'a>(
439        oracles: &'a Oracles<E::ScalarField>,
440        pk: &'a ProvingKey<E>,
441    ) -> Result<Vec<&'a DensePolynomial<E::ScalarField>>, PlonkError> {
442        Ok(vec![
443            &oracles.plookup_oracles.prod_lookup_poly,
444            &pk.plookup_pk.as_ref().unwrap().range_table_poly,
445            &pk.plookup_pk.as_ref().unwrap().key_table_poly,
446            &oracles.plookup_oracles.h_polys[0],
447            &oracles.plookup_oracles.h_polys[1],
448            pk.q_lookup_poly()?,
449            &oracles.wire_polys[3],
450            &oracles.wire_polys[4],
451            &pk.plookup_pk.as_ref().unwrap().table_dom_sep_poly,
452        ])
453    }
454
455    /// Mask the polynomial so that it remains hidden after revealing
456    /// `hiding_bound` evaluations.
457    fn mask_polynomial<R: CryptoRng + RngCore>(
458        &self,
459        prng: &mut R,
460        poly: DensePolynomial<E::ScalarField>,
461        hiding_bound: usize,
462    ) -> DensePolynomial<E::ScalarField> {
463        let mask_poly =
464            DensePolynomial::rand(hiding_bound, prng).mul_by_vanishing_poly(self.domain);
465        mask_poly + poly
466    }
467
468    /// Return a batched opening proof given a list of polynomials `polys_ref`,
469    /// evaluation point `eval_point`, and randomized combiner `r`.
470    fn compute_batched_witness_polynomial_commitment(
471        ck: &CommitKey<E>,
472        polys_ref: &[&DensePolynomial<E::ScalarField>],
473        r: &E::ScalarField,
474        eval_point: &E::ScalarField,
475    ) -> Result<Commitment<E>, PlonkError> {
476        // Compute the aggregated polynomial
477        let (batch_poly, _) = polys_ref.iter().fold(
478            (DensePolynomial::zero(), E::ScalarField::one()),
479            |(acc, coeff), &poly| (acc + Self::mul_poly(poly, &coeff), coeff * r),
480        );
481
482        // Compute opening witness polynomial and its commitment
483        let divisor =
484            DensePolynomial::from_coefficients_vec(vec![-*eval_point, E::ScalarField::one()]);
485        let witness_poly = &batch_poly / &divisor;
486
487        UnivariateKzgPCS::commit(ck, &witness_poly).map_err(PlonkError::PCSError)
488    }
489
490    /// Compute the quotient polynomial via (i)FFTs.
491    fn compute_quotient_polynomial(
492        &self,
493        challenges: &Challenges<E::ScalarField>,
494        pks: &[&ProvingKey<E>],
495        online_oracles: &[Oracles<E::ScalarField>],
496        num_wire_types: usize,
497    ) -> Result<DensePolynomial<E::ScalarField>, PlonkError> {
498        if pks.is_empty() || pks.len() != online_oracles.len() {
499            return Err(ParameterError(
500                "inconsistent pks/online oracles when computing quotient polys".to_string(),
501            )
502            .into());
503        }
504
505        let n = self.domain.size();
506        let m = self.quot_domain.size();
507        let domain_size_ratio = m / n;
508        // Compute 1/Z_H(w^i).
509        let z_h_inv: Vec<E::ScalarField> = (0..domain_size_ratio)
510            .map(|i| {
511                ((E::ScalarField::GENERATOR * self.quot_domain.element(i)).pow([n as u64])
512                    - E::ScalarField::one())
513                .inverse()
514                .unwrap()
515            })
516            .collect();
517
518        // Compute coset evaluations of the quotient polynomial.
519        let mut quot_poly_coset_evals_sum = vec![E::ScalarField::zero(); m];
520        let mut alpha_base = E::ScalarField::one();
521        let alpha_3 = challenges.alpha.square() * challenges.alpha;
522        let alpha_7 = alpha_3.square() * challenges.alpha;
523        // TODO: figure out if the unwrap is safe/map error?
524        let coset = self
525            .quot_domain
526            .get_coset(E::ScalarField::GENERATOR)
527            .unwrap();
528        // enumerate proving instances
529        for (oracles, pk) in online_oracles.iter().zip(pks.iter()) {
530            // lookup_flag = 1 if support Plookup argument.
531            let lookup_flag = pk.plookup_pk.is_some();
532
533            // Compute coset evaluations.
534            let selectors_coset_fft: Vec<Vec<E::ScalarField>> =
535                parallelizable_slice_iter(&pk.selectors)
536                    .map(|poly| coset.fft(poly.coeffs()))
537                    .collect();
538            let sigmas_coset_fft: Vec<Vec<E::ScalarField>> = parallelizable_slice_iter(&pk.sigmas)
539                .map(|poly| coset.fft(poly.coeffs()))
540                .collect();
541            let wire_polys_coset_fft: Vec<Vec<E::ScalarField>> =
542                parallelizable_slice_iter(&oracles.wire_polys)
543                    .map(|poly| coset.fft(poly.coeffs()))
544                    .collect();
545
546            // TODO: (binyi) we can also compute below in parallel with
547            // `wire_polys_coset_fft`.
548            let prod_perm_poly_coset_fft = coset.fft(oracles.prod_perm_poly.coeffs());
549            let pub_input_poly_coset_fft = coset.fft(oracles.pub_inp_poly.coeffs());
550
551            // Compute coset evaluations of Plookup online oracles.
552            let (
553                table_dom_sep_coset_fft,
554                q_dom_sep_coset_fft,
555                range_table_coset_fft,
556                key_table_coset_fft,
557                h_coset_ffts,
558                prod_lookup_poly_coset_fft,
559            ) = if lookup_flag {
560                let table_dom_sep_coset_fft =
561                    coset.fft(pk.plookup_pk.as_ref().unwrap().table_dom_sep_poly.coeffs());
562                let q_dom_sep_coset_fft =
563                    coset.fft(pk.plookup_pk.as_ref().unwrap().q_dom_sep_poly.coeffs());
564                let range_table_coset_fft =
565                    coset.fft(pk.plookup_pk.as_ref().unwrap().range_table_poly.coeffs()); // safe unwrap
566                let key_table_coset_fft =
567                    coset.fft(pk.plookup_pk.as_ref().unwrap().key_table_poly.coeffs()); // safe unwrap
568                let h_coset_ffts: Vec<Vec<E::ScalarField>> =
569                    parallelizable_slice_iter(&oracles.plookup_oracles.h_polys)
570                        .map(|poly| coset.fft(poly.coeffs()))
571                        .collect();
572                let prod_lookup_poly_coset_fft =
573                    coset.fft(oracles.plookup_oracles.prod_lookup_poly.coeffs());
574                (
575                    Some(table_dom_sep_coset_fft),
576                    Some(q_dom_sep_coset_fft),
577                    Some(range_table_coset_fft),
578                    Some(key_table_coset_fft),
579                    Some(h_coset_ffts),
580                    Some(prod_lookup_poly_coset_fft),
581                )
582            } else {
583                (None, None, None, None, None, None)
584            };
585
586            // Compute coset evaluations of the quotient polynomial.
587            let quot_poly_coset_evals: Vec<E::ScalarField> =
588                parallelizable_slice_iter(&(0..m).collect::<Vec<_>>())
589                    .map(|&i| {
590                        let w: Vec<E::ScalarField> = (0..num_wire_types)
591                            .map(|j| wire_polys_coset_fft[j][i])
592                            .collect();
593                        let w_next: Vec<E::ScalarField> = (0..num_wire_types)
594                            .map(|j| wire_polys_coset_fft[j][(i + domain_size_ratio) % m])
595                            .collect();
596
597                        let t_circ = Self::compute_quotient_circuit_contribution(
598                            i,
599                            &w,
600                            &pub_input_poly_coset_fft[i],
601                            &selectors_coset_fft,
602                        );
603                        let (t_perm_1, t_perm_2) =
604                            Self::compute_quotient_copy_constraint_contribution(
605                                i,
606                                self.quot_domain.element(i) * E::ScalarField::GENERATOR,
607                                pk,
608                                &w,
609                                &prod_perm_poly_coset_fft[i],
610                                &prod_perm_poly_coset_fft[(i + domain_size_ratio) % m],
611                                challenges,
612                                &sigmas_coset_fft,
613                            );
614                        let mut t1 = t_circ + t_perm_1;
615                        let mut t2 = t_perm_2;
616
617                        // add Plookup-related terms
618                        if lookup_flag {
619                            let (t_lookup_1, t_lookup_2) = self
620                                .compute_quotient_plookup_contribution(
621                                    i,
622                                    self.quot_domain.element(i) * E::ScalarField::GENERATOR,
623                                    pk,
624                                    &w,
625                                    &w_next,
626                                    h_coset_ffts.as_ref().unwrap(),
627                                    prod_lookup_poly_coset_fft.as_ref().unwrap(),
628                                    range_table_coset_fft.as_ref().unwrap(),
629                                    key_table_coset_fft.as_ref().unwrap(),
630                                    selectors_coset_fft.last().unwrap(), /* TODO: add a method
631                                                                          * to extract
632                                                                          * q_lookup_coset_fft */
633                                    table_dom_sep_coset_fft.as_ref().unwrap(),
634                                    q_dom_sep_coset_fft.as_ref().unwrap(),
635                                    challenges,
636                                );
637                            t1 += t_lookup_1;
638                            t2 += t_lookup_2;
639                        }
640                        t1 * z_h_inv[i % domain_size_ratio] + t2
641                    })
642                    .collect();
643
644            for (a, b) in quot_poly_coset_evals_sum
645                .iter_mut()
646                .zip(quot_poly_coset_evals.iter())
647            {
648                *a += alpha_base * b;
649            }
650            // update the random combiner for aggregating multiple proving instances
651            if lookup_flag {
652                alpha_base *= alpha_7;
653            } else {
654                alpha_base *= alpha_3;
655            }
656        }
657        // Compute the coefficient form of the quotient polynomial
658        Ok(DensePolynomial::from_coefficients_vec(
659            coset.ifft(&quot_poly_coset_evals_sum),
660        ))
661    }
662
663    // Compute the i-th coset evaluation of the circuit part of the quotient
664    // polynomial.
665    fn compute_quotient_circuit_contribution(
666        i: usize,
667        w: &[E::ScalarField],
668        pi: &E::ScalarField,
669        selectors_coset_fft: &[Vec<E::ScalarField>],
670    ) -> E::ScalarField {
671        // Selectors
672        // The order: q_lc, q_mul, q_hash, q_o, q_c, q_ecc
673        // TODO: (binyi) get the order from a function.
674        let q_lc: Vec<E::ScalarField> =
675            (0..GATE_WIDTH).map(|j| selectors_coset_fft[j][i]).collect();
676        let q_mul: Vec<E::ScalarField> = (GATE_WIDTH..GATE_WIDTH + 2)
677            .map(|j| selectors_coset_fft[j][i])
678            .collect();
679        let q_hash: Vec<E::ScalarField> = (GATE_WIDTH + 2..2 * GATE_WIDTH + 2)
680            .map(|j| selectors_coset_fft[j][i])
681            .collect();
682        let q_o = selectors_coset_fft[2 * GATE_WIDTH + 2][i];
683        let q_c = selectors_coset_fft[2 * GATE_WIDTH + 3][i];
684        let q_ecc = selectors_coset_fft[2 * GATE_WIDTH + 4][i];
685
686        q_c + pi
687            + q_lc[0] * w[0]
688            + q_lc[1] * w[1]
689            + q_lc[2] * w[2]
690            + q_lc[3] * w[3]
691            + q_mul[0] * w[0] * w[1]
692            + q_mul[1] * w[2] * w[3]
693            + q_ecc * w[0] * w[1] * w[2] * w[3] * w[4]
694            + q_hash[0] * w[0].pow([5])
695            + q_hash[1] * w[1].pow([5])
696            + q_hash[2] * w[2].pow([5])
697            + q_hash[3] * w[3].pow([5])
698            - q_o * w[4]
699    }
700
701    /// Compute the i-th coset evaluation of the copy constraint part of the
702    /// quotient polynomial.
703    /// `eval_point` - the evaluation point.
704    /// `w` - the wire polynomial coset evaluations at `eval_point`.
705    /// `z_x` - the permutation product polynomial evaluation at `eval_point`.
706    /// `z_xw`-  the permutation product polynomial evaluation at `eval_point *
707    /// g`, where `g` is the root of unity of the original domain.
708    #[allow(clippy::too_many_arguments)]
709    fn compute_quotient_copy_constraint_contribution(
710        i: usize,
711        eval_point: E::ScalarField,
712        pk: &ProvingKey<E>,
713        w: &[E::ScalarField],
714        z_x: &E::ScalarField,
715        z_xw: &E::ScalarField,
716        challenges: &Challenges<E::ScalarField>,
717        sigmas_coset_fft: &[Vec<E::ScalarField>],
718    ) -> (E::ScalarField, E::ScalarField) {
719        let num_wire_types = w.len();
720        let n = pk.domain_size();
721
722        // The check that:
723        //   \prod_i [w_i(X) + beta * k_i * X + gamma] * z(X)
724        // - \prod_i [w_i(X) + beta * sigma_i(X) + gamma] * z(wX) = 0
725        // on the vanishing set.
726        // Delay the division of Z_H(X).
727        //
728        // Extended permutation values
729        let sigmas: Vec<E::ScalarField> = (0..num_wire_types)
730            .map(|j| sigmas_coset_fft[j][i])
731            .collect();
732
733        // Compute the 1st term.
734        let mut result_1 = challenges.alpha
735            * w.iter().enumerate().fold(*z_x, |acc, (j, &w)| {
736                acc * (w + pk.k()[j] * eval_point * challenges.beta + challenges.gamma)
737            });
738        // Minus the 2nd term.
739        result_1 -= challenges.alpha
740            * w.iter()
741                .zip(sigmas.iter())
742                .fold(*z_xw, |acc, (&w, &sigma)| {
743                    acc * (w + sigma * challenges.beta + challenges.gamma)
744                });
745
746        // The check that z(x) = 1 at point 1.
747        // (z(x)-1) * L1(x) * alpha^2 / Z_H(x) = (z(x)-1) * alpha^2 / (n * (x - 1))
748        let result_2 = challenges.alpha.square() * (*z_x - E::ScalarField::one())
749            / (E::ScalarField::from(n as u64) * (eval_point - E::ScalarField::one()));
750
751        (result_1, result_2)
752    }
753
754    /// Compute the i-th coset evaluation of the lookup constraint part of the
755    /// quotient polynomial.
756    /// `eval_point`: the evaluation point.
757    /// `pk`: proving key.
758    /// `lookup_w`: (merged) lookup witness coset evaluations at `eval_point`.
759    /// `h_coset_ffts`: coset evaluations for the sorted lookup vector
760    /// polynomials. `prod_lookup_coset_fft`: coset evaluations for the
761    /// Plookup product polynomial. `challenges`: Fiat-shamir challenges.
762    ///
763    /// The coset evaluations should be non-empty. The proving key should be
764    /// guaranteed to support lookup.
765    #[allow(clippy::too_many_arguments)]
766    fn compute_quotient_plookup_contribution(
767        &self,
768        i: usize,
769        eval_point: E::ScalarField,
770        pk: &ProvingKey<E>,
771        w: &[E::ScalarField],
772        w_next: &[E::ScalarField],
773        h_coset_ffts: &[Vec<E::ScalarField>],
774        prod_lookup_coset_fft: &[E::ScalarField],
775        range_table_coset_fft: &[E::ScalarField],
776        key_table_coset_fft: &[E::ScalarField],
777        q_lookup_coset_fft: &[E::ScalarField],
778        table_dom_sep_coset_fft: &[E::ScalarField],
779        q_dom_sep_coset_fft: &[E::ScalarField],
780        challenges: &Challenges<E::ScalarField>,
781    ) -> (E::ScalarField, E::ScalarField) {
782        assert!(pk.plookup_pk.is_some());
783        assert_eq!(h_coset_ffts.len(), 2);
784
785        let n = pk.domain_size();
786        let m = self.quot_domain.size();
787        let domain_size_ratio = m / n;
788        let vanish_eval = self.domain.evaluate_vanishing_polynomial(eval_point);
789        let (lagrange_1_coeff, lagrange_n_coeff) =
790            self.domain.first_and_last_lagrange_coeffs(eval_point);
791        let lagrange_1_coeff_div_vanish = lagrange_1_coeff / vanish_eval;
792        let lagrange_n_coeff_div_vanish = lagrange_n_coeff / vanish_eval;
793
794        let mut alpha_power = challenges.alpha * challenges.alpha * challenges.alpha;
795
796        // extract polynomial evaluations
797        let h_1_x = h_coset_ffts[0][i];
798        let h_1_xw = h_coset_ffts[0][(i + domain_size_ratio) % m];
799        let h_2_x = h_coset_ffts[1][i];
800        let h_2_xw = h_coset_ffts[1][(i + domain_size_ratio) % m];
801        let p_x = prod_lookup_coset_fft[i];
802        let p_xw = prod_lookup_coset_fft[(i + domain_size_ratio) % m];
803        let range_table_x = range_table_coset_fft[i];
804        let key_table_x = key_table_coset_fft[i];
805        let table_dom_sep_x = table_dom_sep_coset_fft[i];
806        let q_dom_sep_x = q_dom_sep_coset_fft[i];
807
808        let range_table_xw = range_table_coset_fft[(i + domain_size_ratio) % m];
809        let key_table_xw = key_table_coset_fft[(i + domain_size_ratio) % m];
810        let table_dom_sep_xw = table_dom_sep_coset_fft[(i + domain_size_ratio) % m];
811        let merged_table_x = eval_merged_table::<E>(
812            challenges.tau.unwrap(),
813            range_table_x,
814            key_table_x,
815            q_lookup_coset_fft[i],
816            w[3],
817            w[4],
818            table_dom_sep_x,
819        );
820        let merged_table_xw = eval_merged_table::<E>(
821            challenges.tau.unwrap(),
822            range_table_xw,
823            key_table_xw,
824            q_lookup_coset_fft[(i + domain_size_ratio) % m],
825            w_next[3],
826            w_next[4],
827            table_dom_sep_xw,
828        );
829        let merged_lookup_x = eval_merged_lookup_witness::<E>(
830            challenges.tau.unwrap(),
831            w[5],
832            w[0],
833            w[1],
834            w[2],
835            q_lookup_coset_fft[i],
836            q_dom_sep_x,
837        );
838
839        // The check that h1(X) - h2(wX) = 0 at point w^{n-1}
840        //
841        // Fh(X)/Z_H(X) = (Ln(X) * (h1(X) - h2(wX))) / Z_H(X) = (h1(X) - h2(wX)) *
842        // w^{n-1} / (n * (X - w^{n-1}))
843        let term_h = (h_1_x - h_2_xw) * lagrange_n_coeff_div_vanish;
844        let mut result_2 = alpha_power * term_h;
845        alpha_power *= challenges.alpha;
846
847        // The check that p(X) = 1 at point 1.
848        //
849        // Fp1(X)/Z_H(X) = (L1(X) * (p(X) - 1)) / Z_H(X) = (p(X) - 1) / (n * (X - 1))
850        let term_p_1 = (p_x - E::ScalarField::one()) * lagrange_1_coeff_div_vanish;
851        result_2 += alpha_power * term_p_1;
852        alpha_power *= challenges.alpha;
853
854        // The check that p(X) = 1 at point w^{n-1}.
855        //
856        // Fp2(X)/Z_H(X) = (Ln(X) * (p(X) - 1)) / Z_H(X) = (p(X) - 1) * w^{n-1} / (n *
857        // (X - w^{n-1}))
858        let term_p_2 = (p_x - E::ScalarField::one()) * lagrange_n_coeff_div_vanish;
859        result_2 += alpha_power * term_p_2;
860        alpha_power *= challenges.alpha;
861
862        // The relation check between adjacent points on the vanishing set.
863        // Delay the division of Z_H(X).
864        //
865        // Fp3(X) = (X - w^{n-1}) * p(X) * (1+beta) * (gamma + merged_lookup(X)) *
866        // [gamma*(1+beta) + merged_table(X) + beta * merged_table(Xw)]
867        //        - (X - w^{n-1}) * p(Xw) * [gamma(1+beta) + h_1(X) + beta * h_1(Xw)] *
868        //          [gamma(1+beta) + h_2(X) + beta * h_2(Xw)]
869        let beta_plus_one = E::ScalarField::one() + challenges.beta;
870        let gamma_mul_beta_plus_one = beta_plus_one * challenges.gamma;
871        let term_p_3 = (eval_point - self.domain.group_gen_inv)
872            * (p_x
873                * beta_plus_one
874                * (challenges.gamma + merged_lookup_x)
875                * (gamma_mul_beta_plus_one + merged_table_x + challenges.beta * merged_table_xw)
876                - p_xw
877                    * (gamma_mul_beta_plus_one + h_1_x + challenges.beta * h_1_xw)
878                    * (gamma_mul_beta_plus_one + h_2_x + challenges.beta * h_2_xw));
879        let result_1 = alpha_power * term_p_3;
880
881        (result_1, result_2)
882    }
883
884    /// Split the quotient polynomial into `num_wire_types` polynomials.
885    /// The first `num_wire_types`-1 polynomials have degree `domain_size`+1.
886    ///
887    /// Let t(X) be the input quotient polynomial, t_i(X) be the output
888    /// splitting polynomials. t(X) = \sum_{i=0}^{num_wire_types}
889    /// X^{i*(n+2)} * t_i(X)
890    ///
891    /// NOTE: we have a step polynomial of X^(n+2) instead of X^n as in the
892    /// GWC19 paper to achieve better balance among degrees of all splitting
893    /// polynomials (especially the highest-degree/last one).
894    fn split_quotient_polynomial<R: CryptoRng + RngCore>(
895        &self,
896        prng: &mut R,
897        quot_poly: &DensePolynomial<E::ScalarField>,
898        num_wire_types: usize,
899    ) -> Result<Vec<DensePolynomial<E::ScalarField>>, PlonkError> {
900        let expected_degree = quotient_polynomial_degree(self.domain.size(), num_wire_types);
901        if quot_poly.degree() != expected_degree {
902            return Err(WrongQuotientPolyDegree(quot_poly.degree(), expected_degree).into());
903        }
904        let n = self.domain.size();
905        // compute the splitting polynomials t'_i(X) s.t. t(X) =
906        // \sum_{i=0}^{num_wire_types} X^{i*(n+2)} * t'_i(X)
907        let mut split_quot_polys: Vec<DensePolynomial<E::ScalarField>> =
908            parallelizable_slice_iter(&(0..num_wire_types).collect::<Vec<_>>())
909                .map(|&i| {
910                    let end = if i < num_wire_types - 1 {
911                        (i + 1) * (n + 2)
912                    } else {
913                        quot_poly.degree() + 1
914                    };
915                    // Degree-(n+1) polynomial has n + 2 coefficients.
916                    DensePolynomial::<E::ScalarField>::from_coefficients_slice(
917                        &quot_poly.coeffs[i * (n + 2)..end],
918                    )
919                })
920                .collect();
921
922        // mask splitting polynomials t_i(X), for i in {0..num_wire_types}.
923        // t_i(X) = t'_i(X) - b_last_i + b_now_i * X^(n+2)
924        // with t_lowest_i(X) = t_lowest_i(X) - 0 + b_now_i * X^(n+2)
925        // and t_highest_i(X) = t_highest_i(X) - b_last_i
926        let mut last_randomizer = E::ScalarField::zero();
927        split_quot_polys
928            .iter_mut()
929            .take(num_wire_types - 1)
930            .for_each(|poly| {
931                let now_randomizer = E::ScalarField::rand(prng);
932
933                poly.coeffs[0] -= last_randomizer;
934                assert_eq!(poly.degree(), n + 1);
935                poly.coeffs.push(now_randomizer);
936
937                last_randomizer = now_randomizer;
938            });
939        // mask the highest splitting poly
940        split_quot_polys[num_wire_types - 1].coeffs[0] -= last_randomizer;
941
942        Ok(split_quot_polys)
943    }
944
945    // Compute the circuit part of the linearization polynomial
946    fn compute_lin_poly_circuit_contribution(
947        pk: &ProvingKey<E>,
948        w_evals: &[E::ScalarField],
949    ) -> DensePolynomial<E::ScalarField> {
950        // The selectors order: q_lc, q_mul, q_hash, q_o, q_c, q_ecc
951        // TODO: (binyi) get the order from a function.
952        let q_lc = &pk.selectors[..GATE_WIDTH];
953        let q_mul = &pk.selectors[GATE_WIDTH..GATE_WIDTH + 2];
954        let q_hash = &pk.selectors[GATE_WIDTH + 2..2 * GATE_WIDTH + 2];
955        let q_o = &pk.selectors[2 * GATE_WIDTH + 2];
956        let q_c = &pk.selectors[2 * GATE_WIDTH + 3];
957        let q_ecc = &pk.selectors[2 * GATE_WIDTH + 4];
958
959        // TODO(binyi): add polynomials in parallel.
960        // Note we don't need to compute the constant term of the polynomial.
961        Self::mul_poly(&q_lc[0], &w_evals[0])
962            + Self::mul_poly(&q_lc[1], &w_evals[1])
963            + Self::mul_poly(&q_lc[2], &w_evals[2])
964            + Self::mul_poly(&q_lc[3], &w_evals[3])
965            + Self::mul_poly(&q_mul[0], &(w_evals[0] * w_evals[1]))
966            + Self::mul_poly(&q_mul[1], &(w_evals[2] * w_evals[3]))
967            + Self::mul_poly(&q_hash[0], &w_evals[0].pow([5]))
968            + Self::mul_poly(&q_hash[1], &w_evals[1].pow([5]))
969            + Self::mul_poly(&q_hash[2], &w_evals[2].pow([5]))
970            + Self::mul_poly(&q_hash[3], &w_evals[3].pow([5]))
971            + Self::mul_poly(
972                q_ecc,
973                &(w_evals[0] * w_evals[1] * w_evals[2] * w_evals[3] * w_evals[4]),
974            )
975            + Self::mul_poly(q_o, &(-w_evals[4]))
976            + q_c.clone()
977    }
978
979    // Compute the wire permutation part of the linearization polynomial
980    fn compute_lin_poly_copy_constraint_contribution(
981        &self,
982        pk: &ProvingKey<E>,
983        challenges: &Challenges<E::ScalarField>,
984        poly_evals: &ProofEvaluations<E::ScalarField>,
985        prod_perm_poly: &DensePolynomial<E::ScalarField>,
986    ) -> DensePolynomial<E::ScalarField> {
987        let lagrange_1_eval = self.domain.first_lagrange_coeff(challenges.zeta);
988
989        // Compute the coefficient of z(X)
990        let coeff = poly_evals.wires_evals.iter().enumerate().fold(
991            challenges.alpha,
992            |acc, (j, &wire_eval)| {
993                acc * (wire_eval
994                    + challenges.beta * pk.vk.k[j] * challenges.zeta
995                    + challenges.gamma)
996            },
997        ) + challenges.alpha.square() * lagrange_1_eval;
998        let mut r_perm = Self::mul_poly(prod_perm_poly, &coeff);
999
1000        // Compute the coefficient of the last sigma wire permutation polynomial
1001        let num_wire_types = poly_evals.wires_evals.len();
1002        let coeff = -poly_evals
1003            .wires_evals
1004            .iter()
1005            .take(num_wire_types - 1)
1006            .zip(poly_evals.wire_sigma_evals.iter())
1007            .fold(
1008                challenges.alpha * challenges.beta * poly_evals.perm_next_eval,
1009                |acc, (&wire_eval, &sigma_eval)| {
1010                    acc * (wire_eval + challenges.beta * sigma_eval + challenges.gamma)
1011                },
1012            );
1013        r_perm = r_perm + Self::mul_poly(&pk.sigmas[num_wire_types - 1], &coeff);
1014        r_perm
1015    }
1016
1017    // Compute the Plookup part of the linearization polynomial
1018    fn compute_lin_poly_plookup_contribution(
1019        &self,
1020        challenges: &Challenges<E::ScalarField>,
1021        w_evals: &[E::ScalarField],
1022        plookup_evals: &PlookupEvaluations<E::ScalarField>,
1023        oracles: &PlookupOracles<E::ScalarField>,
1024    ) -> DensePolynomial<E::ScalarField> {
1025        let alpha_2 = challenges.alpha.square();
1026        let alpha_4 = alpha_2.square();
1027        let alpha_5 = alpha_4 * challenges.alpha;
1028        let alpha_6 = alpha_4 * alpha_2;
1029        let one = E::ScalarField::one();
1030
1031        // compute lagrange_1 and lagrange_n
1032        let (lagrange_1_eval, lagrange_n_eval) =
1033            self.domain.first_and_last_lagrange_coeffs(challenges.zeta);
1034
1035        // compute the coefficient for polynomial `prod_lookup_poly`
1036        let merged_table_eval = eval_merged_table::<E>(
1037            challenges.tau.unwrap(),
1038            plookup_evals.range_table_eval,
1039            plookup_evals.key_table_eval,
1040            plookup_evals.q_lookup_eval,
1041            w_evals[3],
1042            w_evals[4],
1043            plookup_evals.table_dom_sep_eval,
1044        );
1045        let merged_table_next_eval = eval_merged_table::<E>(
1046            challenges.tau.unwrap(),
1047            plookup_evals.range_table_next_eval,
1048            plookup_evals.key_table_next_eval,
1049            plookup_evals.q_lookup_next_eval,
1050            plookup_evals.w_3_next_eval,
1051            plookup_evals.w_4_next_eval,
1052            plookup_evals.table_dom_sep_next_eval,
1053        );
1054        let merged_lookup_eval = eval_merged_lookup_witness::<E>(
1055            challenges.tau.unwrap(),
1056            w_evals[5],
1057            w_evals[0],
1058            w_evals[1],
1059            w_evals[2],
1060            plookup_evals.q_lookup_eval,
1061            plookup_evals.q_dom_sep_eval,
1062        );
1063
1064        let beta_plus_one = one + challenges.beta;
1065        let zeta_minus_g_inv = challenges.zeta - self.domain.group_gen_inv;
1066        let coeff = alpha_4 * lagrange_1_eval
1067            + alpha_5 * lagrange_n_eval
1068            + alpha_6
1069                * zeta_minus_g_inv
1070                * beta_plus_one
1071                * (challenges.gamma + merged_lookup_eval)
1072                * (challenges.gamma * beta_plus_one
1073                    + merged_table_eval
1074                    + challenges.beta * merged_table_next_eval);
1075        let mut r_lookup = Self::mul_poly(&oracles.prod_lookup_poly, &coeff);
1076
1077        // compute the coefficient for polynomial `h_2_poly`
1078        let coeff = -alpha_6
1079            * zeta_minus_g_inv
1080            * plookup_evals.prod_next_eval
1081            * (challenges.gamma * beta_plus_one
1082                + plookup_evals.h_1_eval
1083                + challenges.beta * plookup_evals.h_1_next_eval);
1084        r_lookup = r_lookup + Self::mul_poly(&oracles.h_polys[1], &coeff);
1085
1086        r_lookup
1087    }
1088
1089    #[inline]
1090    fn mul_poly(
1091        poly: &DensePolynomial<E::ScalarField>,
1092        coeff: &E::ScalarField,
1093    ) -> DensePolynomial<E::ScalarField> {
1094        DensePolynomial::<E::ScalarField>::from_coefficients_vec(
1095            parallelizable_slice_iter(&poly.coeffs)
1096                .map(|c| *coeff * c)
1097                .collect(),
1098        )
1099    }
1100}
1101
1102#[inline]
1103fn quotient_polynomial_degree(domain_size: usize, num_wire_types: usize) -> usize {
1104    num_wire_types * (domain_size + 1) + 2
1105}
1106
1107#[cfg(test)]
1108mod test {
1109    use super::*;
1110    use ark_bls12_377::Bls12_377;
1111    use ark_bls12_381::Bls12_381;
1112    use ark_bn254::Bn254;
1113    use ark_bw6_761::BW6_761;
1114    use jf_utils::test_rng;
1115
1116    #[test]
1117    fn test_split_quotient_polynomial_wrong_degree() -> Result<(), PlonkError> {
1118        test_split_quotient_polynomial_wrong_degree_helper::<Bn254>()?;
1119        test_split_quotient_polynomial_wrong_degree_helper::<Bls12_377>()?;
1120        test_split_quotient_polynomial_wrong_degree_helper::<Bls12_381>()?;
1121        test_split_quotient_polynomial_wrong_degree_helper::<BW6_761>()
1122    }
1123
1124    fn test_split_quotient_polynomial_wrong_degree_helper<E: Pairing>() -> Result<(), PlonkError> {
1125        let prover = Prover::<E>::new(4, GATE_WIDTH + 1)?;
1126        let rng = &mut test_rng();
1127        let bad_quot_poly = DensePolynomial::<E::ScalarField>::rand(25, rng);
1128        assert!(prover
1129            .split_quotient_polynomial(rng, &bad_quot_poly, GATE_WIDTH + 1)
1130            .is_err());
1131        Ok(())
1132    }
1133}
jf_plonk/proof_system/prover.rs

jf_plonk/proof_system/
prover.rs
