jf_relation/gadgets/
logic.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! Logic related circuit implementations
8
9use crate::{
10    gates::{CondSelectGate, LogicOrGate, LogicOrOutputGate},
11    BoolVar, Circuit, CircuitError, PlonkCircuit, Variable,
12};
13use ark_ff::PrimeField;
14use ark_std::{boxed::Box, string::ToString};
15
16impl<F: PrimeField> PlonkCircuit<F> {
17    /// Constrain that `a` is true or `b` is true.
18    /// Return error if variables are invalid.
19    pub fn logic_or_gate(&mut self, a: BoolVar, b: BoolVar) -> Result<(), CircuitError> {
20        self.check_var_bound(a.into())?;
21        self.check_var_bound(b.into())?;
22        let wire_vars = &[a.into(), b.into(), 0, 0, 0];
23        self.insert_gate(wire_vars, Box::new(LogicOrGate))?;
24        Ok(())
25    }
26
27    /// Obtain a bool variable representing whether two input variables are
28    /// equal. Return error if variables are invalid.
29    pub fn is_equal(&mut self, a: Variable, b: Variable) -> Result<BoolVar, CircuitError> {
30        self.check_var_bound(a)?;
31        self.check_var_bound(b)?;
32        let delta = self.sub(a, b)?;
33        self.is_zero(delta)
34    }
35
36    /// Obtain a bool variable representing whether input variable is zero.
37    /// Return error if the input variable is invalid.
38    pub fn is_zero(&mut self, a: Variable) -> Result<BoolVar, CircuitError> {
39        self.check_var_bound(a)?;
40
41        // y is the bit indicating if a == zero
42        // a_inv is the inverse of a when it's not 0
43        let a_val = self.witness(a)?;
44        let (y, a_inv) = if a_val.is_zero() {
45            (F::one(), F::zero())
46        } else {
47            (
48                F::zero(),
49                a_val.inverse().ok_or_else(|| {
50                    CircuitError::FieldAlgebraError("Unable to find inverse".to_string())
51                })?,
52            )
53        };
54        let y = self.create_boolean_variable_unchecked(y)?;
55        let a_inv = self.create_variable(a_inv)?;
56
57        // constraint 1: 1 - a * a^(-1) = y, i.e., a * a^(-1) + 1 * y = 1
58        self.mul_add_gate(
59            &[a, a_inv, self.one(), y.into(), self.one()],
60            &[F::one(), F::one()],
61        )?;
62        // constraint 2: multiplication y * a = 0
63        self.mul_gate(y.into(), a, self.zero())?;
64        Ok(y)
65    }
66
67    /// Constrain a variable to be non-zero.
68    /// Return error if the variable is invalid.
69    pub fn non_zero_gate(&mut self, var: Variable) -> Result<(), CircuitError> {
70        let inverse = self.witness(var)?.inverse().unwrap_or_else(F::zero);
71        let inv_var = self.create_variable(inverse)?;
72        let one_var = self.one();
73        self.mul_gate(var, inv_var, one_var)
74    }
75
76    /// Obtain a variable representing the result of a logic negation gate.
77    /// Return the index of the variable. Return error if the input variable
78    /// is invalid.
79    pub fn logic_neg(&mut self, a: BoolVar) -> Result<BoolVar, CircuitError> {
80        self.is_zero(a.into())
81    }
82
83    /// Obtain a variable representing the result of a logic AND gate. Return
84    /// the index of the variable. Return error if the input variables are
85    /// invalid.
86    pub fn logic_and(&mut self, a: BoolVar, b: BoolVar) -> Result<BoolVar, CircuitError> {
87        let c = self
88            .create_boolean_variable_unchecked(self.witness(a.into())? * self.witness(b.into())?)?;
89        self.mul_gate(a.into(), b.into(), c.into())?;
90        Ok(c)
91    }
92
93    /// Given a list of boolean variables, obtain a variable representing the
94    /// result of a logic AND gate. Return the index of the variable. Return
95    /// error if the input variables are invalid.
96    pub fn logic_and_all(&mut self, vars: &[BoolVar]) -> Result<BoolVar, CircuitError> {
97        if vars.is_empty() {
98            return Err(CircuitError::ParameterError(
99                "logic_and_all: empty variable list".to_string(),
100            ));
101        }
102        let mut res = vars[0];
103        for &var in vars.iter().skip(1) {
104            res = self.logic_and(res, var)?;
105        }
106        Ok(res)
107    }
108
109    /// Obtain a variable representing the result of a logic OR gate. Return the
110    /// index of the variable. Return error if the input variables are
111    /// invalid.
112    pub fn logic_or(&mut self, a: BoolVar, b: BoolVar) -> Result<BoolVar, CircuitError> {
113        self.check_var_bound(a.into())?;
114        self.check_var_bound(b.into())?;
115
116        let a_val = self.witness(a.into())?;
117        let b_val = self.witness(b.into())?;
118        let c_val = a_val + b_val - a_val * b_val;
119
120        let c = self.create_boolean_variable_unchecked(c_val)?;
121        let wire_vars = &[a.into(), b.into(), 0, 0, c.into()];
122        self.insert_gate(wire_vars, Box::new(LogicOrOutputGate))?;
123
124        Ok(c)
125    }
126
127    /// Assuming values represented by `a` is boolean.
128    /// Constrain `a` is true
129    pub fn enforce_true(&mut self, a: Variable) -> Result<(), CircuitError> {
130        self.enforce_constant(a, F::one())
131    }
132
133    /// Assuming values represented by `a` is boolean.
134    /// Constrain `a` is false
135    pub fn enforce_false(&mut self, a: Variable) -> Result<(), CircuitError> {
136        self.enforce_constant(a, F::zero())
137    }
138
139    /// Obtain a variable that equals `x_0` if `b` is zero, or `x_1` if `b` is
140    /// one. Return error if variables are invalid.
141    pub fn conditional_select(
142        &mut self,
143        b: BoolVar,
144        x_0: Variable,
145        x_1: Variable,
146    ) -> Result<Variable, CircuitError> {
147        self.check_var_bound(b.into())?;
148        self.check_var_bound(x_0)?;
149        self.check_var_bound(x_1)?;
150
151        // y = x_bit
152        let y = if self.witness(b.into())? == F::zero() {
153            self.create_variable(self.witness(x_0)?)?
154        } else if self.witness(b.into())? == F::one() {
155            self.create_variable(self.witness(x_1)?)?
156        } else {
157            return Err(CircuitError::ParameterError(
158                "b in Conditional Selection gate is not a boolean variable".to_string(),
159            ));
160        };
161        let wire_vars = [b.into(), x_0, b.into(), x_1, y];
162        self.insert_gate(&wire_vars, Box::new(CondSelectGate))?;
163        Ok(y)
164    }
165}
166
167#[cfg(test)]
168mod test {
169    use crate::{
170        gadgets::test_utils::test_variable_independence_for_circuit, Circuit, CircuitError,
171        PlonkCircuit,
172    };
173    use ark_bls12_377::Fq as Fq377;
174    use ark_ed_on_bls12_377::Fq as FqEd377;
175    use ark_ed_on_bls12_381::Fq as FqEd381;
176    use ark_ed_on_bn254::Fq as FqEd254;
177    use ark_ff::PrimeField;
178
179    #[test]
180    fn test_logic_or() -> Result<(), CircuitError> {
181        test_logic_or_helper::<FqEd254>()?;
182        test_logic_or_helper::<FqEd377>()?;
183        test_logic_or_helper::<FqEd381>()?;
184        test_logic_or_helper::<Fq377>()
185    }
186
187    fn test_logic_or_helper<F: PrimeField>() -> Result<(), CircuitError> {
188        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
189        let false_var = circuit.false_var();
190        let true_var = circuit.true_var();
191        // Good path
192        let should_be_true = circuit.logic_or(false_var, true_var)?;
193        assert!(circuit.witness(should_be_true.into())?.eq(&F::one()));
194        let should_be_true = circuit.logic_or(true_var, false_var)?;
195        assert!(circuit.witness(should_be_true.into())?.eq(&F::one()));
196        let should_be_true = circuit.logic_or(true_var, true_var)?;
197        assert!(circuit.witness(should_be_true.into())?.eq(&F::one()));
198        // Error path
199        let should_be_false = circuit.logic_or(false_var, false_var)?;
200        assert!(circuit.witness(should_be_false.into())?.eq(&F::zero()));
201        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
202
203        Ok(())
204    }
205    #[test]
206    fn test_logic_or_gate() -> Result<(), CircuitError> {
207        test_logic_or_gate_helper::<FqEd254>()?;
208        test_logic_or_gate_helper::<FqEd377>()?;
209        test_logic_or_gate_helper::<FqEd381>()?;
210        test_logic_or_gate_helper::<Fq377>()
211    }
212
213    fn test_logic_or_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
214        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
215        let false_var = circuit.false_var();
216        let true_var = circuit.true_var();
217        // Good path
218        circuit.logic_or_gate(false_var, true_var)?;
219        circuit.logic_or_gate(true_var, false_var)?;
220        circuit.logic_or_gate(true_var, true_var)?;
221        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
222        // Error path
223        circuit.logic_or_gate(false_var, false_var)?;
224        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
225
226        let circuit_1 = build_logic_or_circuit(true, true)?;
227        let circuit_2 = build_logic_or_circuit(false, true)?;
228        test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
229
230        Ok(())
231    }
232
233    fn build_logic_or_circuit<F: PrimeField>(
234        a: bool,
235        b: bool,
236    ) -> Result<PlonkCircuit<F>, CircuitError> {
237        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
238        let a = circuit.create_boolean_variable(a)?;
239        let b = circuit.create_boolean_variable(b)?;
240        circuit.logic_or_gate(a, b)?;
241        circuit.finalize_for_arithmetization()?;
242        Ok(circuit)
243    }
244
245    #[test]
246    fn test_logic_and() -> Result<(), CircuitError> {
247        test_logic_and_helper::<FqEd254>()?;
248        test_logic_and_helper::<FqEd377>()?;
249        test_logic_and_helper::<FqEd381>()?;
250        test_logic_and_helper::<Fq377>()
251    }
252
253    fn test_logic_and_helper<F: PrimeField>() -> Result<(), CircuitError> {
254        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
255        let false_var = circuit.false_var();
256        let true_var = circuit.true_var();
257        // Good path
258        let a = circuit.logic_and(false_var, true_var)?;
259        assert_eq!(F::zero(), circuit.witness(a.into())?);
260        let b = circuit.logic_and(true_var, false_var)?;
261        assert_eq!(F::zero(), circuit.witness(b.into())?);
262        let c = circuit.logic_and(true_var, true_var)?;
263        assert_eq!(F::one(), circuit.witness(c.into())?);
264        let d = circuit.logic_and_all(&[false_var, true_var, true_var])?;
265        assert_eq!(F::zero(), circuit.witness(d.into())?);
266        let e = circuit.logic_and_all(&[true_var, true_var, true_var])?;
267        assert_eq!(F::one(), circuit.witness(e.into())?);
268        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
269        // Error path
270        *circuit.witness_mut(e.into()) = F::zero();
271        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
272        *circuit.witness_mut(e.into()) = F::one();
273        assert!(circuit.logic_and_all(&[]).is_err());
274
275        let circuit_1 = build_logic_and_circuit(true, true)?;
276        let circuit_2 = build_logic_and_circuit(false, true)?;
277        test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
278
279        Ok(())
280    }
281
282    fn build_logic_and_circuit<F: PrimeField>(
283        a: bool,
284        b: bool,
285    ) -> Result<PlonkCircuit<F>, CircuitError> {
286        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
287        let a = circuit.create_boolean_variable(a)?;
288        let b = circuit.create_boolean_variable(b)?;
289        circuit.logic_and(a, b)?;
290        circuit.finalize_for_arithmetization()?;
291        Ok(circuit)
292    }
293
294    #[test]
295    fn test_is_equal() -> Result<(), CircuitError> {
296        test_is_equal_helper::<FqEd254>()?;
297        test_is_equal_helper::<FqEd377>()?;
298        test_is_equal_helper::<FqEd381>()?;
299        test_is_equal_helper::<Fq377>()
300    }
301    fn test_is_equal_helper<F: PrimeField>() -> Result<(), CircuitError> {
302        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
303        let val = F::from(31415u32);
304        let a = circuit.create_variable(val)?;
305        let b = circuit.create_variable(val)?;
306        let a_b_eq = circuit.is_equal(a, b)?;
307        let a_zero_eq = circuit.is_equal(a, circuit.zero())?;
308
309        // check circuit
310        assert_eq!(circuit.witness(a_b_eq.into())?, F::one());
311        assert_eq!(circuit.witness(a_zero_eq.into())?, F::zero());
312        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
313        *circuit.witness_mut(b) = val + F::one();
314        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
315        // Check variable out of bound error.
316        assert!(circuit.is_equal(circuit.num_vars(), a).is_err());
317
318        let circuit_1 = build_is_equal_circuit(F::one(), F::one())?;
319        let circuit_2 = build_is_equal_circuit(F::zero(), F::one())?;
320        test_variable_independence_for_circuit(circuit_1, circuit_2)?;
321
322        Ok(())
323    }
324
325    fn build_is_equal_circuit<F: PrimeField>(a: F, b: F) -> Result<PlonkCircuit<F>, CircuitError> {
326        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
327        let a = circuit.create_variable(a)?;
328        let b = circuit.create_variable(b)?;
329        circuit.is_equal(a, b)?;
330        circuit.finalize_for_arithmetization()?;
331        Ok(circuit)
332    }
333
334    #[test]
335    fn test_check_is_zero() -> Result<(), CircuitError> {
336        test_check_is_zero_helper::<FqEd254>()?;
337        test_check_is_zero_helper::<FqEd377>()?;
338        test_check_is_zero_helper::<FqEd381>()?;
339        test_check_is_zero_helper::<Fq377>()
340    }
341    fn test_check_is_zero_helper<F: PrimeField>() -> Result<(), CircuitError> {
342        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
343        let val = F::from(31415u32);
344        let a = circuit.create_variable(val)?;
345        let a_zero_eq = circuit.is_zero(a)?;
346        let zero_zero_eq = circuit.is_zero(circuit.zero())?;
347
348        // check circuit
349        assert_eq!(circuit.witness(a_zero_eq.into())?, F::zero());
350        assert_eq!(circuit.witness(zero_zero_eq.into())?, F::one());
351        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
352        *circuit.witness_mut(zero_zero_eq.into()) = F::zero();
353        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
354        *circuit.witness_mut(zero_zero_eq.into()) = F::one();
355        *circuit.witness_mut(a) = F::zero();
356        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
357        // Check variable out of bound error.
358        assert!(circuit.is_zero(circuit.num_vars()).is_err());
359
360        let circuit_1 = build_check_is_zero_circuit(F::one())?;
361        let circuit_2 = build_check_is_zero_circuit(F::zero())?;
362        test_variable_independence_for_circuit(circuit_1, circuit_2)?;
363
364        Ok(())
365    }
366
367    fn build_check_is_zero_circuit<F: PrimeField>(a: F) -> Result<PlonkCircuit<F>, CircuitError> {
368        let mut circuit = PlonkCircuit::new_turbo_plonk();
369        let a = circuit.create_variable(a)?;
370        circuit.is_zero(a)?;
371        circuit.finalize_for_arithmetization()?;
372        Ok(circuit)
373    }
374
375    #[test]
376    fn test_conditional_select() -> Result<(), CircuitError> {
377        test_conditional_select_helper::<FqEd254>()?;
378        test_conditional_select_helper::<FqEd377>()?;
379        test_conditional_select_helper::<FqEd381>()?;
380        test_conditional_select_helper::<Fq377>()
381    }
382
383    fn test_conditional_select_helper<F: PrimeField>() -> Result<(), CircuitError> {
384        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
385        let bit_true = circuit.true_var();
386        let bit_false = circuit.false_var();
387
388        let x_0 = circuit.create_variable(F::from(23u32))?;
389        let x_1 = circuit.create_variable(F::from(24u32))?;
390        let select_true = circuit.conditional_select(bit_true, x_0, x_1)?;
391        let select_false = circuit.conditional_select(bit_false, x_0, x_1)?;
392
393        assert_eq!(circuit.witness(select_true)?, circuit.witness(x_1)?);
394        assert_eq!(circuit.witness(select_false)?, circuit.witness(x_0)?);
395        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
396
397        // if mess up the wire value, should fail
398        *circuit.witness_mut(bit_false.into()) = F::one();
399        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
400        // Check variable out of bound error.
401        assert!(circuit
402            .conditional_select(bit_false, circuit.num_vars(), x_1)
403            .is_err());
404
405        // build two fixed circuits with different variable assignments, checking that
406        // the arithmetized extended permutation polynomial is variable
407        // independent
408        let circuit_1 = build_conditional_select_circuit(true, F::from(23u32), F::from(24u32))?;
409        let circuit_2 = build_conditional_select_circuit(false, F::from(99u32), F::from(98u32))?;
410        test_variable_independence_for_circuit(circuit_1, circuit_2)?;
411        Ok(())
412    }
413
414    fn build_conditional_select_circuit<F: PrimeField>(
415        bit: bool,
416        x_0: F,
417        x_1: F,
418    ) -> Result<PlonkCircuit<F>, CircuitError> {
419        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
420        let bit_var = circuit.create_boolean_variable(bit)?;
421        let x_0_var = circuit.create_variable(x_0)?;
422        let x_1_var = circuit.create_variable(x_1)?;
423        circuit.conditional_select(bit_var, x_0_var, x_1_var)?;
424        circuit.finalize_for_arithmetization()?;
425        Ok(circuit)
426    }
427
428    #[test]
429    fn test_non_zero_gate() -> Result<(), CircuitError> {
430        test_non_zero_gate_helper::<FqEd254>()?;
431        test_non_zero_gate_helper::<FqEd377>()?;
432        test_non_zero_gate_helper::<FqEd381>()?;
433        test_non_zero_gate_helper::<Fq377>()
434    }
435    fn test_non_zero_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
436        // Create the circuit
437        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
438        let non_zero_var = circuit.create_variable(F::from(2_u32))?;
439        let _ = circuit.non_zero_gate(non_zero_var);
440        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
441
442        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
443        let zero_var = circuit.create_variable(F::from(0_u32))?;
444        let _ = circuit.non_zero_gate(zero_var);
445        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
446
447        Ok(())
448    }
449}
jf_relation/gadgets/logic.rs

jf_relation/gadgets/
logic.rs
