Skip to main content

jf_relation/
constraint_system.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
7//! Definitions and constructions of plonk constraint system
8use crate::{
9    constants::{compute_coset_representatives, GATE_WIDTH, N_MUL_SELECTORS},
10    gates::*,
11    CircuitError,
12    CircuitError::*,
13};
14use ark_ff::{FftField, Field, PrimeField};
15use ark_poly::{
16    domain::Radix2EvaluationDomain, univariate::DensePolynomial, DenseUVPolynomial,
17    EvaluationDomain,
18};
19use ark_std::{boxed::Box, cmp::max, format, string::ToString, vec, vec::Vec};
20use hashbrown::{HashMap, HashSet};
21use jf_utils::par_utils::parallelizable_slice_iter;
22#[cfg(feature = "parallel")]
23use rayon::prelude::*;
24
25/// An index to a gate in circuit.
26pub type GateId = usize;
27/// An index to the type of gate wires.
28/// There are 4 different types of input gate wires (with indices 0..3),
29/// 1 type of output gate wires (with index 4), and 1 type of lookup gate wires
30/// (with index 5).
31pub type WireId = usize;
32/// An index to one of the witness values.
33pub type Variable = usize;
34/// An index to a witness value of boolean type.
35#[derive(Debug, Clone, Copy)]
36pub struct BoolVar(pub usize);
37
38impl From<BoolVar> for Variable {
39    fn from(bv: BoolVar) -> Self {
40        bv.0
41    }
42}
43
44impl BoolVar {
45    /// Create a `BoolVar` without any check. Be careful!
46    /// This is an internal API, shouldn't be used unless you know what you are
47    /// doing. Normally you should only construct `BoolVar` through
48    /// `Circuit::create_boolean_variable()`.
49    pub(crate) fn new_unchecked(inner: usize) -> Self {
50        Self(inner)
51    }
52}
53
54#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
55/// Enum for each type of Plonk scheme.
56pub enum PlonkType {
57    /// TurboPlonk
58    TurboPlonk,
59    /// TurboPlonk that supports Plookup
60    UltraPlonk,
61}
62
63#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
64/// Enum for each type of mergeable circuit. We can only merge circuits from
65/// different types.
66pub enum MergeableCircuitType {
67    /// First type
68    TypeA,
69    /// Second type
70    TypeB,
71}
72
73/// An interface for Plonk constraint systems.
74pub trait Circuit<F: Field> {
75    /// The number of constraints.
76    fn num_gates(&self) -> usize;
77
78    /// The number of variables.
79    fn num_vars(&self) -> usize;
80
81    /// The number of public input variables.
82    fn num_inputs(&self) -> usize;
83
84    /// The number of wire types of the circuit.
85    /// E.g., UltraPlonk has 4 different types of input wires, 1 type of output
86    /// wires, and 1 type of lookup wires.
87    fn num_wire_types(&self) -> usize;
88
89    /// The list of public input values.
90    fn public_input(&self) -> Result<Vec<F>, CircuitError>;
91
92    /// Check circuit satisfiability against a public input.
93    fn check_circuit_satisfiability(&self, pub_input: &[F]) -> Result<(), CircuitError>;
94
95    /// Add a constant variable to the circuit; return the index of the
96    /// variable.
97    fn create_constant_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
98
99    /// Add a variable to the circuit; return the index of the variable.
100    fn create_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
101
102    /// Add a bool variable to the circuit; return the index of the variable.
103    fn create_boolean_variable(&mut self, val: bool) -> Result<BoolVar, CircuitError> {
104        let val_scalar = if val { F::one() } else { F::zero() };
105        let var = self.create_variable(val_scalar)?;
106        self.enforce_bool(var)?;
107        Ok(BoolVar(var))
108    }
109
110    /// Add a public input variable; return the index of the variable.
111    fn create_public_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
112
113    /// Add a public bool variable to the circuit; return the index of the
114    /// variable.
115    fn create_public_boolean_variable(&mut self, val: bool) -> Result<BoolVar, CircuitError> {
116        let val_scalar = if val { F::one() } else { F::zero() };
117        let var = self.create_public_variable(val_scalar)?;
118        Ok(BoolVar(var))
119    }
120
121    /// Set a variable to a public variable
122    fn set_variable_public(&mut self, var: Variable) -> Result<(), CircuitError>;
123
124    /// Return a default variable with value zero.
125    fn zero(&self) -> Variable;
126
127    /// Return a default variable with value one.
128    fn one(&self) -> Variable;
129
130    /// Return a default variable with value `false` (namely zero).
131    fn false_var(&self) -> BoolVar {
132        BoolVar::new_unchecked(self.zero())
133    }
134
135    /// Return a default variable with value `true` (namely one).
136    fn true_var(&self) -> BoolVar {
137        BoolVar::new_unchecked(self.one())
138    }
139
140    /// Return the witness value of variable `idx`.
141    /// Return error if the input variable is invalid.
142    fn witness(&self, idx: Variable) -> Result<F, CircuitError>;
143
144    /// Common gates that should be implemented in any constraint systems.
145    ///
146    /// Constrain a variable to a constant.
147    /// Return error if `var` is an invalid variable.
148    fn enforce_constant(&mut self, var: Variable, constant: F) -> Result<(), CircuitError>;
149
150    /// Constrain variable `c` to the addition of `a` and `b`.
151    /// Return error if the input variables are invalid.
152    fn add_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
153
154    /// Obtain a variable representing an addition.
155    /// Return the index of the variable.
156    /// Return error if the input variables are invalid.
157    fn add(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
158
159    /// Constrain variable `c` to the subtraction of `a` and `b`.
160    /// Return error if the input variables are invalid.
161    fn sub_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
162
163    /// Obtain a variable representing a subtraction.
164    /// Return the index of the variable.
165    /// Return error if the input variables are invalid.
166    fn sub(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
167
168    /// Constrain variable `c` to the multiplication of `a` and `b`.
169    /// Return error if the input variables are invalid.
170    fn mul_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
171
172    /// Obtain a variable representing a multiplication.
173    /// Return the index of the variable.
174    /// Return error if the input variables are invalid.
175    fn mul(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
176
177    /// Constrain a variable to a bool.
178    /// Return error if the input is invalid.
179    fn enforce_bool(&mut self, a: Variable) -> Result<(), CircuitError>;
180
181    /// Constrain two variables to have the same value.
182    /// Return error if the input variables are invalid.
183    fn enforce_equal(&mut self, a: Variable, b: Variable) -> Result<(), CircuitError>;
184
185    /// Pad the circuit with n dummy gates
186    fn pad_gates(&mut self, n: usize);
187
188    /// Plookup-related methods.
189    /// Return true if the circuit support lookup gates.
190    fn support_lookup(&self) -> bool;
191}
192
193// The sorted concatenation of the lookup table and the witness values to be
194// checked in lookup gates. It also includes 2 polynomials that interpolate the
195// sorted vector.
196pub(crate) type SortedLookupVecAndPolys<F> = (Vec<F>, DensePolynomial<F>, DensePolynomial<F>);
197
198/// An interface that transforms Plonk circuits to polynomial used by
199/// Plonk-based SNARKs.
200pub trait Arithmetization<F: FftField>: Circuit<F> {
201    /// The required SRS size for the circuit.
202    fn srs_size(&self) -> Result<usize, CircuitError>;
203
204    /// Get the size of the evaluation domain for arithmetization (after circuit
205    /// has been finalized).
206    fn eval_domain_size(&self) -> Result<usize, CircuitError>;
207
208    /// Compute and return selector polynomials.
209    /// Return an error if the circuit has not been finalized yet.
210    fn compute_selector_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
211
212    /// Compute and return extended permutation polynomials.
213    /// Return an error if the circuit has not been finalized yet.
214    fn compute_extended_permutation_polynomials(
215        &self,
216    ) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
217
218    /// Compute and return the product polynomial for permutation arguments.
219    /// Return an error if the circuit has not been finalized yet.
220    fn compute_prod_permutation_polynomial(
221        &self,
222        beta: &F,
223        gamma: &F,
224    ) -> Result<DensePolynomial<F>, CircuitError>;
225
226    /// Compute and return the list of wiring witness polynomials.
227    /// Return an error if the circuit has not been finalized yet.
228    fn compute_wire_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
229
230    /// Compute and return the public input polynomial.
231    /// Return an error if the circuit has not been finalized yet.
232    /// The IO gates of the circuit are guaranteed to be in the front.
233    fn compute_pub_input_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError>;
234
235    /// Plookup-related methods
236    /// Return default errors if the constraint system does not support lookup
237    /// gates.
238    ///
239    /// Compute and return the polynomial that interpolates the range table
240    /// elements. Return an error if the circuit does not support lookup or
241    /// has not been finalized yet.
242    fn compute_range_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
243        Err(CircuitError::LookupUnsupported)
244    }
245
246    /// Compute and return the polynomial that interpolates the key table
247    /// elements. Return an error if the circuit does not support lookup or
248    /// has not been finalized yet.
249    fn compute_key_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
250        Err(CircuitError::LookupUnsupported)
251    }
252
253    /// Compute and return the polynomial that interpolates the table domain
254    /// separation ids. Return an error if the circuit does not support
255    /// lookup or has not been finalized.
256    fn compute_table_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
257        Err(CircuitError::LookupUnsupported)
258    }
259
260    /// Compute and return the polynomial that interpolates the lookup domain
261    /// separation selectors for the lookup gates. Return an error if the
262    /// circuit does not support lookup or has not been finalized.
263    fn compute_q_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
264        Err(CircuitError::LookupUnsupported)
265    }
266
267    /// Compute and return the combined lookup table vector given random
268    /// challenge `tau`.
269    fn compute_merged_lookup_table(&self, _tau: F) -> Result<Vec<F>, CircuitError> {
270        Err(CircuitError::LookupUnsupported)
271    }
272
273    /// Compute the sorted concatenation of the (merged) lookup table and the
274    /// witness values to be checked in lookup gates. Return the sorted
275    /// vector and 2 polynomials that interpolate the vector. Return an
276    /// error if the circuit does not support lookup or has not been
277    /// finalized yet.
278    fn compute_lookup_sorted_vec_polynomials(
279        &self,
280        _tau: F,
281        _lookup_table: &[F],
282    ) -> Result<SortedLookupVecAndPolys<F>, CircuitError> {
283        Err(CircuitError::LookupUnsupported)
284    }
285
286    /// Compute and return the product polynomial for Plookup arguments.
287    /// `beta` and `gamma` are random challenges, `sorted_vec` is the sorted
288    /// concatenation of the lookup table and the lookup witnesses.
289    /// Return an error if the circuit does not support lookup or
290    /// has not been finalized yet.
291    fn compute_lookup_prod_polynomial(
292        &self,
293        _tau: &F,
294        _beta: &F,
295        _gamma: &F,
296        _lookup_table: &[F],
297        _sorted_vec: &[F],
298    ) -> Result<DensePolynomial<F>, CircuitError> {
299        Err(CircuitError::LookupUnsupported)
300    }
301}
302
303/// The wire type identifier for range gates.
304const RANGE_WIRE_ID: usize = 5;
305/// The wire type identifier for the key index in a lookup gate
306const LOOKUP_KEY_WIRE_ID: usize = 0;
307/// The wire type identifiers for the searched pair values in a lookup gate
308const LOOKUP_VAL_1_WIRE_ID: usize = 1;
309const LOOKUP_VAL_2_WIRE_ID: usize = 2;
310/// The wire type identifiers for the pair values in the lookup table
311const TABLE_VAL_1_WIRE_ID: usize = 3;
312const TABLE_VAL_2_WIRE_ID: usize = 4;
313
314/// Hardcoded parameters for Plonk systems.
315#[derive(Debug, Clone, Copy)]
316struct PlonkParams {
317    /// The Plonk type of the circuit.
318    plonk_type: PlonkType,
319
320    /// The bit length of a range-check. None for TurboPlonk.
321    range_bit_len: Option<usize>,
322}
323
324impl PlonkParams {
325    fn init(plonk_type: PlonkType, range_bit_len: Option<usize>) -> Result<Self, CircuitError> {
326        if plonk_type == PlonkType::TurboPlonk {
327            return Ok(Self {
328                plonk_type,
329                range_bit_len: None,
330            });
331        }
332        if range_bit_len.is_none() {
333            return Err(ParameterError(
334                "range bit len cannot be none for UltraPlonk".to_string(),
335            ));
336        }
337
338        Ok(Self {
339            plonk_type,
340            range_bit_len,
341        })
342    }
343}
344
345/// A specific Plonk circuit instantiation.
346#[derive(Debug, Clone)]
347pub struct PlonkCircuit<F>
348where
349    F: FftField,
350{
351    /// The number of variables.
352    num_vars: usize,
353
354    /// The gate of each (algebraic) constraint
355    gates: Vec<Box<dyn Gate<F>>>,
356    /// The map from arithmetic/lookup gate wires to variables.
357    wire_variables: [Vec<Variable>; GATE_WIDTH + 2],
358    /// The IO gates for the list of public input variables.
359    pub_input_gate_ids: Vec<GateId>,
360    /// The actual values of variables.
361    witness: Vec<F>,
362
363    /// The permutation over wires.
364    /// Each algebraic gate has 5 wires, i.e., 4 input wires and an output
365    /// wire; each lookup gate has a single wire that maps to a witness to
366    /// be checked over the lookup table. In total there are 6 * n wires
367    /// where n is the (padded) number of arithmetic/lookup gates.  
368    /// We build a permutation over the set of wires so that each set of wires
369    /// that map to the same witness forms a cycle.
370    ///
371    /// Each wire is represented by a pair (`WireId, GateId`) so that the wire
372    /// is in the `GateId`-th arithmetic/lookup gate and `WireId` represents
373    /// the wire type (e.g., 0 represents 1st input wires, 4 represents
374    /// output wires, and 5 represents lookup wires).
375    wire_permutation: Vec<(WireId, GateId)>,
376    /// The extended identity permutation.
377    extended_id_permutation: Vec<F>,
378    /// The number of wire types. 5 for TurboPlonk and 6 for UltraPlonk.
379    num_wire_types: usize,
380
381    /// The evaluation domain for arithmetization of the circuit into various
382    /// polynomials. This is only relevant after the circuit is finalized for
383    /// arithmetization, by default it is a domain with size 1 (only with
384    /// element 0).
385    eval_domain: Radix2EvaluationDomain<F>,
386
387    /// The Plonk parameters.
388    plonk_params: PlonkParams,
389
390    /// The number of key-value table elements being inserted.
391    num_table_elems: usize,
392
393    /// The lookup gates indices for the inserted tables.
394    /// For each inserted table, the 1st value is the start id of the table,
395    /// the 2nd values is the length of the table.
396    table_gate_ids: Vec<(GateId, usize)>,
397}
398
399impl<F: FftField> Default for PlonkCircuit<F> {
400    fn default() -> Self {
401        let params = PlonkParams::init(PlonkType::TurboPlonk, None).unwrap();
402        Self::new(params)
403    }
404}
405
406impl<F: FftField> PlonkCircuit<F> {
407    /// Construct a new circuit with type `plonk_type`.
408    fn new(plonk_params: PlonkParams) -> Self {
409        let zero = F::zero();
410        let one = F::one();
411        let mut circuit = Self {
412            num_vars: 2,
413            witness: vec![zero, one],
414            gates: vec![],
415            // size is `num_wire_types`
416            wire_variables: [vec![], vec![], vec![], vec![], vec![], vec![]],
417            pub_input_gate_ids: vec![],
418
419            wire_permutation: vec![],
420            extended_id_permutation: vec![],
421            num_wire_types: GATE_WIDTH
422                + 1
423                + match plonk_params.plonk_type {
424                    PlonkType::TurboPlonk => 0,
425                    PlonkType::UltraPlonk => 1,
426                },
427            eval_domain: Radix2EvaluationDomain::new(1).unwrap(),
428            plonk_params,
429            num_table_elems: 0,
430            table_gate_ids: vec![],
431        };
432        // Constrain variables `0`/`1` to have value 0/1.
433        circuit.enforce_constant(0, zero).unwrap(); // safe unwrap
434        circuit.enforce_constant(1, one).unwrap(); // safe unwrap
435        circuit
436    }
437
438    /// Construct a new TurboPlonk circuit.
439    pub fn new_turbo_plonk() -> Self {
440        let plonk_params = PlonkParams::init(PlonkType::TurboPlonk, None).unwrap(); // safe unwrap
441        Self::new(plonk_params)
442    }
443
444    /// Construct a new UltraPlonk circuit.
445    pub fn new_ultra_plonk(range_bit_len: usize) -> Self {
446        let plonk_params = PlonkParams::init(PlonkType::UltraPlonk, Some(range_bit_len)).unwrap(); // safe unwrap
447        Self::new(plonk_params)
448    }
449
450    /// Insert a general (algebraic) gate
451    /// * `wire_vars` - wire variables. Each of these variables must be in range
452    /// * `gate` - specific gate to be inserted
453    /// * `returns` - an error if some verification fails
454    pub fn insert_gate(
455        &mut self,
456        wire_vars: &[Variable; GATE_WIDTH + 1],
457        gate: Box<dyn Gate<F>>,
458    ) -> Result<(), CircuitError> {
459        self.check_finalize_flag(false)?;
460
461        for (wire_var, wire_variable) in wire_vars
462            .iter()
463            .zip(self.wire_variables.iter_mut().take(GATE_WIDTH + 1))
464        {
465            wire_variable.push(*wire_var)
466        }
467
468        self.gates.push(gate);
469        Ok(())
470    }
471
472    /// Add a range_check gate that checks whether a variable is in the range
473    /// [0, range_size). Return an error if the circuit does not support
474    /// lookup.
475    pub fn add_range_check_variable(&mut self, var: Variable) -> Result<(), CircuitError> {
476        self.check_plonk_type(PlonkType::UltraPlonk)?;
477        self.check_finalize_flag(false)?;
478        self.check_var_bound(var)?;
479        self.wire_variables[RANGE_WIRE_ID].push(var);
480        Ok(())
481    }
482
483    #[inline]
484    /// Checks if a variable is strictly less than the number of variables.
485    /// This function must be invoked for each gate as this check is not applied
486    /// in the function `insert_gate`
487    /// * `var` - variable to check
488    /// * `returns` - Error if the variable is out of bound (i.e. >= number of
489    ///   variables)
490    pub fn check_var_bound(&self, var: Variable) -> Result<(), CircuitError> {
491        if var >= self.num_vars {
492            return Err(VarIndexOutOfBound(var, self.num_vars));
493        }
494        Ok(())
495    }
496
497    /// Check if a list of variables are strictly less than the number of
498    /// variables.
499    /// * `vars` - variables to check
500    /// * `returns` - Error if the variable is out of bound (i.e. >= number of
501    ///   variables)
502    pub fn check_vars_bound(&self, vars: &[Variable]) -> Result<(), CircuitError> {
503        for &var in vars {
504            self.check_var_bound(var)?
505        }
506        Ok(())
507    }
508
509    /// Change the value of a variable. Only used for testing.
510    // TODO: make this function test only.
511    pub fn witness_mut(&mut self, idx: Variable) -> &mut F {
512        &mut self.witness[idx]
513    }
514
515    /// Get the mutable reference of the inserted table ids.
516    pub(crate) fn table_gate_ids_mut(&mut self) -> &mut Vec<(GateId, usize)> {
517        &mut self.table_gate_ids
518    }
519
520    /// Get the mutable reference of the number of inserted table elements.
521    pub(crate) fn num_table_elems_mut(&mut self) -> &mut usize {
522        &mut self.num_table_elems
523    }
524
525    /// Get the number of inserted table elements.
526    pub(crate) fn num_table_elems(&self) -> usize {
527        self.num_table_elems
528    }
529
530    /// The bit length of UltraPlonk range gates.
531    pub fn range_bit_len(&self) -> Result<usize, CircuitError> {
532        if self.plonk_params.plonk_type != PlonkType::UltraPlonk {
533            return Err(ParameterError(
534                "call range_bit_len() with non-ultraplonk circuit".to_string(),
535            ));
536        }
537        Ok(self.plonk_params.range_bit_len.unwrap()) // safe unwrap
538    }
539
540    /// The range size of UltraPlonk range gates.
541    pub fn range_size(&self) -> Result<usize, CircuitError> {
542        Ok(1 << self.range_bit_len()?)
543    }
544
545    /// creating a `BoolVar` without checking if `v` is a boolean value!
546    /// You should absolutely sure about what you are doing.
547    /// You should normally only use this API if you already enforce `v` to be a
548    /// boolean value using other constraints.
549    pub(crate) fn create_boolean_variable_unchecked(
550        &mut self,
551        a: F,
552    ) -> Result<BoolVar, CircuitError> {
553        let var = self.create_variable(a)?;
554        Ok(BoolVar::new_unchecked(var))
555    }
556}
557
558impl<F: FftField> Circuit<F> for PlonkCircuit<F> {
559    fn num_gates(&self) -> usize {
560        self.gates.len()
561    }
562
563    fn num_vars(&self) -> usize {
564        self.num_vars
565    }
566
567    fn num_inputs(&self) -> usize {
568        self.pub_input_gate_ids.len()
569    }
570
571    fn num_wire_types(&self) -> usize {
572        self.num_wire_types
573    }
574
575    fn public_input(&self) -> Result<Vec<F>, CircuitError> {
576        self.pub_input_gate_ids
577            .iter()
578            .map(|&gate_id| -> Result<F, CircuitError> {
579                let var = self.wire_variables[GATE_WIDTH][gate_id];
580                self.witness(var)
581            })
582            .collect::<Result<Vec<F>, CircuitError>>()
583    }
584
585    fn check_circuit_satisfiability(&self, pub_input: &[F]) -> Result<(), CircuitError> {
586        if pub_input.len() != self.num_inputs() {
587            return Err(PubInputLenMismatch(
588                pub_input.len(),
589                self.pub_input_gate_ids.len(),
590            ));
591        }
592        // Check public I/O gates
593        for (i, gate_id) in self.pub_input_gate_ids.iter().enumerate() {
594            let pi = pub_input[i];
595            self.check_gate(*gate_id, &pi)?;
596        }
597        // Check rest of the gates
598        for gate_id in 0..self.num_gates() {
599            if !self.is_io_gate(gate_id) {
600                let pi = F::zero();
601                self.check_gate(gate_id, &pi)?;
602            }
603        }
604        // Check range/lookup gates if the circuit supports lookup
605        if self.plonk_params.plonk_type == PlonkType::UltraPlonk {
606            // range gates
607            for idx in 0..self.wire_variables[RANGE_WIRE_ID].len() {
608                self.check_range_gate(idx)?
609            }
610            // key-value map lookup gates
611            let mut key_val_table = HashSet::new();
612            key_val_table.insert((F::zero(), F::zero(), F::zero(), F::zero()));
613            let q_lookup_vec = self.q_lookup();
614            let q_dom_sep_vec = self.q_dom_sep();
615            let table_key_vec = self.table_key_vec();
616            let table_dom_sep_vec = self.table_dom_sep_vec();
617            // insert table elements
618            for (gate_id, ((&q_lookup, &table_dom_sep), &table_key)) in q_lookup_vec
619                .iter()
620                .zip(table_dom_sep_vec.iter())
621                .zip(table_key_vec.iter())
622                .enumerate()
623            {
624                if q_lookup != F::zero() {
625                    let val0 = self.witness(self.wire_variable(TABLE_VAL_1_WIRE_ID, gate_id))?;
626                    let val1 = self.witness(self.wire_variable(TABLE_VAL_2_WIRE_ID, gate_id))?;
627                    key_val_table.insert((table_dom_sep, table_key, val0, val1));
628                }
629            }
630            // check lookups
631            for (gate_id, (&q_lookup, &q_dom_sep)) in
632                q_lookup_vec.iter().zip(q_dom_sep_vec.iter()).enumerate()
633            {
634                if q_lookup != F::zero() {
635                    let key = self.witness(self.wire_variable(LOOKUP_KEY_WIRE_ID, gate_id))?;
636                    let val0 = self.witness(self.wire_variable(LOOKUP_VAL_1_WIRE_ID, gate_id))?;
637                    let val1 = self.witness(self.wire_variable(LOOKUP_VAL_2_WIRE_ID, gate_id))?;
638                    if !key_val_table.contains(&(q_dom_sep, key, val0, val1)) {
639                        return Err(GateCheckFailure(
640                            gate_id,
641                            format!(
642                                "Lookup gate failed: ({q_dom_sep}, {key}, {val0}, {val1}) not in the table",
643                            ),
644                        ));
645                    }
646                }
647            }
648        }
649        Ok(())
650    }
651
652    fn create_constant_variable(&mut self, val: F) -> Result<Variable, CircuitError> {
653        let var = self.create_variable(val)?;
654        self.enforce_constant(var, val)?;
655        Ok(var)
656    }
657
658    fn create_variable(&mut self, val: F) -> Result<Variable, CircuitError> {
659        self.check_finalize_flag(false)?;
660        self.witness.push(val);
661        self.num_vars += 1;
662        // the index is from `0` to `num_vars - 1`
663        Ok(self.num_vars - 1)
664    }
665
666    fn create_public_variable(&mut self, val: F) -> Result<Variable, CircuitError> {
667        let var = self.create_variable(val)?;
668        self.set_variable_public(var)?;
669        Ok(var)
670    }
671
672    fn set_variable_public(&mut self, var: Variable) -> Result<(), CircuitError> {
673        self.check_finalize_flag(false)?;
674        self.pub_input_gate_ids.push(self.num_gates());
675
676        // Create an io gate that forces `witness[var] = public_input`.
677        let wire_vars = &[0, 0, 0, 0, var];
678        self.insert_gate(wire_vars, Box::new(IoGate))?;
679        Ok(())
680    }
681
682    /// Default zero variable
683    fn zero(&self) -> Variable {
684        0
685    }
686
687    /// Default one variable
688    fn one(&self) -> Variable {
689        1
690    }
691
692    fn witness(&self, idx: Variable) -> Result<F, CircuitError> {
693        self.check_var_bound(idx)?;
694        Ok(self.witness[idx])
695    }
696
697    fn enforce_constant(&mut self, var: Variable, constant: F) -> Result<(), CircuitError> {
698        self.check_var_bound(var)?;
699
700        let wire_vars = &[0, 0, 0, 0, var];
701        self.insert_gate(wire_vars, Box::new(ConstantGate(constant)))?;
702        Ok(())
703    }
704
705    fn add_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError> {
706        self.check_var_bound(a)?;
707        self.check_var_bound(b)?;
708        self.check_var_bound(c)?;
709
710        let wire_vars = &[a, b, 0, 0, c];
711        self.insert_gate(wire_vars, Box::new(AdditionGate))?;
712        Ok(())
713    }
714
715    fn add(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError> {
716        self.check_var_bound(a)?;
717        self.check_var_bound(b)?;
718        let val = self.witness(a)? + self.witness(b)?;
719        let c = self.create_variable(val)?;
720        self.add_gate(a, b, c)?;
721        Ok(c)
722    }
723
724    fn sub_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError> {
725        self.check_var_bound(a)?;
726        self.check_var_bound(b)?;
727        self.check_var_bound(c)?;
728
729        let wire_vars = &[a, b, 0, 0, c];
730        self.insert_gate(wire_vars, Box::new(SubtractionGate))?;
731        Ok(())
732    }
733
734    fn sub(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError> {
735        self.check_var_bound(a)?;
736        self.check_var_bound(b)?;
737        let val = self.witness(a)? - self.witness(b)?;
738        let c = self.create_variable(val)?;
739        self.sub_gate(a, b, c)?;
740        Ok(c)
741    }
742
743    fn mul_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError> {
744        self.check_var_bound(a)?;
745        self.check_var_bound(b)?;
746        self.check_var_bound(c)?;
747
748        let wire_vars = &[a, b, 0, 0, c];
749        self.insert_gate(wire_vars, Box::new(MultiplicationGate))?;
750        Ok(())
751    }
752
753    fn mul(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError> {
754        self.check_var_bound(a)?;
755        self.check_var_bound(b)?;
756        let val = self.witness(a)? * self.witness(b)?;
757        let c = self.create_variable(val)?;
758        self.mul_gate(a, b, c)?;
759        Ok(c)
760    }
761
762    fn enforce_bool(&mut self, a: Variable) -> Result<(), CircuitError> {
763        self.check_var_bound(a)?;
764
765        let wire_vars = &[a, a, 0, 0, a];
766        self.insert_gate(wire_vars, Box::new(BoolGate))?;
767        Ok(())
768    }
769
770    fn enforce_equal(&mut self, a: Variable, b: Variable) -> Result<(), CircuitError> {
771        self.check_var_bound(a)?;
772        self.check_var_bound(b)?;
773
774        let wire_vars = &[a, b, 0, 0, 0];
775        self.insert_gate(wire_vars, Box::new(EqualityGate))?;
776        Ok(())
777    }
778
779    fn pad_gates(&mut self, n: usize) {
780        // TODO: FIXME
781        // this is interesting...
782        // if we insert a PaddingGate
783        // the padded gate does not have a gate_id, and will bug
784        // when we check circuit satisfiability
785        // we temporarily insert equality gate to by pass the issue
786        let wire_vars = &[self.zero(), self.zero(), 0, 0, 0];
787        for _ in 0..n {
788            self.insert_gate(wire_vars, Box::new(EqualityGate)).unwrap();
789        }
790    }
791
792    // Plookup-related methods
793    //
794    fn support_lookup(&self) -> bool {
795        self.plonk_params.plonk_type == PlonkType::UltraPlonk
796    }
797}
798
799/// Private helper methods
800impl<F: FftField> PlonkCircuit<F> {
801    /// Check correctness of the idx-th range gate. Return an error if the
802    /// circuit does not support lookup.
803    fn check_range_gate(&self, idx: usize) -> Result<(), CircuitError> {
804        self.check_plonk_type(PlonkType::UltraPlonk)?;
805        if idx >= self.wire_variables[RANGE_WIRE_ID].len() {
806            return Err(IndexError);
807        }
808        let range_size = self.range_size()?;
809        if self.witness[self.wire_variables[RANGE_WIRE_ID][idx]] >= F::from(range_size as u32) {
810            return Err(GateCheckFailure(
811                idx,
812                format!(
813                    "Range gate failed: {} >= {}",
814                    self.witness[self.wire_variables[RANGE_WIRE_ID][idx]], range_size
815                ),
816            ));
817        }
818        Ok(())
819    }
820
821    fn is_finalized(&self) -> bool {
822        self.eval_domain.size() != 1
823    }
824
825    /// Re-arrange the order of the gates so that:
826    /// 1. io gates are in the front.
827    /// 2. variable table lookup gate are at the rear so that they do not affect
828    ///    the range gates when merging the lookup tables.
829    ///
830    /// Remember to pad gates before calling the method.
831    fn rearrange_gates(&mut self) -> Result<(), CircuitError> {
832        self.check_finalize_flag(true)?;
833        for (gate_id, io_gate_id) in self.pub_input_gate_ids.iter_mut().enumerate() {
834            if *io_gate_id > gate_id {
835                // Swap gate types
836                self.gates.swap(gate_id, *io_gate_id);
837                // Swap wire variables
838                for wires in &mut self.wire_variables[..GATE_WIDTH + 1] {
839                    wires.swap(gate_id, *io_gate_id);
840                }
841                // Update io gate index
842                *io_gate_id = gate_id;
843            }
844        }
845        if self.support_lookup() {
846            // move lookup gates to the rear, the relative order of the lookup
847            // gates should not change
848            let n = self.eval_domain.size();
849            // be careful that we can't put a lookup gates at the very last
850            // slot.
851            let mut cur_gate_id = n - 2;
852            for &(table_gate_id, table_size) in self.table_gate_ids.iter().rev() {
853                for gate_id in (table_gate_id..table_gate_id + table_size).rev() {
854                    if gate_id < cur_gate_id {
855                        // Swap gate types
856                        self.gates.swap(gate_id, cur_gate_id);
857                        // Swap wire variables
858                        for wires in &mut self.wire_variables[..GATE_WIDTH + 1] {
859                            wires.swap(gate_id, cur_gate_id);
860                        }
861                        cur_gate_id -= 1;
862                    }
863                }
864            }
865        }
866        Ok(())
867    }
868    // use downcast to check whether a gate is of IoGate type
869    fn is_io_gate(&self, gate_id: GateId) -> bool {
870        self.gates[gate_id].as_any().is::<IoGate>()
871    }
872
873    // pad a finalized circuit to match the evaluation domain, prepared for
874    // arithmetization.
875    fn pad(&mut self) -> Result<(), CircuitError> {
876        self.check_finalize_flag(true)?;
877        let n = self.eval_domain.size();
878        for _ in self.num_gates()..n {
879            self.gates.push(Box::new(PaddingGate));
880        }
881        for wire_id in 0..self.num_wire_types() {
882            self.wire_variables[wire_id].resize(n, self.zero());
883        }
884        Ok(())
885    }
886
887    /// Check that the `gate_id`-th gate is satisfied by the circuit's witness
888    /// and the public input value `pub_input`. `gate_id` is guaranteed to
889    /// be in the range. The gate equation:
890    /// qo * wo = pub_input + q_c +
891    ///           q_mul0 * w0 * w1 + q_mul1 * w2 * w3 +
892    ///           q_lc0 * w0 + q_lc1 * w1 + q_lc2 * w2 + q_lc3 * w3 +
893    ///           q_hash0 * w0 + q_hash1 * w1 + q_hash2 * w2 + q_hash3 * w3 +
894    ///           q_ecc * w0 * w1 * w2 * w3 * wo
895    fn check_gate(&self, gate_id: Variable, pub_input: &F) -> Result<(), CircuitError> {
896        // Compute wire values
897
898        let w_vals: Vec<F> = (0..GATE_WIDTH + 1)
899            .map(|i| self.witness[self.wire_variables[i][gate_id]])
900            .collect();
901        // Compute selector values.
902        let q_lc: [F; GATE_WIDTH] = self.gates[gate_id].q_lc();
903        let q_mul: [F; N_MUL_SELECTORS] = self.gates[gate_id].q_mul();
904        let q_hash: [F; GATE_WIDTH] = self.gates[gate_id].q_hash();
905        let q_c = self.gates[gate_id].q_c();
906        let q_o = self.gates[gate_id].q_o();
907        let q_ecc = self.gates[gate_id].q_ecc();
908
909        // Compute the gate output
910        let expected_gate_output = *pub_input
911            + q_lc[0] * w_vals[0]
912            + q_lc[1] * w_vals[1]
913            + q_lc[2] * w_vals[2]
914            + q_lc[3] * w_vals[3]
915            + q_mul[0] * w_vals[0] * w_vals[1]
916            + q_mul[1] * w_vals[2] * w_vals[3]
917            + q_ecc * w_vals[0] * w_vals[1] * w_vals[2] * w_vals[3] * w_vals[4]
918            + q_hash[0] * w_vals[0].pow([5])
919            + q_hash[1] * w_vals[1].pow([5])
920            + q_hash[2] * w_vals[2].pow([5])
921            + q_hash[3] * w_vals[3].pow([5])
922            + q_c;
923        let gate_output = q_o * w_vals[4];
924        if expected_gate_output != gate_output {
925            return Err(
926                GateCheckFailure(
927                    gate_id,
928                    format!(
929                        "gate: {:?}, wire values: {:?}, pub_input: {}, expected_gate_output: {}, gate_output: {}",
930                        self.gates[gate_id],
931                        w_vals,
932                        pub_input,
933                        expected_gate_output,
934                        gate_output
935                    )
936                ));
937        }
938        Ok(())
939    }
940
941    // Compute the permutation over wires.
942    // The circuit is guaranteed to be padded before calling the method.
943    #[inline]
944    fn compute_wire_permutation(&mut self) {
945        assert!(self.is_finalized());
946        let n = self.eval_domain.size();
947        let m = self.num_vars();
948
949        // Compute the mapping from variables to wires.
950        // NOTE: we can use a vector as a map because our variable (the intended
951        // "key" value type of the Map) is sorted and match exactly as the
952        // non-negative integer ranged from 0 to m. Our current implementation
953        // should be slightly faster than using a `HashMap<Variable,
954        // Vec<(WireId, GateId)>>` as we avoid any constant overhead from the
955        // hashmap read/write.
956        let mut variable_wires_map = vec![vec![]; m];
957        for (gate_wire_id, variables) in self
958            .wire_variables
959            .iter()
960            .take(self.num_wire_types())
961            .enumerate()
962        {
963            for (gate_id, &var) in variables.iter().enumerate() {
964                variable_wires_map[var].push((gate_wire_id, gate_id));
965            }
966        }
967
968        // Compute the wire permutation
969        self.wire_permutation = vec![(0usize, 0usize); self.num_wire_types * n];
970        for wires_vec in variable_wires_map.iter_mut() {
971            // The list of wires that map to the same variable forms a cycle.
972            if !wires_vec.is_empty() {
973                // push the first item so that window iterator will visit the
974                // last item paired with the first item, forming a cycle
975                wires_vec.push(wires_vec[0]);
976                for window in wires_vec.windows(2) {
977                    self.wire_permutation[window[0].0 * n + window[0].1] = window[1];
978                }
979                // remove the extra first item pushed at the beginning of the
980                // iterator
981                wires_vec.pop();
982            }
983        }
984    }
985
986    // Check whether the circuit is finalized. Return an error if the finalizing
987    // status is different from the expected status.
988    #[inline]
989    fn check_finalize_flag(&self, expect_finalized: bool) -> Result<(), CircuitError> {
990        if !self.is_finalized() && expect_finalized {
991            return Err(UnfinalizedCircuit);
992        }
993        if self.is_finalized() && !expect_finalized {
994            return Err(ModifyFinalizedCircuit);
995        }
996        Ok(())
997    }
998
999    // Check whether the Plonk type is the expected Plonk type. Return an error
1000    // if not.
1001    #[inline]
1002    fn check_plonk_type(&self, expect_type: PlonkType) -> Result<(), CircuitError> {
1003        if self.plonk_params.plonk_type != expect_type {
1004            return Err(WrongPlonkType);
1005        }
1006        Ok(())
1007    }
1008
1009    // Return the variable that maps to a wire `(i, j)` where i is the wire type
1010    // and j is the gate index. If gate `j` is a padded dummy gate, return zero
1011    // variable.
1012    #[inline]
1013    fn wire_variable(&self, i: WireId, j: GateId) -> Variable {
1014        match j < self.wire_variables[i].len() {
1015            true => self.wire_variables[i][j],
1016            false => self.zero(),
1017        }
1018    }
1019
1020    // getter for all linear combination selector
1021    #[inline]
1022    fn q_lc(&self) -> [Vec<F>; GATE_WIDTH] {
1023        let mut result = [vec![], vec![], vec![], vec![]];
1024        for gate in &self.gates {
1025            let q_lc_vec = gate.q_lc();
1026            result[0].push(q_lc_vec[0]);
1027            result[1].push(q_lc_vec[1]);
1028            result[2].push(q_lc_vec[2]);
1029            result[3].push(q_lc_vec[3]);
1030        }
1031        result
1032    }
1033    // getter for all multiplication selector
1034    #[inline]
1035    fn q_mul(&self) -> [Vec<F>; N_MUL_SELECTORS] {
1036        let mut result = [vec![], vec![]];
1037        for gate in &self.gates {
1038            let q_mul_vec = gate.q_mul();
1039            result[0].push(q_mul_vec[0]);
1040            result[1].push(q_mul_vec[1]);
1041        }
1042        result
1043    }
1044    // getter for all hash selector
1045    #[inline]
1046    fn q_hash(&self) -> [Vec<F>; GATE_WIDTH] {
1047        let mut result = [vec![], vec![], vec![], vec![]];
1048        for gate in &self.gates {
1049            let q_hash_vec = gate.q_hash();
1050            result[0].push(q_hash_vec[0]);
1051            result[1].push(q_hash_vec[1]);
1052            result[2].push(q_hash_vec[2]);
1053            result[3].push(q_hash_vec[3]);
1054        }
1055        result
1056    }
1057    // getter for all output selector
1058    #[inline]
1059    fn q_o(&self) -> Vec<F> {
1060        self.gates.iter().map(|g| g.q_o()).collect()
1061    }
1062    // getter for all constant selector
1063    #[inline]
1064    fn q_c(&self) -> Vec<F> {
1065        self.gates.iter().map(|g| g.q_c()).collect()
1066    }
1067    // getter for all ecc selector
1068    #[inline]
1069    fn q_ecc(&self) -> Vec<F> {
1070        self.gates.iter().map(|g| g.q_ecc()).collect()
1071    }
1072    // getter for all lookup selector
1073    #[inline]
1074    fn q_lookup(&self) -> Vec<F> {
1075        self.gates.iter().map(|g| g.q_lookup()).collect()
1076    }
1077    // getter for all lookup domain separation selector
1078    #[inline]
1079    fn q_dom_sep(&self) -> Vec<F> {
1080        self.gates.iter().map(|g| g.q_dom_sep()).collect()
1081    }
1082    // getter for the vector of table keys
1083    #[inline]
1084    fn table_key_vec(&self) -> Vec<F> {
1085        self.gates.iter().map(|g| g.table_key()).collect()
1086    }
1087    // getter for the vector of table domain separation ids
1088    #[inline]
1089    fn table_dom_sep_vec(&self) -> Vec<F> {
1090        self.gates.iter().map(|g| g.table_dom_sep()).collect()
1091    }
1092    // TODO: (alex) try return reference instead of expensive clone
1093    // getter for all selectors in the following order:
1094    // q_lc, q_mul, q_hash, q_o, q_c, q_ecc, [q_lookup (if support lookup)]
1095    #[inline]
1096    fn all_selectors(&self) -> Vec<Vec<F>> {
1097        let mut selectors = vec![];
1098        self.q_lc()
1099            .as_ref()
1100            .iter()
1101            .chain(self.q_mul().as_ref().iter())
1102            .chain(self.q_hash().as_ref().iter())
1103            .for_each(|s| selectors.push(s.clone()));
1104        selectors.push(self.q_o());
1105        selectors.push(self.q_c());
1106        selectors.push(self.q_ecc());
1107        if self.support_lookup() {
1108            selectors.push(self.q_lookup());
1109        }
1110        selectors
1111    }
1112}
1113
1114/// Private permutation related methods
1115impl<F: PrimeField> PlonkCircuit<F> {
1116    /// Copy constraints: precompute the extended permutation over circuit
1117    /// wires. Refer to Sec 5.2 and Sec 8.1 of https://eprint.iacr.org/2019/953.pdf for more details.
1118    #[inline]
1119    fn compute_extended_id_permutation(&mut self) {
1120        assert!(self.is_finalized());
1121        let n = self.eval_domain.size();
1122
1123        // Compute the extended identity permutation
1124        // id[i*n+j] = k[i] * g^j
1125        let k: Vec<F> = compute_coset_representatives(self.num_wire_types, Some(n));
1126        // Precompute domain elements
1127        let group_elems: Vec<F> = self.eval_domain.elements().collect();
1128        // Compute extended identity permutation
1129        self.extended_id_permutation = vec![F::zero(); self.num_wire_types * n];
1130        for (i, &coset_repr) in k.iter().enumerate() {
1131            for (j, &group_elem) in group_elems.iter().enumerate() {
1132                self.extended_id_permutation[i * n + j] = coset_repr * group_elem;
1133            }
1134        }
1135    }
1136
1137    #[inline]
1138    fn compute_extended_permutation(&self) -> Result<Vec<F>, CircuitError> {
1139        assert!(self.is_finalized());
1140        let n = self.eval_domain.size();
1141
1142        // The extended wire permutation can be computed as
1143        // extended_perm[i] = id[wire_perm[i].into() * n + wire_perm[i].1]
1144        let extended_perm: Vec<F> = self
1145            .wire_permutation
1146            .iter()
1147            .map(|&(wire_id, gate_id)| {
1148                // if permutation value undefined, return 0
1149                if wire_id >= self.num_wire_types {
1150                    F::zero()
1151                } else {
1152                    self.extended_id_permutation[wire_id * n + gate_id]
1153                }
1154            })
1155            .collect();
1156        if extended_perm.len() != self.num_wire_types * n {
1157            return Err(ParameterError(
1158                "Length of the extended permutation vector should be number of gate \
1159                         (including padded dummy gates) * number of wire types"
1160                    .to_string(),
1161            ));
1162        }
1163        Ok(extended_perm)
1164    }
1165}
1166
1167/// Methods for finalizing and merging the circuits.
1168impl<F: PrimeField> PlonkCircuit<F> {
1169    /// Finalize the setup of the circuit before arithmetization.
1170    pub fn finalize_for_arithmetization(&mut self) -> Result<(), CircuitError> {
1171        if self.is_finalized() {
1172            return Ok(());
1173        }
1174        let num_slots_needed = match self.support_lookup() {
1175            false => self.num_gates(),
1176            true => max(
1177                self.num_gates(),
1178                max(self.range_size()?, self.wire_variables[RANGE_WIRE_ID].len())
1179                    + self.num_table_elems()
1180                    + 1,
1181            ), // range gates and lookup gates need to have separate slots
1182        };
1183        self.eval_domain = Radix2EvaluationDomain::new(num_slots_needed)
1184            .ok_or(CircuitError::DomainCreationError)?;
1185        self.pad()?;
1186        self.rearrange_gates()?;
1187        self.compute_wire_permutation();
1188        self.compute_extended_id_permutation();
1189        Ok(())
1190    }
1191
1192    /// Finalize the setup of a mergeable circuit.
1193    /// Two circuits can be merged only if they are with different circuit types
1194    /// The method only supports TurboPlonk circuits.
1195    pub fn finalize_for_mergeable_circuit(
1196        &mut self,
1197        circuit_type: MergeableCircuitType,
1198    ) -> Result<(), CircuitError> {
1199        if self.plonk_params.plonk_type != PlonkType::TurboPlonk {
1200            return Err(WrongPlonkType);
1201        }
1202        self.finalize_for_arithmetization()?;
1203        // double the domain size
1204        let n = self.eval_domain_size()?;
1205        self.eval_domain =
1206            Radix2EvaluationDomain::new(2 * n).ok_or(CircuitError::DomainCreationError)?;
1207        // pad dummy gates/wires in slots [n..2n)
1208        for _ in 0..n {
1209            self.gates.push(Box::new(PaddingGate));
1210        }
1211        for wire_id in 0..self.num_wire_types() {
1212            self.wire_variables[wire_id].resize(2 * n, self.zero());
1213        }
1214        if circuit_type == MergeableCircuitType::TypeA {
1215            // update wire permutation
1216            let mut wire_perm = vec![(self.num_wire_types, 0usize); self.num_wire_types * 2 * n];
1217            for i in 0..self.num_wire_types {
1218                for j in 0..n {
1219                    wire_perm[i * 2 * n + j] = self.wire_permutation[i * n + j];
1220                }
1221            }
1222            self.wire_permutation = wire_perm;
1223        } else {
1224            // reverse the gate indices.
1225            self.gates.reverse();
1226            for wire_id in 0..self.num_wire_types() {
1227                self.wire_variables[wire_id].reverse();
1228            }
1229            for io_gate in self.pub_input_gate_ids.iter_mut() {
1230                *io_gate = 2 * n - 1 - *io_gate;
1231            }
1232            // update wire_permutation
1233            let mut wire_perm = vec![(self.num_wire_types, 0usize); self.num_wire_types * 2 * n];
1234            for i in 0..self.num_wire_types {
1235                for j in 0..n {
1236                    let (wire_id, gate_id) = self.wire_permutation[i * n + j];
1237                    // the new gate index is the reverse of the original gate
1238                    // index
1239                    let gate_id = 2 * n - 1 - gate_id;
1240                    wire_perm[i * 2 * n + 2 * n - 1 - j] = (wire_id, gate_id);
1241                }
1242            }
1243            self.wire_permutation = wire_perm;
1244        }
1245        // need to recompute extended_id_permutation because the domain has
1246        // changed.
1247        self.compute_extended_id_permutation();
1248        Ok(())
1249    }
1250
1251    /// Merge a type A circuit with a type B circuit.
1252    /// Both circuits should have been finalized before.
1253    /// The method only supports TurboPlonk circuits.
1254    #[allow(dead_code)]
1255    pub fn merge(&self, other: &Self) -> Result<Self, CircuitError> {
1256        self.check_finalize_flag(true)?;
1257        other.check_finalize_flag(true)?;
1258        if self.eval_domain_size()? != other.eval_domain_size()? {
1259            return Err(ParameterError(format!(
1260                "cannot merge circuits with different domain sizes: {}, {}",
1261                self.eval_domain_size()?,
1262                other.eval_domain_size()?
1263            )));
1264        }
1265        if self.plonk_params.plonk_type != PlonkType::TurboPlonk
1266            || other.plonk_params.plonk_type != PlonkType::TurboPlonk
1267        {
1268            return Err(ParameterError(
1269                "do not support merging non-TurboPlonk circuits.".to_string(),
1270            ));
1271        }
1272        if self.num_inputs() != other.num_inputs() {
1273            return Err(ParameterError(format!(
1274                "self.num_inputs = {} different from other.num_inputs = {}",
1275                self.num_inputs(),
1276                other.num_inputs()
1277            )));
1278        }
1279        if self.pub_input_gate_ids[0] != 0 {
1280            return Err(ParameterError(
1281                "the first circuit is not type A".to_string(),
1282            ));
1283        }
1284        if other.pub_input_gate_ids[0] != other.eval_domain_size()? - 1 {
1285            return Err(ParameterError(
1286                "the second circuit is not type B".to_string(),
1287            ));
1288        }
1289        let num_vars = self.num_vars + other.num_vars;
1290        let witness: Vec<F> = [self.witness.as_slice(), other.witness.as_slice()].concat();
1291        let pub_input_gate_ids: Vec<usize> = [
1292            self.pub_input_gate_ids.as_slice(),
1293            other.pub_input_gate_ids.as_slice(),
1294        ]
1295        .concat();
1296
1297        // merge gates and wire variables
1298        // the first circuit occupies the first n gates, the second circuit
1299        // occupies the last n gates.
1300        let n = self.eval_domain_size()? / 2;
1301        let mut gates = vec![];
1302        let mut wire_variables = [vec![], vec![], vec![], vec![], vec![], vec![]];
1303        for (j, gate) in self.gates.iter().take(n).enumerate() {
1304            gates.push((*gate).clone());
1305            for (i, wire_vars) in wire_variables
1306                .iter_mut()
1307                .enumerate()
1308                .take(self.num_wire_types)
1309            {
1310                wire_vars.push(self.wire_variable(i, j));
1311            }
1312        }
1313        for (j, gate) in other.gates.iter().skip(n).enumerate() {
1314            gates.push((*gate).clone());
1315            for (i, wire_vars) in wire_variables
1316                .iter_mut()
1317                .enumerate()
1318                .take(self.num_wire_types)
1319            {
1320                wire_vars.push(other.wire_variable(i, n + j) + self.num_vars);
1321            }
1322        }
1323
1324        // merge wire_permutation
1325        let mut wire_permutation = vec![(0usize, 0usize); self.num_wire_types * 2 * n];
1326        for i in 0..self.num_wire_types {
1327            for j in 0..n {
1328                wire_permutation[i * 2 * n + j] = self.wire_permutation[i * 2 * n + j];
1329                wire_permutation[i * 2 * n + n + j] = other.wire_permutation[i * 2 * n + n + j];
1330            }
1331        }
1332
1333        Ok(Self {
1334            num_vars,
1335            witness,
1336            gates,
1337            wire_variables,
1338            pub_input_gate_ids,
1339            wire_permutation,
1340            extended_id_permutation: self.extended_id_permutation.clone(),
1341            num_wire_types: self.num_wire_types,
1342            eval_domain: self.eval_domain,
1343            plonk_params: self.plonk_params,
1344            num_table_elems: 0,
1345            table_gate_ids: vec![],
1346        })
1347    }
1348}
1349
1350impl<F> Arithmetization<F> for PlonkCircuit<F>
1351where
1352    F: PrimeField,
1353{
1354    fn srs_size(&self) -> Result<usize, CircuitError> {
1355        // extra 2 degree for masking polynomial to make snark zero-knowledge
1356        Ok(self.eval_domain_size()? + 2)
1357    }
1358
1359    fn eval_domain_size(&self) -> Result<usize, CircuitError> {
1360        self.check_finalize_flag(true)?;
1361        Ok(self.eval_domain.size())
1362    }
1363
1364    fn compute_selector_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError> {
1365        self.check_finalize_flag(true)?;
1366        let domain = &self.eval_domain;
1367        if domain.size() < self.num_gates() {
1368            return Err(ParameterError(
1369                "Domain size should be bigger than number of constraint".to_string(),
1370            ));
1371        }
1372        // order: (lc, mul, hash, o, c, ecc) as specified in spec
1373        let selector_polys = parallelizable_slice_iter(&self.all_selectors())
1374            .map(|selector| DensePolynomial::from_coefficients_vec(domain.ifft(selector)))
1375            .collect();
1376        Ok(selector_polys)
1377    }
1378
1379    fn compute_extended_permutation_polynomials(
1380        &self,
1381    ) -> Result<Vec<DensePolynomial<F>>, CircuitError> {
1382        self.check_finalize_flag(true)?;
1383        let domain = &self.eval_domain;
1384        let n = domain.size();
1385        let extended_perm = self.compute_extended_permutation()?;
1386
1387        let extended_perm_polys: Vec<DensePolynomial<F>> =
1388            parallelizable_slice_iter(&(0..self.num_wire_types).collect::<Vec<_>>()) // current par_utils only support slice iterator, not range iterator.
1389                .map(|i| {
1390                    DensePolynomial::from_coefficients_vec(
1391                        domain.ifft(&extended_perm[i * n..(i + 1) * n]),
1392                    )
1393                })
1394                .collect();
1395
1396        Ok(extended_perm_polys)
1397    }
1398
1399    fn compute_prod_permutation_polynomial(
1400        &self,
1401        beta: &F,
1402        gamma: &F,
1403    ) -> Result<DensePolynomial<F>, CircuitError> {
1404        self.check_finalize_flag(true)?;
1405        let mut product_vec = vec![F::one()];
1406        let domain = &self.eval_domain;
1407        let n = domain.size();
1408        for j in 0..(n - 1) {
1409            // Nominator
1410            let mut a = F::one();
1411            // Denominator
1412            let mut b = F::one();
1413            for i in 0..self.num_wire_types {
1414                let wire_value = self.witness[self.wire_variable(i, j)];
1415                let tmp = wire_value + gamma;
1416                a *= tmp + *beta * self.extended_id_permutation[i * n + j];
1417                let (perm_i, perm_j) = self.wire_permutation[i * n + j];
1418                b *= tmp + *beta * self.extended_id_permutation[perm_i * n + perm_j];
1419            }
1420            let prev_prod = *product_vec.last().ok_or(CircuitError::IndexError)?;
1421            product_vec.push(prev_prod * a / b);
1422        }
1423        domain.ifft_in_place(&mut product_vec);
1424        Ok(DensePolynomial::from_coefficients_vec(product_vec))
1425    }
1426
1427    fn compute_wire_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError> {
1428        self.check_finalize_flag(true)?;
1429        let domain = &self.eval_domain;
1430        if domain.size() < self.num_gates() {
1431            return Err(ParameterError(format!(
1432                "Domain size {} should be bigger than number of constraint {}",
1433                domain.size(),
1434                self.num_gates()
1435            )));
1436        }
1437        let witness = &self.witness;
1438        let wire_polys: Vec<DensePolynomial<F>> = parallelizable_slice_iter(&self.wire_variables)
1439            .take(self.num_wire_types())
1440            .map(|wire_vars| {
1441                let mut wire_vec: Vec<F> = wire_vars.iter().map(|&var| witness[var]).collect();
1442                domain.ifft_in_place(&mut wire_vec);
1443                DensePolynomial::from_coefficients_vec(wire_vec)
1444            })
1445            .collect();
1446
1447        assert_eq!(wire_polys.len(), self.num_wire_types());
1448        Ok(wire_polys)
1449    }
1450
1451    fn compute_pub_input_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
1452        self.check_finalize_flag(true)?;
1453        let domain = &self.eval_domain;
1454        let mut pub_input_vec = vec![F::zero(); domain.size()];
1455        self.pub_input_gate_ids.iter().for_each(|&io_gate_id| {
1456            let var = self.wire_variables[GATE_WIDTH][io_gate_id];
1457            pub_input_vec[io_gate_id] = self.witness[var];
1458        });
1459        domain.ifft_in_place(&mut pub_input_vec);
1460        Ok(DensePolynomial::from_coefficients_vec(pub_input_vec))
1461    }
1462
1463    // Plookup-related methods
1464    //
1465    fn compute_range_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
1466        let range_table = self.compute_range_table()?;
1467        let domain = &self.eval_domain;
1468        Ok(DensePolynomial::from_coefficients_vec(
1469            domain.ifft(&range_table),
1470        ))
1471    }
1472
1473    fn compute_key_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
1474        self.check_plonk_type(PlonkType::UltraPlonk)?;
1475        self.check_finalize_flag(true)?;
1476        let domain = &self.eval_domain;
1477        Ok(DensePolynomial::from_coefficients_vec(
1478            domain.ifft(&self.table_key_vec()),
1479        ))
1480    }
1481
1482    fn compute_table_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
1483        self.check_plonk_type(PlonkType::UltraPlonk)?;
1484        self.check_finalize_flag(true)?;
1485        let domain = &self.eval_domain;
1486        Ok(DensePolynomial::from_coefficients_vec(
1487            domain.ifft(&self.table_dom_sep_vec()),
1488        ))
1489    }
1490
1491    fn compute_q_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
1492        self.check_plonk_type(PlonkType::UltraPlonk)?;
1493        self.check_finalize_flag(true)?;
1494        let domain = &self.eval_domain;
1495        Ok(DensePolynomial::from_coefficients_vec(
1496            domain.ifft(&self.q_dom_sep()),
1497        ))
1498    }
1499
1500    fn compute_merged_lookup_table(&self, tau: F) -> Result<Vec<F>, CircuitError> {
1501        let range_table = self.compute_range_table()?;
1502        let table_key_vec = self.table_key_vec();
1503        let table_dom_sep_vec = self.table_dom_sep_vec();
1504        let q_lookup_vec = self.q_lookup();
1505
1506        let mut merged_lookup_table = vec![];
1507        for i in 0..self.eval_domain_size()? {
1508            merged_lookup_table.push(self.merged_table_value(
1509                tau,
1510                &range_table,
1511                &table_key_vec,
1512                &table_dom_sep_vec,
1513                &q_lookup_vec,
1514                i,
1515            )?);
1516        }
1517
1518        Ok(merged_lookup_table)
1519    }
1520
1521    fn compute_lookup_prod_polynomial(
1522        &self,
1523        tau: &F,
1524        beta: &F,
1525        gamma: &F,
1526        merged_lookup_table: &[F],
1527        sorted_vec: &[F],
1528    ) -> Result<DensePolynomial<F>, CircuitError> {
1529        self.check_plonk_type(PlonkType::UltraPlonk)?;
1530        self.check_finalize_flag(true)?;
1531        let domain = &self.eval_domain;
1532        let n = domain.size();
1533        if n != self.wire_variables[RANGE_WIRE_ID].len() {
1534            return Err(ParameterError(
1535                "Domain size should match the size of the padded lookup variables vector"
1536                    .to_string(),
1537            ));
1538        }
1539        if n != merged_lookup_table.len() {
1540            return Err(ParameterError(
1541                "Domain size should match the size of the padded lookup table".to_string(),
1542            ));
1543        }
1544        if 2 * n - 1 != sorted_vec.len() {
1545            return Err(ParameterError(
1546                "The sorted vector has wrong length".to_string(),
1547            ));
1548        }
1549
1550        let mut product_vec = vec![F::one()];
1551        let beta_plus_one = F::one() + *beta;
1552        let gamma_mul_beta_plus_one = *gamma * beta_plus_one;
1553        let q_lookup_vec = self.q_lookup();
1554        let q_dom_sep_vec = self.q_dom_sep();
1555        for j in 0..(n - 2) {
1556            // compute merged lookup witness value
1557            let lookup_wire_val =
1558                self.merged_lookup_wire_value(*tau, j, &q_lookup_vec, &q_dom_sep_vec)?;
1559            let table_val = merged_lookup_table[j];
1560            let table_next_val = merged_lookup_table[j + 1];
1561            let h1_val = sorted_vec[j];
1562            let h1_next_val = sorted_vec[j + 1];
1563            let h2_val = sorted_vec[n - 1 + j];
1564            let h2_next_val = sorted_vec[n + j];
1565
1566            // Nominator
1567            let a = beta_plus_one
1568                * (*gamma + lookup_wire_val)
1569                * (gamma_mul_beta_plus_one + table_val + *beta * table_next_val);
1570            // Denominator
1571            let b = (gamma_mul_beta_plus_one + h1_val + *beta * h1_next_val)
1572                * (gamma_mul_beta_plus_one + h2_val + *beta * h2_next_val);
1573
1574            let prev_prod = *product_vec.last().ok_or(CircuitError::IndexError)?;
1575            product_vec.push(prev_prod * a / b);
1576        }
1577        product_vec.push(F::one());
1578        domain.ifft_in_place(&mut product_vec);
1579        Ok(DensePolynomial::from_coefficients_vec(product_vec))
1580    }
1581
1582    fn compute_lookup_sorted_vec_polynomials(
1583        &self,
1584        tau: F,
1585        merged_lookup_table: &[F],
1586    ) -> Result<SortedLookupVecAndPolys<F>, CircuitError> {
1587        self.check_plonk_type(PlonkType::UltraPlonk)?;
1588        self.check_finalize_flag(true)?;
1589        let domain = &self.eval_domain;
1590        let n = domain.size();
1591        if n != self.wire_variables[RANGE_WIRE_ID].len() {
1592            return Err(ParameterError(
1593                "Domain size should match the size of the padded lookup variables vector"
1594                    .to_string(),
1595            ));
1596        }
1597        if n != merged_lookup_table.len() {
1598            return Err(ParameterError(
1599                "Domain size should match the size of the padded lookup table".to_string(),
1600            ));
1601        }
1602        // only the first n-1 variables are for lookup
1603        let mut lookup_map = HashMap::<F, usize>::new();
1604        let q_lookup_vec = self.q_lookup();
1605        let q_dom_sep_vec = self.q_dom_sep();
1606        for i in 0..(n - 1) {
1607            let elem = self.merged_lookup_wire_value(tau, i, &q_lookup_vec, &q_dom_sep_vec)?;
1608            let n_lookups = lookup_map.entry(elem).or_insert(0);
1609            *n_lookups += 1;
1610        }
1611        // merge-sort the lookup vector with the (merged) lookup table
1612        // according to the order of the (merged) lookup table.
1613        let mut sorted_vec = vec![];
1614        for elem in merged_lookup_table.iter() {
1615            if let Some(n_lookup) = lookup_map.get(elem) {
1616                sorted_vec.extend(vec![*elem; 1 + n_lookup]);
1617                lookup_map.remove(elem);
1618            } else {
1619                sorted_vec.push(*elem);
1620            }
1621        }
1622
1623        if sorted_vec.len() != 2 * n - 1 {
1624            return Err(ParameterError("The sorted vector has wrong length, some lookup variables might be outside the table".to_string()));
1625        }
1626        let h1_poly = DensePolynomial::from_coefficients_vec(domain.ifft(&sorted_vec[..n]));
1627        let h2_poly = DensePolynomial::from_coefficients_vec(domain.ifft(&sorted_vec[n - 1..]));
1628        Ok((sorted_vec, h1_poly, h2_poly))
1629    }
1630}
1631
1632/// Private helper methods for arithmetizations.
1633impl<F: PrimeField> PlonkCircuit<F> {
1634    #[inline]
1635    fn compute_range_table(&self) -> Result<Vec<F>, CircuitError> {
1636        self.check_plonk_type(PlonkType::UltraPlonk)?;
1637        self.check_finalize_flag(true)?;
1638        let domain = &self.eval_domain;
1639        let range_size = self.range_size()?;
1640        if domain.size() < range_size {
1641            return Err(ParameterError(format!(
1642                "Domain size {} < range size {}",
1643                domain.size(),
1644                range_size
1645            )));
1646        }
1647        let mut range_table: Vec<F> = (0..range_size).map(|i| F::from(i as u32)).collect();
1648        range_table.resize(domain.size(), F::zero());
1649        Ok(range_table)
1650    }
1651
1652    #[inline]
1653    fn merged_table_value(
1654        &self,
1655        tau: F,
1656        range_table: &[F],
1657        table_key_vec: &[F],
1658        table_dom_sep_vec: &[F],
1659        q_lookup_vec: &[F],
1660        i: usize,
1661    ) -> Result<F, CircuitError> {
1662        let range_val = range_table[i];
1663        let key_val = table_key_vec[i];
1664        let dom_sep_val = table_dom_sep_vec[i];
1665        let q_lookup_val = q_lookup_vec[i];
1666        let table_val_1 = self.witness(self.wire_variable(TABLE_VAL_1_WIRE_ID, i))?;
1667        let table_val_2 = self.witness(self.wire_variable(TABLE_VAL_2_WIRE_ID, i))?;
1668        Ok(range_val
1669            + q_lookup_val
1670                * tau
1671                * (dom_sep_val + tau * (key_val + tau * (table_val_1 + tau * table_val_2))))
1672    }
1673
1674    #[inline]
1675    fn merged_lookup_wire_value(
1676        &self,
1677        tau: F,
1678        i: usize,
1679        q_lookup_vec: &[F],
1680        q_dom_sep_vec: &[F],
1681    ) -> Result<F, CircuitError> {
1682        let w_range_val = self.witness(self.wire_variable(RANGE_WIRE_ID, i))?;
1683        let lookup_key = self.witness(self.wire_variable(LOOKUP_KEY_WIRE_ID, i))?;
1684        let lookup_val_1 = self.witness(self.wire_variable(LOOKUP_VAL_1_WIRE_ID, i))?;
1685        let lookup_val_2 = self.witness(self.wire_variable(LOOKUP_VAL_2_WIRE_ID, i))?;
1686        let q_lookup_val = q_lookup_vec[i];
1687        let q_dom_sep_val = q_dom_sep_vec[i];
1688        Ok(w_range_val
1689            + q_lookup_val
1690                * tau
1691                * (q_dom_sep_val + tau * (lookup_key + tau * (lookup_val_1 + tau * lookup_val_2))))
1692    }
1693}
1694
1695#[cfg(test)]
1696pub(crate) mod test {
1697    use super::{Arithmetization, Circuit, PlonkCircuit};
1698    use crate::{constants::compute_coset_representatives, CircuitError};
1699    use ark_bls12_377::Fq as Fq377;
1700    use ark_ed_on_bls12_377::Fq as FqEd377;
1701    use ark_ed_on_bls12_381::Fq as FqEd381;
1702    use ark_ed_on_bn254::Fq as FqEd254;
1703    use ark_ff::PrimeField;
1704    use ark_poly::{domain::Radix2EvaluationDomain, univariate::DensePolynomial, EvaluationDomain};
1705    use ark_std::{vec, vec::Vec};
1706    use jf_utils::test_rng;
1707
1708    #[test]
1709    fn test_circuit_trait() -> Result<(), CircuitError> {
1710        test_circuit_trait_helper::<FqEd254>()?;
1711        test_circuit_trait_helper::<FqEd377>()?;
1712        test_circuit_trait_helper::<FqEd381>()?;
1713        test_circuit_trait_helper::<Fq377>()
1714    }
1715
1716    fn test_circuit_trait_helper<F: PrimeField>() -> Result<(), CircuitError> {
1717        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1718        // Create secret variables.
1719        let a = circuit.create_variable(F::from(3u32))?;
1720        let b = circuit.create_variable(F::from(1u32))?;
1721        // Constant gate: a = 3.
1722        circuit.enforce_constant(a, F::from(3u32))?;
1723        // Bool gate: b is bool.
1724        circuit.enforce_bool(b)?;
1725        // Addition gate: c = a + b = 4.
1726        let c = circuit.add(a, b)?;
1727        // Subtraction gate: d = a - b = 2.
1728        let d = circuit.sub(a, b)?;
1729        // Multiplication gate: e = c * d = 8
1730        let e = circuit.mul(c, d)?;
1731        // Create public variables.
1732        let f = circuit.create_public_variable(F::from(8u32))?;
1733        // Equality gate: e = f = 8
1734        circuit.enforce_equal(e, f)?;
1735
1736        // Check the number of gates:
1737        // 2 constant gates for default 0/1, 6 arithmetic gates, 1 io gate.
1738        assert_eq!(circuit.num_gates(), 9);
1739        // Check the number of variables:
1740        assert_eq!(circuit.num_vars(), 8);
1741        // Check the number of public inputs:
1742        assert_eq!(circuit.num_inputs(), 1);
1743
1744        // Check circuit satisfiability
1745        let pub_input = &[F::from(8u32)];
1746        let verify = circuit.check_circuit_satisfiability(pub_input);
1747        assert!(verify.is_ok(), "{:?}", verify.unwrap_err());
1748        let bad_pub_input = &[F::from(0u32)];
1749        assert!(circuit.check_circuit_satisfiability(bad_pub_input).is_err());
1750        // Wrong public input length
1751        let bad_pub_input = &[F::from(8u32), F::from(8u32)];
1752        assert!(circuit.check_circuit_satisfiability(bad_pub_input).is_err());
1753
1754        Ok(())
1755    }
1756
1757    #[test]
1758    fn test_add() -> Result<(), CircuitError> {
1759        test_add_helper::<FqEd254>()?;
1760        test_add_helper::<FqEd377>()?;
1761        test_add_helper::<FqEd381>()?;
1762        test_add_helper::<Fq377>()
1763    }
1764
1765    fn test_add_helper<F: PrimeField>() -> Result<(), CircuitError> {
1766        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1767        let a = circuit.create_variable(F::from(3u32))?;
1768        let b = circuit.create_variable(F::from(1u32))?;
1769        let c = circuit.add(a, b)?;
1770
1771        // Check circuits.
1772        assert_eq!(circuit.witness(c)?, F::from(4u32));
1773        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1774        *circuit.witness_mut(c) = F::from(1u32);
1775        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1776
1777        // Check variable out of bound error.
1778        assert!(circuit.add(circuit.num_vars(), a).is_err());
1779
1780        Ok(())
1781    }
1782
1783    #[test]
1784    fn test_sub() -> Result<(), CircuitError> {
1785        test_sub_helper::<FqEd254>()?;
1786        test_sub_helper::<FqEd377>()?;
1787        test_sub_helper::<FqEd381>()?;
1788        test_sub_helper::<Fq377>()
1789    }
1790
1791    fn test_sub_helper<F: PrimeField>() -> Result<(), CircuitError> {
1792        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1793        let a = circuit.create_variable(F::from(3u32))?;
1794        let b = circuit.create_variable(F::from(1u32))?;
1795        let c = circuit.sub(a, b)?;
1796
1797        // Check circuits.
1798        assert_eq!(circuit.witness(c)?, F::from(2u32));
1799        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1800        *circuit.witness_mut(c) = F::from(1u32);
1801        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1802
1803        // Check variable out of bound error.
1804        assert!(circuit.sub(circuit.num_vars(), a).is_err());
1805
1806        Ok(())
1807    }
1808
1809    #[test]
1810    fn test_mul() -> Result<(), CircuitError> {
1811        test_mul_helper::<FqEd254>()?;
1812        test_mul_helper::<FqEd377>()?;
1813        test_mul_helper::<FqEd381>()?;
1814        test_mul_helper::<Fq377>()
1815    }
1816
1817    fn test_mul_helper<F: PrimeField>() -> Result<(), CircuitError> {
1818        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1819        let a = circuit.create_variable(F::from(3u32))?;
1820        let b = circuit.create_variable(F::from(2u32))?;
1821        let c = circuit.mul(a, b)?;
1822
1823        // Check circuits.
1824        assert_eq!(circuit.witness(c)?, F::from(6u32));
1825        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1826        *circuit.witness_mut(c) = F::from(1u32);
1827        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1828
1829        // Check variable out of bound error.
1830        assert!(circuit.mul(circuit.num_vars(), a).is_err());
1831
1832        Ok(())
1833    }
1834
1835    #[test]
1836    fn test_equal_gate() -> Result<(), CircuitError> {
1837        test_equal_gate_helper::<FqEd254>()?;
1838        test_equal_gate_helper::<FqEd377>()?;
1839        test_equal_gate_helper::<FqEd381>()?;
1840        test_equal_gate_helper::<Fq377>()
1841    }
1842    fn test_equal_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
1843        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1844        let a = circuit.create_variable(F::from(3u32))?;
1845        let b = circuit.create_variable(F::from(3u32))?;
1846        circuit.enforce_equal(a, b)?;
1847
1848        // Check circuits.
1849        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1850        *circuit.witness_mut(b) = F::from(1u32);
1851        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1852
1853        // Check variable out of bound error.
1854        assert!(circuit.enforce_equal(circuit.num_vars(), a).is_err());
1855
1856        Ok(())
1857    }
1858
1859    #[test]
1860    fn test_bool() -> Result<(), CircuitError> {
1861        test_bool_helper::<FqEd254>()?;
1862        test_bool_helper::<FqEd377>()?;
1863        test_bool_helper::<FqEd381>()?;
1864        test_bool_helper::<Fq377>()
1865    }
1866
1867    fn test_bool_helper<F: PrimeField>() -> Result<(), CircuitError> {
1868        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1869        let a = circuit.create_variable(F::from(0u32))?;
1870        circuit.enforce_bool(a)?;
1871
1872        // Check circuits.
1873        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1874        *circuit.witness_mut(a) = F::from(2u32);
1875        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1876
1877        // Check variable out of bound error.
1878        assert!(circuit.enforce_bool(circuit.num_vars()).is_err());
1879
1880        Ok(())
1881    }
1882
1883    #[test]
1884    fn test_constant() -> Result<(), CircuitError> {
1885        test_constant_helper::<FqEd254>()?;
1886        test_constant_helper::<FqEd377>()?;
1887        test_constant_helper::<FqEd381>()?;
1888        test_constant_helper::<Fq377>()
1889    }
1890    fn test_constant_helper<F: PrimeField>() -> Result<(), CircuitError> {
1891        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1892        let a = circuit.create_variable(F::from(10u32))?;
1893        circuit.enforce_constant(a, F::from(10u32))?;
1894
1895        // Check circuits.
1896        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1897        *circuit.witness_mut(a) = F::from(2u32);
1898        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1899
1900        // Check variable out of bound error.
1901        assert!(circuit
1902            .enforce_constant(circuit.num_vars(), F::from(0u32))
1903            .is_err());
1904
1905        Ok(())
1906    }
1907
1908    #[test]
1909    fn test_io_gate() -> Result<(), CircuitError> {
1910        test_io_gate_helper::<FqEd254>()?;
1911        test_io_gate_helper::<FqEd377>()?;
1912        test_io_gate_helper::<FqEd381>()?;
1913        test_io_gate_helper::<Fq377>()
1914    }
1915
1916    fn test_io_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
1917        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
1918        let b = circuit.create_variable(F::from(0u32))?;
1919        let a = circuit.create_public_variable(F::from(1u32))?;
1920        circuit.enforce_bool(a)?;
1921        circuit.enforce_bool(b)?;
1922        circuit.set_variable_public(b)?;
1923
1924        // Different valid public inputs should all pass the circuit check.
1925        assert!(circuit
1926            .check_circuit_satisfiability(&[F::from(1u32), F::from(0u32)])
1927            .is_ok());
1928        *circuit.witness_mut(a) = F::from(0u32);
1929        assert!(circuit
1930            .check_circuit_satisfiability(&[F::from(0u32), F::from(0u32)])
1931            .is_ok());
1932        *circuit.witness_mut(b) = F::from(1u32);
1933        assert!(circuit
1934            .check_circuit_satisfiability(&[F::from(0u32), F::from(1u32)])
1935            .is_ok());
1936
1937        // Invalid public inputs should fail the circuit check.
1938        assert!(circuit
1939            .check_circuit_satisfiability(&[F::from(2u32), F::from(1u32)])
1940            .is_err());
1941        *circuit.witness_mut(a) = F::from(2u32);
1942        assert!(circuit
1943            .check_circuit_satisfiability(&[F::from(2u32), F::from(1u32)])
1944            .is_err());
1945        *circuit.witness_mut(a) = F::from(0u32);
1946        assert!(circuit
1947            .check_circuit_satisfiability(&[F::from(0u32), F::from(2u32)])
1948            .is_err());
1949        *circuit.witness_mut(b) = F::from(2u32);
1950        assert!(circuit
1951            .check_circuit_satisfiability(&[F::from(0u32), F::from(2u32)])
1952            .is_err());
1953
1954        Ok(())
1955    }
1956
1957    #[test]
1958    fn test_io_gate_multi_inputs() -> Result<(), CircuitError> {
1959        test_io_gate_multi_inputs_helper::<FqEd254>()?;
1960        test_io_gate_multi_inputs_helper::<FqEd377>()?;
1961        test_io_gate_multi_inputs_helper::<FqEd381>()?;
1962        test_io_gate_multi_inputs_helper::<Fq377>()
1963    }
1964    fn test_io_gate_multi_inputs_helper<F: PrimeField>() -> Result<(), CircuitError> {
1965        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
1966        let a = circuit.create_public_variable(F::from(1u32))?;
1967        let b = circuit.create_public_variable(F::from(2u32))?;
1968        let c = circuit.create_public_variable(F::from(3u32))?;
1969        circuit.add_gate(a, b, c)?;
1970
1971        // Good path
1972        assert!(circuit
1973            .check_circuit_satisfiability(&[F::from(1u32), F::from(2u32), F::from(3u32)])
1974            .is_ok());
1975        // The circuit check should fail given a public input with wrong order.
1976        assert!(circuit
1977            .check_circuit_satisfiability(&[F::from(2u32), F::from(1u32), F::from(3u32)])
1978            .is_err());
1979        // A different valid public input should pass the circuit check.
1980        *circuit.witness_mut(a) = F::from(4u32);
1981        *circuit.witness_mut(b) = F::from(8u32);
1982        *circuit.witness_mut(c) = F::from(12u32);
1983        assert!(circuit
1984            .check_circuit_satisfiability(&[F::from(4u32), F::from(8u32), F::from(12u32)])
1985            .is_ok());
1986        // An invalid public input should fail the circuit check.
1987        *circuit.witness_mut(a) = F::from(2u32);
1988        assert!(circuit
1989            .check_circuit_satisfiability(&[F::from(2u32), F::from(8u32), F::from(12u32)])
1990            .is_err());
1991
1992        Ok(())
1993    }
1994
1995    fn create_turbo_plonk_instance<F: PrimeField>(
1996    ) -> Result<(PlonkCircuit<F>, Vec<F>), CircuitError> {
1997        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
1998        let a = circuit.create_variable(F::from(3u32))?;
1999        let b = circuit.create_public_variable(F::from(1u32))?;
2000        circuit.enforce_constant(a, F::from(3u32))?;
2001        circuit.enforce_bool(b)?;
2002        let c = circuit.add(a, b)?;
2003        let d = circuit.sub(a, b)?;
2004        let e = circuit.mul(c, d)?;
2005        let f = circuit.create_public_variable(F::from(8u32))?;
2006        circuit.enforce_equal(e, f)?;
2007
2008        Ok((circuit, vec![F::from(1u32), F::from(8u32)]))
2009    }
2010
2011    fn create_ultra_plonk_instance<F: PrimeField>(
2012    ) -> Result<(PlonkCircuit<F>, Vec<F>), CircuitError> {
2013        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(4);
2014        let a = circuit.create_variable(F::from(3u32))?;
2015        let b = circuit.create_public_variable(F::from(1u32))?;
2016        circuit.enforce_constant(a, F::from(3u32))?;
2017        circuit.enforce_bool(b)?;
2018        let c = circuit.add(a, b)?;
2019        let d = circuit.sub(a, b)?;
2020        let e = circuit.mul(c, d)?;
2021        let f = circuit.create_public_variable(F::from(8u32))?;
2022        circuit.enforce_equal(e, f)?;
2023
2024        // Add range gates
2025        circuit.add_range_check_variable(b)?;
2026        circuit.add_range_check_variable(c)?;
2027        circuit.add_range_check_variable(e)?;
2028        circuit.add_range_check_variable(f)?;
2029        circuit.add_range_check_variable(circuit.zero())?;
2030
2031        // Add variable table lookup gates
2032        // table = [(3,1), (4,2), (8,8)]
2033        let table_vars = [(a, b), (c, d), (e, f)];
2034        // lookup_witness = [(0, 3, 1), (2, 8, 8)]
2035        let x = circuit.create_variable(F::from(3u8))?;
2036        let y = circuit.create_variable(F::from(8u8))?;
2037        let key1 = circuit.create_variable(F::from(2u8))?;
2038        let lookup_vars = [(circuit.zero(), x, circuit.one()), (key1, y, y)];
2039        circuit.create_table_and_lookup_variables(&lookup_vars, &table_vars)?;
2040
2041        Ok((circuit, vec![F::from(1u32), F::from(8u32)]))
2042    }
2043
2044    /// Tests related to permutations
2045    #[test]
2046    fn test_compute_extended_permutation() -> Result<(), CircuitError> {
2047        test_compute_extended_permutation_helper::<FqEd254>()?;
2048        test_compute_extended_permutation_helper::<FqEd377>()?;
2049        test_compute_extended_permutation_helper::<FqEd381>()?;
2050        test_compute_extended_permutation_helper::<Fq377>()
2051    }
2052
2053    fn test_compute_extended_permutation_helper<F: PrimeField>() -> Result<(), CircuitError> {
2054        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
2055        let a = circuit.create_variable(F::from(2u32))?;
2056        let b = circuit.create_public_variable(F::from(3u32))?;
2057        let c = circuit.add(a, b)?;
2058        let d = circuit.add(circuit.one(), a)?;
2059        let _ = circuit.mul(c, d)?;
2060
2061        // Create a UltraPlonk instance
2062        let (mut circuit, _) = create_ultra_plonk_instance::<F>()?;
2063        check_wire_permutation_and_extended_id_permutation(&mut circuit)?;
2064
2065        Ok(())
2066    }
2067
2068    fn check_wire_permutation_and_extended_id_permutation<F: PrimeField>(
2069        circuit: &mut PlonkCircuit<F>,
2070    ) -> Result<(), CircuitError> {
2071        let domain = Radix2EvaluationDomain::<F>::new(circuit.num_gates())
2072            .ok_or(CircuitError::DomainCreationError)?;
2073        let n = domain.size();
2074        circuit.eval_domain = domain;
2075
2076        // Check wire permutation's correctness
2077        circuit.pad()?;
2078        circuit.compute_wire_permutation();
2079        let mut visit_wire = vec![false; circuit.num_wire_types * n];
2080        let mut visit_variable = vec![false; circuit.num_vars()];
2081
2082        for i in 0..circuit.num_wire_types {
2083            for j in 0..n {
2084                if visit_wire[i * n + j] {
2085                    continue;
2086                }
2087                // Compute the cycle's variable.
2088                let cycle_var = circuit.wire_variable(i, j);
2089                // The variable shouldn't have been marked yet.
2090                assert!(!visit_variable[cycle_var]);
2091                visit_variable[cycle_var] = true;
2092
2093                // Visit the cycle.
2094                let mut wire_id = i;
2095                let mut gate_id = j;
2096                visit_wire[i * n + j] = true;
2097                loop {
2098                    let (next_wire_id, next_gate_id) =
2099                        circuit.wire_permutation[wire_id * n + gate_id];
2100                    // Break the loop if back to the starting wire.
2101                    if next_wire_id == i && next_gate_id == j {
2102                        break;
2103                    }
2104                    let next_var = circuit.wire_variable(next_wire_id, next_gate_id);
2105                    // The adjacent wire's variable should be the same.
2106                    assert_eq!(cycle_var, next_var);
2107                    // The adjacent wire shouldn't have been marked yet.
2108                    assert!(!visit_wire[next_wire_id * n + next_gate_id]);
2109                    visit_wire[next_wire_id * n + next_gate_id] = true;
2110                    wire_id = next_wire_id;
2111                    gate_id = next_gate_id;
2112                }
2113            }
2114        }
2115
2116        // Check the correctness of the extended id permutation
2117        circuit.compute_extended_id_permutation();
2118        // Compute quadratic non-residues and group elements.
2119        let k: Vec<F> = compute_coset_representatives(circuit.num_wire_types, Some(n));
2120        let group_elems: Vec<F> = domain.elements().collect();
2121        (0..circuit.num_wire_types).for_each(|i| {
2122            (0..n).for_each(|j| {
2123                assert_eq!(
2124                    k[i] * group_elems[j],
2125                    circuit.extended_id_permutation[i * n + j]
2126                )
2127            });
2128        });
2129
2130        Ok(())
2131    }
2132
2133    // Test flags
2134    //
2135
2136    #[test]
2137    fn test_ultra_plonk_flag() -> Result<(), CircuitError> {
2138        test_ultra_plonk_flag_helper::<FqEd254>()?;
2139        test_ultra_plonk_flag_helper::<FqEd377>()?;
2140        test_ultra_plonk_flag_helper::<FqEd381>()?;
2141        test_ultra_plonk_flag_helper::<Fq377>()
2142    }
2143
2144    fn test_ultra_plonk_flag_helper<F: PrimeField>() -> Result<(), CircuitError> {
2145        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
2146        // Check that below methods return errors when not in UltraPlonk mode.
2147        assert!(circuit.add_range_check_variable(0).is_err());
2148        circuit.finalize_for_arithmetization()?;
2149        assert!(circuit.compute_range_table_polynomial().is_err());
2150        assert!(circuit.compute_key_table_polynomial().is_err());
2151        assert!(circuit.compute_merged_lookup_table(F::one()).is_err());
2152        assert!(circuit
2153            .compute_lookup_sorted_vec_polynomials(F::one(), &[])
2154            .is_err());
2155        assert!(circuit
2156            .compute_lookup_prod_polynomial(&F::one(), &F::one(), &F::one(), &[], &[])
2157            .is_err());
2158
2159        Ok(())
2160    }
2161
2162    #[test]
2163    fn test_finalized_flag() -> Result<(), CircuitError> {
2164        test_finalized_flag_helper::<FqEd254>()?;
2165        test_finalized_flag_helper::<FqEd377>()?;
2166        test_finalized_flag_helper::<FqEd381>()?;
2167        test_finalized_flag_helper::<Fq377>()
2168    }
2169
2170    fn test_finalized_flag_helper<F: PrimeField>() -> Result<(), CircuitError> {
2171        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
2172        // Should not call arithmetization methods before finalizing the
2173        // circuit.
2174        assert!(circuit.compute_selector_polynomials().is_err());
2175        assert!(circuit.compute_extended_permutation_polynomials().is_err());
2176        assert!(circuit.compute_pub_input_polynomial().is_err());
2177        assert!(circuit.compute_wire_polynomials().is_err());
2178        assert!(circuit
2179            .compute_prod_permutation_polynomial(&F::one(), &F::one())
2180            .is_err());
2181
2182        // Should not insert gates or add variables after finalizing the
2183        // circuit.
2184        circuit.finalize_for_arithmetization()?;
2185        assert!(circuit.create_variable(F::one()).is_err());
2186        assert!(circuit.create_public_variable(F::one()).is_err());
2187        assert!(circuit.add_gate(0, 0, 0).is_err());
2188        assert!(circuit.sub_gate(0, 0, 0).is_err());
2189        assert!(circuit.mul_gate(0, 0, 0).is_err());
2190        assert!(circuit.enforce_constant(0, F::one()).is_err());
2191        assert!(circuit.enforce_bool(0).is_err());
2192        assert!(circuit.enforce_equal(0, 0).is_err());
2193
2194        Ok(())
2195    }
2196
2197    #[test]
2198
2199    fn test_ultra_plonk_finalized_flag() -> Result<(), CircuitError> {
2200        test_ultra_plonk_finalized_flag_helper::<FqEd254>()?;
2201        test_ultra_plonk_finalized_flag_helper::<FqEd377>()?;
2202        test_ultra_plonk_finalized_flag_helper::<FqEd381>()?;
2203        test_ultra_plonk_finalized_flag_helper::<Fq377>()
2204    }
2205
2206    fn test_ultra_plonk_finalized_flag_helper<F: PrimeField>() -> Result<(), CircuitError> {
2207        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(1);
2208        // Should not call arithmetization methods before finalizing the
2209        // circuit.
2210        assert!(circuit.compute_selector_polynomials().is_err());
2211        assert!(circuit.compute_extended_permutation_polynomials().is_err());
2212        assert!(circuit.compute_pub_input_polynomial().is_err());
2213        assert!(circuit.compute_wire_polynomials().is_err());
2214        assert!(circuit
2215            .compute_prod_permutation_polynomial(&F::one(), &F::one())
2216            .is_err());
2217        assert!(circuit.compute_range_table_polynomial().is_err());
2218        assert!(circuit.compute_key_table_polynomial().is_err());
2219        assert!(circuit.compute_merged_lookup_table(F::one()).is_err());
2220        assert!(circuit
2221            .compute_lookup_sorted_vec_polynomials(F::one(), &[])
2222            .is_err());
2223        assert!(circuit
2224            .compute_lookup_prod_polynomial(&F::one(), &F::one(), &F::one(), &[], &[])
2225            .is_err());
2226
2227        // Should not insert gates or add variables after finalizing the
2228        // circuit.
2229        circuit.finalize_for_arithmetization()?;
2230        assert!(circuit.create_variable(F::one()).is_err());
2231        assert!(circuit.create_public_variable(F::one()).is_err());
2232        assert!(circuit.add_gate(0, 0, 0).is_err());
2233        assert!(circuit.sub_gate(0, 0, 0).is_err());
2234        assert!(circuit.mul_gate(0, 0, 0).is_err());
2235        assert!(circuit.enforce_constant(0, F::one()).is_err());
2236        assert!(circuit.enforce_bool(0).is_err());
2237        assert!(circuit.enforce_equal(0, 0).is_err());
2238        // Plookup-related methods
2239        assert!(circuit.add_range_check_variable(0).is_err());
2240
2241        Ok(())
2242    }
2243
2244    // Test arithmetizations
2245    //
2246    #[test]
2247    fn test_arithmetization() -> Result<(), CircuitError> {
2248        test_arithmetization_helper::<FqEd254>()?;
2249        test_arithmetization_helper::<FqEd377>()?;
2250        test_arithmetization_helper::<FqEd381>()?;
2251        test_arithmetization_helper::<Fq377>()
2252    }
2253
2254    fn test_arithmetization_helper<F: PrimeField>() -> Result<(), CircuitError> {
2255        // Create the TurboPlonk circuit
2256        let (mut circuit, pub_inputs) = create_turbo_plonk_instance::<F>()?;
2257        circuit.finalize_for_arithmetization()?;
2258        test_arithmetization_for_circuit(circuit, pub_inputs)?;
2259
2260        // Create the UltraPlonk circuit
2261        let (mut circuit, pub_inputs) = create_ultra_plonk_instance::<F>()?;
2262        circuit.finalize_for_arithmetization()?;
2263        test_arithmetization_for_lookup_circuit(&circuit)?;
2264        test_arithmetization_for_circuit(circuit, pub_inputs)?;
2265
2266        Ok(())
2267    }
2268
2269    // Check that the polynomial `poly` is consistent with the evaluations
2270    // `evals` over the domain.
2271    fn check_polynomial<F: PrimeField>(poly: &DensePolynomial<F>, evals: &[F]) {
2272        let domain = Radix2EvaluationDomain::new(evals.len()).unwrap();
2273        let poly_eval = poly.evaluate_over_domain_by_ref(domain);
2274        for (&a, &b) in poly_eval.evals.iter().zip(evals.iter()) {
2275            assert_eq!(a, b);
2276        }
2277    }
2278
2279    pub(crate) fn test_arithmetization_for_lookup_circuit<F: PrimeField>(
2280        circuit: &PlonkCircuit<F>,
2281    ) -> Result<(), CircuitError> {
2282        let n = circuit.eval_domain.size();
2283
2284        // Check range table polynomial
2285        let range_table_poly = circuit.compute_range_table_polynomial()?;
2286        let range_table = circuit.compute_range_table()?;
2287        check_polynomial(&range_table_poly, &range_table);
2288
2289        // Check key table polynomial
2290        let key_table_poly = circuit.compute_key_table_polynomial()?;
2291        let key_table = circuit.table_key_vec();
2292        check_polynomial(&key_table_poly, &key_table);
2293
2294        // Check sorted vector polynomials
2295        let rng = &mut test_rng();
2296        let tau = F::rand(rng);
2297        let merged_lookup_table = circuit.compute_merged_lookup_table(tau)?;
2298        let (sorted_vec, h1_poly, h2_poly) =
2299            circuit.compute_lookup_sorted_vec_polynomials(tau, &merged_lookup_table)?;
2300        assert_eq!(sorted_vec.len(), 2 * n - 1);
2301        // check that sorted_vec is sorted according to the order of
2302        // `merged_lookup_table`.
2303        assert_eq!(sorted_vec[0], merged_lookup_table[0]);
2304        let mut ptr = 1;
2305        for slice in sorted_vec.windows(2) {
2306            // find the next different value in `sorted_vec`
2307            if slice[0] == slice[1] {
2308                continue;
2309            }
2310            // find the next different value in `merged_lookup_table`
2311            while ptr < n && merged_lookup_table[ptr] == merged_lookup_table[ptr - 1] {
2312                ptr += 1;
2313            }
2314            assert!(ptr < n);
2315            assert_eq!(merged_lookup_table[ptr], slice[1]);
2316            ptr += 1;
2317        }
2318        // assert that the elements in `merged_lookup_table` have been exhausted
2319        assert_eq!(ptr, n);
2320
2321        check_polynomial(&h1_poly, &sorted_vec[..n]);
2322        check_polynomial(&h2_poly, &sorted_vec[n - 1..]);
2323
2324        // Check product accumulation polynomial
2325        let beta = F::rand(rng);
2326        let gamma = F::rand(rng);
2327        let prod_poly = circuit.compute_lookup_prod_polynomial(
2328            &tau,
2329            &beta,
2330            &gamma,
2331            &merged_lookup_table,
2332            &sorted_vec,
2333        )?;
2334        let mut prod_evals = vec![F::one()];
2335        let one_plus_beta = F::one() + beta;
2336        let gamma_mul_one_plus_beta = gamma * one_plus_beta;
2337        let q_lookup_vec = circuit.q_lookup();
2338        let q_dom_sep = circuit.q_dom_sep();
2339        for j in 0..(n - 2) {
2340            let lookup_wire_val =
2341                circuit.merged_lookup_wire_value(tau, j, &q_lookup_vec, &q_dom_sep)?;
2342            let table_val = merged_lookup_table[j];
2343            let table_next_val = merged_lookup_table[j + 1];
2344            let h1_val = sorted_vec[j];
2345            let h1_next_val = sorted_vec[j + 1];
2346            let h2_val = sorted_vec[n - 1 + j];
2347            let h2_next_val = sorted_vec[n + j];
2348
2349            // Nominator
2350            let a = one_plus_beta
2351                * (gamma + lookup_wire_val)
2352                * (gamma_mul_one_plus_beta + table_val + beta * table_next_val);
2353            // Denominator
2354            let b = (gamma_mul_one_plus_beta + h1_val + beta * h1_next_val)
2355                * (gamma_mul_one_plus_beta + h2_val + beta * h2_next_val);
2356            let prod = prod_evals[j] * a / b;
2357            prod_evals.push(prod);
2358        }
2359        prod_evals.push(F::one());
2360        check_polynomial(&prod_poly, &prod_evals);
2361
2362        Ok(())
2363    }
2364
2365    pub(crate) fn test_arithmetization_for_circuit<F: PrimeField>(
2366        circuit: PlonkCircuit<F>,
2367        pub_inputs: Vec<F>,
2368    ) -> Result<(), CircuitError> {
2369        // Check arithmetizations
2370        let n = circuit.eval_domain.size();
2371
2372        // Check selector polynomials
2373        let selector_polys = circuit.compute_selector_polynomials()?;
2374        selector_polys
2375            .iter()
2376            .zip(circuit.all_selectors().iter())
2377            .for_each(|(poly, evals)| check_polynomial(poly, evals));
2378
2379        // Check wire witness polynomials
2380        let wire_polys = circuit.compute_wire_polynomials()?;
2381        for (poly, wire_vars) in wire_polys
2382            .iter()
2383            .zip(circuit.wire_variables.iter().take(circuit.num_wire_types()))
2384        {
2385            let wire_evals: Vec<F> = wire_vars.iter().map(|&var| circuit.witness[var]).collect();
2386            check_polynomial(poly, &wire_evals);
2387        }
2388
2389        // Check public input polynomial
2390        let pi_poly = circuit.compute_pub_input_polynomial()?;
2391        let mut pi_evals = pub_inputs;
2392        pi_evals.extend(vec![F::zero(); n - 2]);
2393        check_polynomial(&pi_poly, &pi_evals);
2394
2395        // Check extended permutation polynomials
2396        let sigma_polys = circuit.compute_extended_permutation_polynomials()?;
2397        let extended_perm: Vec<F> = circuit
2398            .wire_permutation
2399            .iter()
2400            .map(|&(i, j)| circuit.extended_id_permutation[i * n + j])
2401            .collect();
2402        for (i, poly) in sigma_polys.iter().enumerate() {
2403            check_polynomial(poly, &extended_perm[i * n..(i + 1) * n]);
2404        }
2405
2406        // Check grand product polynomial for permutation
2407        let rng = &mut test_rng();
2408        let beta = F::rand(rng);
2409        let gamma = F::rand(rng);
2410        let prod_poly = circuit.compute_prod_permutation_polynomial(&beta, &gamma)?;
2411        let mut prod_evals = vec![F::one()];
2412        for j in 0..(n - 1) {
2413            // Nominator
2414            let mut a = F::one();
2415            // Denominator
2416            let mut b = F::one();
2417            for i in 0..circuit.num_wire_types {
2418                let wire_value = circuit.witness[circuit.wire_variable(i, j)];
2419                a *= wire_value + beta * circuit.extended_id_permutation[i * n + j] + gamma;
2420                b *= wire_value + beta * extended_perm[i * n + j] + gamma;
2421            }
2422            let prod = prod_evals[j] * a / b;
2423            prod_evals.push(prod);
2424        }
2425        check_polynomial(&prod_poly, &prod_evals);
2426
2427        Ok(())
2428    }
2429}