midnight_circuits/instructions/
arithmetic.rs

1// This file is part of MIDNIGHT-ZK.
2// Copyright (C) 2025 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 ff::PrimeField;
29use midnight_proofs::{circuit::Layouter, plonk::Error};
30
31use crate::{
32    instructions::{AssertionInstructions, AssignmentInstructions},
33    types::InnerValue,
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: PrimeField,
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,
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: PrimeField,
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(meta, &[committed_instance_column, instance_column])
453        }
454
455        fn synthesize(
456            &self,
457            config: Self::Config,
458            mut layouter: impl Layouter<F>,
459        ) -> Result<(), Error> {
460            let chip = ArithChip::new_from_scratch(&config);
461
462            // y does not apply in tests of arity-1 functions.
463            let y_idx = min(self.inputs.len() - 1, 1);
464            let x = chip.assign(&mut layouter, Value::known(self.inputs[0].clone()))?;
465            let y = chip.assign_fixed(&mut layouter, self.inputs[y_idx].clone())?;
466            let k = self.inputs[y_idx].clone();
467
468            let res = match self.operation {
469                Operation::Add => chip.add(&mut layouter, &x, &y),
470                Operation::Sub => chip.sub(&mut layouter, &x, &y),
471                Operation::Mul => chip.mul(&mut layouter, &x, &y, None),
472                Operation::Div => chip.div(&mut layouter, &x, &y),
473                Operation::Neg => chip.neg(&mut layouter, &x),
474                Operation::Inv => chip.inv(&mut layouter, &x),
475                Operation::Pow(n) => chip.pow(&mut layouter, &x, n),
476                Operation::AddConst => chip.add_constant(&mut layouter, &x, k),
477                Operation::MulByConst => chip.mul_by_constant(&mut layouter, &x, k),
478                Operation::LinearComb => {
479                    let mut terms = vec![];
480                    for i in 0..(self.inputs.len() / 2) {
481                        let coeff = self.inputs[2 * i].clone();
482                        let x_val = self.inputs[2 * i + 1].clone();
483                        let x = chip.assign(&mut layouter, Value::known(x_val))?;
484                        terms.push((coeff, x));
485                    }
486                    let constant = self.inputs.last().unwrap().clone();
487                    chip.linear_combination(&mut layouter, &terms, constant)
488                }
489                Operation::AddAndMul => chip.add_and_mul(
490                    &mut layouter,
491                    (Assigned::Element::from(1), &x),
492                    (Assigned::Element::from(1), &y),
493                    (Assigned::Element::from(0), &y),
494                    Assigned::Element::from(0),
495                    Assigned::Element::from(1),
496                ),
497            }?;
498
499            let expected = chip.assign_fixed(&mut layouter, self.expected.clone())?;
500            chip.assert_equal(&mut layouter, &expected, &res)?;
501
502            chip.load_from_scratch(&mut layouter)
503        }
504    }
505
506    fn run<F, Assigned, ArithChip>(
507        inputs: &[Assigned::Element],
508        expected: Assigned::Element,
509        operation: Operation,
510        must_pass: bool,
511        cost_model: bool,
512        chip_name: &str,
513        op_name: &str,
514    ) where
515        F: PrimeField + FromUniformBytes<64> + Ord,
516        Assigned: InnerValue,
517        Assigned::Element: Default
518            + PartialEq
519            + From<u64>
520            + Add<Output = Assigned::Element>
521            + Neg<Output = Assigned::Element>,
522        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
523    {
524        let circuit = TestCircuit::<F, Assigned, ArithChip> {
525            inputs: inputs.to_vec(),
526            expected,
527            operation: operation.clone(),
528            _marker: PhantomData,
529        };
530        let log2_nb_rows = 10;
531        let public_inputs = vec![vec![], vec![]];
532        match MockProver::run(log2_nb_rows, &circuit, public_inputs) {
533            Ok(prover) => match prover.verify() {
534                Ok(()) => assert!(must_pass),
535                Err(e) => assert!(!must_pass, "Failed verifier with error {e:?}"),
536            },
537            Err(e) => assert!(!must_pass, "Failed prover with error {e:?}"),
538        }
539
540        if cost_model {
541            circuit_to_json(chip_name, op_name, circuit);
542        }
543    }
544
545    fn i64_to_element<Element>(x: &i64) -> Element
546    where
547        Element: From<u64> + Neg<Output = Element>,
548    {
549        let mut res = Element::from(x.unsigned_abs());
550        if *x < 0 {
551            res = -res
552        }
553        res
554    }
555
556    pub fn test_add<F, Assigned, ArithChip>(chip_name: &str)
557    where
558        F: PrimeField + FromUniformBytes<64> + Ord,
559        Assigned: InnerValue,
560        Assigned::Element: Default
561            + PartialEq
562            + From<u64>
563            + Add<Output = Assigned::Element>
564            + Neg<Output = Assigned::Element>,
565        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
566    {
567        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
568        let r = rng.next_u32() as i64;
569        let s = rng.next_u32() as i64;
570        let mut cost_model = true;
571        [
572            (r, r, 2 * r, true),
573            (r, s, r + s, true),
574            (0, 0, 0, true),
575            (0, 1, 1, true),
576            (1, 0, 1, true),
577            (1, 1, 2, true),
578            (3, 5, 8, true),
579            (1, 1, 3, false),
580        ]
581        .iter()
582        .for_each(|(x, y, expected, must_pass)| {
583            let inputs = [i64_to_element(x), i64_to_element(y)];
584            let expected: Assigned::Element = i64_to_element(expected);
585            run::<F, Assigned, ArithChip>(
586                &inputs,
587                expected.clone(),
588                Operation::Add,
589                *must_pass,
590                cost_model,
591                chip_name,
592                "add",
593            );
594            run::<F, Assigned, ArithChip>(
595                &inputs,
596                expected,
597                Operation::AddConst,
598                *must_pass,
599                cost_model,
600                chip_name,
601                "add_constant",
602            );
603            cost_model = false;
604        });
605    }
606
607    pub fn test_sub<F, Assigned, ArithChip>(cost_model_name: &str)
608    where
609        F: PrimeField + FromUniformBytes<64> + Ord,
610        Assigned: InnerValue,
611        Assigned::Element: Default
612            + PartialEq
613            + From<u64>
614            + Add<Output = Assigned::Element>
615            + Neg<Output = Assigned::Element>,
616        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
617    {
618        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
619        let r = rng.next_u32() as i64;
620        let s = rng.next_u32() as i64;
621        let mut cost_model = true;
622        [
623            (r, r, 0, true),
624            (r, s, r - s, true),
625            (0, 0, 0, true),
626            (1, 0, 1, true),
627            (2, 1, 1, true),
628            (8, 5, 3, true),
629            (3, -5, 8, true),
630            (3, -3, 0, false),
631        ]
632        .iter()
633        .for_each(|(x, y, expected, must_pass)| {
634            let inputs = [i64_to_element(x), i64_to_element(y)];
635            let expected = i64_to_element(expected);
636            run::<F, Assigned, ArithChip>(
637                &inputs,
638                expected,
639                Operation::Sub,
640                *must_pass,
641                cost_model,
642                cost_model_name,
643                "sub",
644            );
645            cost_model = false;
646        });
647    }
648
649    pub fn test_mul<F, Assigned, ArithChip>(cost_model_name: &str)
650    where
651        F: PrimeField + FromUniformBytes<64> + Ord,
652        Assigned: InnerValue,
653        Assigned::Element: Default
654            + PartialEq
655            + From<u64>
656            + Add<Output = Assigned::Element>
657            + Neg<Output = Assigned::Element>,
658        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
659    {
660        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
661        let r = rng.next_u32() as i64;
662        let s = rng.next_u32() as i64;
663        let mut cost_model = true;
664        [
665            (2, r, 2 * r, true),
666            (s, 0, 0, true),
667            (0, 0, 0, true),
668            (1, 0, 0, true),
669            (-2, -1, 2, true),
670            (8, 5, 40, true),
671            (3, -5, -15, true),
672            (0, 1, 1, false),
673            (2, 1, 0, false),
674        ]
675        .iter()
676        .for_each(|(x, y, expected, must_pass)| {
677            let inputs = [i64_to_element(x), i64_to_element(y)];
678            let expected: Assigned::Element = i64_to_element(expected);
679            run::<F, Assigned, ArithChip>(
680                &inputs,
681                expected.clone(),
682                Operation::Mul,
683                *must_pass,
684                cost_model,
685                cost_model_name,
686                "mul",
687            );
688            run::<F, Assigned, ArithChip>(
689                &inputs,
690                expected,
691                Operation::MulByConst,
692                *must_pass,
693                cost_model,
694                cost_model_name,
695                "mul_by_const",
696            );
697            cost_model = false;
698        });
699    }
700
701    pub fn test_div<F, Assigned, ArithChip>(cost_model_name: &str)
702    where
703        F: PrimeField + FromUniformBytes<64> + Ord,
704        Assigned: InnerValue,
705        Assigned::Element: Default
706            + PartialEq
707            + From<u64>
708            + Add<Output = Assigned::Element>
709            + Neg<Output = Assigned::Element>,
710        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
711    {
712        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
713        let r = rng.next_u32() as i64;
714        let s = rng.next_u32() as i64;
715        let mut cost_model = true;
716        [
717            (r, r, 1, true),
718            (s, 1, s, true),
719            (0, 1, 0, true),
720            (1, 1, 1, true),
721            (2, -1, -2, true),
722            (8, 4, 2, true),
723            (91, 13, 7, true),
724            (0, 0, 0, false),
725            (3, 2, 1, false),
726            (s, s, -1, false),
727        ]
728        .iter()
729        .for_each(|(x, y, expected, must_pass)| {
730            let inputs = [i64_to_element(x), i64_to_element(y)];
731            let expected = i64_to_element(expected);
732            run::<F, Assigned, ArithChip>(
733                &inputs,
734                expected,
735                Operation::Div,
736                *must_pass,
737                cost_model,
738                cost_model_name,
739                "div",
740            );
741            cost_model = false;
742        });
743    }
744
745    pub fn test_neg<F, Assigned, ArithChip>(cost_model_name: &str)
746    where
747        F: PrimeField + FromUniformBytes<64> + Ord,
748        Assigned: InnerValue,
749        Assigned::Element: Default
750            + PartialEq
751            + From<u64>
752            + Add<Output = Assigned::Element>
753            + Neg<Output = Assigned::Element>,
754        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
755    {
756        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
757        let r = rng.next_u32() as i64;
758        let mut cost_model = true;
759        [
760            (r, -r, true),
761            (0, 0, true),
762            (1, -1, true),
763            (-1, 1, true),
764            (2, -2, true),
765            (1, 1, false),
766        ]
767        .iter()
768        .for_each(|(x, expected, must_pass)| {
769            let inputs = [i64_to_element(x)];
770            let expected = i64_to_element(expected);
771            run::<F, Assigned, ArithChip>(
772                &inputs,
773                expected,
774                Operation::Neg,
775                *must_pass,
776                cost_model,
777                cost_model_name,
778                "neg",
779            );
780            cost_model = false;
781        });
782    }
783
784    pub fn test_inv<F, Assigned, ArithChip>(cost_model_name: &str)
785    where
786        F: PrimeField + FromUniformBytes<64> + Ord,
787        Assigned: InnerValue,
788        Assigned::Element: Default
789            + PartialEq
790            + From<u64>
791            + Add<Output = Assigned::Element>
792            + Neg<Output = Assigned::Element>
793            + Invertible,
794        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
795    {
796        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
797        let zero = Assigned::Element::from(0);
798        let one = Assigned::Element::from(1);
799        let r = i64_to_element::<Assigned::Element>(&(rng.next_u32() as i64));
800        let mut cost_model = true;
801        [
802            (r.invert(), r.clone(), true),
803            (one.clone(), one.clone(), true),
804            (-one.clone(), -one.clone(), true),
805            (-one.clone(), one, false),
806            (r.clone(), r, false),
807            (zero.clone(), zero, false),
808        ]
809        .into_iter()
810        .for_each(|(x, expected, must_pass)| {
811            run::<F, Assigned, ArithChip>(
812                &[x],
813                expected,
814                Operation::Inv,
815                must_pass,
816                cost_model,
817                cost_model_name,
818                "inv",
819            );
820            cost_model = false;
821        });
822    }
823
824    pub fn test_pow<F, Assigned, ArithChip>(cost_model_name: &str)
825    where
826        F: PrimeField + FromUniformBytes<64> + Ord,
827        Assigned: InnerValue,
828        Assigned::Element: Default
829            + PartialEq
830            + From<u64>
831            + Add<Output = Assigned::Element>
832            + Neg<Output = Assigned::Element>,
833        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
834    {
835        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
836        let r = (rng.next_u32() >> 1) as i64;
837        let mut cost_model = true;
838        [
839            (r, 2, r * r, true),
840            (0, 0, 1, true),
841            (1, 0, 1, true),
842            (r, 0, 1, true),
843            (1, 1, 1, true),
844            (1, 2, 1, true),
845            (2, 3, 8, true),
846            (4, 5, 1024, true),
847            (-3, 2, 9, true),
848            (-7, 3, -343, true),
849            (2, 62, 1 << 62, true),
850            (r, 0, 0, false),
851            (2, 2, 3, false),
852        ]
853        .iter()
854        .for_each(|(x, n, expected, must_pass)| {
855            let inputs = [i64_to_element(x)];
856            let expected: Assigned::Element = i64_to_element(expected);
857            run::<F, Assigned, ArithChip>(
858                &inputs,
859                expected.clone(),
860                Operation::Pow(*n),
861                *must_pass,
862                cost_model,
863                cost_model_name,
864                "pow",
865            );
866            cost_model = false;
867        });
868    }
869
870    pub fn test_linear_combination<F, Assigned, ArithChip>(cost_model_name: &str)
871    where
872        F: PrimeField + FromUniformBytes<64> + Ord,
873        Assigned: InnerValue,
874        Assigned::Element: Default
875            + PartialEq
876            + From<u64>
877            + Add<Output = Assigned::Element>
878            + Neg<Output = Assigned::Element>,
879        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
880    {
881        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
882        let r = rng.next_u32() as i64;
883        let s = rng.next_u32() as i64;
884        let mut cost_model = true;
885        [
886            (vec![(17, r), (-4, s)], 2, 17 * r - 4 * s + 2, true),
887            (vec![], r, r, true),
888            (vec![(7, 13)], -1, 90, true),
889            (vec![(-10, 5), (5, 10)], 0, 0, true),
890            (vec![(0, 0), (0, 0)], 0, 0, true),
891            (vec![(2, 3), (4, 7), (-1, 2)], 5, 37, true),
892            (vec![(1, 1), (2, 1), (4, 1), (8, 1)], 0, 15, true),
893            (vec![(1, 3), (2, 3), (4, 3), (8, 3), (16, 3)], 7, 100, true),
894            (
895                vec![
896                    (1, 3),
897                    (2, 3),
898                    (4, 3),
899                    (8, 3),
900                    (16, 3),
901                    (1, 1),
902                    (2, 1),
903                    (4, 1),
904                    (8, 1),
905                ],
906                7,
907                115,
908                true,
909            ),
910        ]
911        .iter()
912        .for_each(|(terms, constant, expected, must_pass)| {
913            let mut inputs = vec![];
914            for (coeff, x_val) in terms {
915                inputs.push(i64_to_element(coeff));
916                inputs.push(i64_to_element(x_val));
917            }
918            inputs.push(i64_to_element(constant));
919            let expected = i64_to_element(expected);
920            run::<F, Assigned, ArithChip>(
921                &inputs,
922                expected,
923                Operation::LinearComb,
924                *must_pass,
925                cost_model,
926                cost_model_name,
927                "linear_comb",
928            );
929            cost_model = false;
930        });
931    }
932
933    pub fn test_add_and_mul<F, Assigned, ArithChip>(chip_name: &str)
934    where
935        F: PrimeField + FromUniformBytes<64> + Ord,
936        Assigned: Clone + Debug + InnerValue,
937        Assigned::Element: Clone
938            + Debug
939            + Default
940            + PartialEq
941            + From<u64>
942            + Add<Output = Assigned::Element>
943            + Neg<Output = Assigned::Element>,
944        ArithChip: ArithInstructions<F, Assigned> + FromScratch<F>,
945    {
946        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
947        // divide by 2 to avoid overflow in multiplication
948        let r = (rng.next_u32() as i64) / 2;
949        let s = (rng.next_u32() as i64) / 2;
950        let mut cost_model = true;
951        [
952            (r, s, r + s + r * s, true),
953            (0, 0, 0, true),
954            (1, 1, 2, false),
955            (1, r, 2 * r + 1, true),
956        ]
957        .iter()
958        .for_each(|(x, y, expected, must_pass)| {
959            let inputs = [i64_to_element(x), i64_to_element(y)];
960            let expected: Assigned::Element = i64_to_element(expected);
961            run::<F, Assigned, ArithChip>(
962                &inputs,
963                expected.clone(),
964                Operation::AddAndMul,
965                *must_pass,
966                cost_model,
967                chip_name,
968                "add_and_mul",
969            );
970            cost_model = false;
971        });
972    }
973}
midnight_circuits/instructions/arithmetic.rs

midnight_circuits/instructions/
arithmetic.rs
