midnight_circuits/instructions/
field.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//! Field instructions interface.
15
16use ff::Field;
17use midnight_proofs::{circuit::Layouter, plonk::Error};
18use num_bigint::BigUint;
19
20use super::PublicInputInstructions;
21use crate::{
22    instructions::{
23        ArithInstructions, AssertionInstructions, AssignmentInstructions, ControlFlowInstructions,
24        EqualityInstructions, ZeroInstructions,
25    },
26    types::{AssignedBit, InnerConstants, Instantiable},
27    utils::util::qnr,
28    CircuitField,
29};
30
31/// The set of circuit instructions for field operations.
32pub trait FieldInstructions<F, Assigned>:
33    AssignmentInstructions<F, Assigned>
34    + PublicInputInstructions<F, Assigned>
35    + AssertionInstructions<F, Assigned>
36    + ArithInstructions<F, Assigned>
37    + EqualityInstructions<F, Assigned>
38    + ZeroInstructions<F, Assigned>
39    + ControlFlowInstructions<F, Assigned>
40    + AssignmentInstructions<F, AssignedBit<F>>
41where
42    F: CircuitField,
43    Assigned::Element: CircuitField,
44    Assigned: Instantiable<F> + InnerConstants + Clone,
45{
46    /// The field order.
47    fn order(&self) -> BigUint;
48
49    /// Assert that the given input is a quadratic residue of the field.
50    /// This is done by exhibiting a square root.
51    fn assert_qr(&self, layouter: &mut impl Layouter<F>, x: &Assigned) -> Result<(), Error> {
52        let sqrt_x_value =
53            x.value().map(|x| Assigned::Element::sqrt(&x).expect("a quadratic residue"));
54
55        let sqrt_x = self.assign(layouter, sqrt_x_value)?;
56        let sqr = self.mul(layouter, &sqrt_x, &sqrt_x, None)?;
57        self.assert_equal(layouter, &sqr, x)
58    }
59
60    /// Returns `1` if the given input is a quadratic residue and `0` otherwise.
61    fn is_square(
62        &self,
63        layouter: &mut impl Layouter<F>,
64        x: &Assigned,
65    ) -> Result<AssignedBit<F>, Error> {
66        let is_square_value = x.value().map(|x| bool::from(x.sqrt().is_some()));
67        let is_square = self.assign(layouter, is_square_value)?;
68
69        // x is a quadratic residue iff x * qnr is not.
70        let x_times_qnr = self.mul_by_constant(layouter, x, qnr::<Assigned::Element>())?;
71        let y = self.select(layouter, &is_square, x, &x_times_qnr)?;
72
73        self.assert_qr(layouter, &y)?;
74
75        Ok(is_square)
76    }
77}
midnight_circuits/instructions/field.rs

midnight_circuits/instructions/
field.rs
