fullcodec_plonk/constraint_system/
composer.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4//
5// Copyright (c) DUSK NETWORK. All rights reserved.
6
7//! A `Composer` could be understood as some sort of Trait that is actually
8//! defining some kind of Circuit Builder for PLONK.
9//!
10//! In that sense, here we have the implementation of the [`TurboComposer`]
11//! which has been designed in order to provide the maximum amount of
12//! performance while having a big scope in utility terms.
13//!
14//! It allows us not only to build Add and Mul gates but also to build
15//! ECC op. gates, Range checks, Logical gates (Bitwise ops) etc.
16
17// Gate fn's have a large number of attributes but
18// it is intended to be like this in order to provide
19// maximum performance and minimum circuit sizes.
20
21use crate::constraint_system::{Constraint, Selector, WiredWitness, Witness};
22use crate::permutation::Permutation;
23use crate::plonkup::LookupTable;
24use dusk_bls12_381::BlsScalar;
25use hashbrown::HashMap;
26use sp_std::collections::btree_map::BTreeMap;
27use sp_std::vec;
28use sp_std::vec::Vec;
29
30/// The TurboComposer is the circuit-builder tool that the `dusk-plonk`
31/// repository provides so that circuit descriptions can be written, stored and
32/// transformed into a [`Proof`](crate::proof_system::Proof) at some point.
33///
34/// A TurboComposer stores all of the circuit information, being this one
35/// all of the witness and circuit descriptors info (values, positions in the
36/// circuits, gates and Wires that occupy..), the public inputs, the connection
37/// relationships between the witnesses and how they're repesented as Wires (so
38/// basically the Permutation argument etc..).
39///
40/// The TurboComposer also grants us a way to introduce our secret witnesses in
41/// a for of a [`Witness`] into the circuit description as well as the public
42/// inputs. We can do this with methods like [`TurboComposer::append_witness`].
43///
44/// The TurboComposer also contains as associated functions all the
45/// neccessary tools to be able to istrument the circuits that the user needs
46/// through the addition of gates. There are functions that may add a single
47/// gate to the circuit as for example [`TurboComposer::gate_add`] and others
48/// that can add several gates to the circuit description such as
49/// [`TurboComposer::component_select`].
50///
51/// Each gate or group of gates adds an specific functionallity or operation to
52/// de circuit description, and so, that's why we can understand
53/// the TurboComposer as a builder.
54#[derive(Debug)]
55pub struct TurboComposer {
56    /// Number of arithmetic gates in the circuit
57    pub(crate) n: u32,
58
59    // Constraint vectors
60    /// Multiplier selector
61    pub(crate) q_m: Vec<BlsScalar>,
62    /// Left wire selector
63    pub(crate) q_l: Vec<BlsScalar>,
64    /// Right wire selector
65    pub(crate) q_r: Vec<BlsScalar>,
66    /// Output wire selector
67    pub(crate) q_o: Vec<BlsScalar>,
68    /// Fourth wire selector
69    pub(crate) q_4: Vec<BlsScalar>,
70    /// Constant wire selector
71    pub(crate) q_c: Vec<BlsScalar>,
72    /// Arithmetic wire selector
73    pub(crate) q_arith: Vec<BlsScalar>,
74    /// Range selector
75    pub(crate) q_range: Vec<BlsScalar>,
76    /// Logic selector
77    pub(crate) q_logic: Vec<BlsScalar>,
78    /// Fixed base group addition selector
79    pub(crate) q_fixed_group_add: Vec<BlsScalar>,
80    /// Variable base group addition selector
81    pub(crate) q_variable_group_add: Vec<BlsScalar>,
82    /// Plonkup gate wire selector
83    pub(crate) q_lookup: Vec<BlsScalar>,
84
85    /// Sparse representation of the Public Inputs linking the positions of the
86    /// non-zero ones to it's actual values.
87    pub(crate) public_inputs_sparse_store: BTreeMap<u32, BlsScalar>,
88
89    // Witness vectors
90    /// Left wire witness vector.
91    pub(crate) w_l: Vec<Witness>,
92    /// Right wire witness vector.
93    pub(crate) w_r: Vec<Witness>,
94    /// Output wire witness vector.
95    pub(crate) w_o: Vec<Witness>,
96    /// Fourth wire witness vector.
97    pub(crate) w_4: Vec<Witness>,
98
99    /// Public lookup table
100    pub(crate) lookup_table: LookupTable,
101
102    /// These are the actual variable values.
103    pub(crate) witnesses: HashMap<Witness, BlsScalar>,
104
105    /// Permutation argument.
106    pub(crate) perm: Permutation,
107}
108
109impl TurboComposer {
110    /// Returns a [`Witness`] representation of zero.
111    ///
112    /// Every [`TurboComposer`] is initialized with a circuit description
113    /// containing a representation of zero. This function will return the
114    /// index of that representation.
115    pub const fn constant_zero() -> Witness {
116        Witness::new(0)
117    }
118
119    /// Return the number of gates in the circuit
120    pub const fn gates(&self) -> u32 {
121        self.n
122    }
123
124    /// Evaluate the runtime value of a witness
125    ///
126    /// # Safety
127    ///
128    /// Witness evaluation inside a gadget isn't expected and could produce an
129    /// unsound circuit (different circuit representation for the same code).
130    ///
131    /// Calling this function performs operations outside the circuit.
132    pub unsafe fn evaluate_witness(&self, witness: &Witness) -> &BlsScalar {
133        &self.witnesses[witness]
134    }
135
136    /// Constructs a dense vector of the Public Inputs from the positions and
137    /// the sparse vector that contains the values.
138    pub(crate) fn to_dense_public_inputs(&self) -> Vec<BlsScalar> {
139        let mut pi = vec![BlsScalar::zero(); self.n as usize];
140        self.public_inputs_sparse_store
141            .iter()
142            .for_each(|(pos, value)| {
143                pi[*pos as usize] = *value;
144            });
145        pi
146    }
147
148    /// Returns the positions that the Public Inputs occupy in this Composer
149    /// instance.
150    // TODO: Find a more performant solution which can return a ref to a Vec or
151    // Iterator.
152    pub fn public_input_indexes(&self) -> Vec<u32> {
153        self.public_inputs_sparse_store
154            .keys()
155            .copied()
156            .collect::<Vec<u32>>()
157    }
158}
159
160impl Default for TurboComposer {
161    fn default() -> Self {
162        Self::new()
163    }
164}
165
166impl TurboComposer {
167    /// Generates a new empty `TurboComposer` with all of it's fields
168    /// set to hold an initial capacity of 0.
169    ///
170    /// # Note
171    ///
172    /// The usage of this may cause lots of re-allocations since the `Composer`
173    /// holds `Vec` for every polynomial, and these will need to be re-allocated
174    /// each time the circuit grows considerably.
175    pub(crate) fn new() -> Self {
176        TurboComposer::with_size(0)
177    }
178
179    /// Constrain a scalar into the circuit description and return an allocated
180    /// [`Witness`] with its value
181    pub fn append_constant(&mut self, value: BlsScalar) -> Witness {
182        let witness = self.append_witness(value);
183
184        self.assert_equal_constant(witness, value, None);
185
186        witness
187    }
188
189    /// Creates a new circuit with an expected circuit size.
190    /// This will allow for less reallocations when building the circuit
191    /// since the `Vec`s will already have an appropriate allocation at the
192    /// beginning of the composing stage.
193    pub(crate) fn with_size(size: usize) -> Self {
194        let mut composer = TurboComposer {
195            n: 0,
196
197            q_m: Vec::with_capacity(size),
198            q_l: Vec::with_capacity(size),
199            q_r: Vec::with_capacity(size),
200            q_o: Vec::with_capacity(size),
201            q_c: Vec::with_capacity(size),
202            q_4: Vec::with_capacity(size),
203            q_arith: Vec::with_capacity(size),
204            q_range: Vec::with_capacity(size),
205            q_logic: Vec::with_capacity(size),
206            q_fixed_group_add: Vec::with_capacity(size),
207            q_variable_group_add: Vec::with_capacity(size),
208            q_lookup: Vec::with_capacity(size),
209            public_inputs_sparse_store: BTreeMap::new(),
210
211            w_l: Vec::with_capacity(size),
212            w_r: Vec::with_capacity(size),
213            w_o: Vec::with_capacity(size),
214            w_4: Vec::with_capacity(size),
215
216            lookup_table: LookupTable::new(),
217
218            witnesses: HashMap::with_capacity(size),
219
220            perm: Permutation::new(),
221        };
222
223        // Reserve the first witness to be zero
224        composer.append_constant(BlsScalar::zero());
225
226        // Add dummy gates
227        composer.append_dummy_gates();
228
229        composer
230    }
231
232    /// Allocate a witness value into the composer and return its index.
233    pub fn append_witness<T: Into<BlsScalar>>(&mut self, scalar: T) -> Witness {
234        let scalar = scalar.into();
235
236        // Get a new Witness from the permutation
237        let var = self.perm.new_variable();
238
239        // The composer now links the BlsScalar to the Witness returned from
240        // the Permutation
241        self.witnesses.insert(var, scalar);
242
243        var
244    }
245
246    /// Adds a width-4 poly gate.
247    ///
248    /// The final constraint added will enforce the following:
249    /// `q_m · a · b  + q_l · a + q_r · b + q_o · o + q_4 · d + q_c + PI = 0`.
250    pub fn append_gate(&mut self, s: Constraint) {
251        let a = s.witness(WiredWitness::A);
252        let b = s.witness(WiredWitness::B);
253        let o = s.witness(WiredWitness::O);
254        let d = s.witness(WiredWitness::D);
255
256        let s = Constraint::arithmetic(&s);
257
258        let q_m = *s.coeff(Selector::Multiplication);
259        let q_l = *s.coeff(Selector::Left);
260        let q_r = *s.coeff(Selector::Right);
261        let q_o = *s.coeff(Selector::Output);
262        let q_4 = *s.coeff(Selector::Fourth);
263        let q_c = *s.coeff(Selector::Constant);
264        let pi = *s.coeff(Selector::PublicInput);
265
266        let q_arith = *s.coeff(Selector::Arithmetic);
267        let q_range = *s.coeff(Selector::Range);
268        let q_logic = *s.coeff(Selector::Logic);
269        let q_fixed_group_add = *s.coeff(Selector::GroupAddFixedBase);
270        let q_variable_group_add = *s.coeff(Selector::GroupAddVariableBase);
271        let q_lookup = *s.coeff(Selector::Lookup);
272
273        self.w_l.push(a);
274        self.w_r.push(b);
275        self.w_o.push(o);
276        self.w_4.push(d);
277
278        // Add selector vectors
279        self.q_m.push(q_m);
280        self.q_l.push(q_l);
281        self.q_r.push(q_r);
282        self.q_o.push(q_o);
283        self.q_4.push(q_4);
284        self.q_c.push(q_c);
285
286        self.q_arith.push(q_arith);
287        self.q_range.push(q_range);
288        self.q_logic.push(q_logic);
289        self.q_fixed_group_add.push(q_fixed_group_add);
290        self.q_variable_group_add.push(q_variable_group_add);
291        self.q_lookup.push(q_lookup);
292
293        if s.has_public_input() {
294            self.public_inputs_sparse_store.insert(self.n as u32, pi);
295        }
296
297        self.perm.add_variables_to_map(a, b, o, d, self.n as usize);
298
299        self.n += 1;
300    }
301
302    /// Constrain `a` to be equal to `constant + pi`.
303    ///
304    /// `constant` will be defined as part of the public circuit description.
305    pub fn assert_equal_constant(
306        &mut self,
307        a: Witness,
308        constant: BlsScalar,
309        pi: Option<BlsScalar>,
310    ) {
311        let constraint = Constraint::new().left(1).constant(-constant).a(a);
312
313        // TODO maybe accept `Constraint` instead of `Option<Scalar>`?
314        let constraint = match pi {
315            Some(pi) => constraint.public(pi),
316            None => constraint,
317        };
318
319        self.append_gate(constraint);
320    }
321
322    /// Asserts `a == b` by appending a gate
323    pub fn assert_equal(&mut self, a: Witness, b: Witness) {
324        let constraint =
325            Constraint::new().left(1).right(-BlsScalar::one()).a(a).b(b);
326
327        self.append_gate(constraint);
328    }
329
330    /// Conditionally selects a [`Witness`] based on an input bit.
331    ///
332    /// bit == 1 => a,
333    /// bit == 0 => b,
334    ///
335    /// `bit` is expected to be constrained by
336    /// [`TurboComposer::component_boolean`]
337    pub fn component_select(
338        &mut self,
339        bit: Witness,
340        a: Witness,
341        b: Witness,
342    ) -> Witness {
343        debug_assert!(
344            self.witnesses[&bit] == BlsScalar::one()
345                || self.witnesses[&bit] == BlsScalar::zero()
346        );
347
348        // bit * a
349        let constraint = Constraint::new().mult(1).a(bit).b(a);
350        let bit_times_a = self.gate_mul(constraint);
351
352        // 1 - bit
353        let constraint =
354            Constraint::new().left(-BlsScalar::one()).constant(1).a(bit);
355        let one_min_bit = self.gate_add(constraint);
356
357        // (1 - bit) * b
358        let constraint = Constraint::new().mult(1).a(one_min_bit).b(b);
359        let one_min_bit_b = self.gate_mul(constraint);
360
361        // [ (1 - bit) * b ] + [ bit * a ]
362        let constraint = Constraint::new()
363            .left(1)
364            .right(1)
365            .a(one_min_bit_b)
366            .b(bit_times_a);
367        self.gate_add(constraint)
368    }
369
370    /// Conditionally selects a [`Witness`] based on an input bit.
371    ///
372    /// bit == 1 => value,
373    /// bit == 0 => 0,
374    ///
375    /// `bit` is expected to be constrained by
376    /// [`TurboComposer::component_boolean`]
377    pub fn component_select_zero(
378        &mut self,
379        bit: Witness,
380        value: Witness,
381    ) -> Witness {
382        debug_assert!(
383            self.witnesses[&bit] == BlsScalar::one()
384                || self.witnesses[&bit] == BlsScalar::zero()
385        );
386
387        let constraint = Constraint::new().mult(1).a(bit).b(value);
388
389        self.gate_mul(constraint)
390    }
391
392    /// Conditionally selects a [`Witness`] based on an input bit.
393    ///
394    /// bit == 1 => value,
395    /// bit == 0 => 1,
396    ///
397    /// `bit` is expected to be constrained by
398    /// [`TurboComposer::component_boolean`]
399    pub fn component_select_one(
400        &mut self,
401        bit: Witness,
402        value: Witness,
403    ) -> Witness {
404        debug_assert!(
405            self.witnesses[&bit] == BlsScalar::one()
406                || self.witnesses[&bit] == BlsScalar::zero()
407        );
408
409        let b = self.witnesses[&bit];
410        let v = self.witnesses[&value];
411
412        let f_x = BlsScalar::one() - b + (b * v);
413        let f_x = self.append_witness(f_x);
414
415        let constraint = Constraint::new()
416            .mult(1)
417            .left(-BlsScalar::one())
418            .output(-BlsScalar::one())
419            .constant(1)
420            .a(bit)
421            .b(value)
422            .o(f_x);
423
424        self.append_gate(constraint);
425
426        f_x
427    }
428
429    /// Decomposes `scalar` into an array truncated to `N` bits (max 256).
430    ///
431    /// Asserts the reconstruction of the bits to be equal to `scalar`.
432    ///
433    /// Consume `2 · N + 1` gates
434    pub fn component_decomposition<const N: usize>(
435        &mut self,
436        scalar: Witness,
437    ) -> [Witness; N] {
438        // Static assertion
439        assert!(0 < N && N <= 256);
440
441        let mut decomposition = [Self::constant_zero(); N];
442
443        let acc = Self::constant_zero();
444        let acc = self.witnesses[&scalar]
445            .to_bits()
446            .iter()
447            .enumerate()
448            .zip(decomposition.iter_mut())
449            .fold(acc, |acc, ((i, w), d)| {
450                *d = self.append_witness(BlsScalar::from(*w as u64));
451
452                self.component_boolean(*d);
453
454                let constraint = Constraint::new()
455                    .left(BlsScalar::pow_of_2(i as u64))
456                    .right(1)
457                    .a(*d)
458                    .b(acc);
459
460                self.gate_add(constraint)
461            });
462
463        self.assert_equal(acc, scalar);
464
465        decomposition
466    }
467
468    /// This function is used to add a blinding factor to the witness
469    /// polynomials. It essentially adds two dummy gates to the circuit
470    /// description which are guaranteed to always satisfy the gate equation.
471    pub fn append_dummy_gates(&mut self) {
472        // Add a dummy constraint so that we do not have zero polynomials
473        self.q_m.push(BlsScalar::from(1));
474        self.q_l.push(BlsScalar::from(2));
475        self.q_r.push(BlsScalar::from(3));
476        self.q_o.push(BlsScalar::from(4));
477        self.q_c.push(BlsScalar::from(4));
478        self.q_4.push(BlsScalar::one());
479        self.q_arith.push(BlsScalar::one());
480        self.q_range.push(BlsScalar::zero());
481        self.q_logic.push(BlsScalar::zero());
482        self.q_fixed_group_add.push(BlsScalar::zero());
483        self.q_variable_group_add.push(BlsScalar::zero());
484        self.q_lookup.push(BlsScalar::one());
485        let var_six = self.append_witness(BlsScalar::from(6));
486        let var_one = self.append_witness(BlsScalar::from(1));
487        let var_seven = self.append_witness(BlsScalar::from(7));
488        let var_min_twenty = self.append_witness(-BlsScalar::from(20));
489        self.w_l.push(var_six);
490        self.w_r.push(var_seven);
491        self.w_o.push(var_min_twenty);
492        self.w_4.push(var_one);
493        self.perm.add_variables_to_map(
494            var_six,
495            var_seven,
496            var_min_twenty,
497            var_one,
498            self.n as usize,
499        );
500        self.n += 1;
501        //Add another dummy constraint so that we do not get the identity
502        // permutation
503        self.q_m.push(BlsScalar::from(1));
504        self.q_l.push(BlsScalar::from(1));
505        self.q_r.push(BlsScalar::from(1));
506        self.q_o.push(BlsScalar::from(1));
507        self.q_c.push(BlsScalar::from(127));
508        self.q_4.push(BlsScalar::zero());
509        self.q_arith.push(BlsScalar::one());
510        self.q_range.push(BlsScalar::zero());
511        self.q_logic.push(BlsScalar::zero());
512        self.q_fixed_group_add.push(BlsScalar::zero());
513        self.q_variable_group_add.push(BlsScalar::zero());
514        self.q_lookup.push(BlsScalar::one());
515        self.w_l.push(var_min_twenty);
516        self.w_r.push(var_six);
517        self.w_o.push(var_seven);
518        self.w_4.push(Self::constant_zero());
519        self.perm.add_variables_to_map(
520            var_min_twenty,
521            var_six,
522            var_seven,
523            Self::constant_zero(),
524            self.n as usize,
525        );
526
527        // Add dummy rows to lookup table
528        // Notice two rows here match dummy wire values above
529        self.lookup_table.0.insert(
530            0,
531            [
532                BlsScalar::from(6),
533                BlsScalar::from(7),
534                -BlsScalar::from(20),
535                BlsScalar::from(1),
536            ],
537        );
538
539        self.lookup_table.0.insert(
540            0,
541            [
542                -BlsScalar::from(20),
543                BlsScalar::from(6),
544                BlsScalar::from(7),
545                BlsScalar::from(0),
546            ],
547        );
548
549        self.lookup_table.0.insert(
550            0,
551            [
552                BlsScalar::from(3),
553                BlsScalar::from(1),
554                BlsScalar::from(4),
555                BlsScalar::from(9),
556            ],
557        );
558
559        self.n += 1;
560    }
561
562    pub(crate) fn append_output_witness(&mut self, s: Constraint) -> Witness {
563        let a = s.witness(WiredWitness::A);
564        let b = s.witness(WiredWitness::B);
565        let d = s.witness(WiredWitness::D);
566
567        let a = self.witnesses[&a];
568        let b = self.witnesses[&b];
569        let d = self.witnesses[&d];
570
571        let qm = s.coeff(Selector::Multiplication);
572        let ql = s.coeff(Selector::Left);
573        let qr = s.coeff(Selector::Right);
574        let qd = s.coeff(Selector::Fourth);
575        let qc = s.coeff(Selector::Constant);
576        let pi = s.coeff(Selector::PublicInput);
577
578        let x = qm * a * b + ql * a + qr * b + qd * d + qc + pi;
579
580        let y = s.coeff(Selector::Output);
581        let y: Option<BlsScalar> = y.invert().into();
582        let y = -y.expect("Inconsistent internal usage of `Constraint::evaluate_output`: Output selector should not be zero");
583
584        let o = x * y;
585        self.append_witness(o)
586    }
587
588    /// Utility function that allows to check on the "front-end"
589    /// side of the PLONK implementation if the identity polynomial
590    /// is satisfied for each one of the [`TurboComposer`]'s gates.
591    ///
592    /// The recommended usage is to derive the std output and the std error to a
593    /// text file and analyze there the gates.
594    ///
595    /// # Panic
596    /// The function by itself will print each circuit gate info until one of
597    /// the gates does not satisfy the equation or there are no more gates. If
598    /// the cause is an unsatisfied gate equation, the function will panic.
599    #[cfg(feature = "trace")]
600    #[allow(dead_code)]
601    pub(crate) fn check_circuit_satisfied(&self) {
602        let w_l: Vec<&BlsScalar> = self
603            .w_l
604            .iter()
605            .map(|w_l_i| self.witnesses.get(w_l_i).unwrap())
606            .collect();
607        let w_r: Vec<&BlsScalar> = self
608            .w_r
609            .iter()
610            .map(|w_r_i| self.witnesses.get(w_r_i).unwrap())
611            .collect();
612        let w_o: Vec<&BlsScalar> = self
613            .w_o
614            .iter()
615            .map(|w_o_i| self.witnesses.get(w_o_i).unwrap())
616            .collect();
617        let w_4: Vec<&BlsScalar> = self
618            .w_4
619            .iter()
620            .map(|w_4_i| self.witnesses.get(w_4_i).unwrap())
621            .collect();
622
623        // Computes f(f-1)(f-2)(f-3)
624        let delta = |f: BlsScalar| -> BlsScalar {
625            let f_1 = f - BlsScalar::one();
626            let f_2 = f - BlsScalar::from(2);
627            let f_3 = f - BlsScalar::from(3);
628            f * f_1 * f_2 * f_3
629        };
630
631        let pi_vec = self.to_dense_public_inputs();
632        let four = BlsScalar::from(4);
633
634        for i in 0..self.n {
635            let qm = self.q_m[i];
636            let ql = self.q_l[i];
637            let qr = self.q_r[i];
638            let qo = self.q_o[i];
639            let qc = self.q_c[i];
640            let q4 = self.q_4[i];
641            let qarith = self.q_arith[i];
642            let qrange = self.q_range[i];
643            let qlogic = self.q_logic[i];
644            let qfixed = self.q_fixed_group_add[i];
645            let qvar = self.q_variable_group_add[i];
646            let pi = pi_vec[i];
647
648            let a = w_l[i];
649            let a_next = w_l[(i + 1) % self.n];
650            let b = w_r[i];
651            let b_next = w_r[(i + 1) % self.n];
652            let c = w_o[i];
653            let d = w_4[i];
654            let d_next = w_4[(i + 1) % self.n];
655
656            #[cfg(all(feature = "trace-print", feature = "std"))]
657            std::println!(
658                "--------------------------------------------\n
659            #Gate Index = {}
660            #Constraint Polynomials:\n
661            - qm -> {:?}\n
662            - ql -> {:?}\n
663            - qr -> {:?}\n
664            - q4 -> {:?}\n
665            - qo -> {:?}\n
666            - qc -> {:?}\n
667            - q_arith -> {:?}\n
668            - q_range -> {:?}\n
669            - q_logic -> {:?}\n
670            - q_fixed_group_add -> {:?}\n
671            - q_variable_group_add -> {:?}\n
672            # Witness polynomials:\n
673            - w_l -> {:?}\n
674            - w_r -> {:?}\n
675            - w_o -> {:?}\n
676            - w_4 -> {:?}\n",
677                i,
678                qm,
679                ql,
680                qr,
681                q4,
682                qo,
683                qc,
684                qarith,
685                qrange,
686                qlogic,
687                qfixed,
688                qvar,
689                a,
690                b,
691                c,
692                d
693            );
694
695            let k = qarith
696                * ((qm * a * b)
697                    + (ql * a)
698                    + (qr * b)
699                    + (qo * c)
700                    + (q4 * d)
701                    + pi
702                    + qc)
703                + qlogic
704                    * (((delta(a_next - four * a) - delta(b_next - four * b))
705                        * c)
706                        + delta(a_next - four * a)
707                        + delta(b_next - four * b)
708                        + delta(d_next - four * d)
709                        + match (
710                            qlogic == BlsScalar::one(),
711                            qlogic == -BlsScalar::one(),
712                        ) {
713                            (true, false) => (a & b) - d,
714                            (false, true) => (a ^ b) - d,
715                            (false, false) => BlsScalar::zero(),
716                            _ => unreachable!(),
717                        })
718                + qrange
719                    * (delta(c - four * d)
720                        + delta(b - four * c)
721                        + delta(a - four * b)
722                        + delta(d_next - four * a));
723
724            assert_eq!(k, BlsScalar::zero(), "Check failed at gate {}", i,);
725        }
726    }
727
728    /// Adds a plonkup gate to the circuit with its corresponding
729    /// gates.
730    ///
731    /// This type of gate is usually used when we need to have
732    /// the largest amount of performance and the minimum circuit-size
733    /// possible. Since it allows the end-user to set every selector coefficient
734    /// as scaling value on the gate eq.
735    pub fn append_plonkup_gate(
736        &mut self,
737        a: Witness,
738        b: Witness,
739        c: Witness,
740        d: Witness,
741        pi: Option<BlsScalar>,
742    ) -> Witness {
743        self.w_l.push(a);
744        self.w_r.push(b);
745        self.w_o.push(c);
746        self.w_4.push(d);
747
748        // Add selector vectors
749        self.q_l.push(BlsScalar::zero());
750        self.q_r.push(BlsScalar::zero());
751        self.q_o.push(BlsScalar::zero());
752        self.q_c.push(BlsScalar::zero());
753        self.q_4.push(BlsScalar::zero());
754        self.q_arith.push(BlsScalar::zero());
755        self.q_m.push(BlsScalar::zero());
756        self.q_range.push(BlsScalar::zero());
757        self.q_logic.push(BlsScalar::zero());
758        self.q_fixed_group_add.push(BlsScalar::zero());
759        self.q_variable_group_add.push(BlsScalar::zero());
760
761        // For a lookup gate, only one selector poly is
762        // turned on as the output is inputted directly
763        self.q_lookup.push(BlsScalar::one());
764
765        if let Some(pi) = pi {
766            debug_assert!(self.public_inputs_sparse_store.get(&self.n).is_none(), "The invariant of already having a PI inserted for this position should never exist");
767
768            self.public_inputs_sparse_store.insert(self.n, pi);
769        }
770
771        self.perm.add_variables_to_map(a, b, c, d, self.n as usize);
772
773        self.n += 1;
774
775        c
776    }
777
778    /// When [`TurboComposer`] is initialised, it spawns a dummy table
779    /// with 3 entries that should not be removed. This function appends
780    /// its input table to the composer's dummy table
781    pub fn append_plonkup_table(&mut self, table: &LookupTable) {
782        table.0.iter().for_each(|k| self.lookup_table.0.push(*k))
783    }
784}
785
786#[cfg(feature = "std")]
787#[cfg(test)]
788mod tests {
789    use super::*;
790    use crate::commitment_scheme::PublicParameters;
791    use crate::constraint_system::helper::*;
792    use crate::error::Error;
793    use crate::proof_system::{Prover, Verifier};
794    use rand_core::OsRng;
795
796    #[test]
797    /// Tests that a circuit initially has 3 gates
798    fn test_initial_gates() {
799        let composer: TurboComposer = TurboComposer::new();
800        // Circuit size is n+3 because
801        // - We have an extra gate which forces the first witness to be zero.
802        //   This is used when the advice wire is not being used.
803        // - We have two gates which ensure that the permutation polynomial is
804        //   not the identity and
805        // - Another gate which ensures that the selector polynomials are not
806        //   all zeroes
807        assert_eq!(3, composer.gates())
808    }
809
810    #[allow(unused_variables)]
811    #[test]
812    /// Tests that an empty circuit proof passes
813    fn test_minimal_circuit() {
814        let res = gadget_tester(
815            |composer| {
816                // do nothing except add the dummy gates
817                composer.append_dummy_gates();
818            },
819            200,
820        );
821        assert!(res.is_ok());
822    }
823
824    #[test]
825    fn test_component_select() {
826        let res = gadget_tester(
827            |composer| {
828                let bit_1 = composer.append_witness(BlsScalar::one());
829                let bit_0 = TurboComposer::constant_zero();
830
831                let choice_a = composer.append_witness(BlsScalar::from(10u64));
832                let choice_b = composer.append_witness(BlsScalar::from(20u64));
833
834                let choice =
835                    composer.component_select(bit_1, choice_a, choice_b);
836                composer.assert_equal(choice, choice_a);
837
838                let choice =
839                    composer.component_select(bit_0, choice_a, choice_b);
840                composer.assert_equal(choice, choice_b);
841            },
842            32,
843        );
844        assert!(res.is_ok());
845    }
846
847    #[test]
848    fn test_gadget() {
849        let mut t = LookupTable::new();
850        t.insert_special_row(
851            BlsScalar::from(12),
852            BlsScalar::from(12),
853            BlsScalar::from(12),
854            BlsScalar::from(12),
855        );
856        t.insert_special_row(
857            BlsScalar::from(3),
858            BlsScalar::from(0),
859            BlsScalar::from(12),
860            BlsScalar::from(341),
861        );
862        t.insert_special_row(
863            BlsScalar::from(341),
864            BlsScalar::from(341),
865            BlsScalar::from(10),
866            BlsScalar::from(10),
867        );
868        let res = gadget_plonkup_tester(
869            |composer| {
870                let bit_1 = composer.append_witness(BlsScalar::one());
871                let bit_0 = TurboComposer::constant_zero();
872
873                let choice_a = composer.append_witness(BlsScalar::from(10u64));
874                let choice_b = composer.append_witness(BlsScalar::from(20u64));
875
876                let choice =
877                    composer.component_select(bit_1, choice_a, choice_b);
878                composer.assert_equal(choice, choice_a);
879
880                let choice =
881                    composer.component_select(bit_0, choice_a, choice_b);
882                composer.assert_equal(choice, choice_b);
883            },
884            65,
885            t,
886        );
887        assert!(res.is_ok());
888    }
889
890    #[test]
891    #[should_panic]
892    fn test_gadget_fail() {
893        let mut t = LookupTable::new();
894        t.insert_special_row(
895            BlsScalar::from(12),
896            BlsScalar::from(12),
897            BlsScalar::from(12),
898            BlsScalar::from(12),
899        );
900        let res = gadget_plonkup_tester(
901            |composer| {
902                let twelve = composer.append_constant(BlsScalar::from(12));
903                let three = composer.append_constant(BlsScalar::from(3));
904
905                composer
906                    .append_plonkup_gate(twelve, twelve, twelve, three, None);
907            },
908            65,
909            t,
910        );
911        assert!(res.is_err());
912    }
913
914    #[test]
915    // XXX: Move this to integration tests
916    fn test_multiple_proofs() {
917        let public_parameters =
918            PublicParameters::setup(2 * 30, &mut OsRng).unwrap();
919
920        // Create a prover struct
921        let mut prover = Prover::new(b"demo");
922
923        // Add gadgets
924        dummy_gadget(10, prover.composer_mut());
925
926        // Commit Key
927        let (ck, _) = public_parameters.trim(2 * 20).unwrap();
928
929        // Preprocess circuit
930        prover.preprocess(&ck).unwrap();
931
932        let public_inputs = prover.cs.to_dense_public_inputs();
933
934        let mut proofs = Vec::new();
935
936        // Compute multiple proofs
937        for _ in 0..3 {
938            proofs.push(prover.prove(&ck).unwrap());
939
940            // Add another witness instance
941            dummy_gadget(10, prover.composer_mut());
942        }
943
944        // Verifier
945        //
946        let mut verifier = Verifier::new(b"demo");
947
948        // Add gadgets
949        dummy_gadget(10, verifier.composer_mut());
950
951        // Commit and Verifier Key
952        let (ck, vk) = public_parameters.trim(2 * 20).unwrap();
953
954        // Preprocess
955        verifier.preprocess(&ck).unwrap();
956
957        for proof in proofs {
958            assert!(verifier.verify(&proof, &vk, &public_inputs).is_ok());
959        }
960    }
961
962    #[test]
963    fn test_plonkup_full() {
964        let public_parameters =
965            PublicParameters::setup(2 * 70, &mut OsRng).unwrap();
966
967        // Create a prover struct
968        let mut prover = Prover::new(b"test");
969
970        prover.cs.lookup_table.insert_multi_mul(0, 3);
971
972        // add to trans
973        prover.key_transcript(b"key", b"additional seed information");
974
975        let output = prover.cs.lookup_table.lookup(
976            BlsScalar::from(2),
977            BlsScalar::from(3),
978            BlsScalar::one(),
979        );
980
981        let two = prover.cs.append_constant(BlsScalar::from(2));
982        let three = prover.cs.append_constant(BlsScalar::from(3));
983        let result = prover.cs.append_constant(output.unwrap());
984        let one = prover.cs.append_constant(BlsScalar::one());
985
986        prover.cs.append_plonkup_gate(two, three, result, one, None);
987        prover.cs.append_plonkup_gate(two, three, result, one, None);
988        prover.cs.append_plonkup_gate(two, three, result, one, None);
989        prover.cs.append_plonkup_gate(two, three, result, one, None);
990        prover.cs.append_plonkup_gate(two, three, result, one, None);
991
992        let constraint = Constraint::new().left(1).right(1).a(two).b(three);
993        prover.cs.gate_add(constraint);
994
995        // Commit Key
996        let (ck, _) = public_parameters.trim(2 * 70).unwrap();
997
998        // Preprocess circuit
999        prover.preprocess(&ck).unwrap();
1000
1001        // Once the prove method is called, the public inputs are cleared
1002        // So pre-fetch these before calling Prove
1003        let public_inputs = prover.cs.to_dense_public_inputs();
1004
1005        prover.prove(&ck).unwrap();
1006        drop(public_inputs);
1007    }
1008
1009    #[test]
1010    fn test_plonkup_proof() -> Result<(), Error> {
1011        let public_parameters = PublicParameters::setup(1 << 8, &mut OsRng)?;
1012
1013        // Create a prover struct
1014        let mut prover = Prover::new(b"test");
1015        let mut verifier = Verifier::new(b"test");
1016
1017        // Add gadgets
1018        dummy_gadget_plonkup(4, prover.composer_mut());
1019        prover.cs.lookup_table.insert_multi_mul(0, 3);
1020
1021        dummy_gadget_plonkup(4, verifier.composer_mut());
1022        verifier.cs.lookup_table.insert_multi_mul(0, 3);
1023
1024        // Commit and verifier key
1025        let (ck, vk) = public_parameters.trim(1 << 7)?;
1026
1027        // Preprocess circuit
1028        prover.preprocess(&ck)?;
1029        verifier.preprocess(&ck)?;
1030
1031        let public_inputs = prover.cs.to_dense_public_inputs();
1032
1033        let proof = prover.prove(&ck)?;
1034
1035        assert!(verifier.verify(&proof, &vk, &public_inputs).is_ok());
1036
1037        Ok(())
1038    }
1039}
fullcodec_plonk/constraint_system/composer.rs

fullcodec_plonk/constraint_system/
composer.rs
