snarkvm_circuit_types_boolean/
ternary.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> Ternary for Boolean<E> {
19    type Boolean = Boolean<E>;
20    type Output = Self;
21
22    /// Returns `first` if `condition` is `true`, otherwise returns `second`.
23    fn ternary(condition: &Self::Boolean, first: &Self, second: &Self) -> Self::Output {
24        // Constant `condition`
25        if condition.is_constant() {
26            match condition.eject_value() {
27                true => first.clone(),
28                false => second.clone(),
29            }
30        }
31        // Constant `first`
32        else if first.is_constant() {
33            match first.eject_value() {
34                true => condition | second,
35                false => !condition & second,
36            }
37        }
38        // Constant `second`
39        else if second.is_constant() {
40            match second.eject_value() {
41                true => !condition | first,
42                false => condition & first,
43            }
44        }
45        // Variables
46        else {
47            // Compute the witness value, based on the condition.
48            let witness = match condition.eject_value() {
49                true => first.eject_value(),
50                false => second.eject_value(),
51            };
52
53            // Declare a new variable with the expected output as witness.
54            // Note: The constraint below will ensure `output` is either 0 or 1,
55            // assuming `self` and `other` are well-formed (they are either 0 or 1).
56            let output = Boolean(
57                E::new_variable(Mode::Private, match witness {
58                    true => E::BaseField::one(),
59                    false => E::BaseField::zero(),
60                })
61                .into(),
62            );
63
64            //
65            // Ternary Enforcement
66            // -------------------------------------------------------
67            //    output = condition * a + (1 - condition) * b
68            // => output = b + condition * (a - b)
69            // => condition * (a - b) = output - b
70            //
71            // See `Field::ternary()` for the proof of correctness.
72            //
73            E::enforce(|| (condition, (&first.0 - &second.0), (&output.0 - &second.0)));
74
75            output
76        }
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use snarkvm_circuit_environment::Circuit;
84
85    fn check_ternary(
86        name: &str,
87        expected: bool,
88        condition: Boolean<Circuit>,
89        a: Boolean<Circuit>,
90        b: Boolean<Circuit>,
91        num_constants: u64,
92        num_public: u64,
93        num_private: u64,
94        num_constraints: u64,
95    ) {
96        Circuit::scope(name, || {
97            let case = format!("({} ? {} : {})", condition.eject_value(), a.eject_value(), b.eject_value());
98            let candidate = Boolean::ternary(&condition, &a, &b);
99            assert_eq!(expected, candidate.eject_value(), "{case}");
100            assert_scope!(num_constants, num_public, num_private, num_constraints);
101        });
102    }
103
104    fn run_test(
105        mode_condition: Mode,
106        mode_a: Mode,
107        mode_b: Mode,
108        num_constants: u64,
109        num_public: u64,
110        num_private: u64,
111        num_constraints: u64,
112    ) {
113        for flag in [true, false] {
114            for first in [true, false] {
115                for second in [true, false] {
116                    let condition = Boolean::<Circuit>::new(mode_condition, flag);
117                    let a = Boolean::<Circuit>::new(mode_a, first);
118                    let b = Boolean::<Circuit>::new(mode_b, second);
119
120                    let name = format!("{mode_condition} ? {mode_a} : {mode_b}");
121                    check_ternary(
122                        &name,
123                        if flag { first } else { second },
124                        condition,
125                        a,
126                        b,
127                        num_constants,
128                        num_public,
129                        num_private,
130                        num_constraints,
131                    );
132                }
133            }
134        }
135    }
136
137    #[test]
138    fn test_if_constant_then_constant_else_constant() {
139        run_test(Mode::Constant, Mode::Constant, Mode::Constant, 0, 0, 0, 0);
140    }
141
142    #[test]
143    fn test_if_constant_then_constant_else_public() {
144        run_test(Mode::Constant, Mode::Constant, Mode::Public, 0, 0, 0, 0);
145    }
146
147    #[test]
148    fn test_if_constant_then_constant_else_private() {
149        run_test(Mode::Constant, Mode::Constant, Mode::Private, 0, 0, 0, 0);
150    }
151
152    #[test]
153    fn test_if_constant_then_public_else_constant() {
154        run_test(Mode::Constant, Mode::Public, Mode::Constant, 0, 0, 0, 0);
155    }
156
157    #[test]
158    fn test_if_constant_then_public_else_public() {
159        run_test(Mode::Constant, Mode::Public, Mode::Public, 0, 0, 0, 0);
160    }
161
162    #[test]
163    fn test_if_constant_then_public_else_private() {
164        run_test(Mode::Constant, Mode::Public, Mode::Private, 0, 0, 0, 0);
165    }
166
167    #[test]
168    fn test_if_constant_then_private_else_constant() {
169        run_test(Mode::Constant, Mode::Private, Mode::Constant, 0, 0, 0, 0);
170    }
171
172    #[test]
173    fn test_if_constant_then_private_else_public() {
174        run_test(Mode::Constant, Mode::Private, Mode::Public, 0, 0, 0, 0);
175    }
176
177    #[test]
178    fn test_if_constant_then_private_else_private() {
179        run_test(Mode::Constant, Mode::Private, Mode::Private, 0, 0, 0, 0);
180    }
181
182    #[test]
183    fn test_if_public_then_constant_else_constant() {
184        run_test(Mode::Public, Mode::Constant, Mode::Constant, 0, 0, 0, 0);
185    }
186
187    #[test]
188    fn test_if_public_then_constant_else_public() {
189        run_test(Mode::Public, Mode::Constant, Mode::Public, 0, 0, 1, 1);
190    }
191
192    #[test]
193    fn test_if_public_then_constant_else_private() {
194        run_test(Mode::Public, Mode::Constant, Mode::Private, 0, 0, 1, 1);
195    }
196
197    #[test]
198    fn test_if_public_then_public_else_constant() {
199        run_test(Mode::Public, Mode::Public, Mode::Constant, 0, 0, 1, 1);
200    }
201
202    #[test]
203    fn test_if_public_then_public_else_public() {
204        run_test(Mode::Public, Mode::Public, Mode::Public, 0, 0, 1, 1);
205    }
206
207    #[test]
208    fn test_if_public_then_public_else_private() {
209        run_test(Mode::Public, Mode::Public, Mode::Private, 0, 0, 1, 1);
210    }
211
212    #[test]
213    fn test_if_public_then_private_else_constant() {
214        run_test(Mode::Public, Mode::Private, Mode::Constant, 0, 0, 1, 1);
215    }
216
217    #[test]
218    fn test_if_public_then_private_else_public() {
219        run_test(Mode::Public, Mode::Private, Mode::Public, 0, 0, 1, 1);
220    }
221
222    #[test]
223    fn test_if_public_then_private_else_private() {
224        run_test(Mode::Public, Mode::Private, Mode::Private, 0, 0, 1, 1);
225    }
226
227    #[test]
228    fn test_if_private_then_constant_else_constant() {
229        run_test(Mode::Private, Mode::Constant, Mode::Constant, 0, 0, 0, 0);
230    }
231
232    #[test]
233    fn test_if_private_then_constant_else_public() {
234        run_test(Mode::Private, Mode::Constant, Mode::Public, 0, 0, 1, 1);
235    }
236
237    #[test]
238    fn test_if_private_then_constant_else_private() {
239        run_test(Mode::Private, Mode::Constant, Mode::Private, 0, 0, 1, 1);
240    }
241
242    #[test]
243    fn test_if_private_then_public_else_constant() {
244        run_test(Mode::Private, Mode::Public, Mode::Constant, 0, 0, 1, 1);
245    }
246
247    #[test]
248    fn test_if_private_then_public_else_public() {
249        run_test(Mode::Private, Mode::Public, Mode::Public, 0, 0, 1, 1);
250    }
251
252    #[test]
253    fn test_if_private_then_public_else_private() {
254        run_test(Mode::Private, Mode::Public, Mode::Private, 0, 0, 1, 1);
255    }
256
257    #[test]
258    fn test_if_private_then_private_else_constant() {
259        run_test(Mode::Private, Mode::Private, Mode::Constant, 0, 0, 1, 1);
260    }
261
262    #[test]
263    fn test_if_private_then_private_else_public() {
264        run_test(Mode::Private, Mode::Private, Mode::Public, 0, 0, 1, 1);
265    }
266
267    #[test]
268    fn test_if_private_then_private_else_private() {
269        run_test(Mode::Private, Mode::Private, Mode::Private, 0, 0, 1, 1);
270    }
271}
snarkvm_circuit_types_boolean/ternary.rs

snarkvm_circuit_types_boolean/
ternary.rs
