midnight_circuits/instructions/
arithmetic.rs

1// This file is part of MIDNIGHT-ZK.
2// Copyright (C) Midnight Foundation
3// SPDX-License-Identifier: Apache-2.0
4// Licensed under the Apache License, Version 2.0 (the "License");
5// You may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7// http://www.apache.org/licenses/LICENSE-2.0
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14//! Arithmetic instructions interface.
15//!
16//! It provides functions for performing arithmetic operations between assigned
17//! values in the circuit.
18//!
19//! This trait is parametrized by a generic `Assigned` (required to implement
20//! [InnerValue]) which defines the type over which the arithmetic operations
21//! take place.
22
23use std::{
24    fmt::Debug,
25    ops::{Add, Neg},
26};
27
28use midnight_proofs::{circuit::Layouter, plonk::Error};
29
30use crate::{
31    instructions::{AssertionInstructions, AssignmentInstructions},
32    types::InnerValue,
33    CircuitField,
34};
35
36/// The set of circuit instructions for arithmetic operations.
37pub trait ArithInstructions<F, Assigned>:
38    Clone + Debug + AssignmentInstructions<F, Assigned> + AssertionInstructions<F, Assigned>
39where
40    F: CircuitField,
41    Assigned::Element:
42        PartialEq + From<u64> + Add<Output = Assigned::Element> + Neg<Output = Assigned::Element>,
43    Assigned: InnerValue,
44{
45    /// Addition of many elements, given a slice of terms of the form
46    /// `(coeff_i, x_i)` and a constant `k`, returns
47    /// `k + (sum_i coeff_i * x_i)`.
48    ///
49    /// This function is potentially more efficient than folding over
50    /// [add](ArithInstructions::add) and
51    /// [mul_by_constant](ArithInstructions::mul_by_constant).
52    ///
53    /// ```
54    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
55    /// let x = chip.assign(&mut layouter, Value::known(F::from(1)))?;
56    /// let y = chip.assign(&mut layouter, Value::known(F::from(2)))?;
57    /// let z = chip.assign(&mut layouter, Value::known(F::from(3)))?;
58    ///
59    /// let res = chip.linear_combination(
60    ///     &mut layouter,
61    ///     &[(F::from(100), x), (F::from(10), y), (F::ONE, z)],
62    ///     F::ZERO,
63    /// )?;
64    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(123))?;
65    /// # });
66    /// ```
67    fn linear_combination(
68        &self,
69        layouter: &mut impl Layouter<F>,
70        terms: &[(Assigned::Element, Assigned)],
71        constant: Assigned::Element,
72    ) -> Result<Assigned, Error>;
73
74    /// Addition.
75    ///
76    /// ```
77    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
78    /// let x = chip.assign(&mut layouter, Value::known(F::from(2)))?;
79    /// let y = chip.assign(&mut layouter, Value::known(F::from(3)))?;
80    ///
81    /// let res = chip.add(&mut layouter, &x, &y)?;
82    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(5))?;
83    /// # });
84    /// ```
85    fn add(
86        &self,
87        layouter: &mut impl Layouter<F>,
88        x: &Assigned,
89        y: &Assigned,
90    ) -> Result<Assigned, Error> {
91        self.linear_combination(
92            layouter,
93            &[
94                (Assigned::Element::from(1), x.clone()),
95                (Assigned::Element::from(1), y.clone()),
96            ],
97            Assigned::Element::from(0),
98        )
99    }
100
101    /// Subtraction.
102    ///
103    /// ```
104    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
105    /// let x = chip.assign(&mut layouter, Value::known(F::from(2)))?;
106    /// let y = chip.assign(&mut layouter, Value::known(F::from(3)))?;
107    ///
108    /// let res = chip.sub(&mut layouter, &x, &y)?;
109    /// chip.assert_equal_to_fixed(&mut layouter, &res, -F::ONE)?;
110    /// # });
111    /// ```
112    fn sub(
113        &self,
114        layouter: &mut impl Layouter<F>,
115        x: &Assigned,
116        y: &Assigned,
117    ) -> Result<Assigned, Error> {
118        self.linear_combination(
119            layouter,
120            &[
121                (Assigned::Element::from(1), x.clone()),
122                (-Assigned::Element::from(1), y.clone()),
123            ],
124            Assigned::Element::from(0),
125        )
126    }
127
128    /// Multiplication, possibly with an additional multiplying constant.
129    ///
130    /// ```
131    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
132    /// let x = chip.assign(&mut layouter, Value::known(F::from(2)))?;
133    /// let y = chip.assign(&mut layouter, Value::known(F::from(3)))?;
134    ///
135    /// let res = chip.mul(&mut layouter, &x, &y, None)?;
136    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(6))?;
137    /// # });
138    /// ```
139    fn mul(
140        &self,
141        layouter: &mut impl Layouter<F>,
142        x: &Assigned,
143        y: &Assigned,
144        multiplying_constant: Option<Assigned::Element>,
145    ) -> Result<Assigned, Error>;
146
147    /// Division.
148    /// Division of `x` by `y` will make the circuit unsatisfiable if `y = 0`.
149    ///
150    /// ```
151    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
152    /// let x = chip.assign(&mut layouter, Value::known(F::from(15)))?;
153    /// let y = chip.assign(&mut layouter, Value::known(F::from(3)))?;
154    ///
155    /// let res = chip.div(&mut layouter, &x, &y)?;
156    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(5))?;
157    /// # });
158    /// ```
159    ///
160    /// ```should_panic
161    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
162    /// let zero = chip.assign(&mut layouter, Value::known(F::ZERO))?;
163    ///
164    /// let res = chip.div(&mut layouter, &zero, &zero)?;
165    /// # });
166    /// ```
167    fn div(
168        &self,
169        layouter: &mut impl Layouter<F>,
170        x: &Assigned,
171        y: &Assigned,
172    ) -> Result<Assigned, Error>;
173
174    /// Negation (additive inverse).
175    ///
176    /// ```
177    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
178    /// let x = chip.assign(&mut layouter, Value::known(F::from(42)))?;
179    ///
180    /// let res = chip.neg(&mut layouter, &x)?;
181    /// chip.assert_equal_to_fixed(&mut layouter, &res, -F::from(42))?;
182    /// # });
183    /// ```
184    fn neg(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<Assigned, Error> {
185        self.linear_combination(
186            layouter,
187            &[(-Assigned::Element::from(1), x.clone())],
188            Assigned::Element::from(0),
189        )
190    }
191
192    /// Inversion (multiplicative inverse).
193    /// The circuit will become unsatisfiable if `x = 0`.
194    ///
195    /// ```
196    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
197    /// let x = chip.assign(&mut layouter, Value::known(-F::ONE))?;
198    ///
199    /// let res = chip.inv(&mut layouter, &x)?;
200    /// chip.assert_equal_to_fixed(&mut layouter, &res, -F::ONE)?;
201    /// # });
202    /// ```
203    ///
204    /// ```should_panic
205    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
206    /// let zero = chip.assign(&mut layouter, Value::known(F::ZERO))?;
207    ///
208    /// let res = chip.inv(&mut layouter, &zero)?;
209    /// # });
210    /// ```
211    fn inv(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<Assigned, Error>;
212
213    /// Inversion (multiplicative inverse).
214    /// If `x = 0`, this function returns `0`.
215    ///
216    /// ```
217    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
218    /// // inv0 equals inv on non-zero values
219    /// let x = chip.assign(&mut layouter, Value::known(F::from(5)))?;
220    /// let res = chip.inv0(&mut layouter, &x)?;
221    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(5).invert().unwrap())?;
222    ///
223    /// // inv0 of zero does not fail and returns zero
224    /// let zero = chip.assign(&mut layouter, Value::known(F::ZERO))?;
225    /// let res = chip.inv0(&mut layouter, &zero)?;
226    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::ZERO)?;
227    /// # });
228    /// ```
229    fn inv0(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<Assigned, Error>;
230
231    /// Addition of a constant.
232    ///
233    /// This function is potentiallly more efficient than composing
234    /// [assigned_fixed](AssignmentInstructions::assign_fixed) and
235    /// [add](ArithInstructions::add).
236    ///
237    /// ```
238    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
239    /// let x = chip.assign(&mut layouter, Value::known(F::from(7)))?;
240    ///
241    /// let res = chip.add_constant(&mut layouter, &x, F::from(3))?;
242    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(10))?;
243    /// # });
244    /// ```
245    fn add_constant(
246        &self,
247        layouter: &mut impl Layouter<F>,
248        x: &Assigned,
249        constant: Assigned::Element,
250    ) -> Result<Assigned, Error> {
251        if constant == Assigned::Element::from(0) {
252            return Ok(x.clone());
253        }
254        self.linear_combination(
255            layouter,
256            &[(Assigned::Element::from(1), x.clone())],
257            constant,
258        )
259    }
260
261    /// Pair-wise addition of a constant slice to a slice of assigned values.
262    ///
263    /// This function is potentially more efficient than several calls to
264    /// [add_constant](ArithInstructions::add_constant).
265    ///
266    /// # Panics
267    ///
268    /// If the given slices do not have the same length.
269    ///
270    /// ```
271    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
272    /// let x = chip.assign(&mut layouter, Value::known(F::from(22)))?;
273    /// let y = chip.assign(&mut layouter, Value::known(F::from(7)))?;
274    ///
275    /// let res = chip.add_constants(&mut layouter, &[x, y], &[F::from(3), F::from(5)])?;
276    /// chip.assert_equal_to_fixed(&mut layouter, &res[0], F::from(25))?;
277    /// chip.assert_equal_to_fixed(&mut layouter, &res[1], F::from(12))?;
278    /// # });
279    /// ```
280    fn add_constants(
281        &self,
282        layouter: &mut impl Layouter<F>,
283        xs: &[Assigned],
284        constants: &[Assigned::Element],
285    ) -> Result<Vec<Assigned>, Error> {
286        assert_eq!(xs.len(), constants.len());
287
288        (xs.iter().zip(constants.iter()))
289            .map(|(x, c)| self.add_constant(layouter, x, c.clone()))
290            .collect()
291    }
292
293    /// Multiplication by a constant.
294    /// This function is potentially more efficient than composing
295    /// [assigned_fixed](AssignmentInstructions::assign_fixed) and
296    /// [mul](ArithInstructions::mul).
297    ///
298    /// ```
299    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
300    /// let x = chip.assign(&mut layouter, Value::known(F::from(7)))?;
301    ///
302    /// let res = chip.mul_by_constant(&mut layouter, &x, F::from(3))?;
303    /// chip.assert_equal_to_fixed(&mut layouter, &res, F::from(21))?;
304    /// # });
305    /// ```
306    fn mul_by_constant(
307        &self,
308        layouter: &mut impl Layouter<F>,
309        x: &Assigned,
310        constant: Assigned::Element,
311    ) -> Result<Assigned, Error> {
312        if constant == Assigned::Element::from(0) {
313            return self.assign_fixed(layouter, Assigned::Element::from(0));
314        }
315        if constant == Assigned::Element::from(1) {
316            return Ok(x.clone());
317        }
318        self.linear_combination(
319            layouter,
320            &[(constant, x.clone())],
321            Assigned::Element::from(0),
322        )
323    }
324
325    /// Multiplication of an element by itself.
326    fn square(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<Assigned, Error> {
327        self.mul(layouter, x, x, None)
328    }
329
330    /// Exponentiate the given assigned element to the given (constant) n.
331    /// `pow(zero, 0)` is `one` by definition.
332    fn pow(
333        &self,
334        layouter: &mut impl Layouter<F>,
335        x: &Assigned,
336        n: u64,
337    ) -> Result<Assigned, Error> {
338        if n == 0 {
339            return self.assign_fixed(layouter, Assigned::Element::from(1));
340        }
341
342        let mut n = n;
343        let mut tmp = x.clone();
344        let mut res = None;
345
346        // This is a simple square-and-multiply.
347        // TODO: It could be optimized with windows.
348        while n > 0 {
349            if n & 1 != 0 {
350                res = match res {
351                    None => Some(tmp.clone()),
352                    Some(acc) => Some(self.mul(layouter, &acc, &tmp, None)?),
353                };
354            }
355
356            n >>= 1;
357
358            if n > 0 {
359                tmp = self.square(layouter, &tmp)?;
360            }
361        }
362
363        Ok(res.unwrap())
364    }
365
366    /// Computes `a*x + b*y + c*z + k + m*x*y`.
367    fn add_and_mul(
368        &self,
369        layouter: &mut impl Layouter<F>,
370        (a, x): (Assigned::Element, &Assigned),
371        (b, y): (Assigned::Element, &Assigned),
372        (c, z): (Assigned::Element, &Assigned),
373        k: Assigned::Element,
374        m: Assigned::Element,
375    ) -> Result<Assigned, Error> {
376        let p = self.mul(layouter, x, y, None)?;
377        self.linear_combination(
378            layouter,
379            &[(a, x.clone()), (b, y.clone()), (c, z.clone()), (m, p)],
380            k,
381        )
382    }
383}
384
385#[cfg(test)]
386pub(crate) mod tests {
387    use std::{cmp::min, marker::PhantomData};
388
389    use ff::FromUniformBytes;
390    use midnight_proofs::{
391        circuit::{Layouter, SimpleFloorPlanner, Value},
392        dev::MockProver,
393        plonk::{Circuit, ConstraintSystem},
394    };
395    use rand::{RngCore, SeedableRng};
396    use rand_chacha::ChaCha8Rng;
397
398    use super::*;
399    use crate::{
400        testing_utils::{FromScratch, Invertible},
401        utils::circuit_modeling::{circuit_to_json, cost_measure_end, cost_measure_start},
402    };
403
404    #[derive(Clone, Debug)]
405    enum Operation {
406        Add,
407        Sub,
408        Mul,
409        Div,
410        Neg,
411        Inv,
412        Pow(u64),
413        AddConst,
414        MulByConst,
415        LinearComb,
416        AddAndMul,
417    }
418
419    #[derive(Clone, Debug)]
420    struct TestCircuit<F, Assigned, ArithChip>
421    where
422        Assigned: InnerValue,
423    {
424        inputs: Vec<Assigned::Element>,
425        expected: Assigned::Element,
426        operation: Operation,
427        _marker: PhantomData<(F, Assigned, ArithChip)>,
428    }
429
430    impl<F, Assigned, ArithChip> Circuit<F> for TestCircuit<F, Assigned, ArithChip>
431    where
432        F: CircuitField,
433        Assigned: InnerValue,
434        Assigned::Element: Default
435            + PartialEq
436            + From<u64>
437            + Add<Output = Assigned::Element>
438            + Neg<Output = Assigned::Element>,
439        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
440    {
441        type Config = <ArithChip as FromScratch<F>>::Config;
442        type FloorPlanner = SimpleFloorPlanner;
443        type Params = ();
444
445        fn without_witnesses(&self) -> Self {
446            unreachable!()
447        }
448
449        fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
450            let committed_instance_column = meta.instance_column();
451            let instance_column = meta.instance_column();
452            ArithChip::configure_from_scratch(
453                meta,
454                &mut vec![],
455                &mut vec![],
456                &[committed_instance_column, instance_column],
457            )
458        }
459
460        fn synthesize(
461            &self,
462            config: Self::Config,
463            mut layouter: impl Layouter<F>,
464        ) -> Result<(), Error> {
465            let chip = ArithChip::new_from_scratch(&config);
466
467            // y does not apply in tests of arity-1 functions.
468            let y_idx = min(self.inputs.len() - 1, 1);
469            let x = chip.assign(&mut layouter, Value::known(self.inputs[0].clone()))?;
470            let y = chip.assign_fixed(&mut layouter, self.inputs[y_idx].clone())?;
471            let k = self.inputs[y_idx].clone();
472
473            cost_measure_start(&mut layouter);
474            let res = match self.operation {
475                Operation::Add => chip.add(&mut layouter, &x, &y),
476                Operation::Sub => chip.sub(&mut layouter, &x, &y),
477                Operation::Mul => chip.mul(&mut layouter, &x, &y, None),
478                Operation::Div => chip.div(&mut layouter, &x, &y),
479                Operation::Neg => chip.neg(&mut layouter, &x),
480                Operation::Inv => chip.inv(&mut layouter, &x),
481                Operation::Pow(n) => chip.pow(&mut layouter, &x, n),
482                Operation::AddConst => chip.add_constant(&mut layouter, &x, k),
483                Operation::MulByConst => chip.mul_by_constant(&mut layouter, &x, k),
484                Operation::LinearComb => {
485                    let mut terms = vec![];
486                    for i in 0..(self.inputs.len() / 2) {
487                        let coeff = self.inputs[2 * i].clone();
488                        let x_val = self.inputs[2 * i + 1].clone();
489                        let x = chip.assign(&mut layouter, Value::known(x_val))?;
490                        terms.push((coeff, x));
491                    }
492                    let constant = self.inputs.last().unwrap().clone();
493                    chip.linear_combination(&mut layouter, &terms, constant)
494                }
495                Operation::AddAndMul => chip.add_and_mul(
496                    &mut layouter,
497                    (Assigned::Element::from(1), &x),
498                    (Assigned::Element::from(1), &y),
499                    (Assigned::Element::from(0), &y),
500                    Assigned::Element::from(0),
501                    Assigned::Element::from(1),
502                ),
503            }?;
504            cost_measure_end(&mut layouter);
505
506            let expected = chip.assign_fixed(&mut layouter, self.expected.clone())?;
507            chip.assert_equal(&mut layouter, &expected, &res)?;
508
509            chip.load_from_scratch(&mut layouter)
510        }
511    }
512
513    fn run<F, Assigned, ArithChip>(
514        inputs: &[Assigned::Element],
515        expected: Assigned::Element,
516        operation: Operation,
517        must_pass: bool,
518        cost_model: bool,
519        chip_name: &str,
520        op_name: &str,
521    ) where
522        F: CircuitField + FromUniformBytes<64> + Ord,
523        Assigned: InnerValue,
524        Assigned::Element: Default
525            + PartialEq
526            + From<u64>
527            + Add<Output = Assigned::Element>
528            + Neg<Output = Assigned::Element>,
529        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
530    {
531        let circuit = TestCircuit::<F, Assigned, ArithChip> {
532            inputs: inputs.to_vec(),
533            expected,
534            operation: operation.clone(),
535            _marker: PhantomData,
536        };
537        let public_inputs = vec![vec![], vec![]];
538        match MockProver::run(&circuit, public_inputs) {
539            Ok(prover) => match prover.verify() {
540                Ok(()) => assert!(must_pass),
541                Err(e) => assert!(!must_pass, "Failed verifier with error {e:?}"),
542            },
543            Err(e) => assert!(!must_pass, "Failed prover with error {e:?}"),
544        }
545
546        if cost_model {
547            circuit_to_json(chip_name, op_name, circuit);
548        }
549    }
550
551    fn i64_to_element<Element>(x: &i64) -> Element
552    where
553        Element: From<u64> + Neg<Output = Element>,
554    {
555        let mut res = Element::from(x.unsigned_abs());
556        if *x < 0 {
557            res = -res
558        }
559        res
560    }
561
562    pub fn test_add<F, Assigned, ArithChip>(chip_name: &str)
563    where
564        F: CircuitField + FromUniformBytes<64> + Ord,
565        Assigned: InnerValue,
566        Assigned::Element: Default
567            + PartialEq
568            + From<u64>
569            + Add<Output = Assigned::Element>
570            + Neg<Output = Assigned::Element>,
571        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
572    {
573        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
574        let r = rng.next_u32() as i64;
575        let s = rng.next_u32() as i64;
576        let mut cost_model = true;
577        [
578            (r, r, 2 * r, true),
579            (r, s, r + s, true),
580            (0, 0, 0, true),
581            (0, 1, 1, true),
582            (1, 0, 1, true),
583            (1, 1, 2, true),
584            (3, 5, 8, true),
585            (1, 1, 3, false),
586        ]
587        .iter()
588        .for_each(|(x, y, expected, must_pass)| {
589            let inputs = [i64_to_element(x), i64_to_element(y)];
590            let expected: Assigned::Element = i64_to_element(expected);
591            run::<F, Assigned, ArithChip>(
592                &inputs,
593                expected.clone(),
594                Operation::Add,
595                *must_pass,
596                cost_model,
597                chip_name,
598                "add",
599            );
600            run::<F, Assigned, ArithChip>(
601                &inputs,
602                expected,
603                Operation::AddConst,
604                *must_pass,
605                cost_model,
606                chip_name,
607                "add_constant",
608            );
609            cost_model = false;
610        });
611    }
612
613    pub fn test_sub<F, Assigned, ArithChip>(cost_model_name: &str)
614    where
615        F: CircuitField + FromUniformBytes<64> + Ord,
616        Assigned: InnerValue,
617        Assigned::Element: Default
618            + PartialEq
619            + From<u64>
620            + Add<Output = Assigned::Element>
621            + Neg<Output = Assigned::Element>,
622        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
623    {
624        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
625        let r = rng.next_u32() as i64;
626        let s = rng.next_u32() as i64;
627        let mut cost_model = true;
628        [
629            (r, r, 0, true),
630            (r, s, r - s, true),
631            (0, 0, 0, true),
632            (1, 0, 1, true),
633            (2, 1, 1, true),
634            (8, 5, 3, true),
635            (3, -5, 8, true),
636            (3, -3, 0, false),
637        ]
638        .iter()
639        .for_each(|(x, y, expected, must_pass)| {
640            let inputs = [i64_to_element(x), i64_to_element(y)];
641            let expected = i64_to_element(expected);
642            run::<F, Assigned, ArithChip>(
643                &inputs,
644                expected,
645                Operation::Sub,
646                *must_pass,
647                cost_model,
648                cost_model_name,
649                "sub",
650            );
651            cost_model = false;
652        });
653    }
654
655    pub fn test_mul<F, Assigned, ArithChip>(cost_model_name: &str)
656    where
657        F: CircuitField + FromUniformBytes<64> + Ord,
658        Assigned: InnerValue,
659        Assigned::Element: Default
660            + PartialEq
661            + From<u64>
662            + Add<Output = Assigned::Element>
663            + Neg<Output = Assigned::Element>,
664        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
665    {
666        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
667        let r = rng.next_u32() as i64;
668        let s = rng.next_u32() as i64;
669        let mut cost_model = true;
670        [
671            (2, r, 2 * r, true),
672            (s, 0, 0, true),
673            (0, 0, 0, true),
674            (1, 0, 0, true),
675            (-2, -1, 2, true),
676            (8, 5, 40, true),
677            (3, -5, -15, true),
678            (0, 1, 1, false),
679            (2, 1, 0, false),
680        ]
681        .iter()
682        .for_each(|(x, y, expected, must_pass)| {
683            let inputs = [i64_to_element(x), i64_to_element(y)];
684            let expected: Assigned::Element = i64_to_element(expected);
685            run::<F, Assigned, ArithChip>(
686                &inputs,
687                expected.clone(),
688                Operation::Mul,
689                *must_pass,
690                cost_model,
691                cost_model_name,
692                "mul",
693            );
694            run::<F, Assigned, ArithChip>(
695                &inputs,
696                expected,
697                Operation::MulByConst,
698                *must_pass,
699                cost_model,
700                cost_model_name,
701                "mul_by_const",
702            );
703            cost_model = false;
704        });
705    }
706
707    pub fn test_div<F, Assigned, ArithChip>(cost_model_name: &str)
708    where
709        F: CircuitField + FromUniformBytes<64> + Ord,
710        Assigned: InnerValue,
711        Assigned::Element: Default
712            + PartialEq
713            + From<u64>
714            + Add<Output = Assigned::Element>
715            + Neg<Output = Assigned::Element>,
716        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
717    {
718        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
719        let r = rng.next_u32() as i64;
720        let s = rng.next_u32() as i64;
721        let mut cost_model = true;
722        [
723            (r, r, 1, true),
724            (s, 1, s, true),
725            (0, 1, 0, true),
726            (1, 1, 1, true),
727            (2, -1, -2, true),
728            (8, 4, 2, true),
729            (91, 13, 7, true),
730            (0, 0, 0, false),
731            (3, 2, 1, false),
732            (s, s, -1, false),
733        ]
734        .iter()
735        .for_each(|(x, y, expected, must_pass)| {
736            let inputs = [i64_to_element(x), i64_to_element(y)];
737            let expected = i64_to_element(expected);
738            run::<F, Assigned, ArithChip>(
739                &inputs,
740                expected,
741                Operation::Div,
742                *must_pass,
743                cost_model,
744                cost_model_name,
745                "div",
746            );
747            cost_model = false;
748        });
749    }
750
751    pub fn test_neg<F, Assigned, ArithChip>(cost_model_name: &str)
752    where
753        F: CircuitField + FromUniformBytes<64> + Ord,
754        Assigned: InnerValue,
755        Assigned::Element: Default
756            + PartialEq
757            + From<u64>
758            + Add<Output = Assigned::Element>
759            + Neg<Output = Assigned::Element>,
760        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
761    {
762        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
763        let r = rng.next_u32() as i64;
764        let mut cost_model = true;
765        [
766            (r, -r, true),
767            (0, 0, true),
768            (1, -1, true),
769            (-1, 1, true),
770            (2, -2, true),
771            (1, 1, false),
772        ]
773        .iter()
774        .for_each(|(x, expected, must_pass)| {
775            let inputs = [i64_to_element(x)];
776            let expected = i64_to_element(expected);
777            run::<F, Assigned, ArithChip>(
778                &inputs,
779                expected,
780                Operation::Neg,
781                *must_pass,
782                cost_model,
783                cost_model_name,
784                "neg",
785            );
786            cost_model = false;
787        });
788    }
789
790    pub fn test_inv<F, Assigned, ArithChip>(cost_model_name: &str)
791    where
792        F: CircuitField + FromUniformBytes<64> + Ord,
793        Assigned: InnerValue,
794        Assigned::Element: Default
795            + PartialEq
796            + From<u64>
797            + Add<Output = Assigned::Element>
798            + Neg<Output = Assigned::Element>
799            + Invertible,
800        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
801    {
802        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
803        let zero = Assigned::Element::from(0);
804        let one = Assigned::Element::from(1);
805        let r = i64_to_element::<Assigned::Element>(&(rng.next_u32() as i64));
806        let mut cost_model = true;
807        [
808            (r.invert(), r.clone(), true),
809            (one.clone(), one.clone(), true),
810            (-one.clone(), -one.clone(), true),
811            (-one.clone(), one, false),
812            (r.clone(), r, false),
813            (zero.clone(), zero, false),
814        ]
815        .into_iter()
816        .for_each(|(x, expected, must_pass)| {
817            run::<F, Assigned, ArithChip>(
818                &[x],
819                expected,
820                Operation::Inv,
821                must_pass,
822                cost_model,
823                cost_model_name,
824                "inv",
825            );
826            cost_model = false;
827        });
828    }
829
830    pub fn test_pow<F, Assigned, ArithChip>(cost_model_name: &str)
831    where
832        F: CircuitField + FromUniformBytes<64> + Ord,
833        Assigned: InnerValue,
834        Assigned::Element: Default
835            + PartialEq
836            + From<u64>
837            + Add<Output = Assigned::Element>
838            + Neg<Output = Assigned::Element>,
839        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
840    {
841        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
842        let r = (rng.next_u32() >> 1) as i64;
843        let mut cost_model = true;
844        [
845            (r, 2, r * r, true),
846            (0, 0, 1, true),
847            (1, 0, 1, true),
848            (r, 0, 1, true),
849            (1, 1, 1, true),
850            (1, 2, 1, true),
851            (2, 3, 8, true),
852            (4, 5, 1024, true),
853            (-3, 2, 9, true),
854            (-7, 3, -343, true),
855            (2, 62, 1 << 62, true),
856            (r, 0, 0, false),
857            (2, 2, 3, false),
858        ]
859        .iter()
860        .for_each(|(x, n, expected, must_pass)| {
861            let inputs = [i64_to_element(x)];
862            let expected: Assigned::Element = i64_to_element(expected);
863            run::<F, Assigned, ArithChip>(
864                &inputs,
865                expected.clone(),
866                Operation::Pow(*n),
867                *must_pass,
868                cost_model,
869                cost_model_name,
870                "pow",
871            );
872            cost_model = false;
873        });
874    }
875
876    pub fn test_linear_combination<F, Assigned, ArithChip>(cost_model_name: &str)
877    where
878        F: CircuitField + FromUniformBytes<64> + Ord,
879        Assigned: InnerValue,
880        Assigned::Element: Default
881            + PartialEq
882            + From<u64>
883            + Add<Output = Assigned::Element>
884            + Neg<Output = Assigned::Element>,
885        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
886    {
887        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
888        let r = rng.next_u32() as i64;
889        let s = rng.next_u32() as i64;
890        let mut cost_model = true;
891        [
892            (vec![(17, r), (-4, s)], 2, 17 * r - 4 * s + 2, true),
893            (vec![], r, r, true),
894            (vec![(7, 13)], -1, 90, true),
895            (vec![(-10, 5), (5, 10)], 0, 0, true),
896            (vec![(0, 0), (0, 0)], 0, 0, true),
897            (vec![(2, 3), (4, 7), (-1, 2)], 5, 37, true),
898            (vec![(1, 1), (2, 1), (4, 1), (8, 1)], 0, 15, true),
899            (vec![(1, 3), (2, 3), (4, 3), (8, 3), (16, 3)], 7, 100, true),
900            (
901                vec![
902                    (1, 3),
903                    (2, 3),
904                    (4, 3),
905                    (8, 3),
906                    (16, 3),
907                    (1, 1),
908                    (2, 1),
909                    (4, 1),
910                    (8, 1),
911                ],
912                7,
913                115,
914                true,
915            ),
916        ]
917        .iter()
918        .for_each(|(terms, constant, expected, must_pass)| {
919            let mut inputs = vec![];
920            for (coeff, x_val) in terms {
921                inputs.push(i64_to_element(coeff));
922                inputs.push(i64_to_element(x_val));
923            }
924            inputs.push(i64_to_element(constant));
925            let expected = i64_to_element(expected);
926            run::<F, Assigned, ArithChip>(
927                &inputs,
928                expected,
929                Operation::LinearComb,
930                *must_pass,
931                cost_model,
932                cost_model_name,
933                "linear_comb",
934            );
935            cost_model = false;
936        });
937    }
938
939    pub fn test_add_and_mul<F, Assigned, ArithChip>(chip_name: &str)
940    where
941        F: CircuitField + FromUniformBytes<64> + Ord,
942        Assigned: Clone + Debug + InnerValue,
943        Assigned::Element: Clone
944            + Debug
945            + Default
946            + PartialEq
947            + From<u64>
948            + Add<Output = Assigned::Element>
949            + Neg<Output = Assigned::Element>,
950        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
951    {
952        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
953        // divide by 2 to avoid overflow in multiplication
954        let r = (rng.next_u32() as i64) / 2;
955        let s = (rng.next_u32() as i64) / 2;
956        let mut cost_model = true;
957        [
958            (r, s, r + s + r * s, true),
959            (0, 0, 0, true),
960            (1, 1, 2, false),
961            (1, r, 2 * r + 1, true),
962        ]
963        .iter()
964        .for_each(|(x, y, expected, must_pass)| {
965            let inputs = [i64_to_element(x), i64_to_element(y)];
966            let expected: Assigned::Element = i64_to_element(expected);
967            run::<F, Assigned, ArithChip>(
968                &inputs,
969                expected.clone(),
970                Operation::AddAndMul,
971                *must_pass,
972                cost_model,
973                chip_name,
974                "add_and_mul",
975            );
976            cost_model = false;
977        });
978    }
979}
midnight_circuits/instructions/arithmetic.rs

midnight_circuits/instructions/
arithmetic.rs
