fancy_garbling/circuits/binary/
binary_addition.rs

1use crate::{
2    BinaryBundle, FancyBinary,
3    circuit::Circuit,
4    circuits::binary::{BinaryAdder, XorMany},
5};
6use core::marker::PhantomData;
7use swanky_channel::Channel;
8use swanky_error::Result;
9
10/// Binary addition.
11///
12/// For [`BinaryBundle`]s `x` and `y`, return `(x + y, c)`, where `c` is the
13/// carry bit.
14#[derive(Default)]
15pub struct BinaryAddition<'a>(PhantomData<&'a ()>);
16
17impl<'a> BinaryAddition<'a> {
18    /// Create a new [`BinaryAddition`] circuit.
19    pub fn new() -> Self {
20        Default::default()
21    }
22}
23
24impl<'a, F: FancyBinary> Circuit<F> for BinaryAddition<'a>
25where
26    F::Item: 'a,
27{
28    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
29    type Output = (BinaryBundle<F::Item>, F::Item);
30
31    fn execute(
32        &self,
33        backend: &mut F,
34        inputs: Self::Input,
35        channel: &mut Channel,
36    ) -> Result<Self::Output> {
37        let (x, y) = inputs;
38        assert_eq!(x.moduli(), y.moduli());
39        let xwires = x.wires();
40        let ywires = y.wires();
41        let (mut z, mut c) =
42            BinaryAdder::new().execute(backend, (&xwires[0], &ywires[0], None), channel)?;
43        let mut bs = vec![z];
44        for i in 1..xwires.len() {
45            let res =
46                BinaryAdder::new().execute(backend, (&xwires[i], &ywires[i], Some(&c)), channel)?;
47            z = res.0;
48            c = res.1;
49            bs.push(z);
50        }
51        Ok((BinaryBundle::new(bs), c))
52    }
53}
54
55/// Binary addition without a carry.
56///
57/// For [`BinaryBundle`]s `x` and `y`, return `(x + y)`.
58#[derive(Default)]
59pub struct BinaryAdditionNoCarry<'a>(PhantomData<&'a ()>);
60
61impl<'a> BinaryAdditionNoCarry<'a> {
62    /// Create a new [`BinaryAdditionNoCarry`] circuit.
63    pub fn new() -> Self {
64        Default::default()
65    }
66}
67
68impl<'a, F: FancyBinary> Circuit<F> for BinaryAdditionNoCarry<'a>
69where
70    F::Item: 'a,
71{
72    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
73    type Output = BinaryBundle<F::Item>;
74
75    fn execute(
76        &self,
77        backend: &mut F,
78        inputs: Self::Input,
79        channel: &mut Channel,
80    ) -> Result<Self::Output> {
81        let (x, y) = inputs;
82        assert_eq!(x.moduli(), y.moduli());
83        let xwires = x.wires();
84        let ywires = y.wires();
85        let (mut z, mut c) =
86            BinaryAdder::new().execute(backend, (&xwires[0], &ywires[0], None), channel)?;
87        let mut bs = vec![z];
88        for i in 1..xwires.len() - 1 {
89            let res =
90                BinaryAdder::new().execute(backend, (&xwires[i], &ywires[i], Some(&c)), channel)?;
91            z = res.0;
92            c = res.1;
93            bs.push(z);
94        }
95        // XOR instead of using `BinaryAdder`.
96        let xor_inputs = [
97            xwires.last().unwrap().clone(),
98            ywires.last().unwrap().clone(),
99            c,
100        ];
101        z = XorMany::new().execute(backend, &xor_inputs[..], channel)?;
102        bs.push(z);
103        Ok(BinaryBundle::new(bs))
104    }
105}
106
107pub mod test {
108    use super::*;
109    use crate::circuit::CircuitInputMapper;
110
111    /// Circuit for testing [`BinaryAddition`].
112    pub struct TestBinaryAddition(pub usize);
113
114    impl<F: FancyBinary> Circuit<F> for TestBinaryAddition {
115        type Input = (BinaryBundle<F::Item>, BinaryBundle<F::Item>);
116        type Output = (BinaryBundle<F::Item>, F::Item);
117
118        fn execute(
119            &self,
120            backend: &mut F,
121            inputs: Self::Input,
122            channel: &mut Channel,
123        ) -> Result<Self::Output> {
124            BinaryAddition::new().execute(backend, (&inputs.0, &inputs.1), channel)
125        }
126    }
127
128    impl<F: FancyBinary> CircuitInputMapper<F> for TestBinaryAddition {
129        fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
130            assert_eq!(inputs.len(), self.0 * 2);
131            let (x, y) = inputs.split_at(self.0);
132            (BinaryBundle::new(x.to_vec()), BinaryBundle::new(y.to_vec()))
133        }
134
135        fn ninputs(&self) -> usize {
136            self.0 * 2
137        }
138
139        fn modulus(&self, _: usize) -> u16 {
140            2
141        }
142    }
143
144    #[test]
145    fn binary_addition() {
146        use crate::dummy::{Dummy, DummyVal};
147        use rand::Rng;
148
149        let mut rng = rand::thread_rng();
150        let nbits = 64;
151        let q = 1 << nbits;
152        let circuit = BinaryAddition::new();
153
154        for _ in 0..16 {
155            let x = rng.r#gen::<u128>() % q;
156            let y = rng.r#gen::<u128>() % q;
157            let x_input = DummyVal::to_binary(x, nbits);
158            let y_input = DummyVal::to_binary(y, nbits);
159            let outputs = Dummy::eval(&circuit, (&x_input, &y_input)).unwrap();
160            assert_eq!(DummyVal::from_binary(&outputs.0), (x + y) % q);
161            assert_eq!(outputs.1.val(), (x + y >= q) as u16);
162        }
163    }
164
165    #[test]
166    fn binary_addition_no_carry() {
167        use crate::dummy::{Dummy, DummyVal};
168        use rand::Rng;
169
170        let mut rng = rand::thread_rng();
171        let nbits = 64;
172        let q = 1 << nbits;
173
174        for _ in 0..16 {
175            let x = rng.r#gen::<u128>() % q;
176            let y = rng.r#gen::<u128>() % q;
177            let x_input = DummyVal::to_binary(x, nbits);
178            let y_input = DummyVal::to_binary(y, nbits);
179            let output = Dummy::eval(&BinaryAdditionNoCarry::new(), (&x_input, &y_input)).unwrap();
180            assert_eq!(DummyVal::from_binary(&output), (x + y) % q);
181        }
182    }
183}
fancy_garbling/circuits/binary/binary_addition.rs

fancy_garbling/circuits/binary/
binary_addition.rs
