midnight_circuits/instructions/
decomposition.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//! Decomposition instructions interface.
15//!
16//! It provides functions for decomposing assigned values into bits or bytes,
17//! but also composing bits or bytes into assigned values.
18//!
19//! This trait is parametrized by the `Assigned` type (a generic of this trait
20//! that implements [InnerValue](crate::types::InnerValue)) that is being
21//! decomposed/composed.
22
23use std::fmt::Debug;
24
25use midnight_proofs::{circuit::Layouter, plonk::Error};
26
27use crate::{
28    instructions::{ArithInstructions, CanonicityInstructions, ConversionInstructions},
29    types::{AssignedBit, AssignedByte, AssignedNative, InnerConstants, Instantiable},
30    CircuitField,
31};
32
33/// The set of circuit instructions for (de)composition operations.
34pub trait DecompositionInstructions<F, Assigned>:
35    CanonicityInstructions<F, Assigned>
36    + ArithInstructions<F, Assigned>
37    + ConversionInstructions<F, AssignedBit<F>, Assigned>
38    + ConversionInstructions<F, AssignedByte<F>, Assigned>
39where
40    F: CircuitField,
41    Assigned::Element: CircuitField,
42    Assigned: Instantiable<F> + InnerConstants + Clone,
43{
44    /// Returns a vector of assigned bits representing the given assigned
45    /// element in little-endian.
46    ///
47    /// The number of bits (the length of the resulting vector) can be
48    /// specified, but will be capped at `Self::Assigned::Element::NUM_BITS`. If
49    /// unspecified, the resulting vector will contain exactly
50    /// `Self::Assigned::Element::NUM_BITS` bits (the minimum number of bits
51    /// necessary to represent any element).
52    ///
53    /// If `enforce_canonical = true`, the output will be enforced to be in
54    /// **canonical form**, i.e. the underlying system of constraints can
55    /// only be satisfied by a single bit (bool) vector.
56    /// If `enforce_canonical = false`, the output `{b_i}_i` is only restricted
57    /// to satisfy: `x = sum_i 2^i b_i`, which may be satisfiable by more than
58    /// one bit vector.
59    ///
60    /// ```
61    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
62    /// let x = chip.assign(&mut layouter, Value::known(F::from(5)))?;
63    /// let bits = chip.assigned_to_le_bits(&mut layouter, &x, Some(4), true)?;
64    ///
65    /// // 5 is decomposed as 1010 in little-endian.
66    /// assert_eq!(bits.len(), 4);
67    /// chip.assert_equal_to_fixed(&mut layouter, &bits[0], true)?;
68    /// chip.assert_equal_to_fixed(&mut layouter, &bits[1], false)?;
69    /// chip.assert_equal_to_fixed(&mut layouter, &bits[2], true)?;
70    /// chip.assert_equal_to_fixed(&mut layouter, &bits[3], false)?;
71    /// # });
72    /// ```
73    ///
74    /// # Unsatisfiable Circuit
75    ///
76    /// If `x` cannot be decomposed in `nb_bits` bits when such argument is
77    /// provided.
78    ///
79    /// ```should_panic
80    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
81    /// let x = chip.assign(&mut layouter, Value::known(F::from(16)))?;
82    /// let bits = chip.assigned_to_le_bits(&mut layouter, &x, Some(4), true)?;
83    /// # });
84    /// ```
85    fn assigned_to_le_bits(
86        &self,
87        layouter: &mut impl Layouter<F>,
88        x: &Assigned,
89        nb_bits: Option<usize>,
90        enforce_canonical: bool,
91    ) -> Result<Vec<AssignedBit<F>>, Error>;
92
93    /// Same as [assigned_to_le_bits](Self::assigned_to_le_bits) but the output
94    /// bits are given in big-endian.
95    fn assigned_to_be_bits(
96        &self,
97        layouter: &mut impl Layouter<F>,
98        x: &Assigned,
99        nb_bits: Option<usize>,
100        enforce_canonical: bool,
101    ) -> Result<Vec<AssignedBit<F>>, Error> {
102        let mut bits = self.assigned_to_le_bits(layouter, x, nb_bits, enforce_canonical)?;
103        bits.reverse();
104        Ok(bits)
105    }
106
107    /// Returns a vector of assigned bytes representing the given element
108    /// in little-endian.
109    ///
110    /// The output is enforced to be in **canonical form**, that is, there
111    /// exists a single u8 vector that satisfies the underlying system of
112    /// constraints.
113    ///
114    /// The number of bytes (the length of the resulting vector) can be
115    /// specified, but will be capped at
116    /// `ceil(Self::Assigned::Element::NUM_BITS / 8)`. If unspecified, the
117    /// resulting vector will contain exactly
118    /// `ceil(Self::Assigned::Element::NUM_BITS / 8)` bytes (the minimum number
119    /// of bytes necessary to represent any element).
120    ///
121    /// ```
122    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
123    /// let x = chip.assign(&mut layouter, Value::known(F::from(0x12345678)))?;
124    /// let bytes = chip.assigned_to_le_bytes(&mut layouter, &x, Some(5))?;
125    ///
126    /// assert_eq!(bytes.len(), 5);
127    /// chip.assert_equal_to_fixed(&mut layouter, &bytes[0], 0x78)?;
128    /// chip.assert_equal_to_fixed(&mut layouter, &bytes[1], 0x56)?;
129    /// chip.assert_equal_to_fixed(&mut layouter, &bytes[2], 0x34)?;
130    /// chip.assert_equal_to_fixed(&mut layouter, &bytes[3], 0x12)?;
131    /// chip.assert_equal_to_fixed(&mut layouter, &bytes[4], 0x00)?;
132    /// # });
133    /// ```
134    ///
135    /// # Unsatisfiable Circuit
136    ///
137    /// If `x` cannot be decomposed in `nb_bytes` bytes when such argument is
138    /// provided.
139    ///
140    /// ```should_panic
141    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
142    /// let x = chip.assign(&mut layouter, Value::known(F::from(256)))?;
143    /// let bytes = chip.assigned_to_le_bytes(&mut layouter, &x, Some(1))?;
144    /// # });
145    /// ```
146    fn assigned_to_le_bytes(
147        &self,
148        layouter: &mut impl Layouter<F>,
149        x: &Assigned,
150        nb_bytes: Option<usize>,
151    ) -> Result<Vec<AssignedByte<F>>, Error>;
152
153    /// Same as [assigned_to_le_bytes](Self::assigned_to_le_bytes) but the
154    /// output bytes are given in big-endian.
155    fn assigned_to_be_bytes(
156        &self,
157        layouter: &mut impl Layouter<F>,
158        x: &Assigned,
159        nb_bytes: Option<usize>,
160    ) -> Result<Vec<AssignedByte<F>>, Error> {
161        let mut bytes = self.assigned_to_le_bytes(layouter, x, nb_bytes)?;
162        bytes.reverse();
163        Ok(bytes)
164    }
165
166    /// Returns the element represented by the given vector of assigned bits,
167    /// by interpreting it as a little-endian bit encoding.
168    ///
169    /// The number of input bits can be arbitrary.
170    ///
171    /// ```
172    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
173    /// let b0 = chip.assign(&mut layouter, Value::known(false))?;
174    /// let b1 = chip.assign(&mut layouter, Value::known(true))?;
175    /// let b2 = chip.assign(&mut layouter, Value::known(true))?;
176    ///
177    /// let x = chip.assigned_from_le_bits(&mut layouter, &[b0, b1, b2])?;
178    /// chip.assert_equal_to_fixed(&mut layouter, &x, F::from(6))?;
179    /// # });
180    /// ```
181    fn assigned_from_le_bits(
182        &self,
183        layouter: &mut impl Layouter<F>,
184        bits: &[AssignedBit<F>],
185    ) -> Result<Assigned, Error> {
186        let mut coeff = Assigned::Element::from(1);
187        let mut terms = vec![];
188        for b in bits {
189            let b_as_element: Assigned = self.convert(layouter, b)?;
190            terms.push((coeff, b_as_element));
191            coeff = coeff + coeff; // double the coeff
192        }
193        let terms = terms.iter().map(|(c, b)| (*c, b.clone())).collect::<Vec<_>>();
194        self.linear_combination(layouter, &terms, Assigned::Element::from(0))
195    }
196
197    /// Same as [assigned_from_le_bits](Self::assigned_from_le_bits) but the
198    /// output bits are given in big-endian.
199    fn assigned_from_be_bits(
200        &self,
201        layouter: &mut impl Layouter<F>,
202        bits: &[AssignedBit<F>],
203    ) -> Result<Assigned, Error> {
204        let mut bits = bits.to_vec();
205        bits.reverse();
206        self.assigned_from_le_bits(layouter, &bits)
207    }
208
209    /// Returns the element represented by the given vector of assigned bytes,
210    /// by interpreting it in little-endian.
211    ///
212    /// For example, the sequence of bytes `[0x12, 0x34, 0x56, 0x78]`
213    /// will be converted into an element encoding value `0x78563412`.
214    ///
215    /// The number of input bytes can be arbitrary.
216    ///
217    /// ```
218    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
219    /// let b0 = chip.assign(&mut layouter, Value::known(0x12))?;
220    /// let b1 = chip.assign(&mut layouter, Value::known(0x34))?;
221    /// let b2 = chip.assign(&mut layouter, Value::known(0x56))?;
222    /// let b3 = chip.assign(&mut layouter, Value::known(0x78))?;
223    ///
224    /// let x = chip.assigned_from_le_bytes(&mut layouter, &[b0, b1, b2, b3])?;
225    /// chip.assert_equal_to_fixed(&mut layouter, &x, F::from(0x78563412))?;
226    /// # });
227    /// ```
228    fn assigned_from_le_bytes(
229        &self,
230        layouter: &mut impl Layouter<F>,
231        bytes: &[AssignedByte<F>],
232    ) -> Result<Assigned, Error> {
233        let mut coeff = Assigned::Element::from(1);
234        let mut terms = vec![];
235        for byte in bytes {
236            let byte_as_element: Assigned = self.convert(layouter, byte)?;
237            terms.push((coeff, byte_as_element));
238            coeff = Assigned::Element::from(256) * coeff; // scale the coeff
239        }
240        let terms = terms.iter().map(|(c, b)| (*c, b.clone())).collect::<Vec<_>>();
241        self.linear_combination(layouter, &terms, Assigned::Element::from(0))
242    }
243
244    /// Same as [assigned_from_le_bytes](Self::assigned_from_le_bytes) but the
245    /// output bytes are given in big-endian.
246    fn assigned_from_be_bytes(
247        &self,
248        layouter: &mut impl Layouter<F>,
249        bytes: &[AssignedByte<F>],
250    ) -> Result<Assigned, Error> {
251        let mut bytes = bytes.to_vec();
252        bytes.reverse();
253        self.assigned_from_le_bytes(layouter, &bytes)
254    }
255
256    /// Returns a vector of [AssignedNative] values representing the given
257    /// element in little-endian.
258    /// The output length may be specified, in which case this function will be
259    /// imposing an upper bound on the value of `x`.
260    ///
261    /// This vector is NOT guaranteed to be canonical, but it is guaranteed to
262    /// satisfy: `x = sum_i 2^{i * nb_bits_per_chunk} * chunks_i`,
263    /// when interpreting `chunks_i` as `Assigned` values instead of
264    /// [AssignedNative] values. Note that this is possible because
265    /// `Assigned::Element : PrimeField`.
266    ///
267    /// # Unsatisfiable Circuit
268    ///
269    /// If `x` cannot be decomposed in `nb_chunks` chunks of `nb_bits_per_chunk`
270    /// bits, when the argument `nb_chunks` is provided.
271    ///
272    /// # Panics
273    ///
274    /// If `nb_bits_per_chunk >= F::NUM_BITS`.
275    fn assigned_to_le_chunks(
276        &self,
277        layouter: &mut impl Layouter<F>,
278        x: &Assigned,
279        nb_bits_per_chunk: usize,
280        nb_chunks: Option<usize>,
281    ) -> Result<Vec<AssignedNative<F>>, Error>;
282
283    /// Sign function as described in RFC 9380. `sgn0(x) := x mod 2`.
284    fn sgn0(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<AssignedBit<F>, Error> {
285        let bits = self.assigned_to_le_bits(layouter, x, None, true)?;
286        Ok(bits[0].clone())
287    }
288}
289
290/// Pow2Range range-check instructions.
291pub trait Pow2RangeInstructions<F: CircuitField>: Debug + Clone {
292    /// Asserts that all the given assigned values in the range `[0, 2^n)`.
293    fn assert_values_lower_than_2_pow_n(
294        &self,
295        layouter: &mut impl Layouter<F>,
296        values: &[AssignedNative<F>],
297        n: usize,
298    ) -> Result<(), Error>;
299}
300
301#[cfg(test)]
302pub(crate) mod tests {
303    use std::marker::PhantomData;
304
305    use ff::{Field, FromUniformBytes};
306    use midnight_proofs::{
307        circuit::{Layouter, SimpleFloorPlanner},
308        dev::MockProver,
309        plonk::{Circuit, ConstraintSystem},
310    };
311    use num_bigint::BigUint;
312    use num_traits::One;
313    use rand::{RngCore, SeedableRng};
314    use rand_chacha::ChaCha8Rng;
315
316    use super::*;
317    use crate::{
318        instructions::{AssertionInstructions, AssignmentInstructions},
319        testing_utils::FromScratch,
320        types::InnerValue,
321        utils::{
322            circuit_modeling::{circuit_to_json, cost_measure_end, cost_measure_start},
323            util::big_to_fe,
324        },
325    };
326
327    #[derive(Clone, Debug)]
328    enum Endianess {
329        LE,
330        BE,
331    }
332
333    #[derive(Clone, Debug)]
334    enum Operation {
335        ToBits,
336        ToBytes,
337        FromBits,
338        FromBytes,
339        Sgn0,
340    }
341
342    #[derive(Clone, Debug)]
343    struct TestCircuit<F, Assigned, DecompChip, AuxChip>
344    where
345        Assigned: InnerValue,
346    {
347        x: Assigned::Element,
348        decomposed: Vec<u8>,
349        nb_parts: Option<usize>,
350        endianess: Endianess,
351        operation: Operation,
352        _marker: PhantomData<(F, Assigned, DecompChip, AuxChip)>,
353    }
354
355    impl<F, Assigned, DecompChip, AuxChip> Circuit<F> for TestCircuit<F, Assigned, DecompChip, AuxChip>
356    where
357        F: CircuitField,
358        Assigned::Element: CircuitField,
359        Assigned: Instantiable<F> + InnerConstants + Clone,
360        DecompChip: DecompositionInstructions<F, Assigned> + FromScratch<F>,
361        AuxChip: AssertionInstructions<F, AssignedBit<F>>
362            + AssertionInstructions<F, AssignedByte<F>>
363            + AssignmentInstructions<F, AssignedBit<F>>
364            + AssignmentInstructions<F, AssignedByte<F>>
365            + FromScratch<F>,
366    {
367        type Config = (
368            <DecompChip as FromScratch<F>>::Config,
369            <AuxChip as FromScratch<F>>::Config,
370        );
371        type FloorPlanner = SimpleFloorPlanner;
372        type Params = ();
373
374        fn without_witnesses(&self) -> Self {
375            unreachable!()
376        }
377
378        fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
379            let committed_instance_column = meta.instance_column();
380            let instance_column = meta.instance_column();
381            let instance_columns = [committed_instance_column, instance_column];
382            let mut advice_columns = vec![];
383            let mut fixed_columns = vec![];
384            (
385                DecompChip::configure_from_scratch(
386                    meta,
387                    &mut advice_columns,
388                    &mut fixed_columns,
389                    &instance_columns,
390                ),
391                AuxChip::configure_from_scratch(
392                    meta,
393                    &mut advice_columns,
394                    &mut fixed_columns,
395                    &instance_columns,
396                ),
397            )
398        }
399
400        fn synthesize(
401            &self,
402            config: Self::Config,
403            mut layouter: impl Layouter<F>,
404        ) -> Result<(), Error> {
405            let chip = DecompChip::new_from_scratch(&config.0);
406            let aux_chip = AuxChip::new_from_scratch(&config.1);
407
408            use Endianess::*;
409            cost_measure_start(&mut layouter);
410            match self.operation {
411                Operation::ToBits => {
412                    let x: Assigned = chip.assign_fixed(&mut layouter, self.x)?;
413                    let nb_bits = self.nb_parts;
414                    let bits = match self.endianess {
415                        LE => chip.assigned_to_le_bits(&mut layouter, &x, nb_bits, true),
416                        BE => chip.assigned_to_be_bits(&mut layouter, &x, nb_bits, true),
417                    }?;
418                    assert_eq!(bits.len(), self.decomposed.len());
419                    bits.iter().zip(self.decomposed.iter()).try_for_each(|(bit, expected)| {
420                        aux_chip.assert_equal_to_fixed(&mut layouter, bit, *expected == 1)
421                    })
422                }
423                Operation::ToBytes => {
424                    let x: Assigned = chip.assign_fixed(&mut layouter, self.x)?;
425                    let nb_bytes = self.nb_parts;
426                    let bytes = match self.endianess {
427                        LE => chip.assigned_to_le_bytes(&mut layouter, &x, nb_bytes),
428                        BE => chip.assigned_to_be_bytes(&mut layouter, &x, nb_bytes),
429                    }?;
430                    bytes.iter().zip(self.decomposed.iter()).try_for_each(|(bit, expected)| {
431                        aux_chip.assert_equal_to_fixed(&mut layouter, bit, *expected)
432                    })
433                }
434                Operation::FromBits => {
435                    let bits = self
436                        .decomposed
437                        .iter()
438                        .map(|b| chip.assign_fixed(&mut layouter, *b == 1))
439                        .collect::<Result<Vec<_>, Error>>()?;
440                    let x = match self.endianess {
441                        LE => chip.assigned_from_le_bits(&mut layouter, &bits),
442                        BE => chip.assigned_from_be_bits(&mut layouter, &bits),
443                    }?;
444                    chip.assert_equal_to_fixed(&mut layouter, &x, self.x)
445                }
446                Operation::FromBytes => {
447                    let bytes = self
448                        .decomposed
449                        .iter()
450                        .map(|byte| aux_chip.assign_fixed(&mut layouter, *byte))
451                        .collect::<Result<Vec<_>, Error>>()?;
452                    let x = match self.endianess {
453                        LE => chip.assigned_from_le_bytes(&mut layouter, &bytes),
454                        BE => chip.assigned_from_be_bytes(&mut layouter, &bytes),
455                    }?;
456                    chip.assert_equal_to_fixed(&mut layouter, &x, self.x)
457                }
458                Operation::Sgn0 => {
459                    // Handle 0.
460                    let decomposed = if self.decomposed.is_empty() {
461                        &vec![0u8]
462                    } else {
463                        &self.decomposed
464                    };
465                    let x: Assigned = chip.assign_fixed(&mut layouter, self.x)?;
466                    let sign = chip.sgn0(&mut layouter, &x)?;
467                    let lsb = match self.endianess {
468                        LE => decomposed[0] & 1,
469                        BE => decomposed.last().unwrap() & 1,
470                    };
471                    aux_chip.assert_equal_to_fixed(&mut layouter, &sign, lsb == 1u8)
472                }
473            }?;
474            cost_measure_end(&mut layouter);
475
476            chip.load_from_scratch(&mut layouter)?;
477            aux_chip.load_from_scratch(&mut layouter)
478        }
479    }
480
481    #[allow(clippy::too_many_arguments)]
482    fn run<F, Assigned, DecompChip, AuxChip>(
483        x: Assigned::Element,
484        decomposed: &[u8],
485        nb_parts: Option<usize>,
486        endianess: Endianess,
487        operation: Operation,
488        must_pass: bool,
489        cost_model: bool,
490        chip_name: &str,
491        op_name: &str,
492    ) where
493        F: CircuitField + FromUniformBytes<64> + Ord,
494        Assigned::Element: CircuitField,
495        Assigned: Instantiable<F> + InnerConstants + Clone,
496        DecompChip: DecompositionInstructions<F, Assigned> + FromScratch<F>,
497        AuxChip: AssertionInstructions<F, AssignedBit<F>>
498            + AssertionInstructions<F, AssignedByte<F>>
499            + AssignmentInstructions<F, AssignedBit<F>>
500            + AssignmentInstructions<F, AssignedByte<F>>
501            + FromScratch<F>,
502    {
503        let circuit = TestCircuit::<F, Assigned, DecompChip, AuxChip> {
504            x,
505            decomposed: decomposed.to_vec(),
506            nb_parts,
507            endianess,
508            operation,
509            _marker: PhantomData,
510        };
511        let public_inputs = vec![vec![], vec![]];
512        match MockProver::run(&circuit, public_inputs) {
513            Ok(prover) => match prover.verify() {
514                Ok(()) => assert!(must_pass),
515                Err(e) => assert!(!must_pass, "Failed verifier with error {e:?}"),
516            },
517            Err(e) => assert!(!must_pass, "Failed prover with error {e:?}"),
518        }
519
520        if cost_model {
521            circuit_to_json(chip_name, op_name, circuit);
522        }
523    }
524
525    /// The output type is u8 instead of bool because, for readability, we
526    /// express the test vectors with integers `0` and `1` instead of
527    /// `false` and `true` (respectively).
528    fn biguint_to_bits(n: &BigUint) -> Vec<u8> {
529        (0..(n.bits() as usize)).map(|i| if n.bit(i as u64) { 1 } else { 0 }).collect()
530    }
531
532    fn biguint_to_bytes(n: &BigUint) -> Vec<u8> {
533        biguint_to_bits(n)
534            .chunks(8)
535            .map(|chunk| chunk.iter().enumerate().map(|(i, bi)| (1 << i) * bi).sum())
536            .collect()
537    }
538
539    macro_rules! parse {
540        ($n:expr) => {
541            Assigned::Element::from($n)
542        };
543    }
544
545    pub fn test_bit_decomposition<F, Assigned, DecompChip, AuxChip>(name: &str)
546    where
547        F: CircuitField + FromUniformBytes<64> + Ord,
548        Assigned::Element: CircuitField,
549        Assigned: Instantiable<F> + InnerConstants + Clone,
550        DecompChip: DecompositionInstructions<F, Assigned> + FromScratch<F>,
551        AuxChip: AssertionInstructions<F, AssignedBit<F>>
552            + AssertionInstructions<F, AssignedByte<F>>
553            + AssignmentInstructions<F, AssignedBit<F>>
554            + AssignmentInstructions<F, AssignedByte<F>>
555            + FromScratch<F>,
556    {
557        use Endianess::*;
558        use Operation::*;
559        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
560        let r = rng.next_u64();
561        let mut bits_of_r = biguint_to_bits(&r.into());
562        bits_of_r.resize(64, 0);
563        let m = Assigned::Element::modulus();
564        let m_minus_1 = m.clone() - BigUint::one();
565        let mut cost_model = true;
566        [
567            // These test vectors are designed in little-endian
568            (parse!(r), bits_of_r, Some(64), true, true),
569            (parse!(0), biguint_to_bits(&m), None, false, true),
570            (-parse!(1), biguint_to_bits(&m_minus_1), None, true, true),
571            (parse!(0), vec![], Some(0), true, true),
572            (parse!(0), vec![0], Some(1), true, true),
573            (parse!(1), vec![1], Some(1), true, true),
574            (parse!(3), vec![1, 1, 0, 0, 0], Some(5), true, true),
575            (parse!(3), vec![0, 0, 0, 1, 1], Some(5), false, false),
576        ]
577        .iter()
578        .for_each(|(x, bits, nb_bits, ok_to, ok_from)| {
579            let mut rev = bits.clone();
580            rev.reverse();
581            run::<F, Assigned, DecompChip, AuxChip>(
582                *x, bits, *nb_bits, LE, ToBits, *ok_to, cost_model, name, "to_bits",
583            );
584            run::<F, Assigned, DecompChip, AuxChip>(
585                *x,
586                bits,
587                None,
588                LE,
589                FromBits,
590                *ok_from,
591                cost_model,
592                name,
593                "from_bits",
594            );
595            cost_model = false;
596            run::<F, Assigned, DecompChip, AuxChip>(
597                *x, &rev, *nb_bits, BE, ToBits, *ok_to, false, "", "",
598            );
599            run::<F, Assigned, DecompChip, AuxChip>(
600                *x, &rev, None, BE, FromBits, *ok_from, false, "", "",
601            );
602        });
603    }
604
605    pub fn test_byte_decomposition<F, Assigned, DecompChip, AuxChip>(name: &str)
606    where
607        F: CircuitField + FromUniformBytes<64> + Ord,
608        Assigned::Element: CircuitField,
609        Assigned: Instantiable<F> + InnerConstants + Clone,
610        DecompChip: DecompositionInstructions<F, Assigned> + FromScratch<F>,
611        AuxChip: AssertionInstructions<F, AssignedBit<F>>
612            + AssertionInstructions<F, AssignedByte<F>>
613            + AssignmentInstructions<F, AssignedBit<F>>
614            + AssignmentInstructions<F, AssignedByte<F>>
615            + FromScratch<F>,
616    {
617        use Endianess::*;
618        use Operation::*;
619
620        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
621        let r = rng.next_u64();
622        let mut bytes_of_r = biguint_to_bytes(&r.into());
623        bytes_of_r.resize(8, 0);
624        let m = Assigned::Element::modulus();
625        let m_minus_1 = m.clone() - BigUint::one();
626        let mut cost_model = true;
627        [
628            // These test vectors are designed in little-endian
629            (parse!(r), bytes_of_r, Some(8), true, true),
630            (parse!(0), biguint_to_bytes(&m), None, false, true),
631            (-parse!(1), biguint_to_bytes(&m_minus_1), None, true, true),
632            (parse!(0), vec![], Some(0), true, true),
633            (parse!(255), vec![255, 0], Some(2), true, true),
634            (parse!(256), vec![0, 1], Some(2), true, true),
635            (parse!(256), vec![1, 0], Some(2), false, false),
636            (
637                parse!(0x12345678),
638                vec![0x78, 0x56, 0x34, 0x12, 0x00, 0x00, 0x00],
639                Some(7),
640                true,
641                true,
642            ),
643        ]
644        .iter()
645        .for_each(|(x, bytes, nb_bytes, ok_to, ok_from)| {
646            let mut rev = bytes.clone();
647            rev.reverse();
648            run::<F, Assigned, DecompChip, AuxChip>(
649                *x, bytes, *nb_bytes, LE, ToBytes, *ok_to, cost_model, name, "to_bytes",
650            );
651            run::<F, Assigned, DecompChip, AuxChip>(
652                *x,
653                bytes,
654                None,
655                LE,
656                FromBytes,
657                *ok_from,
658                cost_model,
659                name,
660                "from_bytes",
661            );
662            cost_model = false;
663            run::<F, Assigned, DecompChip, AuxChip>(
664                *x, &rev, *nb_bytes, BE, ToBytes, *ok_to, false, "", "",
665            );
666            run::<F, Assigned, DecompChip, AuxChip>(
667                *x, &rev, None, BE, FromBytes, *ok_from, false, "", "",
668            );
669        });
670    }
671
672    pub fn test_sgn0<F, Assigned, DecompChip, AuxChip>(name: &str)
673    where
674        F: CircuitField + FromUniformBytes<64> + Ord,
675        Assigned::Element: CircuitField,
676        Assigned: Instantiable<F> + InnerConstants + Clone,
677        DecompChip: DecompositionInstructions<F, Assigned> + FromScratch<F>,
678        AuxChip: AssertionInstructions<F, AssignedBit<F>>
679            + AssertionInstructions<F, AssignedByte<F>>
680            + AssignmentInstructions<F, AssignedBit<F>>
681            + AssignmentInstructions<F, AssignedByte<F>>
682            + FromScratch<F>,
683    {
684        // Random test cases.
685        let mut rng = ChaCha8Rng::seed_from_u64(0xc0ffee);
686        let random_test_cases: Vec<_> =
687            (0..100).map(|_| Assigned::Element::random(&mut rng)).collect();
688
689        // Edge case where x = 0 | p_mid | 1.
690        // (same as the modulus p but with the msb turned to 0).
691        let mut p = Assigned::Element::modulus();
692        p.set_bit(F::NUM_BITS as u64 - 1, false);
693        let x = big_to_fe(p.clone());
694
695        let edge_cases = &[
696            parse!(0),
697            parse!(1),
698            x,
699            big_to_fe(Assigned::Element::modulus() - BigUint::one()),
700        ];
701
702        let test_cases = &[random_test_cases.as_slice(), edge_cases].concat();
703
704        test_cases.iter().enumerate().for_each(|(i, x)| {
705            let bytes = biguint_to_bytes(&x.to_biguint());
706            run::<F, Assigned, DecompChip, AuxChip>(
707                *x,
708                &bytes,
709                None,
710                Endianess::LE,
711                Operation::Sgn0,
712                true,
713                i == 0, // Cost model on for the first example.
714                name,
715                "sgn0",
716            );
717        })
718    }
719}
midnight_circuits/instructions/decomposition.rs

midnight_circuits/instructions/
decomposition.rs
