snarkvm_circuit_types_field/
equal.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> Equal<Self> for Field<E> {
19    type Output = Boolean<E>;
20
21    ///
22    /// Returns `true` if `self` and `other` are equal.
23    ///
24    /// This method costs 2 constraints.
25    ///
26    fn is_equal(&self, other: &Self) -> Self::Output {
27        !self.is_not_equal(other)
28    }
29
30    ///
31    /// Returns `true` if `self` and `other` are *not* equal.
32    ///
33    /// This method constructs a boolean that indicates if
34    /// `self` and `other ` are *not* equal to each other.
35    ///
36    /// This method costs 2 constraints.
37    ///
38    fn is_not_equal(&self, other: &Self) -> Self::Output {
39        // Initialize a (console) boolean that is `true` if `this` and `that` are not equivalent.
40        let is_neq_ejected = self.eject_value() != other.eject_value();
41
42        match (self.is_constant(), other.is_constant()) {
43            // If both operands are 'Constant', the result is also 'Constant'.
44            (true, true) => Boolean::new(Mode::Constant, is_neq_ejected),
45            _ => {
46                // Inequality Enforcement
47                // ----------------------------------------------------------------
48                // Check 1:  (a - b) * multiplier = is_neq
49                // Check 2:  (a - b) * (1 - is_neq) = 0
50                //
51                //
52                // Case 1: a == b AND is_neq == 0 (honest)
53                // ----------------------------------------------------------------
54                // Check 1:  (a - b) * multiplier = 0
55                //                 0 * multiplier = 0
56                //                              0 = 0
57                // => The constraint is satisfied.
58                //
59                // Check 2:  (a - b) * (1 - 0) = 0
60                //                       0 * 1 = 0
61                //                           0 = 0
62                // => The constraint is satisfied.
63                //
64                //
65                // Case 2: a == b AND is_neq != 0 (dishonest)
66                // ----------------------------------------------------------------
67                // Check 1:  (a - b) * multiplier = is_neq
68                //                 0 * multiplier = is_neq
69                //                              0 = is_neq
70                // => As is_neq != 0, the constraint is not satisfied.
71                //
72                //
73                // Case 3: a != b AND is_neq != 1 (dishonest).
74                // ----------------------------------------------------------------
75                // Check 2:  (a - b) * (1 - is_neq) = 0
76                //                     (1 - is_neq) = 0
77                // => As is_neq != 1, the constraint is not satisfied.
78                //
79                //
80                // Case 4a: a != b AND is_neq == 1 AND multiplier = n [!= (a - b)^(-1)] (dishonest)
81                // ---------------------------------------------------------------------------------
82                // Check 1:  (a - b) * n = 1
83                // => As n != (a - b)^(-1), the constraint is not satisfied.
84                //
85                //
86                // Case 4b: a != b AND is_neq == 1 AND multiplier = (a - b)^(-1) (honest)
87                // ---------------------------------------------------------------------------------
88                // Check 1:  (a - b) * (a - b)^(-1) = 1
89                //                                1 = 1
90                // => The constraint is satisfied.
91                //
92                // Check 2:  (a - b) * (1 - 1) = 0
93                //                 (a - b) * 0 = 0
94                //                           0 = 0
95                // => The constraint is satisfied.
96                //
97                //
98                // Observe that in both of the honest cases, `is_neq` is always 0 or 1.
99
100                // Witness a boolean that is `true` if `this` and `that` are not equivalent.
101                let is_neq = Boolean::from_variable(E::new_variable(Mode::Private, match is_neq_ejected {
102                    true => E::BaseField::one(),
103                    false => E::BaseField::zero(),
104                }));
105
106                // Compute `self` - `other`.
107                let delta = self - other;
108
109                // Assign the expected multiplier as a witness.
110                //
111                // Note: the inverse of `delta` is not guaranteed to exist, and if it does not,
112                // we pick 1 as the multiplier, as its value is irrelevant to satisfy the constraints.
113                let multiplier: Field<E> = witness!(|delta| {
114                    match delta.inverse() {
115                        Ok(inverse) => inverse,
116                        _ => console::Field::one(),
117                    }
118                });
119
120                // Negate `is_neq`.
121                let is_eq = !is_neq.clone();
122
123                // Check 1: (a - b) * multiplier = is_neq
124                E::enforce(|| (&delta, &multiplier, &is_neq));
125
126                // Check 2: (a - b) * not(is_neq) = 0
127                E::enforce(|| (delta, is_eq, E::zero()));
128
129                // Return `is_neq`.
130                is_neq
131            }
132        }
133    }
134}
135
136impl<E: Environment> Metrics<dyn Equal<Field<E>, Output = Boolean<E>>> for Field<E> {
137    type Case = (Mode, Mode);
138
139    // TODO: How to deal where both operands are the same field element, since it changes the number of gates produced? We could use upper bounds.
140    fn count(case: &Self::Case) -> Count {
141        match case {
142            (Mode::Constant, Mode::Constant) => Count::is(1, 0, 0, 0),
143            _ => Count::is(0, 0, 2, 2),
144        }
145    }
146}
147
148impl<E: Environment> OutputMode<dyn Equal<Field<E>, Output = Boolean<E>>> for Field<E> {
149    type Case = (Mode, Mode);
150
151    fn output_mode(case: &Self::Case) -> Mode {
152        match case {
153            (Mode::Constant, Mode::Constant) => Mode::Constant,
154            _ => Mode::Private,
155        }
156    }
157}
158
159#[cfg(test)]
160mod tests {
161    use super::*;
162    use snarkvm_circuit_environment::Circuit;
163
164    const ITERATIONS: u64 = 200;
165
166    fn check_is_equal(name: &str, expected: bool, a: &Field<Circuit>, b: &Field<Circuit>) {
167        Circuit::scope(name, || {
168            let candidate = a.is_equal(b);
169            assert_eq!(expected, candidate.eject_value(), "({} == {})", a.eject_value(), b.eject_value());
170            assert_count!(Equal(Field, Field) => Boolean, &(a.eject_mode(), b.eject_mode()));
171            assert_output_mode!(Equal(Field, Field) => Boolean, &(a.eject_mode(), b.eject_mode()), candidate);
172        });
173    }
174
175    fn check_is_not_equal(name: &str, expected: bool, a: &Field<Circuit>, b: &Field<Circuit>) {
176        Circuit::scope(name, || {
177            let candidate = a.is_not_equal(b);
178            assert_eq!(expected, candidate.eject_value(), "({} != {})", a.eject_value(), b.eject_value());
179            assert_count!(Equal(Field, Field) => Boolean, &(a.eject_mode(), b.eject_mode()));
180            assert_output_mode!(Equal(Field, Field) => Boolean, &(a.eject_mode(), b.eject_mode()), candidate);
181        });
182    }
183
184    fn run_test(mode_a: Mode, mode_b: Mode) {
185        let mut rng = TestRng::default();
186
187        for i in 0..ITERATIONS {
188            let first = Uniform::rand(&mut rng);
189            let second = Uniform::rand(&mut rng);
190
191            let a = Field::<Circuit>::new(mode_a, first);
192            let b = Field::<Circuit>::new(mode_b, second);
193
194            let name = format!("Equal: a == b {i}");
195            check_is_equal(&name, first == second, &a, &b);
196
197            let name = format!("Not Equal: a != b {i}");
198            check_is_not_equal(&name, first != second, &a, &b);
199
200            // Check first is equal to first.
201            let a = Field::<Circuit>::new(mode_a, first);
202            let b = Field::<Circuit>::new(mode_b, first);
203            let name = format!("{first} == {first}");
204            check_is_equal(&name, true, &a, &b);
205
206            // Check second is equal to second.
207            let a = Field::<Circuit>::new(mode_a, second);
208            let b = Field::<Circuit>::new(mode_b, second);
209            let name = format!("{second} == {second}");
210            check_is_equal(&name, true, &a, &b);
211        }
212    }
213
214    #[test]
215    fn test_constant_is_equal_to_constant() {
216        run_test(Mode::Constant, Mode::Constant);
217    }
218
219    #[test]
220    fn test_constant_is_not_equal_to_public() {
221        run_test(Mode::Constant, Mode::Public);
222    }
223
224    #[test]
225    fn test_constant_is_not_equal_to_private() {
226        run_test(Mode::Constant, Mode::Private);
227    }
228
229    #[test]
230    fn test_public_is_equal_to_constant() {
231        run_test(Mode::Public, Mode::Constant);
232    }
233
234    #[test]
235    fn test_private_is_equal_to_constant() {
236        run_test(Mode::Private, Mode::Constant);
237    }
238
239    #[test]
240    fn test_public_is_equal_to_public() {
241        run_test(Mode::Public, Mode::Public);
242    }
243
244    #[test]
245    fn test_public_is_not_equal_to_private() {
246        run_test(Mode::Public, Mode::Private);
247    }
248
249    #[test]
250    fn test_private_is_equal_to_public() {
251        run_test(Mode::Private, Mode::Public);
252    }
253
254    #[test]
255    fn test_private_is_equal_to_private() {
256        run_test(Mode::Private, Mode::Private);
257    }
258
259    #[test]
260    fn test_is_eq_cases() {
261        let one = console::Field::<<Circuit as Environment>::Network>::one();
262
263        // Basic `true` and `false` cases
264        {
265            let mut accumulator = one + one;
266
267            for _ in 0..ITERATIONS {
268                let a = Field::<Circuit>::new(Mode::Private, accumulator);
269                let b = Field::<Circuit>::new(Mode::Private, accumulator);
270                let is_eq = a.is_equal(&b);
271                assert!(is_eq.eject_value()); // true
272
273                let a = Field::<Circuit>::new(Mode::Private, one);
274                let b = Field::<Circuit>::new(Mode::Private, accumulator);
275                let is_eq = a.is_equal(&b);
276                assert!(!is_eq.eject_value()); // false
277
278                let a = Field::<Circuit>::new(Mode::Private, accumulator);
279                let b = Field::<Circuit>::new(Mode::Private, accumulator - one);
280                let is_eq = a.is_equal(&b);
281                assert!(!is_eq.eject_value()); // false
282
283                accumulator += one;
284            }
285        }
286    }
287
288    #[test]
289    fn test_is_neq_cases() {
290        let zero = console::Field::<<Circuit as Environment>::Network>::zero();
291        let one = console::Field::<<Circuit as Environment>::Network>::one();
292        let two = one + one;
293        let five = two + two + one;
294
295        // Inequality Enforcement
296        // ----------------------------------------------------------------
297        // Check 1:  (a - b) * multiplier = is_neq
298        // Check 2:  (a - b) * not(is_neq) = 0
299
300        let enforce = |a: Field<Circuit>, b: Field<Circuit>, multiplier: Field<Circuit>, is_neq: Boolean<Circuit>| {
301            // Compute `self` - `other`.
302            let delta = &a - &b;
303
304            // Negate `is_neq`.
305            let is_eq = !is_neq.clone();
306
307            // Check 1: (a - b) * multiplier = is_neq
308            Circuit::enforce(|| (delta.clone(), multiplier, is_neq.clone()));
309
310            // Check 2: (a - b) * not(is_neq) = 0
311            Circuit::enforce(|| (delta, is_eq, Circuit::zero()));
312        };
313
314        //
315        // Case 1: a == b AND is_neq == 0 (honest)
316        // ----------------------------------------------------------------
317
318        let a = Field::<Circuit>::new(Mode::Private, five);
319        let b = Field::<Circuit>::new(Mode::Private, five);
320        let multiplier = Field::<Circuit>::new(Mode::Private, one);
321        let is_neq = Boolean::new(Mode::Private, false);
322
323        assert!(Circuit::is_satisfied());
324        enforce(a, b, multiplier, is_neq);
325        assert!(Circuit::is_satisfied());
326        Circuit::reset();
327
328        //
329        // Case 2: a == b AND is_neq == 1 (dishonest)
330        // ----------------------------------------------------------------
331
332        let a = Field::<Circuit>::new(Mode::Private, five);
333        let b = Field::<Circuit>::new(Mode::Private, five);
334        let multiplier = Field::<Circuit>::new(Mode::Private, one);
335        let is_neq = Boolean::new(Mode::Private, true);
336
337        assert!(Circuit::is_satisfied());
338        enforce(a, b, multiplier, is_neq);
339        assert!(!Circuit::is_satisfied());
340        Circuit::reset();
341
342        // Case 3a: a != b AND is_neq == 0 AND multiplier = 0 (dishonest)
343        // ----------------------------------------------------------------
344
345        let a = Field::<Circuit>::new(Mode::Private, five);
346        let b = Field::<Circuit>::new(Mode::Private, two);
347        let multiplier = Field::<Circuit>::new(Mode::Private, zero);
348        let is_neq = Boolean::new(Mode::Private, false);
349
350        assert!(Circuit::is_satisfied());
351        enforce(a, b, multiplier, is_neq);
352        assert!(!Circuit::is_satisfied());
353        Circuit::reset();
354
355        //
356        // Case 3b: a != b AND is_neq == 0 AND multiplier = 1 (dishonest)
357        // ----------------------------------------------------------------
358
359        let a = Field::<Circuit>::new(Mode::Private, five);
360        let b = Field::<Circuit>::new(Mode::Private, two);
361        let multiplier = Field::<Circuit>::new(Mode::Private, one);
362        let is_neq = Boolean::new(Mode::Private, false);
363
364        assert!(Circuit::is_satisfied());
365        enforce(a, b, multiplier, is_neq);
366        assert!(!Circuit::is_satisfied());
367        Circuit::reset();
368
369        //
370        // Case 4a: a != b AND is_neq == 1 AND multiplier = n [!= (a - b)^(-1)] (dishonest)
371        // ---------------------------------------------------------------------------------
372
373        let a = Field::<Circuit>::new(Mode::Private, five);
374        let b = Field::<Circuit>::new(Mode::Private, two);
375        let multiplier = Field::<Circuit>::new(Mode::Private, two);
376        let is_neq = Boolean::new(Mode::Private, true);
377
378        assert!(Circuit::is_satisfied());
379        enforce(a, b, multiplier, is_neq);
380        assert!(!Circuit::is_satisfied());
381        Circuit::reset();
382
383        //
384        // Case 4b: a != b AND is_neq == 1 AND multiplier = (a - b)^(-1) (honest)
385        // ---------------------------------------------------------------------------------
386
387        let a = Field::<Circuit>::new(Mode::Private, five);
388        let b = Field::<Circuit>::new(Mode::Private, two);
389        let multiplier =
390            Field::<Circuit>::new(Mode::Private, (five - two).inverse().expect("Failed to compute a native inverse"));
391        let is_neq = Boolean::new(Mode::Private, true);
392
393        assert!(Circuit::is_satisfied());
394        enforce(a, b, multiplier, is_neq);
395        assert!(Circuit::is_satisfied());
396        Circuit::reset();
397    }
398}
snarkvm_circuit_types_field/equal.rs

snarkvm_circuit_types_field/
equal.rs
