mpc_engine/
circuit.rs

1//! The [`Circuit`] representation used by the MPC engine.
2//!
3//! A circuit is made up of logic gates and value-carrying wires between the
4//! gates. Each gate takes one or more wires as input, depending on the type of
5//! gate, and has exactly one output wire.
6//!
7//! Conceptually, a circuit is a sequence of input or logic (XOR/AND/NOT) gates,
8//! with all input gates at the beginning of the sequence, followed by all logic
9//! gates. The index of a gate in the sequence determines its "wire index",
10//! which is available as the input to any gate later in the sequence. For
11//! example, in a circuit with two input gates (1 bit for party A, 1 bit for
12//! party B), followed by three logic gates (an XOR of the two input gates, an
13//! AND of the two input gates, and an XOR of these two XOR/AND gates), the
14//! input gates would be the wires 0 and 1, the XOR of these two input gates
15//! would be specified as `Gate::Xor(0, 1)` and have wire index 2, the AND of
16//! the two input gates would be specified as `Gate::And(0, 1)` and have wire
17//! index 3, and the XOR of the two logic gates would be specified as
18//! `Gate::Xor(2, 3)` and have wire index 4:
19//!
20//! ```text
21//! Input A (Wire 0) ----+----------+
22//!                      |          |
23//! Input B (Wire 1) ----|-----+----|-----+
24//!                      |     |    |     |
25//!                      +-XOR-+    |     |
26//!         (Wire 2) =====> |       |     |
27//!                         |       +-AND-+
28//!         (Wire 3) =======|========> |
29//!                         +---XOR----+
30//!         (Wire 4) ==========> |
31//! ```
32//!
33//! The input gates of different parties cannot be interleaved: Each party must
34//! supply all of their inputs before the next party's inputs can start.
35//!
36//! At least one input bit must be specified, and every party contributing
37//! inputs to the circuit has to specify at least one input bit. Party input
38//! gates may not refer to other input gates' wire indices.
39//!
40//! This module is derived from the circuit representation of
41//! [`garble_lang`](https://github.com/sine-fdn/garble-lang/tree/main), the
42//! license of which is reproduced below.
43//!
44//! > MIT License
45//! >
46//! > Copyright (c) 2022 SINE e.V.
47//! >
48//! > Permission is hereby granted, free of charge, to any person obtaining a
49//! > copy of this software and associated documentation files (the "Software"),
50//! > to deal in the Software without restriction, including without limitation
51//! > the rights to use, copy, modify, merge, publish, distribute, sublicense,
52//! > and/or sell copies of the Software, and to permit persons to whom the
53//! > Software is furnished to do so, subject to the following conditions:
54//! >
55//! > The above copyright notice and this permission notice shall be included in
56//! > all copies or substantial portions of the Software.
57//! >
58//! > THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
59//! > IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
60//! > FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
61//! > THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
62//! > LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
63//! > FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
64//! > DEALINGS IN THE SOFTWARE.
65//!
66//!
67
68use crate::STATISTICAL_SECURITY;
69
70/// Data type to uniquely identify gate output wires.
71pub type WireIndex = usize;
72
73/// An input gate or a logic gate with its input wire specification.
74#[derive(Debug, Clone)]
75pub enum WiredGate {
76    /// An input wire, with its value coming directly from one of the parties.
77    /// Its [`WireIndex`] must refer to its own gate index.
78    Input(WireIndex),
79    /// A logical XOR gate attached to the two specified input wires. The
80    /// [`WireIndex`] of each input wire must refer to a lower index than the
81    /// gate's own index.
82    Xor(WireIndex, WireIndex),
83    /// A logical AND gate attached to the two specified input wires. The
84    /// [`WireIndex`] of each input wire must refer to a lower index than the
85    /// gate's own index.
86    And(WireIndex, WireIndex),
87    /// A logical NOT gate attached to the specified input wire. The
88    /// [`WireIndex`] of the input wire must refer to a lower index than the
89    /// gate's own index.
90    Not(WireIndex),
91}
92
93/// Specifies how many input bits a party is expected to contribute to the
94/// evaluation.
95pub type InputWidth = usize;
96/// Representation of a circuit evaluated by an MPC engine.
97#[derive(Debug, Clone)]
98pub struct Circuit {
99    /// The bit-width of the inputs expected by the different parties,
100    /// [`InputWidth`] at index `i` representing the number of input bits for
101    /// party `i`.
102    pub input_widths: Vec<InputWidth>,
103    /// The circuit's gates.
104    pub gates: Vec<WiredGate>,
105    /// The indices of the gates in [`Circuit::gates`] that produce output bits.
106    pub output_gates: Vec<WireIndex>,
107}
108
109/// Errors occurring during the validation or the execution of the MPC protocol.
110#[derive(Debug, PartialEq, Eq)]
111pub enum CircuitError {
112    /// The provided party input does not match the number of input bits for
113    /// that party expected by the circuit.
114    PartyInputMismatch(usize, usize),
115    /// The provided set of inputs does not match the number of party inputs
116    /// expected by the circuit.
117    PartyCountMismatch(usize, usize),
118    /// The gate with the specified wire index contains invalid gate connections
119    /// or is placed out of sequence.
120    InvalidGate(usize),
121    /// The specified output gate does not exist in the circuit.
122    InvalidOutputWire(usize),
123    /// The circuit does not specify any output gates.
124    EmptyOutputSpecification,
125    /// The circuit does not specify input wires.
126    EmptyInputSpecification,
127    /// The circuit specifies a zero-width input.
128    InvalidInputSpecification,
129}
130
131impl std::fmt::Display for CircuitError {
132    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133        match self {
134            CircuitError::PartyInputMismatch(expected_inputs, actual_inputs) => write!(
135                f,
136                "expected {} input bits for a party, but received {} input bits",
137                *expected_inputs, *actual_inputs
138            ),
139            CircuitError::PartyCountMismatch(expected_parties, actual_parties) => write!(
140                f,
141                "expected inputs for {} parties, but received inputs for {} parties",
142                *expected_parties, *actual_parties
143            ),
144            CircuitError::InvalidGate(gate_index) => write!(
145                f,
146                "found out of order placement or invalid wiring at gate index {}",
147                *gate_index
148            ),
149            CircuitError::InvalidOutputWire(oob_index) => {
150                write!(f, "output index {} is out of bounds", *oob_index)
151            }
152            CircuitError::EmptyOutputSpecification => {
153                write!(f, "circuit does not specify output bits")
154            }
155            CircuitError::EmptyInputSpecification => {
156                write!(f, "circuit does not specify any party inputs")
157            }
158            CircuitError::InvalidInputSpecification => {
159                write!(f, "circuit specifies an empty party input")
160            }
161        }
162    }
163}
164
165impl Circuit {
166    /// Number of parties expected to contribute inputs to the circuit.
167    pub fn number_of_parties(&self) -> usize {
168        self.input_widths.len()
169    }
170
171    /// Check validity of circuit specification.
172    ///
173    /// In particular:
174    /// * Validate input specification: Input width specification does not allow
175    ///   0-width inputs and at least one party must provide input bits.
176    /// * Validate gate sequence: All input gates must be at the beginning of
177    ///   the gate sequence, followed only by logic gates.
178    /// * Validate gate wiring: A logic gate with index `i` can only take input
179    ///   wires with strictly smaller indices. An input gate with index `i` must
180    ///   refer to its own index as the input wire index.
181    /// * Validate output specification: The number of specified output wires
182    ///  must be non-zero and all output wire indices must refer to valid wire
183    ///  indices in the circuit, i.e. output wire indices must be smaller or
184    ///  equal to the highest wire index used in the circuit.
185    pub fn validate_circuit_specification(&self) -> Result<(), CircuitError> {
186        // Check input validity.
187        if self.input_widths.is_empty() {
188            return Err(CircuitError::EmptyInputSpecification);
189        }
190        for input_width in &self.input_widths {
191            if *input_width == 0 {
192                return Err(CircuitError::InvalidInputSpecification);
193            }
194        }
195
196        // Check gate and gate sequence validity.
197        let mut total_input_width = 0;
198        for party_input_width in &self.input_widths {
199            total_input_width += party_input_width;
200        }
201
202        for (gate_index, gate) in self.gates.iter().enumerate() {
203            match *gate {
204                WiredGate::Input(x) => {
205                    if x != gate_index || gate_index >= total_input_width {
206                        return Err(CircuitError::InvalidGate(gate_index));
207                    }
208                }
209                WiredGate::Xor(x, y) => {
210                    if x >= gate_index || y >= gate_index || gate_index < total_input_width {
211                        return Err(CircuitError::InvalidGate(gate_index));
212                    }
213                }
214                WiredGate::And(x, y) => {
215                    if x >= gate_index || y >= gate_index || gate_index < total_input_width {
216                        return Err(CircuitError::InvalidGate(gate_index));
217                    }
218                }
219                WiredGate::Not(x) => {
220                    if x >= gate_index || gate_index < total_input_width {
221                        return Err(CircuitError::InvalidGate(gate_index));
222                    }
223                }
224            }
225        }
226
227        // Validate non-empty output specification.
228        if self.output_gates.is_empty() {
229            return Err(CircuitError::EmptyOutputSpecification);
230        }
231
232        // Validate output wire bounds.
233        for &output_wire in &self.output_gates {
234            if output_wire >= self.gates.len() {
235                return Err(CircuitError::InvalidOutputWire(output_wire));
236            }
237        }
238
239        Ok(())
240    }
241
242    /// Validate that a given set of party inputs corresponds to the circuit
243    /// specification.
244    ///
245    /// In particular:
246    /// * Validate that the number of input vectors corresponds to the number of parties
247    ///   expected to provide inputs.
248    /// * Validate, for each input vector, that the number of input bits matches the
249    ///   corresponding parties' expected input width.
250    pub fn validate_input_vectors(&self, inputs: &[Vec<bool>]) -> Result<(), CircuitError> {
251        if self.number_of_parties() != inputs.len() {
252            return Err(CircuitError::PartyCountMismatch(
253                self.number_of_parties(),
254                inputs.len(),
255            ));
256        }
257
258        for (party, &expected_input_gates) in self.input_widths.iter().enumerate() {
259            if expected_input_gates != inputs[party].len() {
260                return Err(CircuitError::PartyInputMismatch(
261                    expected_input_gates,
262                    inputs[party].len(),
263                ));
264            }
265        }
266
267        Ok(())
268    }
269
270    /// Evaluates a circuit with the specified inputs (with one `Vec<bool>` per
271    /// party).
272    ///
273    /// After validation of the circuit specification and validation of the
274    /// provided input vectors, the circuit is evaluated gate by gate:
275    ///
276    /// * Input gates are evaluated as the identity function on the provided
277    ///   input.
278    /// * Logic gates are evaluated by applying the given logical operation to
279    ///   the wire values of the gates' input wires.
280    ///
281    /// Circuit validation ensures that, during sequential evaluation, gate
282    /// input wires can only refer to previously evaluated gates, or values
283    /// provided in the circuit inputs in the case of input gate evaulation.
284    ///
285    /// The circuit output is packed into a bitstring, with the indicated output
286    /// wire values appearing in sequential order.
287    pub fn eval(&self, inputs: &[Vec<bool>]) -> Result<Vec<bool>, CircuitError> {
288        self.validate_circuit_specification()?;
289        self.validate_input_vectors(inputs)?;
290
291        let mut wire_evaluations: Vec<bool> = inputs.iter().flat_map(|b| b.clone()).collect();
292
293        for gate in &self.gates {
294            let output_bit = match gate {
295                WiredGate::Input(x) => wire_evaluations[*x],
296                WiredGate::Xor(x, y) => wire_evaluations[*x] ^ wire_evaluations[*y],
297                WiredGate::And(x, y) => wire_evaluations[*x] & wire_evaluations[*y],
298                WiredGate::Not(x) => !wire_evaluations[*x],
299            };
300            wire_evaluations.push(output_bit);
301        }
302
303        let mut output_packed: Vec<bool> = Vec::with_capacity(self.output_gates.len());
304        for output_gate in &self.output_gates {
305            output_packed.push(wire_evaluations[*output_gate]);
306        }
307        Ok(output_packed)
308    }
309
310    /// Returns the number of gates (i.e. the size) of the circuit.
311    pub fn num_gates(&self) -> usize {
312        self.gates.len()
313    }
314
315    /// Computes the required bucket size for leaky AND triple combination.
316    pub fn and_bucket_size(&self) -> usize {
317        (STATISTICAL_SECURITY as u32 / self.num_gates().ilog2())
318            .try_into()
319            .unwrap()
320    }
321
322    /// Returns the number of AND gates in the circuit.
323    pub fn num_and_gates(&self) -> usize {
324        self.gates
325            .iter()
326            .filter(|gate| matches!(gate, WiredGate::And(_, _)))
327            .count()
328    }
329    /// Computes the total number of share authentications that will be necessary
330    /// to evaluate this circuit using the MPC protocol, excluding malicious security overhead.
331    pub fn share_authentication_cost(&self) -> usize {
332        let mut result: usize = 0;
333
334        for party_input_width in self.input_widths.iter() {
335            result += party_input_width;
336        }
337
338        let num_and_gates = self
339            .gates
340            .iter()
341            .filter(|gate| matches!(gate, WiredGate::And(_, _)))
342            .count();
343
344        result += num_and_gates;
345        result += num_and_gates * 3 * self.and_bucket_size();
346
347        result
348    }
349}