fancy_garbling/
circuit_analyzer.rs

1//! [`Fancy`] instantiation for computing gate counts and multiplicative depth
2//! of a [`Fancy`] circuit.
3
4use crate::{
5    Fancy, FancyArithmetic, FancyBinary, FancyEncode, FancyOutput, FancyProj, HasModulus,
6    circuit::CircuitInputMapper,
7};
8use core::cmp::max;
9use swanky_channel::Channel;
10use swanky_error::{ErrorKind, Result};
11
12/// An instantiation of [`Fancy::Item`] used by [`CircuitAnalyzer`].
13#[derive(Clone, Debug)]
14pub struct AnalyzerItem {
15    modulus: u16,
16    depth: usize,
17}
18
19impl AnalyzerItem {
20    /// Create a new [`AnalyzerItem`] with the provided modulus.
21    pub fn new(modulus: u16) -> Self {
22        Self { modulus, depth: 0 }
23    }
24}
25
26impl HasModulus for AnalyzerItem {
27    fn modulus(&self) -> u16 {
28        self.modulus
29    }
30}
31
32/// A [`Fancy`] object which counts gates and depth of a
33/// [`crate::circuit::Circuit`].
34///
35/// Specifically, [`CircuitAnalyzer`] stores the number of inputs, ands, xors,
36/// negations, constants, multiplications, additions, subtractions, and
37/// multiplicative depth of the computation.
38#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
39pub struct CircuitAnalyzer {
40    ninputs: usize,
41    nconstants: usize,
42    nands: usize,
43    nxors: usize,
44    nnegs: usize,
45    nadds: usize,
46    nsubs: usize,
47    ncmuls: usize,
48    nmuls: usize,
49    mul_depth: usize,
50}
51
52impl std::fmt::Display for CircuitAnalyzer {
53    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
54        writeln!(f, "computation info:")?;
55        writeln!(f, "   # inputs:  {:16}", self.ninputs)?;
56        writeln!(f, "   # consts:  {:16}", self.nconstants)?;
57        writeln!(f, "   # adds:    {:16}", self.nadds)?;
58        writeln!(f, "   # subs:    {:16}", self.nsubs)?;
59        writeln!(f, "   # cmuls:   {:16}", self.ncmuls)?;
60        writeln!(f, "   # muls:    {:16}", self.nmuls)?;
61        writeln!(f, "   # ands:    {:16}", self.nands)?;
62        writeln!(f, "   # xors:    {:16}", self.nxors)?;
63        writeln!(f, "   # negates: {:16}", self.nnegs)?;
64        writeln!(
65            f,
66            "   # arithmetic gates: {}",
67            self.nadds + self.nsubs + self.ncmuls + self.nmuls
68        )?;
69        writeln!(f, "   # boolean gates: {}", self.nands + self.nxors)?;
70        writeln!(f, "   mult depth: {}", self.mul_depth)?;
71        Ok(())
72    }
73}
74
75impl CircuitAnalyzer {
76    /// Create a new [`CircuitAnalyzer`].
77    pub fn new() -> CircuitAnalyzer {
78        Default::default()
79    }
80    /// The number of AND gates in the circuit.
81    pub fn nands(&self) -> usize {
82        self.nands
83    }
84    /// The number of input wires of the circuit.
85    pub fn ninputs(&self) -> usize {
86        self.ninputs
87    }
88    /// The number of constant wires of the circuit.
89    pub fn nconstants(&self) -> usize {
90        self.nconstants
91    }
92    /// The number of XOR gates in the circuit.
93    pub fn nxors(&self) -> usize {
94        self.nxors
95    }
96
97    /// Evaluate a circuit using [`CircuitAnalyzer`].
98    ///
99    /// The circuit needs to implement [`CircuitInputMapper`] as the circuit
100    /// analysis is input-size-dependent.
101    pub fn eval<C: CircuitInputMapper<CircuitAnalyzer>>(&mut self, circuit: &C) -> Result<()> {
102        Channel::with(std::io::empty(), |channel| {
103            let inputs = (0..circuit.ninputs())
104                .map(|i| self.receive(circuit.modulus(i), channel))
105                .collect::<Result<Vec<_>>>()?;
106            circuit.execute(self, circuit.map(inputs), channel)?;
107            Ok(())
108        })
109    }
110}
111
112impl FancyBinary for CircuitAnalyzer {
113    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
114        assert_eq!(x.modulus, 2);
115        assert_eq!(y.modulus, 2);
116        self.nxors += 1;
117        AnalyzerItem {
118            modulus: x.modulus,
119            depth: max(x.depth, y.depth),
120        }
121    }
122
123    fn and(&mut self, x: &Self::Item, y: &Self::Item, _: &mut Channel) -> Result<Self::Item> {
124        assert_eq!(x.modulus, 2);
125        assert_eq!(y.modulus, 2);
126        self.nands += 1;
127        let depth = max(x.depth, y.depth) + 1;
128        self.mul_depth = max(self.mul_depth, depth);
129        Ok(AnalyzerItem {
130            modulus: x.modulus,
131            depth,
132        })
133    }
134
135    fn negate(&mut self, x: &Self::Item) -> Self::Item {
136        assert_eq!(x.modulus, 2);
137        self.nnegs += 1;
138        AnalyzerItem {
139            modulus: x.modulus,
140            depth: x.depth,
141        }
142    }
143}
144
145impl FancyArithmetic for CircuitAnalyzer {
146    fn add(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
147        self.nadds += 1;
148        AnalyzerItem {
149            modulus: x.modulus,
150            depth: max(x.depth, y.depth),
151        }
152    }
153
154    fn sub(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
155        self.nsubs += 1;
156        AnalyzerItem {
157            modulus: x.modulus,
158            depth: max(x.depth, y.depth),
159        }
160    }
161
162    fn cmul(&mut self, x: &Self::Item, _y: u16) -> Self::Item {
163        self.ncmuls += 1;
164        AnalyzerItem {
165            modulus: x.modulus,
166            depth: x.depth,
167        }
168    }
169
170    fn mul(&mut self, x: &Self::Item, y: &Self::Item, _: &mut Channel) -> Result<Self::Item> {
171        self.nmuls += 1;
172        let depth = max(x.depth, y.depth) + 1;
173        self.mul_depth = max(self.mul_depth, depth);
174        Ok(AnalyzerItem {
175            modulus: x.modulus,
176            depth: max(x.depth, y.depth) + 1,
177        })
178    }
179}
180
181impl FancyProj for CircuitAnalyzer {
182    fn proj(
183        &mut self,
184        _: &Self::Item,
185        _: u16,
186        _: Option<Vec<u16>>,
187        _: &mut Channel,
188    ) -> Result<Self::Item> {
189        swanky_error::bail!(
190            ErrorKind::UnsupportedError,
191            "Projection gates are unsupported"
192        )
193    }
194}
195
196impl Fancy for CircuitAnalyzer {
197    type Item = AnalyzerItem;
198
199    fn constant(&mut self, _val: u16, q: u16, _: &mut Channel) -> Result<Self::Item> {
200        self.nconstants += 1;
201        Ok(AnalyzerItem {
202            modulus: q,
203            depth: 0,
204        })
205    }
206}
207
208impl FancyEncode for CircuitAnalyzer {
209    fn receive_many(&mut self, moduli: &[u16], _: &mut Channel) -> Result<Vec<Self::Item>> {
210        self.ninputs += moduli.len();
211        Ok(moduli.iter().map(|q| AnalyzerItem::new(*q)).collect())
212    }
213
214    fn encode_many(&mut self, _: &[u16], _: &[u16], _: &mut Channel) -> Result<Vec<Self::Item>> {
215        swanky_error::bail!(
216            ErrorKind::UnsupportedError,
217            "Encoding values is unsupported"
218        )
219    }
220}
221
222impl FancyOutput for CircuitAnalyzer {
223    fn output(&mut self, x: &Self::Item, _: &mut Channel) -> Result<Option<u16>> {
224        self.mul_depth = max(self.mul_depth, x.depth);
225        Ok(None)
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use super::CircuitAnalyzer;
232    use crate::circuits::{aes::AesNonExpanded, sha::Sha256CompressionFunction};
233
234    #[test]
235    fn aes_128_bristol_format_is_correct() {
236        let circuit = AesNonExpanded::new();
237        let mut analyzer = CircuitAnalyzer::new();
238        analyzer.eval(&circuit).unwrap();
239
240        // These counts come from
241        // <https://nigelsmart.github.io/MPC-Circuits/old-circuits.html>
242        //
243        // Note: If we change the AES circuit, these will need to change!
244        assert_eq!(analyzer.nands(), 6800);
245        assert_eq!(analyzer.nxors(), 25124);
246        assert_eq!(analyzer.nnegs, 1692);
247    }
248
249    #[test]
250    fn sha256_compression_fn_bristol_fashion_is_correct() {
251        let circuit = Sha256CompressionFunction::new();
252        let mut analyzer = CircuitAnalyzer::new();
253        analyzer.eval(&circuit).unwrap();
254
255        // These counts come from <https://nigelsmart.github.io/MPC-Circuits/>.
256        //
257        // Note: If we change the SHA-256 compression function circuit, these
258        // will need to change!
259        assert_eq!(analyzer.nands(), 22573);
260        assert_eq!(analyzer.nxors(), 110644);
261        assert_eq!(analyzer.nnegs, 1856);
262        assert_eq!(analyzer.mul_depth, 1607)
263    }
264}
fancy_garbling/circuit_analyzer.rs

fancy_garbling/
circuit_analyzer.rs
