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}