fancy_garbling/
circuit_analyzer.rs

1//! Fancy object to profile a fancy circuit and compute stats such as the multiplicative depth
2//! or the number of boolean and arithmetic gates in a circuit.
3use crate::{
4    FancyArithmetic, FancyBinary,
5    fancy::{Fancy, FancyInput, FancyReveal, HasModulus},
6};
7use std::cmp::max;
8use swanky_channel::Channel;
9use swanky_error::ErrorKind;
10
11/// An instantiation of [`FancyInput::Item`] used by [`CircuitAnalyzer`].
12///
13/// A dummy FancyItem which is returned when profiling a [`Fancy`] circuit.
14/// The [`AnalyzerItem`] contains the wire modulus and the depth of the computation.
15/// This is because [`Fancy::Item`] needs to implement [`HasModulus`].
16#[derive(Clone, Debug)]
17pub struct AnalyzerItem {
18    modulus: u16,
19    depth: usize,
20}
21
22impl HasModulus for AnalyzerItem {
23    fn modulus(&self) -> u16 {
24        self.modulus
25    }
26}
27
28/// A [`Fancy`] object which counts gates in a binary circuit.
29///
30/// Specifically, [`CircuitAnalyzer`] stores the number of inputs,
31/// ands, xors, negations, constants, multiplication, addition, subtraction,
32/// constant operations and multiplication depth of the circuits. This
33/// information is especially useful for pre-processing authenticated
34/// garbling circuits.
35#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
36pub struct CircuitAnalyzer {
37    ninputs: usize,
38    nconstants: usize,
39    nands: usize,
40    nxors: usize,
41    nnegs: usize,
42    nadds: usize,
43    nsubs: usize,
44    ncmuls: usize,
45    nmuls: usize,
46    mul_depth: usize,
47}
48
49impl std::fmt::Display for CircuitAnalyzer {
50    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
51        writeln!(f, "computation info:")?;
52        writeln!(f, "   number of inputs: {:16}", self.ninputs)?;
53        writeln!(f, "   number of constants: {:16}", self.nconstants)?;
54        writeln!(f, "   number of additions: {:16}", self.nadds)?;
55        writeln!(f, "   number of subtractions: {:16}", self.nsubs)?;
56        writeln!(f, "   number of cmuls: {:16}", self.ncmuls)?;
57        writeln!(f, "   number of muls: {:16}", self.nmuls)?;
58        writeln!(f, "   number of ands: {:16}", self.nands)?;
59        writeln!(f, "   number of xors: {:16}", self.nxors)?;
60        writeln!(f, "   number of negations: {:16}", self.nnegs)?;
61        writeln!(
62            f,
63            "   total number of arithmetic gates(ADD, SUB, MUL, CMUL): {:16}",
64            self.nadds + self.nsubs + self.ncmuls + self.nmuls
65        )?;
66        writeln!(
67            f,
68            "   total number of boolean gates (AND, XOR): {:16}",
69            self.nands + self.nxors
70        )?;
71        writeln!(f, "   multiplicative depth: {:16}", self.mul_depth)?;
72        Ok(())
73    }
74}
75
76impl CircuitAnalyzer {
77    /// Create a new [`CircuitAnalyzer`] and sets all the gate
78    /// counts to 0.
79    pub fn new() -> CircuitAnalyzer {
80        Default::default()
81    }
82    /// Return the number of AND gates in the circuit
83    pub fn nands(&self) -> usize {
84        self.nands
85    }
86    /// Return the number of input wires of the circuit
87    pub fn ninputs(&self) -> usize {
88        self.ninputs
89    }
90}
91
92impl FancyInput for CircuitAnalyzer {
93    type Item = AnalyzerItem;
94
95    fn receive_many(
96        &mut self,
97        moduli: &[u16],
98        _: &mut Channel,
99    ) -> swanky_error::Result<Vec<Self::Item>> {
100        self.ninputs += moduli.len();
101        Ok(moduli
102            .iter()
103            .map(|q| AnalyzerItem {
104                modulus: *q,
105                depth: 0,
106            })
107            .collect())
108    }
109
110    fn encode_many(
111        &mut self,
112        _values: &[u16],
113        moduli: &[u16],
114        channel: &mut Channel,
115    ) -> swanky_error::Result<Vec<Self::Item>> {
116        self.receive_many(moduli, channel)
117    }
118}
119
120impl FancyBinary for CircuitAnalyzer {
121    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
122        self.nxors += 1;
123        // Fancy's XOR gate calls the underlying arithmetic addition
124        self.nadds += 1;
125        AnalyzerItem {
126            modulus: x.modulus,
127            // Same depth as an ADD
128            depth: max(x.depth, y.depth),
129        }
130    }
131
132    fn and(
133        &mut self,
134        x: &Self::Item,
135        y: &Self::Item,
136        _: &mut Channel,
137    ) -> swanky_error::Result<Self::Item> {
138        self.nands += 1;
139        // Fancy's AND gate calls the underlying arithmetic multiplication
140        self.nmuls += 1;
141        Ok(AnalyzerItem {
142            modulus: x.modulus,
143            // Same depth as a MUL
144            depth: max(x.depth, y.depth) + 1,
145        })
146    }
147    fn or(
148        &mut self,
149        x: &Self::Item,
150        y: &Self::Item,
151        _: &mut Channel,
152    ) -> swanky_error::Result<Self::Item> {
153        self.nands += 1;
154        self.nnegs += 3;
155        // Fancy binary's AND gate calls the underlying arithmetic multiplication
156        self.nmuls += 1;
157        Ok(AnalyzerItem {
158            modulus: x.modulus,
159            // This is because OR in swanky invokes an AND gate
160            depth: max(x.depth, y.depth) + 1,
161        })
162    }
163    fn negate(&mut self, x: &Self::Item) -> Self::Item {
164        self.nnegs += 1;
165
166        // Fancy implements negation with one constant gate and one XOR
167        self.nconstants += 1;
168        self.nxors += 1;
169
170        // Fancy's XOR gate calls the underlying arithmetic addition
171        self.nadds += 1;
172        AnalyzerItem {
173            modulus: x.modulus,
174            // Same depth as a XOR, except that negation is a unary gate
175            depth: x.depth,
176        }
177    }
178}
179
180impl FancyArithmetic for CircuitAnalyzer {
181    fn add(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
182        self.nadds += 1;
183        AnalyzerItem {
184            modulus: x.modulus,
185            depth: max(x.depth, y.depth),
186        }
187    }
188
189    fn sub(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
190        self.nsubs += 1;
191        AnalyzerItem {
192            modulus: x.modulus,
193            depth: max(x.depth, y.depth),
194        }
195    }
196
197    fn cmul(&mut self, x: &Self::Item, _y: u16) -> Self::Item {
198        self.ncmuls += 1;
199        AnalyzerItem {
200            modulus: x.modulus,
201            depth: x.depth,
202        }
203    }
204
205    fn mul(
206        &mut self,
207        x: &Self::Item,
208        y: &Self::Item,
209        _: &mut Channel,
210    ) -> swanky_error::Result<Self::Item> {
211        self.nmuls += 1;
212        Ok(AnalyzerItem {
213            modulus: x.modulus,
214            depth: max(x.depth, y.depth) + 1,
215        })
216    }
217
218    fn proj(
219        &mut self,
220        _x: &Self::Item,
221        _q: u16,
222        _tt: Option<Vec<u16>>,
223        _: &mut Channel,
224    ) -> swanky_error::Result<Self::Item> {
225        swanky_error::bail!(
226            ErrorKind::UnsupportedError,
227            "Projection gates are unsupported"
228        )
229    }
230}
231
232impl Fancy for CircuitAnalyzer {
233    type Item = AnalyzerItem;
234
235    fn constant(&mut self, _val: u16, q: u16, _: &mut Channel) -> swanky_error::Result<Self::Item> {
236        self.nconstants += 1;
237        Ok(AnalyzerItem {
238            modulus: q,
239            depth: 0,
240        })
241    }
242
243    fn output(&mut self, x: &Self::Item, _: &mut Channel) -> swanky_error::Result<Option<u16>> {
244        self.mul_depth = max(self.mul_depth, x.depth);
245        Ok(None)
246    }
247}
248
249impl FancyReveal for CircuitAnalyzer {
250    fn reveal(&mut self, _x: &Self::Item, _: &mut Channel) -> swanky_error::Result<u16> {
251        Ok(0)
252    }
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258    use crate::BinaryGadgets;
259    #[test]
260    fn single_and_gate_count_is_correct() {
261        let nbits = 64;
262        let x = 0;
263        let y = 0;
264        Channel::with(std::io::empty(), |channel| {
265            let mut analyzer_test: CircuitAnalyzer = CircuitAnalyzer::new();
266            let x = analyzer_test.bin_encode(x, nbits, channel).unwrap();
267            let y = analyzer_test.bin_encode(y, nbits, channel).unwrap();
268            let _c = analyzer_test.bin_and(&x, &y, channel);
269
270            assert_eq!(analyzer_test.ninputs, 128);
271            assert_eq!(analyzer_test.nands, 64);
272            assert_eq!(analyzer_test.nxors, 0);
273            assert_eq!(analyzer_test.nconstants, 0);
274            assert_eq!(analyzer_test.nnegs, 0);
275            Ok(())
276        })
277        .unwrap();
278    }
279    #[test]
280    fn binary_addition_counts_are_correct() {
281        let nbits = 64;
282        let x = 0;
283        let y = 0;
284        Channel::with(std::io::empty(), |channel| {
285            let mut analyzer_test: CircuitAnalyzer = CircuitAnalyzer::new();
286            let x = analyzer_test.bin_encode(x, nbits, channel).unwrap();
287            let y = analyzer_test.bin_encode(y, nbits, channel).unwrap();
288            // bin_addition is equivalent to an "adder" per wire
289            let _c = analyzer_test.bin_addition(&x, &y, channel);
290
291            assert_eq!(analyzer_test.ninputs, 128);
292            assert_eq!(analyzer_test.nands, 64);
293            // There are (nbits -1) adders invoked with a carry
294            // and the very first one without. The adders with
295            // carry have 3 extra XORs, check fancy_garbling::adder
296            // and fancy_garbling::binary_addition for more info
297            assert_eq!(analyzer_test.nxors, 64 * 4 - 3);
298            assert_eq!(analyzer_test.nconstants, 0);
299            assert_eq!(analyzer_test.nnegs, 0);
300            Ok(())
301        })
302        .unwrap();
303    }
304    #[test]
305    fn binary_multiplication_counts_are_correct() {
306        let nbits = 64;
307        let x = 0;
308        let y = 0;
309        Channel::with(std::io::empty(), |channel| {
310            let mut analyzer_test: CircuitAnalyzer = CircuitAnalyzer::new();
311            let x = analyzer_test.bin_encode(x, nbits, channel).unwrap();
312            let y = analyzer_test.bin_encode(y, nbits, channel).unwrap();
313            // bin_addition is equivalent to an "adder" per wire
314            let _c = analyzer_test.bin_mul(&x, &y, channel);
315
316            // In binary multiplication there are :
317            // - 64 * 64 explicit ANDs, i.e. pairwise ANDS between parties input wires.
318            // - Sum(65 to 128) binary additions. Recall that in multiplication the input
319            //   size grows by 1 bit each round until each 2 times the size of the initial
320            //   input (i.e. 64 * 2)
321            assert_eq!(analyzer_test.ninputs, 128);
322            assert_eq!(analyzer_test.nands, (65..128).sum::<usize>() + 64 * 64);
323            assert_eq!(
324                analyzer_test.nxors,
325                (65..128).sum::<usize>() * 4 - (3 * (128 - 65))
326            );
327            assert_eq!(analyzer_test.nconstants, 64);
328            assert_eq!(analyzer_test.nnegs, 0);
329            Ok(())
330        })
331        .unwrap();
332    }
333    #[test]
334    fn binary_twos_complement_counts_are_correct() {
335        let nbits = 64;
336        let x = 0;
337        Channel::with(std::io::empty(), |channel| {
338            let mut analyzer_test: CircuitAnalyzer = CircuitAnalyzer::new();
339            let x = analyzer_test.bin_encode(x, nbits, channel).unwrap();
340            // bin_addition is equivalent to an "adder" per wire
341            let _c = analyzer_test.bin_twos_complement(&x, channel);
342
343            assert_eq!(analyzer_test.ninputs, 64);
344            assert_eq!(analyzer_test.nands, 63);
345            assert_eq!(analyzer_test.nxors, 63 * 4 - 3 + 64 + 2);
346            assert_eq!(analyzer_test.nconstants, 64 + 64);
347            assert_eq!(analyzer_test.nnegs, 64);
348            Ok(())
349        })
350        .unwrap();
351    }
352}
fancy_garbling/circuit_analyzer.rs

fancy_garbling/
circuit_analyzer.rs
