mcircuit/
lib.rs

1//! MCircuit (pronounced mc-urkit) provides a series of types and traits for working with circuits.
2//! Specifically, arithmetic circuits on GF2 and Z64, the former of which are effectively boolean
3//! circuits. It is used by [Reverie](https://github.com/trailofbits/reverie).
4//!
5//! MCircuit includes:
6//! * A circuit parsing library for BLIF files
7//! * Code for evaluating circuits in its gate format
8//! * Traits for constructing, translating, and iterating over gates
9//! * Code to export circuits in the Bristol Fashion format
10
11#[macro_use]
12extern crate variant_count;
13
14use num_traits::Zero;
15use rand::distributions::{Distribution, Standard};
16use rand::Rng;
17use serde::{Deserialize, Serialize};
18
19pub use eval::{dump_vcd, evaluate_composite_program, largest_wires, smallest_wires, VcdDumper};
20pub use has_const::HasConst;
21pub use has_io::HasIO;
22pub use identity::Identity;
23pub use parsers::Parse;
24pub use translatable::Translatable;
25
26mod analysis;
27mod eval;
28pub mod exporters;
29mod has_const;
30mod has_io;
31mod identity;
32mod io_extractors;
33pub mod parsers;
34mod tests;
35mod translatable;
36
37/// Implemented for acceptable types to use as wire values. It would be nice if this could just
38/// be a set of required traits, but `num_traits::is_zero` isn't implemented for `bool`.
39pub trait WireValue: Copy + PartialEq + std::fmt::Debug + Serialize {
40    fn is_zero(&self) -> bool;
41
42    fn to_le_bytes(&self) -> [u8; 8];
43}
44
45impl WireValue for bool {
46    fn is_zero(&self) -> bool {
47        !*self
48    }
49
50    fn to_le_bytes(&self) -> [u8; 8] {
51        [if *self { 1u8 } else { 0u8 }, 0, 0, 0, 0, 0, 0, 0]
52    }
53}
54
55impl WireValue for u64 {
56    fn is_zero(&self) -> bool {
57        Zero::is_zero(self)
58    }
59
60    fn to_le_bytes(&self) -> [u8; 8] {
61        u64::to_le_bytes(*self)
62    }
63}
64
65/// Defines the individual logic gate operations we can support
66#[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq, VariantCount)]
67pub enum Operation<T: WireValue> {
68    /// Read a value from input and emit it on the wire
69    Input(usize),
70    /// Emit a random value on the wire
71    Random(usize),
72    /// Add the two wires together
73    Add(usize, usize, usize),
74    /// Add the wire and the constant
75    AddConst(usize, usize, T),
76    /// Subtract the final wire from the second wire
77    Sub(usize, usize, usize),
78    /// Subtract the constant value from the wire
79    SubConst(usize, usize, T),
80    /// Multiply the two wires together
81    Mul(usize, usize, usize),
82    /// Multiply the first wire by the constant value
83    MulConst(usize, usize, T),
84    /// Assert that the wire has the const value zero
85    AssertZero(usize),
86    /// Emit the const value on the wire
87    Const(usize, T),
88}
89
90/// Defines the possible semantics of the different operands; used to generate random circuits
91#[derive(Clone, Copy)]
92enum OpType<T: WireValue> {
93    /// (dst)
94    Input(fn(usize) -> Operation<T>),
95    /// (dst, constant)
96    InputConst(fn(usize, T) -> Operation<T>),
97    /// (src, constant)
98    Output(fn(usize) -> Operation<T>),
99    /// (dst, src1, src2)
100    Binary(fn(usize, usize, usize) -> Operation<T>),
101    /// (dst, src, constant)
102    BinaryConst(fn(usize, usize, T) -> Operation<T>),
103}
104
105/// Wraps `Operation` to define a field for each gate. Also supports conversions and metadata.
106#[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq)]
107pub enum CombineOperation {
108    /// Circuit Operation on GF2 Finite Field
109    GF2(Operation<bool>),
110    /// Circuit Operation on 64-bit integer ring
111    Z64(Operation<u64>),
112
113    /// Converts a value on GF2 to a value on Z64.
114    /// Takes: (dst, src) where src is the _low bit_ of the 64-bit GF2 slice.
115    /// This means that the least significant bit of the Z64 value will come from the
116    /// GF2 wire with the lowest index. Make sure your circuits are designed accordingly.
117    B2A(usize, usize),
118
119    /// Information about the number of wires needed to evaluate the circuit. As with B2A,
120    /// first item is Z64, second is GF2.
121    SizeHint(usize, usize),
122}
123
124impl<T: WireValue> Operation<T> {
125    /// Convenient way to get a random gate for testing
126    fn random_variant<R: Rng + ?Sized>(rng: &mut R) -> OpType<T> {
127        match rng.gen_range(0..Operation::<T>::VARIANT_COUNT) {
128            0 => OpType::Input(Operation::Input),
129            1 => OpType::Input(Operation::Random),
130            2 => OpType::Binary(Operation::Add),
131            3 => OpType::BinaryConst(Operation::AddConst),
132            4 => OpType::Binary(Operation::Sub),
133            5 => OpType::BinaryConst(Operation::SubConst),
134            6 => OpType::Binary(Operation::Mul),
135            7 => OpType::BinaryConst(Operation::MulConst),
136            8 => OpType::Output(Operation::AssertZero),
137            9 => OpType::InputConst(Operation::Const),
138            _ => {
139                unimplemented!("Operation.random_variant is missing some variants")
140            }
141        }
142    }
143
144    /// Rebuild a gate from its fundamental components. Used by parsers to go from text to gates.
145    fn construct<I1, I2>(
146        ty: OpType<T>,
147        mut inputs: I1,
148        mut outputs: I2,
149        constant: Option<T>,
150    ) -> Operation<T>
151    where
152        I1: Iterator<Item = usize>,
153        I2: Iterator<Item = usize>,
154    {
155        match ty {
156            OpType::Input(op) => op(outputs.next().expect("Input op requires an output wire")),
157            OpType::InputConst(op) => op(
158                outputs
159                    .next()
160                    .expect("InputConst op requires an output wire"),
161                constant.expect("InputConst op requires a constant operand"),
162            ),
163            OpType::Output(op) => op(inputs.next().expect("Output op requires an input wire")),
164            OpType::Binary(op) => op(
165                outputs.next().expect("Binary op requires an output wire"),
166                inputs.next().expect("Binary op requires two input wires"),
167                inputs.next().expect("Binary op requires two input wires"),
168            ),
169            OpType::BinaryConst(op) => op(
170                outputs
171                    .next()
172                    .expect("BinaryConst op requires an output wire"),
173                inputs
174                    .next()
175                    .expect("BinaryConst op requires an input wire"),
176                constant.expect("BinaryConst op requires a constant operand"),
177            ),
178        }
179    }
180}
181
182impl From<Operation<bool>> for CombineOperation {
183    fn from(op: Operation<bool>) -> Self {
184        CombineOperation::GF2(op)
185    }
186}
187
188impl From<Operation<u64>> for CombineOperation {
189    fn from(op: Operation<u64>) -> Self {
190        CombineOperation::Z64(op)
191    }
192}
193
194impl<T: WireValue> Distribution<Operation<T>> for Standard
195where
196    Standard: Distribution<(usize, usize, usize, T)>,
197{
198    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Operation<T> {
199        let (out, i0, i1, c): (usize, usize, usize, T) = rand::random();
200        Operation::<T>::construct(
201            Operation::<T>::random_variant(rng),
202            [i0, i1].iter().copied(),
203            [out].iter().copied(),
204            Some(c),
205        )
206    }
207}
208
209/// Conglomerate trait that wraps all the other useful traits defined in this module.
210pub trait Gate<T>: HasIO + HasConst<T> + Translatable + Identity<T> {}
211impl Gate<u64> for Operation<u64> {}
212impl Gate<bool> for Operation<bool> {}
213impl<T: WireValue> Gate<T> for CombineOperation where CombineOperation: HasConst<T> + Identity<T> {}
mcircuit/lib.rs

mcircuit/
lib.rs
