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

fancy_garbling/
fancy.rs
