midnight_circuits/instructions/
binary.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//! Binary instructions interface.
15//!
16//! It provides functions for performing Boolean operations over [AssignedBit]s.
17
18use midnight_proofs::{circuit::Layouter, plonk::Error};
19
20use crate::{types::AssignedBit, CircuitField};
21
22/// The set of circuit instructions for binary operations.
23pub trait BinaryInstructions<F: CircuitField> {
24    /// Conjunction of the given assigned bits.
25    ///
26    /// # Panics
27    ///
28    /// If `bits` is empty.
29    ///
30    /// ```
31    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
32    /// let b0 = chip.assign(&mut layouter, Value::known(false))?;
33    /// let b1 = chip.assign(&mut layouter, Value::known(true))?;
34    ///
35    /// let res = chip.and(&mut layouter, &[b0, b1])?;
36    /// chip.assert_equal_to_fixed(&mut layouter, &res, false)?;
37    /// # });
38    /// ```
39    ///
40    /// ```should_panic
41    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
42    /// let res = chip.and(&mut layouter, &[])?;
43    /// # });
44    /// ```
45    fn and(
46        &self,
47        layouter: &mut impl Layouter<F>,
48        bits: &[AssignedBit<F>],
49    ) -> Result<AssignedBit<F>, Error>;
50
51    /// Disjunction of the given assigned bits.
52    ///
53    /// # Panics
54    ///
55    /// If `bits` is empty.
56    ///
57    /// ```
58    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
59    /// let b0 = chip.assign(&mut layouter, Value::known(false))?;
60    /// let b1 = chip.assign(&mut layouter, Value::known(true))?;
61    ///
62    /// let res = chip.or(&mut layouter, &[b0, b1])?;
63    /// chip.assert_equal_to_fixed(&mut layouter, &res, true)?;
64    /// # });
65    /// ```
66    fn or(
67        &self,
68        layouter: &mut impl Layouter<F>,
69        bits: &[AssignedBit<F>],
70    ) -> Result<AssignedBit<F>, Error>;
71
72    /// Exclusive-OR of all the given assigned bits.
73    ///
74    /// # Panics
75    ///
76    /// If `bits` is empty.
77    ///
78    /// ```
79    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
80    /// let b0 = chip.assign(&mut layouter, Value::known(false))?;
81    /// let b1 = chip.assign(&mut layouter, Value::known(true))?;
82    /// let b2 = chip.assign(&mut layouter, Value::known(true))?;
83    ///
84    /// let res = chip.xor(&mut layouter, &[b0, b1, b2])?;
85    /// chip.assert_equal_to_fixed(&mut layouter, &res, false)?;
86    /// # });
87    /// ```
88    fn xor(
89        &self,
90        layouter: &mut impl Layouter<F>,
91        bits: &[AssignedBit<F>],
92    ) -> Result<AssignedBit<F>, Error>;
93
94    /// Negation of the given assigned bit.
95    ///
96    /// ```
97    /// # midnight_circuits::run_test_native_gadget!(chip, layouter, {
98    /// let b = chip.assign(&mut layouter, Value::known(false))?;
99    ///
100    /// let res = chip.not(&mut layouter, &b)?;
101    /// chip.assert_equal_to_fixed(&mut layouter, &res, true)?;
102    /// # });
103    /// ```
104    fn not(
105        &self,
106        layouter: &mut impl Layouter<F>,
107        bit: &AssignedBit<F>,
108    ) -> Result<AssignedBit<F>, Error>;
109}
110
111#[cfg(test)]
112pub(crate) mod tests {
113    use std::{cmp::min, marker::PhantomData};
114
115    use ff::FromUniformBytes;
116    use midnight_proofs::{
117        circuit::{Layouter, SimpleFloorPlanner, Value},
118        dev::MockProver,
119        plonk::{Circuit, ConstraintSystem},
120    };
121
122    use super::*;
123    use crate::{
124        instructions::{AssertionInstructions, AssignmentInstructions},
125        testing_utils::FromScratch,
126        utils::circuit_modeling::{circuit_to_json, cost_measure_end, cost_measure_start},
127    };
128
129    #[derive(Clone, Copy, Debug)]
130    enum Operation {
131        And,
132        Or,
133        Xor,
134        Not,
135    }
136
137    #[derive(Clone, Debug)]
138    struct TestCircuit<F, BinaryChip> {
139        inputs: Vec<bool>,
140        expected: bool,
141        operation: Operation,
142        _marker: PhantomData<(F, BinaryChip)>,
143    }
144
145    impl<F, BinaryChip> Circuit<F> for TestCircuit<F, BinaryChip>
146    where
147        F: CircuitField,
148        BinaryChip: BinaryInstructions<F>
149            + AssignmentInstructions<F, AssignedBit<F>>
150            + AssertionInstructions<F, AssignedBit<F>>
151            + FromScratch<F>,
152    {
153        type Config = <BinaryChip as FromScratch<F>>::Config;
154        type FloorPlanner = SimpleFloorPlanner;
155        type Params = ();
156
157        fn without_witnesses(&self) -> Self {
158            unreachable!()
159        }
160
161        fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
162            let committed_instance_column = meta.instance_column();
163            let instance_column = meta.instance_column();
164            BinaryChip::configure_from_scratch(
165                meta,
166                &mut vec![],
167                &mut vec![],
168                &[committed_instance_column, instance_column],
169            )
170        }
171
172        fn synthesize(
173            &self,
174            config: Self::Config,
175            mut layouter: impl Layouter<F>,
176        ) -> Result<(), Error> {
177            let chip = BinaryChip::new_from_scratch(&config);
178
179            // b2 does not apply in tests of arity-1 functions.
180            let b2_idx = min(self.inputs.len() - 1, 1);
181            let b1 = chip.assign(&mut layouter, Value::known(self.inputs[0]))?;
182            let b2 = chip.assign(&mut layouter, Value::known(self.inputs[b2_idx]))?;
183
184            cost_measure_start(&mut layouter);
185            let res = match self.operation {
186                Operation::And => chip.and(&mut layouter, &[b1, b2]),
187                Operation::Or => chip.or(&mut layouter, &[b1, b2]),
188                Operation::Xor => chip.xor(&mut layouter, &[b1, b2]),
189                Operation::Not => chip.not(&mut layouter, &b1),
190            }?;
191            cost_measure_end(&mut layouter);
192
193            chip.assert_equal_to_fixed(&mut layouter, &res, self.expected)?;
194
195            chip.load_from_scratch(&mut layouter)
196        }
197    }
198
199    fn run<F, BinaryChip>(
200        inputs: &[bool],
201        expected: bool,
202        operation: Operation,
203        must_pass: bool,
204        cost_model: bool,
205        chip_name: &str,
206        op_name: &str,
207    ) where
208        F: CircuitField + FromUniformBytes<64> + Ord,
209        BinaryChip: BinaryInstructions<F>
210            + AssignmentInstructions<F, AssignedBit<F>>
211            + AssertionInstructions<F, AssignedBit<F>>
212            + FromScratch<F>,
213    {
214        let circuit = TestCircuit::<F, BinaryChip> {
215            inputs: inputs.to_vec(),
216            expected,
217            operation,
218            _marker: PhantomData,
219        };
220        let public_inputs = vec![vec![], vec![]];
221        match MockProver::run(&circuit, public_inputs) {
222            Ok(prover) => match prover.verify() {
223                Ok(()) => assert!(must_pass),
224                Err(e) => assert!(!must_pass, "Failed verifier with error {e:?}"),
225            },
226            Err(e) => assert!(!must_pass, "Failed prover with error {e:?}"),
227        }
228
229        if cost_model {
230            circuit_to_json(chip_name, op_name, circuit);
231        }
232    }
233
234    fn test_binary_op<F, BinaryChip>(
235        inputs: &[u8],
236        expected: u8,
237        operation: Operation,
238        cost_model: bool,
239        chip_name: &str,
240        op_name: &str,
241    ) where
242        F: CircuitField + FromUniformBytes<64> + Ord,
243        BinaryChip: BinaryInstructions<F>
244            + AssignmentInstructions<F, AssignedBit<F>>
245            + AssertionInstructions<F, AssignedBit<F>>
246            + FromScratch<F>,
247    {
248        let inputs = inputs.iter().map(|b| *b == 1).collect::<Vec<_>>();
249        let expected = expected == 1;
250        run::<F, BinaryChip>(
251            &inputs, expected, operation, true, cost_model, chip_name, op_name,
252        );
253        run::<F, BinaryChip>(
254            &inputs, !expected, operation, false, false, chip_name, op_name,
255        );
256    }
257
258    pub fn test_and<F, BinaryChip>(name: &str)
259    where
260        F: CircuitField + FromUniformBytes<64> + Ord,
261        BinaryChip: BinaryInstructions<F>
262            + AssignmentInstructions<F, AssignedBit<F>>
263            + AssertionInstructions<F, AssignedBit<F>>
264            + FromScratch<F>,
265    {
266        test_binary_op::<F, BinaryChip>(&[0, 0], 0, Operation::And, true, name, "and");
267        test_binary_op::<F, BinaryChip>(&[0, 1], 0, Operation::And, false, "", "");
268        test_binary_op::<F, BinaryChip>(&[1, 0], 0, Operation::And, false, "", "");
269        test_binary_op::<F, BinaryChip>(&[1, 1], 1, Operation::And, false, "", "");
270    }
271
272    pub fn test_or<F, BinaryChip>(name: &str)
273    where
274        F: CircuitField + FromUniformBytes<64> + Ord,
275        BinaryChip: BinaryInstructions<F>
276            + AssignmentInstructions<F, AssignedBit<F>>
277            + AssertionInstructions<F, AssignedBit<F>>
278            + FromScratch<F>,
279    {
280        test_binary_op::<F, BinaryChip>(&[0, 0], 0, Operation::Or, true, name, "or");
281        test_binary_op::<F, BinaryChip>(&[0, 1], 1, Operation::Or, false, "", "");
282        test_binary_op::<F, BinaryChip>(&[1, 0], 1, Operation::Or, false, "", "");
283        test_binary_op::<F, BinaryChip>(&[1, 1], 1, Operation::Or, false, "", "");
284    }
285
286    pub fn test_xor<F, BinaryChip>(name: &str)
287    where
288        F: CircuitField + FromUniformBytes<64> + Ord,
289        BinaryChip: BinaryInstructions<F>
290            + AssignmentInstructions<F, AssignedBit<F>>
291            + AssertionInstructions<F, AssignedBit<F>>
292            + FromScratch<F>,
293    {
294        test_binary_op::<F, BinaryChip>(&[0, 0], 0, Operation::Xor, true, name, "xor");
295        test_binary_op::<F, BinaryChip>(&[0, 1], 1, Operation::Xor, false, "", "");
296        test_binary_op::<F, BinaryChip>(&[1, 0], 1, Operation::Xor, false, "", "");
297        test_binary_op::<F, BinaryChip>(&[1, 1], 0, Operation::Xor, false, "", "");
298    }
299
300    pub fn test_not<F, BinaryChip>(name: &str)
301    where
302        F: CircuitField + FromUniformBytes<64> + Ord,
303        BinaryChip: BinaryInstructions<F>
304            + AssignmentInstructions<F, AssignedBit<F>>
305            + AssertionInstructions<F, AssignedBit<F>>
306            + FromScratch<F>,
307    {
308        test_binary_op::<F, BinaryChip>(&[0], 1, Operation::Not, true, name, "not");
309        test_binary_op::<F, BinaryChip>(&[1], 0, Operation::Not, false, "", "");
310    }
311}
midnight_circuits/instructions/binary.rs

midnight_circuits/instructions/
binary.rs
