fancy_garbling/
fancy.rs

1//! The `Fancy` trait represents the kinds of computations possible in `fancy-garbling`.
2//!
3//! An implementer must be able to create inputs, constants, do modular arithmetic, and
4//! create projections.
5
6use crate::errors::FancyError;
7use itertools::Itertools;
8
9mod binary;
10mod bundle;
11mod crt;
12mod input;
13mod reveal;
14pub use binary::{BinaryBundle, BinaryGadgets};
15pub use bundle::{ArithmeticBundleGadgets, BinaryBundleGadgets, Bundle, BundleGadgets};
16pub use crt::{CrtBundle, CrtGadgets};
17pub use input::FancyInput;
18pub use reveal::FancyReveal;
19
20/// An object that has some modulus. Basic object of `Fancy` computations.
21pub trait HasModulus {
22    /// The modulus of the wire.
23    fn modulus(&self) -> u16;
24}
25
26/// Fancy DSL providing binary operations
27///
28pub trait FancyBinary: Fancy {
29    /// Binary Xor
30    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error>;
31
32    /// Binary And
33    fn and(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error>;
34
35    /// Binary Not
36    fn negate(&mut self, x: &Self::Item) -> Result<Self::Item, Self::Error>;
37
38    /// Uses Demorgan's Rule implemented with an and gate and negation.
39    fn or(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
40        let notx = self.negate(x)?;
41        let noty = self.negate(y)?;
42        let z = self.and(&notx, &noty)?;
43        self.negate(&z)
44    }
45
46    /// Binary adder. Returns the result and the carry.
47    fn adder(
48        &mut self,
49        x: &Self::Item,
50        y: &Self::Item,
51        carry_in: Option<&Self::Item>,
52    ) -> Result<(Self::Item, Self::Item), Self::Error> {
53        if let Some(c) = carry_in {
54            let z1 = self.xor(x, y)?;
55            let z2 = self.xor(&z1, c)?;
56            let z3 = self.xor(x, c)?;
57            let z4 = self.and(&z1, &z3)?;
58            let carry = self.xor(&z4, x)?;
59            Ok((z2, carry))
60        } else {
61            let z = self.xor(x, y)?;
62            let carry = self.and(x, y)?;
63            Ok((z, carry))
64        }
65    }
66    /// Returns 1 if all wires equal 1.
67    fn and_many(&mut self, args: &[Self::Item]) -> Result<Self::Item, Self::Error> {
68        if args.is_empty() {
69            return Err(Self::Error::from(FancyError::InvalidArgNum {
70                got: args.len(),
71                needed: 1,
72            }));
73        }
74        args.iter()
75            .skip(1)
76            .fold(Ok(args[0].clone()), |acc, x| self.and(&(acc?), x))
77    }
78
79    /// Returns 1 if any wire equals 1.
80    fn or_many(&mut self, args: &[Self::Item]) -> Result<Self::Item, Self::Error> {
81        if args.is_empty() {
82            return Err(Self::Error::from(FancyError::InvalidArgNum {
83                got: args.len(),
84                needed: 1,
85            }));
86        }
87        args.iter()
88            .skip(1)
89            .fold(Ok(args[0].clone()), |acc, x| self.or(&(acc?), x))
90    }
91
92    /// XOR many wires together
93    fn xor_many(&mut self, args: &[Self::Item]) -> Result<Self::Item, Self::Error> {
94        if args.len() < 2 {
95            return Err(Self::Error::from(FancyError::InvalidArgNum {
96                got: args.len(),
97                needed: 2,
98            }));
99        }
100        args.iter()
101            .skip(1)
102            .fold(Ok(args[0].clone()), |acc, x| self.xor(&(acc?), x))
103    }
104
105    /// If `x = 0` returns the constant `b1` else return `b2`. Folds constants if possible.
106    fn mux_constant_bits(
107        &mut self,
108        x: &Self::Item,
109        b1: bool,
110        b2: bool,
111    ) -> Result<Self::Item, Self::Error> {
112        match (b1, b2) {
113            (false, true) => Ok(x.clone()),
114            (true, false) => self.negate(x),
115            (false, false) => self.constant(0, 2),
116            (true, true) => self.constant(1, 2),
117        }
118    }
119
120    /// If `b = 0` returns `x` else `y`.
121    fn mux(
122        &mut self,
123        b: &Self::Item,
124        x: &Self::Item,
125        y: &Self::Item,
126    ) -> Result<Self::Item, Self::Error> {
127        let xor = self.xor(x, y)?;
128        let and = self.and(b, &xor)?;
129        self.xor(&and, x)
130    }
131}
132
133/// DSL for the basic computations supported by `fancy-garbling`.
134///
135/// Primarily used as a supertrait for `FancyBinary` and `FancyArithmetic`,
136/// which indicate computation supported by the DSL.
137pub trait Fancy {
138    /// The underlying wire datatype created by an object implementing `Fancy`.
139    type Item: Clone + HasModulus;
140
141    /// Errors which may be thrown by the users of Fancy.
142    type Error: std::fmt::Debug + std::fmt::Display + std::convert::From<FancyError>;
143
144    /// Create a constant `x` with modulus `q`.
145    fn constant(&mut self, x: u16, q: u16) -> Result<Self::Item, Self::Error>;
146
147    /// Process this wire as output. Some `Fancy` implementers don't actually *return*
148    /// output, but they need to be involved in the process, so they can return `None`.
149    fn output(&mut self, x: &Self::Item) -> Result<Option<u16>, Self::Error>;
150
151    /// Output a slice of wires.
152    fn outputs(&mut self, xs: &[Self::Item]) -> Result<Option<Vec<u16>>, Self::Error> {
153        let mut zs = Vec::with_capacity(xs.len());
154        for x in xs.iter() {
155            zs.push(self.output(x)?);
156        }
157        Ok(zs.into_iter().collect())
158    }
159}
160
161/// DSL for arithmetic computation.
162pub trait FancyArithmetic: Fancy {
163    /// Add `x` and `y`.
164    fn add(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error>;
165
166    /// Subtract `x` and `y`.
167    fn sub(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error>;
168
169    /// Multiply `x` times the constant `c`.
170    fn cmul(&mut self, x: &Self::Item, c: u16) -> Result<Self::Item, Self::Error>;
171
172    /// Multiply `x` and `y`.
173    fn mul(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error>;
174
175    /// Project `x` according to the truth table `tt`. Resulting wire has modulus `q`.
176    ///
177    /// Optional `tt` is useful for hiding the gate from the evaluator.
178    fn proj(
179        &mut self,
180        x: &Self::Item,
181        q: u16,
182        tt: Option<Vec<u16>>,
183    ) -> Result<Self::Item, Self::Error>;
184
185    ////////////////////////////////////////////////////////////////////////////////
186    // Functions built on top of arithmetic fancy operations.
187
188    /// Sum up a slice of wires.
189    fn add_many(&mut self, args: &[Self::Item]) -> Result<Self::Item, Self::Error> {
190        if args.len() < 2 {
191            return Err(Self::Error::from(FancyError::InvalidArgNum {
192                got: args.len(),
193                needed: 2,
194            }));
195        }
196        let mut z = args[0].clone();
197        for x in args.iter().skip(1) {
198            z = self.add(&z, x)?;
199        }
200        Ok(z)
201    }
202    /// Change the modulus of `x` to `to_modulus` using a projection gate.
203    fn mod_change(&mut self, x: &Self::Item, to_modulus: u16) -> Result<Self::Item, Self::Error> {
204        let from_modulus = x.modulus();
205        if from_modulus == to_modulus {
206            return Ok(x.clone());
207        }
208        let tab = (0..from_modulus).map(|x| x % to_modulus).collect_vec();
209        self.proj(x, to_modulus, Some(tab))
210    }
211}
212
213macro_rules! check_binary {
214    ($x:ident) => {
215        if $x.modulus() != 2 {
216            return Err(Self::Error::from(FancyError::InvalidArgMod {
217                got: $x.modulus(),
218                needed: 2,
219            }));
220        }
221    };
222}
223
224/// Given an `FancyArithmetic` implementation, it is always possible to derive
225/// the operations required for `FancyBinary` by using the given arithmetic gadgets.
226///
227/// In this macro, `xor` and `and` use `add` and `mul` respectively as a subroutine,
228/// while `negate` xors the wire with a constant.
229/// Additionally, the modulus of each input wire is checked to make sure it is equal to 2.
230/// Note, that there are frequently better ways to implement some of these operations (e.g. negate
231/// in GC can often be written without requiring any communication).
232/// However, this is not always relevant, such as when implementing the `Fancy` DSLs for `Dummy`.
233///
234/// Right now the macro can handle X or X<Y,...> mainly because I used it for `CircuitBuilder<ArithmeticCircuit>`
235macro_rules! derive_binary {
236    ($f:ident$(<$( $t:tt ),+>)?) => {
237        impl FancyBinary for $f$(< $($t),* >)? {
238            fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
239                check_binary!(x);
240                check_binary!(y);
241
242                self.add(x, y)
243            }
244
245            fn and(&mut self, x: &Self::Item, y: &Self::Item) -> Result<Self::Item, Self::Error> {
246                check_binary!(x);
247                check_binary!(y);
248
249                self.mul(x, y)
250            }
251
252            fn negate(&mut self, x: &Self::Item) -> Result<Self::Item, Self::Error> {
253                check_binary!(x);
254
255                let c = self.constant(1, 2)?;
256                self.xor(x, &c)
257            }
258        }
259    };
260}
261pub(crate) use check_binary;
262pub(crate) use derive_binary;
fancy_garbling/fancy.rs

fancy_garbling/
fancy.rs
