fancy_garbling/
parser.rs

1//! Functions for parsing and running circuit files.
2//!
3//! This module provides parsers for two Bristol circuit formats:
4//!
5//! - **Bristol Format**: The original format:
6//!   <https://nigelsmart.github.io/MPC-Circuits/old-circuits.html>
7//! - **Bristol Fashion**: The new format: <https://nigelsmart.github.io/MPC-Circuits>
8
9use crate::circuit::{BinaryCircuit, BinaryGate};
10use regex::{Captures, Regex};
11use std::{io::BufRead, str::FromStr};
12use swanky_error::{ErrorKind, Result, WrapErr, ensure, swanky_error};
13
14enum GateType {
15    AndGate,
16    XorGate,
17}
18
19fn cap2int(cap: &Captures, idx: usize) -> Result<usize> {
20    let s = cap
21        .get(idx)
22        .ok_or_else(|| swanky_error!(ErrorKind::OtherError, "Failed to match index '{idx}'"))?;
23    FromStr::from_str(s.as_str())
24        .wrap_err(ErrorKind::OtherError, "Failed to convert value to string")
25}
26
27fn cap2typ(cap: &Captures, idx: usize) -> Result<GateType> {
28    let s = cap
29        .get(idx)
30        .ok_or_else(|| swanky_error!(ErrorKind::OtherError, "Failed to match index '{idx}'"))?;
31    let s = s.as_str();
32    match s {
33        "AND" => Ok(GateType::AndGate),
34        "XOR" => Ok(GateType::XorGate),
35        s => swanky_error::bail!(ErrorKind::OtherError, "Unknown gate type '{s}'"),
36    }
37}
38
39fn regex2captures<'t>(re: &Regex, line: &'t str) -> Result<Captures<'t>> {
40    re.captures(line)
41        .ok_or_else(|| swanky_error!(ErrorKind::OtherError, "Failed to find match for regex"))
42}
43
44impl BinaryCircuit {
45    /// Generates a new [`BinaryCircuit`] from the provided [`BufRead`]er. The file
46    /// must follow the Bristol Fashion format.
47    pub fn parse_bristol_fashion(mut reader: impl BufRead) -> Result<Self> {
48        // Parse first line: "ngates nwires\n".
49        let mut line = String::new();
50        reader
51            .read_line(&mut line)
52            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
53        let parts = line.split_whitespace().collect::<Vec<_>>();
54        ensure!(
55            parts.len() == 2,
56            ErrorKind::OtherError,
57            "Failed to parse gate and wire count"
58        );
59        let ngates = FromStr::from_str(parts[0])
60            .wrap_err(ErrorKind::OtherError, "Failed to parse gate count")?;
61        let nwires: usize = FromStr::from_str(parts[1])
62            .wrap_err(ErrorKind::OtherError, "Failed to parse wire count")?;
63
64        // Parse second line: "ninputs input1 input2 ...\n".
65        let mut line = String::new();
66        reader
67            .read_line(&mut line)
68            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
69        let parts = line.split_whitespace().collect::<Vec<_>>();
70        ensure!(!parts.is_empty(), ErrorKind::OtherError, "Empty input line");
71
72        let ninputs: usize = FromStr::from_str(parts[0])
73            .wrap_err(ErrorKind::OtherError, "Failed to parse number of parties")?;
74        ensure!(
75            parts.len() == ninputs + 1,
76            ErrorKind::OtherError,
77            "Expected {} input values, got {}",
78            ninputs,
79            parts.len() - 1
80        );
81        let mut ninputs_total = 0;
82        for part in parts.iter().skip(1) {
83            let ninputs: usize = FromStr::from_str(part)
84                .wrap_err(ErrorKind::OtherError, "Failed to parse input count")?;
85            ninputs_total += ninputs;
86        }
87
88        // Parse third line: nparties_output output_bits_party1 output_bits_party2 ...\n
89        // Note: nparties_output can be different from nparties (input parties)
90        let mut line = String::new();
91        reader
92            .read_line(&mut line)
93            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
94        let parts = line.split_whitespace().collect::<Vec<_>>();
95        ensure!(
96            !parts.is_empty(),
97            ErrorKind::OtherError,
98            "Empty output line"
99        );
100        let noutputs: usize = FromStr::from_str(parts[0]).wrap_err(
101            ErrorKind::OtherError,
102            "Failed to parse number of output parties",
103        )?;
104        ensure!(
105            parts.len() == noutputs + 1,
106            ErrorKind::OtherError,
107            "Expected {} output values, got {}",
108            noutputs,
109            parts.len() - 1
110        );
111        let mut noutputs_total = 0;
112        for part in parts.iter().skip(1) {
113            let noutputs: usize = FromStr::from_str(part)
114                .wrap_err(ErrorKind::OtherError, "Failed to parse output count")?;
115            noutputs_total += noutputs;
116        }
117
118        let mut circ = Self::new(Some(ngates));
119
120        let re1 = Regex::new(r"1 1 (\d+) (\d+) INV").expect("regex should be valid");
121        let re2 = Regex::new(r"2 1 (\d+) (\d+) (\d+) ((AND|XOR))").expect("regex should be valid");
122
123        let mut id = 0;
124
125        // Process inputs.
126        for i in 0..ninputs_total {
127            circ.gates.push(BinaryGate::Input { id: i });
128            circ.input_refs.push(i);
129        }
130        // Create a constant wire for negations.
131        circ.gates.push(BinaryGate::Constant { val: 1 });
132        circ.const_refs.push(ninputs_total);
133        // Process outputs.
134        for i in (0..noutputs_total).rev() {
135            circ.output_refs.push(nwires - noutputs_total + i);
136        }
137
138        // Parse gate definitions (same as Bristol Format).
139        for line in reader.lines() {
140            let line = line.wrap_err(ErrorKind::OtherError, "Failed to read line")?;
141            let line = line.trim();
142            if line.is_empty() {
143                continue;
144            }
145            match line.chars().next() {
146                Some('1') => {
147                    let cap = regex2captures(&re1, line)?;
148                    let yref = cap2int(&cap, 1)?;
149                    let out = cap2int(&cap, 2)?;
150                    circ.gates.push(BinaryGate::Inv {
151                        xref: yref,
152                        out: Some(out),
153                    })
154                }
155                Some('2') => {
156                    let cap = regex2captures(&re2, line)?;
157                    let xref = cap2int(&cap, 1)?;
158                    let yref = cap2int(&cap, 2)?;
159                    let out = cap2int(&cap, 3)?;
160                    let typ = cap2typ(&cap, 4)?;
161                    let gate = match typ {
162                        GateType::AndGate => {
163                            let gate = BinaryGate::And {
164                                xref,
165                                yref,
166                                id,
167                                out: Some(out),
168                            };
169                            id += 1;
170                            gate
171                        }
172                        GateType::XorGate => BinaryGate::Xor {
173                            xref,
174                            yref,
175                            out: Some(out),
176                        },
177                    };
178                    circ.gates.push(gate);
179                }
180                None => break,
181                _ => {
182                    swanky_error::bail!(ErrorKind::OtherError, "Invalid gate definition: {}", line);
183                }
184            }
185        }
186        Ok(circ)
187    }
188
189    /// Generates a new [`BinaryCircuit`] from the provided [`BufRead`]er. The file
190    /// must follow the Bristol Format given here:
191    /// <https://nigelsmart.github.io/MPC-Circuits/old-circuits.html>.
192    pub fn parse_bristol_format(mut reader: impl BufRead) -> Result<Self> {
193        // Parse first line: ngates nwires\n
194        let mut line = String::new();
195        reader
196            .read_line(&mut line)
197            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
198        let re = Regex::new(r"(\d+)\s+(\d+)").expect("regex should be valid");
199        let cap = regex2captures(&re, &line)?;
200        let ngates = cap2int(&cap, 1)?;
201        let nwires = cap2int(&cap, 2)?;
202
203        // Parse second line: n1 n2 n3\n
204        let mut line = String::new();
205        reader
206            .read_line(&mut line)
207            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
208        let re = Regex::new(r"(\d+)\s+(\d+)\s+(\d+)").expect("regex should be valid");
209        let cap = regex2captures(&re, &line)?;
210        let n1 = cap2int(&cap, 1)?; // Number of garbler inputs
211        let n2 = cap2int(&cap, 2)?; // Number of evaluator inputs
212        let n3 = cap2int(&cap, 3)?; // Number of outputs
213
214        // Parse third line: \n
215        let mut line = String::new();
216        reader
217            .read_line(&mut line)
218            .wrap_err(ErrorKind::OtherError, "Failed to read line")?;
219        #[allow(clippy::trivial_regex)]
220        let re = Regex::new(r"\n").expect("regex should be valid");
221        let _ = regex2captures(&re, &line)?;
222
223        let mut circ = Self::new(Some(ngates));
224
225        let re1 = Regex::new(r"1 1 (\d+) (\d+) INV").expect("regex should be valid");
226        let re2 = Regex::new(r"2 1 (\d+) (\d+) (\d+) ((AND|XOR))").expect("regex should be valid");
227
228        let mut id = 0;
229
230        // Process inputs.
231        for i in 0..n1 + n2 {
232            circ.gates.push(BinaryGate::Input { id: i });
233            circ.input_refs.push(i);
234        }
235        // Create a constant wire for negations.
236        // This is no longer required for the implementation
237        // of our garbler/evaluator pair. Consider removing
238        circ.gates.push(BinaryGate::Constant { val: 1 });
239        circ.const_refs.push(n1 + n2);
240        // Process outputs.
241        for i in 0..n3 {
242            circ.output_refs.push(nwires - n3 + i);
243        }
244        for line in reader.lines() {
245            let line = line.wrap_err(ErrorKind::OtherError, "Failed to read line")?;
246            match line.chars().next() {
247                Some('1') => {
248                    let cap = regex2captures(&re1, &line)?;
249                    let yref = cap2int(&cap, 1)?;
250                    let out = cap2int(&cap, 2)?;
251                    circ.gates.push(BinaryGate::Inv {
252                        xref: yref,
253                        out: Some(out),
254                    })
255                }
256                Some('2') => {
257                    let cap = regex2captures(&re2, &line)?;
258                    let xref = cap2int(&cap, 1)?;
259                    let yref = cap2int(&cap, 2)?;
260                    let out = cap2int(&cap, 3)?;
261                    let typ = cap2typ(&cap, 4)?;
262                    let gate = match typ {
263                        GateType::AndGate => {
264                            let gate = BinaryGate::And {
265                                xref,
266                                yref,
267                                id,
268                                out: Some(out),
269                            };
270                            id += 1;
271                            gate
272                        }
273                        GateType::XorGate => BinaryGate::Xor {
274                            xref,
275                            yref,
276                            out: Some(out),
277                        },
278                    };
279                    circ.gates.push(gate);
280                }
281                None => break,
282                _ => {
283                    swanky_error::bail!(ErrorKind::OtherError, "Invalid wire value");
284                }
285            }
286        }
287        Ok(circ)
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use crate::circuit::{BinaryCircuit, BinaryGate};
294    use std::io::Cursor;
295
296    #[test]
297    fn bristol_format_parser_works() {
298        // Tests all the circuits in the `circuits/bristol-format` directory.
299
300        let result = BinaryCircuit::parse_bristol_format(Cursor::<&'static [u8]>::new(
301            include_bytes!("../circuits/bristol-format/adder_32bit.txt"),
302        ));
303        assert!(result.is_ok());
304
305        let result = BinaryCircuit::parse_bristol_format(Cursor::<&'static [u8]>::new(
306            include_bytes!("../circuits/bristol-format/AES-non-expanded.txt"),
307        ));
308        assert!(result.is_ok());
309
310        let result = BinaryCircuit::parse_bristol_format(Cursor::<&'static [u8]>::new(
311            include_bytes!("../circuits/bristol-format/sha-1.txt"),
312        ));
313        assert!(result.is_ok());
314
315        let result = BinaryCircuit::parse_bristol_format(Cursor::<&'static [u8]>::new(
316            include_bytes!("../circuits/bristol-format/sha-256.txt"),
317        ));
318        assert!(result.is_ok());
319    }
320
321    #[test]
322    fn bristol_fashion_parser_works() {
323        // Tests all the circuits in the `circuits/bristol-fashion` directory.
324
325        // Test AES-128 circuit.
326        let result = BinaryCircuit::parse_bristol_fashion(Cursor::<&'static [u8]>::new(
327            include_bytes!("../circuits/bristol-fashion/aes_128.txt"),
328        ));
329        assert!(result.is_ok());
330        let circuit = result.unwrap();
331        // AES-128: 2 input values with 128 bits each = 256 inputs total.
332        assert_eq!(circuit.input_refs.len(), 256);
333        // AES-128: 1 output value with 128 bits output = 128 outputs total.
334        assert_eq!(circuit.output_refs.len(), 128);
335        // Verify circuit has gates.
336        assert!(!circuit.gates.is_empty());
337        // First 256 gates should be inputs.
338        for i in 0..256 {
339            if let BinaryGate::Input { id } = circuit.gates[i] {
340                assert_eq!(id, i);
341            } else {
342                panic!("Expected Input gate at position {}", i);
343            }
344        }
345
346        // Test SHA-256 circuit.
347        let result = BinaryCircuit::parse_bristol_fashion(Cursor::<&'static [u8]>::new(
348            include_bytes!("../circuits/bristol-fashion/sha256.txt"),
349        ));
350        assert!(result.is_ok());
351        let circuit = result.unwrap();
352        // SHA-256: 2 parties with 512 + 256 = 768 inputs total
353        assert_eq!(circuit.input_refs.len(), 768);
354        // SHA-256: 1 party with 256 bits output = 256 outputs total
355        assert_eq!(circuit.output_refs.len(), 256);
356        // Verify circuit has gates
357        assert!(!circuit.gates.is_empty());
358    }
359}
fancy_garbling/parser.rs

fancy_garbling/
parser.rs
