fancy_garbling/
informer.rs

1//! `Informer` runs a fancy computation and learns information from it.
2
3use crate::{
4    FancyArithmetic, FancyBinary,
5    fancy::{Fancy, FancyInput, FancyReveal, HasModulus},
6};
7use std::collections::{HashMap, HashSet};
8
9/// Implements `Fancy`. Used to learn information about a `Fancy` computation in
10/// a lightweight way.
11pub struct Informer<F: Fancy> {
12    /// The underlying fancy object.
13    pub underlying: F,
14    stats: InformerStats,
15}
16
17/// The statistics revealed by the informer.
18#[derive(Clone, Debug)]
19pub struct InformerStats {
20    garbler_input_moduli: Vec<u16>,
21    evaluator_input_moduli: Vec<u16>,
22    constants: HashSet<(u16, u16)>,
23    outputs: Vec<u16>,
24    nadds: usize,
25    nsubs: usize,
26    ncmuls: usize,
27    nmuls: usize,
28    nprojs: usize,
29    nciphertexts: usize,
30    moduli: HashMap<u16, usize>,
31}
32
33impl InformerStats {
34    /// Number of garbler inputs in the fancy computation.
35    pub fn num_garbler_inputs(&self) -> usize {
36        self.garbler_input_moduli.len()
37    }
38
39    /// Moduli of garbler inputs in the fancy computation.
40    pub fn garbler_input_moduli(&self) -> Vec<u16> {
41        self.garbler_input_moduli.clone()
42    }
43
44    /// Number of evaluator inputs in the fancy computation.
45    pub fn num_evaluator_inputs(&self) -> usize {
46        self.evaluator_input_moduli.len()
47    }
48
49    /// Moduli of evaluator inputs in the fancy computation.
50    pub fn evaluator_input_moduli(&self) -> Vec<u16> {
51        self.evaluator_input_moduli.clone()
52    }
53
54    /// Number of constants in the fancy computation.
55    pub fn num_consts(&self) -> usize {
56        self.constants.len()
57    }
58
59    /// Number of outputs in the fancy computation.
60    pub fn num_outputs(&self) -> usize {
61        self.outputs.len()
62    }
63
64    /// Number of output ciphertexts.
65    pub fn num_output_ciphertexts(&self) -> usize {
66        self.outputs.iter().map(|&m| m as usize).sum()
67    }
68
69    /// Number of additions in the fancy computation.
70    pub fn num_adds(&self) -> usize {
71        self.nadds
72    }
73
74    /// Number of subtractions in the fancy computation.
75    pub fn num_subs(&self) -> usize {
76        self.nsubs
77    }
78
79    /// Number of scalar multiplications in the fancy computation.
80    pub fn num_cmuls(&self) -> usize {
81        self.ncmuls
82    }
83
84    /// Number of multiplications in the fancy computation.
85    pub fn num_muls(&self) -> usize {
86        self.nmuls
87    }
88
89    /// Number of projections in the fancy computation.
90    pub fn num_projs(&self) -> usize {
91        self.nprojs
92    }
93
94    /// Number of ciphertexts in the fancy computation.
95    pub fn num_ciphertexts(&self) -> usize {
96        self.nciphertexts
97    }
98}
99
100impl std::fmt::Display for InformerStats {
101    /// Print information about the fancy computation.
102    ///
103    /// For example, below is the output when run on `circuits/AES-non-expanded.txt`:
104    /// ```text
105    /// computation info:
106    ///   garbler inputs:                  128 // comms cost: 16 Kb
107    ///   evaluator inputs:                128 // comms cost: 48 Kb
108    ///   outputs:                         128
109    ///   output ciphertexts:              256 // comms cost: 32 Kb
110    ///   constants:                         1 // comms cost: 0.125 Kb
111    ///   additions:                     25124
112    ///   subtractions:                   1692
113    ///   cmuls:                             0
114    ///   projections:                       0
115    ///   multiplications:                6800
116    ///   ciphertexts:                   13600 // comms cost: 1.66 Mb (1700.00 Kb)
117    ///   total comms cost:            1.75 Mb // 1700.00 Kb
118    /// ```
119    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
120        let mut total = 0.0;
121        writeln!(f, "computation info:")?;
122        let comm = self.num_garbler_inputs() as f64 * 128.0 / 1000.0;
123
124        writeln!(
125            f,
126            "  garbler inputs:     {:16} // communication: {:.2} Kb",
127            self.num_garbler_inputs(),
128            comm
129        )?;
130        total += comm;
131        // The cost of IKNP is 256 bits for one random and one 128 bit string
132        // dependent on the random one. This is for each input bit, so for
133        // modulus `q` we need to do `log2(q)` OTs.
134        let comm = self.evaluator_input_moduli.iter().fold(0.0, |acc, q| {
135            acc + (*q as f64).log2().ceil() * 384.0 / 1000.0
136        });
137
138        writeln!(
139            f,
140            "  evaluator inputs:   {:16} // communication: {:.2} Kb",
141            self.num_evaluator_inputs(),
142            comm
143        )?;
144        total += comm;
145        let comm = self.num_output_ciphertexts() as f64 * 128.0 / 1000.0;
146
147        writeln!(f, "  outputs:            {:16}", self.num_outputs())?;
148        writeln!(
149            f,
150            "  output ciphertexts: {:16} // communication: {:.2} Kb",
151            self.num_output_ciphertexts(),
152            comm
153        )?;
154        total += comm;
155        let comm = self.num_consts() as f64 * 128.0 / 1000.0;
156
157        writeln!(
158            f,
159            "  constants:          {:16} // communication: {:.2} Kb",
160            self.num_consts(),
161            comm
162        )?;
163        total += comm;
164
165        writeln!(f, "  additions:          {:16}", self.num_adds())?;
166        writeln!(f, "  subtractions:       {:16}", self.num_subs())?;
167        writeln!(f, "  cmuls:              {:16}", self.num_cmuls())?;
168        writeln!(f, "  projections:        {:16}", self.num_projs())?;
169        writeln!(f, "  multiplications:    {:16}", self.num_muls())?;
170        let cs = self.num_ciphertexts();
171        let kb = cs as f64 * 128.0 / 1000.0;
172        let mb = kb / 1000.0;
173        writeln!(
174            f,
175            "  ciphertexts:        {:16} // communication: {:.2} Mb ({:.2} Kb)",
176            cs, mb, kb
177        )?;
178        total += kb;
179
180        let mb = total / 1000.0;
181        writeln!(f, "  total communication:  {:11.2} Mb", mb)?;
182        writeln!(f, "  wire moduli: {:#?}", self.moduli)?;
183        Ok(())
184    }
185}
186
187impl<F: Fancy> Informer<F> {
188    /// Make a new `Informer`.
189    pub fn new(underlying: F) -> Informer<F> {
190        Informer {
191            underlying,
192            stats: InformerStats {
193                garbler_input_moduli: Vec::new(),
194                evaluator_input_moduli: Vec::new(),
195                constants: HashSet::new(),
196                outputs: Vec::new(),
197                nadds: 0,
198                nsubs: 0,
199                ncmuls: 0,
200                nmuls: 0,
201                nprojs: 0,
202                nciphertexts: 0,
203                moduli: HashMap::new(),
204            },
205        }
206    }
207
208    /// Get the statistics collected by the `Informer`
209    pub fn stats(&self) -> InformerStats {
210        self.stats.clone()
211    }
212
213    fn update_moduli(&mut self, q: u16) {
214        let entry = self.stats.moduli.entry(q).or_insert(0);
215        *entry += 1;
216    }
217}
218
219impl<F: Fancy + FancyInput<Item = <F as Fancy>::Item, Error = <F as Fancy>::Error>> FancyInput
220    for Informer<F>
221{
222    type Item = <F as Fancy>::Item;
223    type Error = <F as Fancy>::Error;
224
225    fn receive_many(&mut self, moduli: &[u16]) -> Result<Vec<Self::Item>, Self::Error> {
226        self.stats
227            .garbler_input_moduli
228            .extend(moduli.iter().cloned());
229        self.underlying.receive_many(moduli)
230    }
231
232    fn encode_many(
233        &mut self,
234        values: &[u16],
235        moduli: &[u16],
236    ) -> Result<Vec<Self::Item>, Self::Error> {
237        self.stats
238            .garbler_input_moduli
239            .extend(moduli.iter().cloned());
240        self.underlying.encode_many(values, moduli)
241    }
242}
243
244impl<F: FancyBinary> FancyBinary for Informer<F> {
245    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
246        let result = self.underlying.xor(x, y)?;
247        self.stats.nadds += 1;
248        self.update_moduli(x.modulus());
249        Ok(result)
250    }
251
252    fn and(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
253        let result = self.underlying.and(x, y)?;
254        self.stats.nmuls += 1;
255        self.stats.nciphertexts += 2;
256        self.update_moduli(x.modulus());
257        Ok(result)
258    }
259
260    fn negate(&mut self, x: &Self::Item) -> Result<Self::Item, Self::Error> {
261        let result = self.underlying.negate(x)?;
262
263        // Technically only the garbler adds: noop for the evaluator
264        self.stats.nadds += 1;
265        self.update_moduli(x.modulus());
266        Ok(result)
267    }
268}
269
270impl<F: FancyArithmetic> FancyArithmetic for Informer<F> {
271    // In general, for the below, we first check to see if the result succeeds before
272    // updating the stats. That way we can avoid checking multiple times that, e.g.
273    // the moduli are equal.
274
275    fn add(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
276        let result = self.underlying.add(x, y)?;
277        self.stats.nadds += 1;
278        self.update_moduli(x.modulus());
279        Ok(result)
280    }
281
282    fn sub(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
283        let result = self.underlying.sub(x, y)?;
284        self.stats.nsubs += 1;
285        self.update_moduli(x.modulus());
286        Ok(result)
287    }
288
289    fn cmul(&mut self, x: &Self::Item, y: u16) -> Result<Self::Item, Self::Error> {
290        let result = self.underlying.cmul(x, y)?;
291        self.stats.ncmuls += 1;
292        self.update_moduli(x.modulus());
293        Ok(result)
294    }
295
296    fn mul(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
297        if x.modulus() < y.modulus() {
298            return self.mul(y, x);
299        }
300        let result = self.underlying.mul(x, y)?;
301        self.stats.nmuls += 1;
302        self.stats.nciphertexts += x.modulus() as usize + y.modulus() as usize - 2;
303        if x.modulus() != y.modulus() {
304            // there is an extra ciphertext to support nonequal inputs
305            self.stats.nciphertexts += 1;
306        }
307        self.update_moduli(x.modulus());
308        Ok(result)
309    }
310
311    fn proj(
312        &mut self,
313        x: &Self::Item,
314        q: u16,
315        tt: Option<Vec<u16>>,
316    ) -> Result<Self::Item, Self::Error> {
317        let result = self.underlying.proj(x, q, tt)?;
318        self.stats.nprojs += 1;
319        self.stats.nciphertexts += x.modulus() as usize - 1;
320        self.update_moduli(q);
321        Ok(result)
322    }
323}
324
325impl<F: Fancy> Fancy for Informer<F> {
326    type Item = F::Item;
327    type Error = F::Error;
328
329    fn constant(&mut self, val: u16, q: u16) -> Result<Self::Item, Self::Error> {
330        self.stats.constants.insert((val, q));
331        self.update_moduli(q);
332        self.underlying.constant(val, q)
333    }
334
335    fn output(&mut self, x: &Self::Item) -> Result<Option<u16>, Self::Error> {
336        let result = self.underlying.output(x)?;
337        self.stats.outputs.push(x.modulus());
338        Ok(result)
339    }
340}
341
342impl<F: Fancy + FancyReveal> FancyReveal for Informer<F> {
343    fn reveal(&mut self, x: &Self::Item) -> Result<u16, Self::Error> {
344        self.underlying.reveal(x)
345    }
346}
fancy_garbling/informer.rs

fancy_garbling/
informer.rs
