snarkvm_circuit_types_boolean/
xor.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
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
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use super::*;
17
18impl<E: Environment> BitXor<Boolean<E>> for Boolean<E> {
19    type Output = Boolean<E>;
20
21    /// Returns `(self != other)`.
22    fn bitxor(self, other: Boolean<E>) -> Self::Output {
23        self ^ &other
24    }
25}
26
27impl<E: Environment> BitXor<Boolean<E>> for &Boolean<E> {
28    type Output = Boolean<E>;
29
30    /// Returns `(self != other)`.
31    fn bitxor(self, other: Boolean<E>) -> Self::Output {
32        self ^ &other
33    }
34}
35
36impl<E: Environment> BitXor<&Boolean<E>> for Boolean<E> {
37    type Output = Boolean<E>;
38
39    /// Returns `(self != other)`.
40    fn bitxor(self, other: &Boolean<E>) -> Self::Output {
41        &self ^ other
42    }
43}
44
45impl<E: Environment> BitXor<&Boolean<E>> for &Boolean<E> {
46    type Output = Boolean<E>;
47
48    /// Returns `(self != other)`.
49    fn bitxor(self, other: &Boolean<E>) -> Self::Output {
50        let mut output = self.clone();
51        output ^= other;
52        output
53    }
54}
55
56impl<E: Environment> BitXorAssign<Boolean<E>> for Boolean<E> {
57    /// Sets `self` as `(self != other)`.
58    fn bitxor_assign(&mut self, other: Boolean<E>) {
59        *self ^= &other;
60    }
61}
62
63impl<E: Environment> BitXorAssign<&Boolean<E>> for Boolean<E> {
64    /// Sets `self` as `(self != other)`.
65    fn bitxor_assign(&mut self, other: &Boolean<E>) {
66        // Stores the bitwise XOR of `self` and `other` in `self`.
67        *self =
68            // Constant `self`
69            if self.is_constant() {
70                match self.eject_value() {
71                    true => !other.clone(),
72                    false => other.clone(),
73                }
74            }
75            // Constant `other`
76            else if other.is_constant() {
77                match other.eject_value() {
78                    true => !self.clone(),
79                    false => self.clone(),
80                }
81            }
82            // Variable != Variable
83            else {
84                // Declare a new variable with the expected output as witness.
85                // Note: The constraint below will ensure `output` is either 0 or 1,
86                // assuming `self` and `other` are well-formed (they are either 0 or 1).
87                let output = Boolean(
88                    E::new_variable(Mode::Private, match self.eject_value() ^ other.eject_value() {
89                        true => E::BaseField::one(),
90                        false => E::BaseField::zero(),
91                    })
92                        .into(),
93                );
94
95                //
96                // Ensure (`self` + `self`) * (`other`) = (`self` + `other` - `output`)
97                // `output` is `1` iff `self` != `other`.
98                //
99                // As `self` and `other` are enforced to be `Boolean` types,
100                // if they are equal, then the `output` is 0,
101                // and if they are different, then `output` must be 1.
102                //
103                // ¬(a ∧ b) ∧ ¬(¬a ∧ ¬b) = c
104                //
105                // (1 - (a * b)) * (1 - ((1 - a) * (1 - b))) = c
106                // (1 - ab) * (1 - (1 - a - b + ab)) = c
107                // (1 - ab) * (a + b - ab) = c
108                // a + b - ab - (a^2)b - (b^2)a + (a^2)(b^2) = c
109                // a + b - ab - ab - ab + ab = c
110                // a + b - 2ab = c
111                // -2a * b = c - a - b
112                // 2a * b = a + b - c
113                // (a + a) * b = a + b - c
114                //
115                E::enforce(|| ((&self.0 + &self.0), other, (&self.0 + &other.0 - &output.0)));
116
117                output
118            }
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125    use snarkvm_circuit_environment::Circuit;
126
127    fn check_xor(
128        name: &str,
129        expected: bool,
130        a: Boolean<Circuit>,
131        b: Boolean<Circuit>,
132        num_constants: u64,
133        num_public: u64,
134        num_private: u64,
135        num_constraints: u64,
136    ) {
137        Circuit::scope(name, || {
138            let candidate = &a ^ &b;
139            assert_eq!(expected, candidate.eject_value(), "({} != {})", a.eject_value(), b.eject_value());
140            assert_scope!(num_constants, num_public, num_private, num_constraints);
141        });
142    }
143
144    #[test]
145    fn test_constant_xor_constant() {
146        // false != false
147        let expected = false;
148        let a = Boolean::<Circuit>::new(Mode::Constant, false);
149        let b = Boolean::<Circuit>::new(Mode::Constant, false);
150        check_xor("false != false", expected, a, b, 0, 0, 0, 0);
151
152        // false != true
153        let expected = true;
154        let a = Boolean::<Circuit>::new(Mode::Constant, false);
155        let b = Boolean::<Circuit>::new(Mode::Constant, true);
156        check_xor("false != true", expected, a, b, 0, 0, 0, 0);
157
158        // true != false
159        let expected = true;
160        let a = Boolean::<Circuit>::new(Mode::Constant, true);
161        let b = Boolean::<Circuit>::new(Mode::Constant, false);
162        check_xor("true != false", expected, a, b, 0, 0, 0, 0);
163
164        // true != true
165        let expected = false;
166        let a = Boolean::<Circuit>::new(Mode::Constant, true);
167        let b = Boolean::<Circuit>::new(Mode::Constant, true);
168        check_xor("true != true", expected, a, b, 0, 0, 0, 0);
169    }
170
171    #[test]
172    fn test_constant_xor_public() {
173        // false != false
174        let expected = false;
175        let a = Boolean::<Circuit>::new(Mode::Constant, false);
176        let b = Boolean::<Circuit>::new(Mode::Public, false);
177        check_xor("false != false", expected, a, b, 0, 0, 0, 0);
178
179        // false != true
180        let expected = true;
181        let a = Boolean::<Circuit>::new(Mode::Constant, false);
182        let b = Boolean::<Circuit>::new(Mode::Public, true);
183        check_xor("false != true", expected, a, b, 0, 0, 0, 0);
184
185        // true != false
186        let expected = true;
187        let a = Boolean::<Circuit>::new(Mode::Constant, true);
188        let b = Boolean::<Circuit>::new(Mode::Public, false);
189        check_xor("true != false", expected, a, b, 0, 0, 0, 0);
190
191        // true != true
192        let expected = false;
193        let a = Boolean::<Circuit>::new(Mode::Constant, true);
194        let b = Boolean::<Circuit>::new(Mode::Public, true);
195        check_xor("true != true", expected, a, b, 0, 0, 0, 0);
196    }
197
198    #[test]
199    fn test_constant_xor_private() {
200        // false != false
201        let expected = false;
202        let a = Boolean::<Circuit>::new(Mode::Constant, false);
203        let b = Boolean::<Circuit>::new(Mode::Private, false);
204        check_xor("false != false", expected, a, b, 0, 0, 0, 0);
205
206        // false != true
207        let expected = true;
208        let a = Boolean::<Circuit>::new(Mode::Constant, false);
209        let b = Boolean::<Circuit>::new(Mode::Private, true);
210        check_xor("false != true", expected, a, b, 0, 0, 0, 0);
211
212        // true != false
213        let expected = true;
214        let a = Boolean::<Circuit>::new(Mode::Constant, true);
215        let b = Boolean::<Circuit>::new(Mode::Private, false);
216        check_xor("true != false", expected, a, b, 0, 0, 0, 0);
217
218        // true != true
219        let expected = false;
220        let a = Boolean::<Circuit>::new(Mode::Constant, true);
221        let b = Boolean::<Circuit>::new(Mode::Private, true);
222        check_xor("true != true", expected, a, b, 0, 0, 0, 0);
223    }
224
225    #[test]
226    fn test_public_xor_constant() {
227        // false != false
228        let expected = false;
229        let a = Boolean::<Circuit>::new(Mode::Public, false);
230        let b = Boolean::<Circuit>::new(Mode::Constant, false);
231        check_xor("false != false", expected, a, b, 0, 0, 0, 0);
232
233        // false != true
234        let expected = true;
235        let a = Boolean::<Circuit>::new(Mode::Public, false);
236        let b = Boolean::<Circuit>::new(Mode::Constant, true);
237        check_xor("false != true", expected, a, b, 0, 0, 0, 0);
238
239        // true != false
240        let expected = true;
241        let a = Boolean::<Circuit>::new(Mode::Public, true);
242        let b = Boolean::<Circuit>::new(Mode::Constant, false);
243        check_xor("true != false", expected, a, b, 0, 0, 0, 0);
244
245        // true != true
246        let expected = false;
247        let a = Boolean::<Circuit>::new(Mode::Public, true);
248        let b = Boolean::<Circuit>::new(Mode::Constant, true);
249        check_xor("true != true", expected, a, b, 0, 0, 0, 0);
250    }
251
252    #[test]
253    fn test_public_xor_public() {
254        // false != false
255        let expected = false;
256        let a = Boolean::<Circuit>::new(Mode::Public, false);
257        let b = Boolean::<Circuit>::new(Mode::Public, false);
258        check_xor("false != false", expected, a, b, 0, 0, 1, 1);
259
260        // false != true
261        let expected = true;
262        let a = Boolean::<Circuit>::new(Mode::Public, false);
263        let b = Boolean::<Circuit>::new(Mode::Public, true);
264        check_xor("false != true", expected, a, b, 0, 0, 1, 1);
265
266        // true != false
267        let expected = true;
268        let a = Boolean::<Circuit>::new(Mode::Public, true);
269        let b = Boolean::<Circuit>::new(Mode::Public, false);
270        check_xor("true != false", expected, a, b, 0, 0, 1, 1);
271
272        // true != true
273        let expected = false;
274        let a = Boolean::<Circuit>::new(Mode::Public, true);
275        let b = Boolean::<Circuit>::new(Mode::Public, true);
276        check_xor("true != true", expected, a, b, 0, 0, 1, 1);
277    }
278
279    #[test]
280    fn test_public_xor_private() {
281        // false != false
282        let expected = false;
283        let a = Boolean::<Circuit>::new(Mode::Public, false);
284        let b = Boolean::<Circuit>::new(Mode::Private, false);
285        check_xor("false != false", expected, a, b, 0, 0, 1, 1);
286
287        // false != true
288        let expected = true;
289        let a = Boolean::<Circuit>::new(Mode::Public, false);
290        let b = Boolean::<Circuit>::new(Mode::Private, true);
291        check_xor("false != true", expected, a, b, 0, 0, 1, 1);
292
293        // true != false
294        let expected = true;
295        let a = Boolean::<Circuit>::new(Mode::Public, true);
296        let b = Boolean::<Circuit>::new(Mode::Private, false);
297        check_xor("true != false", expected, a, b, 0, 0, 1, 1);
298
299        // true != true
300        let expected = false;
301        let a = Boolean::<Circuit>::new(Mode::Public, true);
302        let b = Boolean::<Circuit>::new(Mode::Private, true);
303        check_xor("true != true", expected, a, b, 0, 0, 1, 1);
304    }
305
306    #[test]
307    fn test_private_xor_constant() {
308        // false != false
309        let expected = false;
310        let a = Boolean::<Circuit>::new(Mode::Private, false);
311        let b = Boolean::<Circuit>::new(Mode::Constant, false);
312        check_xor("false != false", expected, a, b, 0, 0, 0, 0);
313
314        // false != true
315        let expected = true;
316        let a = Boolean::<Circuit>::new(Mode::Private, false);
317        let b = Boolean::<Circuit>::new(Mode::Constant, true);
318        check_xor("false != true", expected, a, b, 0, 0, 0, 0);
319
320        // true != false
321        let expected = true;
322        let a = Boolean::<Circuit>::new(Mode::Private, true);
323        let b = Boolean::<Circuit>::new(Mode::Constant, false);
324        check_xor("true != false", expected, a, b, 0, 0, 0, 0);
325
326        // true != true
327        let expected = false;
328        let a = Boolean::<Circuit>::new(Mode::Private, true);
329        let b = Boolean::<Circuit>::new(Mode::Constant, true);
330        check_xor("true != true", expected, a, b, 0, 0, 0, 0);
331    }
332
333    #[test]
334    fn test_private_xor_public() {
335        // false != false
336        let expected = false;
337        let a = Boolean::<Circuit>::new(Mode::Private, false);
338        let b = Boolean::<Circuit>::new(Mode::Public, false);
339        check_xor("false != false", expected, a, b, 0, 0, 1, 1);
340
341        // false != true
342        let expected = true;
343        let a = Boolean::<Circuit>::new(Mode::Private, false);
344        let b = Boolean::<Circuit>::new(Mode::Public, true);
345        check_xor("false != true", expected, a, b, 0, 0, 1, 1);
346
347        // true != false
348        let expected = true;
349        let a = Boolean::<Circuit>::new(Mode::Private, true);
350        let b = Boolean::<Circuit>::new(Mode::Public, false);
351        check_xor("true != false", expected, a, b, 0, 0, 1, 1);
352
353        // true != true
354        let expected = false;
355        let a = Boolean::<Circuit>::new(Mode::Private, true);
356        let b = Boolean::<Circuit>::new(Mode::Public, true);
357        check_xor("true != true", expected, a, b, 0, 0, 1, 1);
358    }
359
360    #[test]
361    fn test_private_xor_private() {
362        // false != false
363        let expected = false;
364        let a = Boolean::<Circuit>::new(Mode::Private, false);
365        let b = Boolean::<Circuit>::new(Mode::Private, false);
366        check_xor("false != false", expected, a, b, 0, 0, 1, 1);
367
368        // false != true
369        let expected = true;
370        let a = Boolean::<Circuit>::new(Mode::Private, false);
371        let b = Boolean::<Circuit>::new(Mode::Private, true);
372        check_xor("false != true", expected, a, b, 0, 0, 1, 1);
373
374        // true != false
375        let expected = true;
376        let a = Boolean::<Circuit>::new(Mode::Private, true);
377        let b = Boolean::<Circuit>::new(Mode::Private, false);
378        check_xor("true != false", expected, a, b, 0, 0, 1, 1);
379
380        // true != true
381        let expected = false;
382        let a = Boolean::<Circuit>::new(Mode::Private, true);
383        let b = Boolean::<Circuit>::new(Mode::Private, true);
384        check_xor("true != true", expected, a, b, 0, 0, 1, 1);
385    }
386}
snarkvm_circuit_types_boolean/xor.rs

snarkvm_circuit_types_boolean/
xor.rs
