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

fancy_garbling/
circuit_analyzer.rs
