snarkvm_circuit_types_field/
compare.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> Compare<Field<E>> for Field<E> {
19    type Output = Boolean<E>;
20
21    /// Returns `true` if `self` is less than `other`.
22    fn is_less_than(&self, other: &Self) -> Self::Output {
23        // Case 1: Constant < Constant
24        if self.is_constant() && other.is_constant() {
25            Boolean::constant(self.eject_value() < other.eject_value())
26        }
27        // Case 2: Constant < Variable
28        else if self.is_constant() {
29            // See the `else` case below for the truth table and description of the logic.
30            self.eject_value().to_bits_le().into_iter().zip_eq(other.to_bits_le()).fold(
31                Boolean::constant(false),
32                |is_less_than, (this, that)| match this {
33                    true => that.bitand(&is_less_than),
34                    false => that.bitor(&is_less_than),
35                },
36            )
37        }
38        // Case 3: Variable < Constant
39        else if other.is_constant() {
40            // See the `else` case below for the truth table and description of the logic.
41            self.to_bits_le().into_iter().zip_eq(other.eject_value().to_bits_le()).fold(
42                Boolean::constant(false),
43                |is_less_than, (this, that)| match that {
44                    true => (!this).bitor(is_less_than),
45                    false => (!this).bitand(&is_less_than),
46                },
47            )
48        }
49        // Case 4: Variable < Variable
50        else {
51            // Check each bitwise pair of `(self, other)` from MSB to LSB as follows:
52            //   - If `this` != `that`, and if `this` is `true`, return `false`.
53            //   - If `this` != `that`, and if `this` is `false`, return `true`.
54            //   - If `this` == `that`, return `is_less_than`.
55            //
56            // The following is the truth table:
57            //
58            // | this    | that    | is_less_than | result |
59            // |---------+---------+--------------+--------|
60            // | `true`  | `true`  | `true`       | `true` |
61            // | `true`  | `true`  | `false`      | `false`|
62            // | `true`  | `false` | `true`       | `true` |
63            // | `true`  | `false` | `false`      | `true` |
64            // | `false` | `true`  | `true`       | `false`|
65            // | `false` | `true`  | `false`      | `false`|
66            // | `false` | `false` | `true`       | `true` |
67            // | `false` | `false` | `false`      | `false`|
68            //
69            self.to_bits_le()
70                .iter()
71                .zip_eq(other.to_bits_le())
72                .fold(Boolean::constant(false), |is_less_than, (this, that)| {
73                    Boolean::ternary(&this.bitxor(&that), &that, &is_less_than)
74                })
75        }
76    }
77
78    /// Returns `true` if `self` is greater than `other`.
79    fn is_greater_than(&self, other: &Self) -> Self::Output {
80        other.is_less_than(self)
81    }
82
83    /// Returns `true` if `self` is less than or equal to `other`.
84    fn is_less_than_or_equal(&self, other: &Self) -> Self::Output {
85        other.is_greater_than_or_equal(self)
86    }
87
88    /// Returns `true` if `self` is greater than or equal to `other`.
89    fn is_greater_than_or_equal(&self, other: &Self) -> Self::Output {
90        !self.is_less_than(other)
91    }
92}
93
94// TODO: Implement `Metrics` and `OutputMode` for `Compare`. Waiting for PR#711  to land as it significantly changes the counts.
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use snarkvm_circuit_environment::Circuit;
100
101    const ITERATIONS: u64 = 100;
102
103    fn check_is_less_than(
104        name: &str,
105        expected: bool,
106        a: &Field<Circuit>,
107        b: &Field<Circuit>,
108        num_constants: u64,
109        num_public: u64,
110        num_private: u64,
111        num_constraints: u64,
112    ) {
113        // Perform the less than comparison.
114        Circuit::scope(name, || {
115            let candidate = a.is_less_than(b);
116            assert_eq!(expected, candidate.eject_value());
117            match (a.eject_mode(), b.eject_mode()) {
118                (Mode::Constant, Mode::Constant) => {
119                    assert_scope!(num_constants, num_public, num_private, num_constraints)
120                }
121                (_, Mode::Constant) | (Mode::Constant, _) => {
122                    assert_scope!(<=num_constants, <=num_public, <=num_private, <=num_constraints)
123                }
124                _ => assert_scope!(num_constants, num_public, num_private, num_constraints),
125            }
126        });
127        Circuit::reset();
128    }
129
130    fn run_test(
131        mode_a: Mode,
132        mode_b: Mode,
133        num_constants: u64,
134        num_public: u64,
135        num_private: u64,
136        num_constraints: u64,
137    ) {
138        let mut rng = TestRng::default();
139
140        for i in 0..ITERATIONS {
141            let first = Uniform::rand(&mut rng);
142            let second = Uniform::rand(&mut rng);
143
144            let a = Field::<Circuit>::new(mode_a, first);
145            let b = Field::<Circuit>::new(mode_b, second);
146            let expected = first < second;
147            let name = format!("{mode_a} {mode_b} {i}");
148            check_is_less_than(&name, expected, &a, &b, num_constants, num_public, num_private, num_constraints);
149
150            // Check `first` is not less than `first`.
151            let a = Field::<Circuit>::new(mode_a, first);
152            let b = Field::<Circuit>::new(mode_b, first);
153            check_is_less_than(
154                "first !< first",
155                false,
156                &a,
157                &b,
158                num_constants,
159                num_public,
160                num_private,
161                num_constraints,
162            );
163        }
164    }
165
166    #[test]
167    fn test_constant_is_less_than_constant() {
168        run_test(Mode::Constant, Mode::Constant, 0, 0, 0, 0);
169    }
170
171    #[test]
172    fn test_constant_is_less_than_public() {
173        run_test(Mode::Constant, Mode::Public, 0, 0, 757, 759);
174    }
175
176    #[test]
177    fn test_constant_is_less_than_private() {
178        run_test(Mode::Constant, Mode::Private, 0, 0, 757, 759);
179    }
180
181    #[test]
182    fn test_public_is_less_than_constant() {
183        run_test(Mode::Public, Mode::Constant, 0, 0, 757, 759);
184    }
185
186    #[test]
187    fn test_public_is_less_than_public() {
188        run_test(Mode::Public, Mode::Public, 0, 0, 1516, 1520);
189    }
190
191    #[test]
192    fn test_public_is_less_than_private() {
193        run_test(Mode::Public, Mode::Private, 0, 0, 1516, 1520);
194    }
195
196    #[test]
197    fn test_private_is_less_than_constant() {
198        run_test(Mode::Private, Mode::Constant, 0, 0, 757, 759);
199    }
200
201    #[test]
202    fn test_private_is_less_than_public() {
203        run_test(Mode::Private, Mode::Public, 0, 0, 1516, 1520);
204    }
205
206    #[test]
207    fn test_private_is_less_than_private() {
208        run_test(Mode::Private, Mode::Private, 0, 0, 1516, 1520);
209    }
210}
snarkvm_circuit_types_field/compare.rs

snarkvm_circuit_types_field/
compare.rs
