fancy_garbling/circuits/binary/
binary_less_than.rs

1use crate::{
2    BinaryBundle, FancyBinary,
3    circuit::Circuit,
4    circuits::binary::{BinarySubtraction, Mux, OrMany},
5};
6use core::marker::PhantomData;
7use swanky_channel::Channel;
8use swanky_error::Result;
9
10/// Binary less than.
11///
12/// For [`BinaryBundle`]s `x` and `y`, return `x < y`.
13#[derive(Default)]
14pub struct BinaryLessThan<'a>(PhantomData<&'a ()>);
15
16impl<'a> BinaryLessThan<'a> {
17    /// Create a new [`BinaryLessThan`] circuit.
18    pub fn new() -> Self {
19        Default::default()
20    }
21}
22
23impl<'a, F: FancyBinary> Circuit<F> for BinaryLessThan<'a>
24where
25    F::Item: 'a,
26{
27    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
28    type Output = F::Item;
29
30    fn execute(
31        &self,
32        backend: &mut F,
33        inputs: Self::Input,
34        channel: &mut Channel,
35    ) -> Result<Self::Output> {
36        assert_eq!(inputs.0.moduli(), inputs.1.moduli());
37        let (x, y) = inputs;
38
39        // underflow indicates y != 0 && x >= y
40        // requiring special care to remove the y != 0, which is what follows.
41        let (_, lhs) = BinarySubtraction::new().execute(backend, (x, y), channel)?;
42
43        // Now we build a clause equal to (y == 0 || x >= y), which we can OR with
44        // lhs to remove the y==0 aspect.
45        // check if y==0
46        let y_contains_1 = OrMany::new().execute(backend, y.wires().as_slice(), channel)?;
47        let y_eq_0 = backend.negate(&y_contains_1);
48
49        // if x != 0, then x >= y, ... assuming x is not negative
50        let x_contains_1 = OrMany::new().execute(backend, x.wires().as_slice(), channel)?;
51
52        // y == 0 && x >= y
53        let rhs = backend.and(&y_eq_0, &x_contains_1, channel)?;
54
55        // (y != 0 && x >= y) || (y == 0 && x >= y)
56        // => x >= y && (y != 0 || y == 0)\
57        // => x >= y && 1
58        // => x >= y
59        let geq = backend.or(&lhs, &rhs, channel)?;
60        let ngeq = backend.negate(&geq);
61
62        let xy_neq_0 = backend.or(&y_contains_1, &x_contains_1, channel)?;
63        backend.and(&xy_neq_0, &ngeq, channel)
64    }
65}
66
67/// Binary signed less than.
68///
69/// For [`BinaryBundle`]s `x` and `y` representing signed integers in two's complement,
70/// return `x < y`.
71#[derive(Default)]
72pub struct BinaryLessThanSigned<'a>(PhantomData<&'a ()>);
73
74impl<'a> BinaryLessThanSigned<'a> {
75    /// Create a new [`BinaryLessThanSigned`] circuit.
76    pub fn new() -> Self {
77        Default::default()
78    }
79}
80
81impl<'a, F: FancyBinary> Circuit<F> for BinaryLessThanSigned<'a>
82where
83    F::Item: 'a,
84{
85    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
86    type Output = F::Item;
87
88    fn execute(
89        &self,
90        backend: &mut F,
91        inputs: Self::Input,
92        channel: &mut Channel,
93    ) -> Result<Self::Output> {
94        assert_eq!(inputs.0.moduli(), inputs.1.moduli());
95        let (x, y) = inputs;
96        let zero = backend.constant(0, 2, channel)?;
97        let one = backend.constant(1, 2, channel)?;
98
99        // Determine whether x and y are positive or negative.
100        // In two's complement, the most significant bit indicates the sign.
101        let x_neg = x.wires().last().unwrap();
102        let y_neg = y.wires().last().unwrap();
103        let x_pos = backend.negate(x_neg);
104        let y_pos = backend.negate(y_neg);
105
106        // Base case: if x and y have the same sign, use unsigned less than.
107        let x_lt_y_unsigned = BinaryLessThan::new().execute(backend, (x, y), channel)?;
108
109        // If x is negative and y is positive, then x < y.
110        let x_neg_y_pos = backend.and(x_neg, &y_pos, channel)?;
111        let r2 = Mux::new().execute(backend, (&x_neg_y_pos, &x_lt_y_unsigned, &one), channel)?;
112
113        // If x is positive and y is negative, then !(x < y).
114        let x_pos_y_neg = backend.and(&x_pos, y_neg, channel)?;
115        Mux::new().execute(backend, (&x_pos_y_neg, &r2, &zero), channel)
116    }
117}
118
119pub mod test {
120    use super::*;
121    use crate::circuit::CircuitInputMapper;
122
123    /// Circuit for testing [`BinaryLessThan`].
124    pub struct TestBinaryLessThan(pub usize);
125    impl<F: FancyBinary> Circuit<F> for TestBinaryLessThan {
126        type Input = (BinaryBundle<F::Item>, BinaryBundle<F::Item>);
127        type Output = F::Item;
128
129        fn execute(
130            &self,
131            backend: &mut F,
132            inputs: Self::Input,
133            channel: &mut Channel,
134        ) -> Result<Self::Output> {
135            BinaryLessThan::new().execute(backend, (&inputs.0, &inputs.1), channel)
136        }
137    }
138
139    impl<F: FancyBinary> CircuitInputMapper<F> for TestBinaryLessThan {
140        fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
141            assert_eq!(inputs.len(), self.0 * 2);
142            let (x, y) = inputs.split_at(self.0);
143            (BinaryBundle::new(x.to_vec()), BinaryBundle::new(y.to_vec()))
144        }
145
146        fn ninputs(&self) -> usize {
147            self.0 * 2
148        }
149
150        fn modulus(&self, _: usize) -> u16 {
151            2
152        }
153    }
154
155    /// Circuit for testing [`BinaryLessThanSigned`].
156    pub struct TestBinaryLessThanSigned(pub usize);
157    impl<F: FancyBinary> Circuit<F> for TestBinaryLessThanSigned {
158        type Input = (BinaryBundle<F::Item>, BinaryBundle<F::Item>);
159        type Output = F::Item;
160
161        fn execute(
162            &self,
163            backend: &mut F,
164            inputs: Self::Input,
165            channel: &mut Channel,
166        ) -> Result<Self::Output> {
167            BinaryLessThanSigned::new().execute(backend, (&inputs.0, &inputs.1), channel)
168        }
169    }
170
171    impl<F: FancyBinary> CircuitInputMapper<F> for TestBinaryLessThanSigned {
172        fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
173            assert_eq!(inputs.len(), self.0 * 2);
174            let (x, y) = inputs.split_at(self.0);
175            (BinaryBundle::new(x.to_vec()), BinaryBundle::new(y.to_vec()))
176        }
177
178        fn ninputs(&self) -> usize {
179            self.0 * 2
180        }
181
182        fn modulus(&self, _: usize) -> u16 {
183            2
184        }
185    }
186
187    #[test]
188    fn binary_less_than() {
189        use crate::dummy::{Dummy, DummyVal};
190        use rand::Rng;
191
192        let mut rng = rand::thread_rng();
193        let nbits = 64;
194        let q = 1 << nbits;
195        let c = TestBinaryLessThan(nbits);
196
197        for _ in 0..16 {
198            let x = rng.r#gen::<u128>() % q;
199            let y = rng.r#gen::<u128>() % q;
200            let x_input = DummyVal::to_binary(x, nbits);
201            let y_input = DummyVal::to_binary(y, nbits);
202            let output = Dummy::eval(&c, (x_input, y_input)).unwrap();
203            assert_eq!(output.val() > 0, x < y);
204        }
205    }
206
207    #[test]
208    fn binary_less_than_signed() {
209        use crate::dummy::{Dummy, DummyVal};
210        use rand::Rng;
211
212        let mut rng = rand::thread_rng();
213        let nbits = 64;
214        let q = 1u128 << nbits;
215        let c = TestBinaryLessThanSigned(nbits);
216
217        for _ in 0..16 {
218            let x = rng.r#gen::<u128>() % q;
219            let y = rng.r#gen::<u128>() % q;
220            let x_input = DummyVal::to_binary(x, nbits);
221            let y_input = DummyVal::to_binary(y, nbits);
222            let output = Dummy::eval(&c, (x_input, y_input)).unwrap();
223            assert_eq!(output.val() > 0, (x as i64) < (y as i64));
224        }
225    }
226}
fancy_garbling/circuits/binary/binary_less_than.rs

fancy_garbling/circuits/binary/
binary_less_than.rs
