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

midnight_circuits/instructions/
field.rs
