1use 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
25pub type GateId = usize;
27pub type WireId = usize;
32pub type Variable = usize;
34#[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 pub(crate) fn new_unchecked(inner: usize) -> Self {
50 Self(inner)
51 }
52}
53
54#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
55pub enum PlonkType {
57 TurboPlonk,
59 UltraPlonk,
61}
62
63#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
64pub enum MergeableCircuitType {
67 TypeA,
69 TypeB,
71}
72
73pub trait Circuit<F: Field> {
75 fn num_gates(&self) -> usize;
77
78 fn num_vars(&self) -> usize;
80
81 fn num_inputs(&self) -> usize;
83
84 fn num_wire_types(&self) -> usize;
88
89 fn public_input(&self) -> Result<Vec<F>, CircuitError>;
91
92 fn check_circuit_satisfiability(&self, pub_input: &[F]) -> Result<(), CircuitError>;
94
95 fn create_constant_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
98
99 fn create_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
101
102 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 fn create_public_variable(&mut self, val: F) -> Result<Variable, CircuitError>;
112
113 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 fn set_variable_public(&mut self, var: Variable) -> Result<(), CircuitError>;
123
124 fn zero(&self) -> Variable;
126
127 fn one(&self) -> Variable;
129
130 fn false_var(&self) -> BoolVar {
132 BoolVar::new_unchecked(self.zero())
133 }
134
135 fn true_var(&self) -> BoolVar {
137 BoolVar::new_unchecked(self.one())
138 }
139
140 fn witness(&self, idx: Variable) -> Result<F, CircuitError>;
143
144 fn enforce_constant(&mut self, var: Variable, constant: F) -> Result<(), CircuitError>;
149
150 fn add_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
153
154 fn add(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
158
159 fn sub_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
162
163 fn sub(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
167
168 fn mul_gate(&mut self, a: Variable, b: Variable, c: Variable) -> Result<(), CircuitError>;
171
172 fn mul(&mut self, a: Variable, b: Variable) -> Result<Variable, CircuitError>;
176
177 fn enforce_bool(&mut self, a: Variable) -> Result<(), CircuitError>;
180
181 fn enforce_equal(&mut self, a: Variable, b: Variable) -> Result<(), CircuitError>;
184
185 fn pad_gates(&mut self, n: usize);
187
188 fn support_lookup(&self) -> bool;
191}
192
193pub(crate) type SortedLookupVecAndPolys<F> = (Vec<F>, DensePolynomial<F>, DensePolynomial<F>);
197
198pub trait Arithmetization<F: FftField>: Circuit<F> {
201 fn srs_size(&self) -> Result<usize, CircuitError>;
203
204 fn eval_domain_size(&self) -> Result<usize, CircuitError>;
207
208 fn compute_selector_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
211
212 fn compute_extended_permutation_polynomials(
215 &self,
216 ) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
217
218 fn compute_prod_permutation_polynomial(
221 &self,
222 beta: &F,
223 gamma: &F,
224 ) -> Result<DensePolynomial<F>, CircuitError>;
225
226 fn compute_wire_polynomials(&self) -> Result<Vec<DensePolynomial<F>>, CircuitError>;
229
230 fn compute_pub_input_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError>;
234
235 fn compute_range_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
243 Err(CircuitError::LookupUnsupported)
244 }
245
246 fn compute_key_table_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
250 Err(CircuitError::LookupUnsupported)
251 }
252
253 fn compute_table_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
257 Err(CircuitError::LookupUnsupported)
258 }
259
260 fn compute_q_dom_sep_polynomial(&self) -> Result<DensePolynomial<F>, CircuitError> {
264 Err(CircuitError::LookupUnsupported)
265 }
266
267 fn compute_merged_lookup_table(&self, _tau: F) -> Result<Vec<F>, CircuitError> {
270 Err(CircuitError::LookupUnsupported)
271 }
272
273 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 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
303const RANGE_WIRE_ID: usize = 5;
305const LOOKUP_KEY_WIRE_ID: usize = 0;
307const LOOKUP_VAL_1_WIRE_ID: usize = 1;
309const LOOKUP_VAL_2_WIRE_ID: usize = 2;
310const TABLE_VAL_1_WIRE_ID: usize = 3;
312const TABLE_VAL_2_WIRE_ID: usize = 4;
313
314#[derive(Debug, Clone, Copy)]
316struct PlonkParams {
317 plonk_type: PlonkType,
319
320 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#[derive(Debug, Clone)]
347pub struct PlonkCircuit<F>
348where
349 F: FftField,
350{
351 num_vars: usize,
353
354 gates: Vec<Box<dyn Gate<F>>>,
356 wire_variables: [Vec<Variable>; GATE_WIDTH + 2],
358 pub_input_gate_ids: Vec<GateId>,
360 witness: Vec<F>,
362
363 wire_permutation: Vec<(WireId, GateId)>,
376 extended_id_permutation: Vec<F>,
378 num_wire_types: usize,
380
381 eval_domain: Radix2EvaluationDomain<F>,
386
387 plonk_params: PlonkParams,
389
390 num_table_elems: usize,
392
393 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 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 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 circuit.enforce_constant(0, zero).unwrap(); circuit.enforce_constant(1, one).unwrap(); circuit
436 }
437
438 pub fn new_turbo_plonk() -> Self {
440 let plonk_params = PlonkParams::init(PlonkType::TurboPlonk, None).unwrap(); Self::new(plonk_params)
442 }
443
444 pub fn new_ultra_plonk(range_bit_len: usize) -> Self {
446 let plonk_params = PlonkParams::init(PlonkType::UltraPlonk, Some(range_bit_len)).unwrap(); Self::new(plonk_params)
448 }
449
450 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 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 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 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 pub fn witness_mut(&mut self, idx: Variable) -> &mut F {
512 &mut self.witness[idx]
513 }
514
515 pub(crate) fn table_gate_ids_mut(&mut self) -> &mut Vec<(GateId, usize)> {
517 &mut self.table_gate_ids
518 }
519
520 pub(crate) fn num_table_elems_mut(&mut self) -> &mut usize {
522 &mut self.num_table_elems
523 }
524
525 pub(crate) fn num_table_elems(&self) -> usize {
527 self.num_table_elems
528 }
529
530 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()) }
539
540 pub fn range_size(&self) -> Result<usize, CircuitError> {
542 Ok(1 << self.range_bit_len()?)
543 }
544
545 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 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 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 if self.plonk_params.plonk_type == PlonkType::UltraPlonk {
606 for idx in 0..self.wire_variables[RANGE_WIRE_ID].len() {
608 self.check_range_gate(idx)?
609 }
610 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 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 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 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 let wire_vars = &[0, 0, 0, 0, var];
678 self.insert_gate(wire_vars, Box::new(IoGate))?;
679 Ok(())
680 }
681
682 fn zero(&self) -> Variable {
684 0
685 }
686
687 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 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 fn support_lookup(&self) -> bool {
795 self.plonk_params.plonk_type == PlonkType::UltraPlonk
796 }
797}
798
799impl<F: FftField> PlonkCircuit<F> {
801 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 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 self.gates.swap(gate_id, *io_gate_id);
837 for wires in &mut self.wire_variables[..GATE_WIDTH + 1] {
839 wires.swap(gate_id, *io_gate_id);
840 }
841 *io_gate_id = gate_id;
843 }
844 }
845 if self.support_lookup() {
846 let n = self.eval_domain.size();
849 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 self.gates.swap(gate_id, cur_gate_id);
857 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 fn is_io_gate(&self, gate_id: GateId) -> bool {
870 self.gates[gate_id].as_any().is::<IoGate>()
871 }
872
873 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 fn check_gate(&self, gate_id: Variable, pub_input: &F) -> Result<(), CircuitError> {
896 let w_vals: Vec<F> = (0..GATE_WIDTH + 1)
899 .map(|i| self.witness[self.wire_variables[i][gate_id]])
900 .collect();
901 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 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 #[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 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 self.wire_permutation = vec![(0usize, 0usize); self.num_wire_types * n];
970 for wires_vec in variable_wires_map.iter_mut() {
971 if !wires_vec.is_empty() {
973 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 wires_vec.pop();
982 }
983 }
984 }
985
986 #[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 #[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 #[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 #[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 #[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 #[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 #[inline]
1059 fn q_o(&self) -> Vec<F> {
1060 self.gates.iter().map(|g| g.q_o()).collect()
1061 }
1062 #[inline]
1064 fn q_c(&self) -> Vec<F> {
1065 self.gates.iter().map(|g| g.q_c()).collect()
1066 }
1067 #[inline]
1069 fn q_ecc(&self) -> Vec<F> {
1070 self.gates.iter().map(|g| g.q_ecc()).collect()
1071 }
1072 #[inline]
1074 fn q_lookup(&self) -> Vec<F> {
1075 self.gates.iter().map(|g| g.q_lookup()).collect()
1076 }
1077 #[inline]
1079 fn q_dom_sep(&self) -> Vec<F> {
1080 self.gates.iter().map(|g| g.q_dom_sep()).collect()
1081 }
1082 #[inline]
1084 fn table_key_vec(&self) -> Vec<F> {
1085 self.gates.iter().map(|g| g.table_key()).collect()
1086 }
1087 #[inline]
1089 fn table_dom_sep_vec(&self) -> Vec<F> {
1090 self.gates.iter().map(|g| g.table_dom_sep()).collect()
1091 }
1092 #[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
1114impl<F: PrimeField> PlonkCircuit<F> {
1116 #[inline]
1119 fn compute_extended_id_permutation(&mut self) {
1120 assert!(self.is_finalized());
1121 let n = self.eval_domain.size();
1122
1123 let k: Vec<F> = compute_coset_representatives(self.num_wire_types, Some(n));
1126 let group_elems: Vec<F> = self.eval_domain.elements().collect();
1128 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 let extended_perm: Vec<F> = self
1145 .wire_permutation
1146 .iter()
1147 .map(|&(wire_id, gate_id)| {
1148 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
1167impl<F: PrimeField> PlonkCircuit<F> {
1169 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 ), };
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 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 let n = self.eval_domain_size()?;
1205 self.eval_domain =
1206 Radix2EvaluationDomain::new(2 * n).ok_or(CircuitError::DomainCreationError)?;
1207 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 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 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 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 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 self.compute_extended_id_permutation();
1248 Ok(())
1249 }
1250
1251 #[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 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 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 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 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<_>>()) .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 let mut a = F::one();
1411 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 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 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 let a = beta_plus_one
1568 * (*gamma + lookup_wire_val)
1569 * (gamma_mul_beta_plus_one + table_val + *beta * table_next_val);
1570 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 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 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
1632impl<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 let a = circuit.create_variable(F::from(3u32))?;
1720 let b = circuit.create_variable(F::from(1u32))?;
1721 circuit.enforce_constant(a, F::from(3u32))?;
1723 circuit.enforce_bool(b)?;
1725 let c = circuit.add(a, b)?;
1727 let d = circuit.sub(a, b)?;
1729 let e = circuit.mul(c, d)?;
1731 let f = circuit.create_public_variable(F::from(8u32))?;
1733 circuit.enforce_equal(e, f)?;
1735
1736 assert_eq!(circuit.num_gates(), 9);
1739 assert_eq!(circuit.num_vars(), 8);
1741 assert_eq!(circuit.num_inputs(), 1);
1743
1744 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 assert!(circuit
1973 .check_circuit_satisfiability(&[F::from(1u32), F::from(2u32), F::from(3u32)])
1974 .is_ok());
1975 assert!(circuit
1977 .check_circuit_satisfiability(&[F::from(2u32), F::from(1u32), F::from(3u32)])
1978 .is_err());
1979 *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 *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 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 let table_vars = [(a, b), (c, d), (e, f)];
2034 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 #[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 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 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 let cycle_var = circuit.wire_variable(i, j);
2089 assert!(!visit_variable[cycle_var]);
2091 visit_variable[cycle_var] = true;
2092
2093 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 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 assert_eq!(cycle_var, next_var);
2107 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 circuit.compute_extended_id_permutation();
2118 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]
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 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 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 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 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 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 assert!(circuit.add_range_check_variable(0).is_err());
2240
2241 Ok(())
2242 }
2243
2244 #[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 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 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 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 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 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 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 assert_eq!(sorted_vec[0], merged_lookup_table[0]);
2304 let mut ptr = 1;
2305 for slice in sorted_vec.windows(2) {
2306 if slice[0] == slice[1] {
2308 continue;
2309 }
2310 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_eq!(ptr, n);
2320
2321 check_polynomial(&h1_poly, &sorted_vec[..n]);
2322 check_polynomial(&h2_poly, &sorted_vec[n - 1..]);
2323
2324 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 let a = one_plus_beta
2351 * (gamma + lookup_wire_val)
2352 * (gamma_mul_one_plus_beta + table_val + beta * table_next_val);
2353 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 let n = circuit.eval_domain.size();
2371
2372 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 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 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 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 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 let mut a = F::one();
2415 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}