fancy_garbling/

classic.rs

//! Provides objects and functions for statically garbling and evaluating a
//! circuit without streaming.

use crate::{
    WireLabel,
    garble::{Evaluator, Garbler},
    util::output_tweak,
};
use fancy_traits::{Circuit, CircuitInputMapper, CircuitOutputMapper, FancyOutput};
use rand::CryptoRng;
use swanky_channel::Channel;
use swanky_error::ErrorKind;
use swanky_field_binary::F2;
use vectoreyes::U8x16;

/// A garbled circuit.
///
/// A garbled circuit at its core is just a vector of garbled rows and constant
/// wirelabels.
#[derive(Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct GarbledCircuit {
    blocks: Vec<U8x16>,
}

impl GarbledCircuit {
    /// Create a [`GarbledCircuit`] from a vector of garbled rows and constant
    /// wirelabels.
    pub fn new(blocks: Vec<U8x16>) -> Self {
        GarbledCircuit { blocks }
    }

    /// The number of garbled rows and constant wires in the garbled circuit.
    pub fn size(&self) -> usize {
        self.blocks.len()
    }

    /// Garble a circuit.
    ///
    /// This outputs three things:
    /// 1. An [`Encoder`] for encoding inputs to valid input wirelabels.
    /// 2. The garbled circuit itself.
    /// 3. An [`OutputMapping`] mapping for mapping output wirelabels to their
    ///    associated underlying values.
    pub fn garble<
        Wire: WireLabel<F2>,
        C: CircuitInputMapper<Garbler<RNG, Wire>> + CircuitOutputMapper<Garbler<RNG, Wire>>,
        RNG: CryptoRng,
    >(
        circuit: &C,
        rng: RNG,
    ) -> swanky_error::Result<(Encoder<Wire>, Self, OutputMapping)> {
        let mut garbler = Garbler::new(rng);

        // Produce zero wirelabels for the inputs.
        let inputs = (0..circuit.ninputs())
            .map(|_| garbler.encode_zero())
            .collect::<Vec<_>>();

        let mut channel = GarbledChannel::new_writer(None);
        let (en, output_mapping) = Channel::with(&mut channel, |channel| {
            // First, garble the circuit, outputting the zero wirelabels
            // associated with the output.
            let zeros = circuit.execute(&mut garbler, circuit.map(inputs.clone()), channel)?;
            let zeros = C::flatten(zeros);
            // Next, map the zero output wirelabels to the set of valid outputs.
            // This is needed for evaluators that don't use the output
            // mapping provided as output; in that case, we need the channel to
            // contain that mapping, which is what the below does.
            garbler.outputs(&zeros, channel)?;

            let en = Encoder::new(inputs, garbler.delta());
            let output_mapping = OutputMapping::new(&zeros, garbler.delta());

            Ok((en, output_mapping))
        })?;
        let gc = GarbledCircuit::new(channel.finish_writing());
        Ok((en, gc, output_mapping))
    }

    /// Evaluate the garbled circuit on the provided inputs, mapping the output
    /// wirelabels to their associated values.
    pub fn eval<Wire: WireLabel<F2>, C: CircuitOutputMapper<Evaluator<Wire>>>(
        &self,
        circuit: &C,
        inputs: C::Input,
        output_mapping: &OutputMapping,
    ) -> swanky_error::Result<Vec<F2>> {
        let wirelabels = self.eval_to_wirelabels(circuit, inputs)?;
        output_mapping.to_outputs(&C::flatten(wirelabels))
    }

    /// Evaluate the garbled circuit on the provided inputs, returning the
    /// output wirelabels.
    pub fn eval_to_wirelabels<Wire: WireLabel<F2>, C: Circuit<Evaluator<Wire>>>(
        &self,
        circuit: &C,
        inputs: C::Input,
    ) -> swanky_error::Result<C::Output> {
        let mut evaluator = Evaluator::new();
        Channel::with(GarbledChannel::from(self), |channel| {
            circuit.execute(&mut evaluator, inputs, channel)
        })
    }
}

/// Encoder for input wirelabels.
#[derive(Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Encoder<Wire> {
    inputs: Vec<Wire>,
    delta: Wire,
}

impl<Wire: WireLabel<F2>> Encoder<Wire> {
    /// Make a new [`Encoder`] from a vector of zero wirelabels and the `Δ`
    /// wirelabel.
    pub fn new(inputs: Vec<Wire>, delta: Wire) -> Self {
        Encoder { inputs, delta }
    }

    /// Encode input values into their associated wirelabels.
    ///
    /// # Panics
    /// This panics if `inputs.len()` does not equal the expected number of
    /// garbler inputs.
    pub fn encode_inputs(&self, inputs: &[F2]) -> Vec<Wire> {
        assert_eq!(inputs.len(), self.inputs.len());
        self.inputs
            .iter()
            .zip(inputs)
            .map(|(zero, x)| *zero + self.delta * (*x).into())
            .collect()
    }
}

/// A mapping of output wirelabels to their associated underlying values.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct OutputMapping(Vec<[U8x16; 2]>);

impl OutputMapping {
    /// Construct a new [`OutputMapping`] from a slice of zero wirelabels and
    /// the `Δ` wirelabel.
    pub fn new<Wire: WireLabel<F2>>(zeros: &[Wire], delta: Wire) -> Self {
        let outputs = zeros
            .iter()
            .enumerate()
            .map(|(i, zero)| {
                core::array::from_fn(|j| {
                    (*zero + delta * (j as u16)).hash(output_tweak(i, j as u16))
                })
            })
            .collect::<Vec<_>>();
        Self(outputs)
    }

    /// Map output wirelabels to their underlying values.
    ///
    /// # Errors
    /// This returns an error if it is unable to find a valid mapping for a
    /// given output wirelabel.
    pub fn to_outputs<Wire: WireLabel<F2>>(
        &self,
        wirelabels: &[Wire],
    ) -> swanky_error::Result<Vec<F2>> {
        wirelabels
            .iter()
            .enumerate()
            .map(|(i, wirelabel)| {
                let mut decoded = None;
                for k in 0..2 {
                    let hashed = wirelabel.hash(output_tweak(i, k));
                    if hashed == self.0[i][k as usize] {
                        decoded = Some(k);
                        break;
                    }
                }
                if let Some(output) = decoded {
                    Ok(F2::from(output != 0))
                } else {
                    swanky_error::bail!(ErrorKind::OtherError, "Decoding failed");
                }
            })
            .collect()
    }
}

/// Type for writing and reading a garbled circuit from memory.
///
/// A [`GarbledChannel`] provides a way to use the [`Channel`] interface to
/// write a garbled circuit to memory, alongside the ability to read it from
/// memory for evaluation.
///
/// A [`GarbledChannel`] can be instantiated in one of two ways: either by
/// calling [`GarbledChannel::new_writer`] to store the garbled circuit in
/// memory, or [`GarbledChannel::from`] on an existing [`GarbledCircuit`] to
/// evaluate the garbled circuit.
///
/// Note that a [`GarbledChannel`] cannot be both a writer and a reader. For
/// example, calling [`GarbledChannel::finish_writing`] on a [`GarbledChannel`]
/// reader results in a panic.
pub struct GarbledChannel {
    reader: Option<GarbledReader>,
    writer: Option<GarbledWriter>,
}

impl GarbledChannel {
    /// Construct a new [`GarbledChannel`] for writing a garbled circuit.
    pub fn new_writer(ngates: Option<usize>) -> Self {
        Self {
            reader: None,
            writer: Some(GarbledWriter::new(ngates)),
        }
    }

    /// Consume the [`GarbledChannel`], outputting the resulting garbled circuit.
    ///
    /// # Panics
    /// Panics if there is no valid writer for the [`GarbledChannel`].
    pub fn finish_writing(self) -> Vec<U8x16> {
        self.writer.unwrap().finish()
    }
}

impl std::io::Read for GarbledChannel {
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
        let reader = self.reader.as_mut().unwrap();
        reader.read(buf)
    }
}

impl std::io::Write for GarbledChannel {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        let writer = self.writer.as_mut().unwrap();
        writer.write(buf)
    }

    fn flush(&mut self) -> std::io::Result<()> {
        let writer = self.writer.as_mut().unwrap();
        writer.flush()
    }
}

impl From<&GarbledCircuit> for GarbledChannel {
    fn from(value: &GarbledCircuit) -> Self {
        Self {
            reader: Some(GarbledReader::new(&value.blocks)),
            writer: None,
        }
    }
}

/// Implementation of the `Read` trait for use by the `Evaluator`.
#[derive(Debug)]
struct GarbledReader {
    blocks: Vec<U8x16>,
    index: usize,
}

impl GarbledReader {
    fn new(blocks: &[U8x16]) -> Self {
        Self {
            blocks: blocks.to_vec(),
            index: 0,
        }
    }
}

impl std::io::Read for GarbledReader {
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
        assert_eq!(buf.len() % 16, 0);
        let start = self.index;
        for data in buf.chunks_mut(16) {
            let block: [u8; 16] = self.blocks[self.index].into();
            for (a, b) in data.iter_mut().zip(block.iter()) {
                *a = *b;
            }
            self.index += 1;
            if self.index == self.blocks.len() {
                // We've read all that we can from the vector of `Block`s, so
                // return the length of bytes that we've read to satisfy the
                // `read` API.
                return Ok(16 * (self.index - start));
            }
        }
        Ok(buf.len())
    }
}

/// Implementation of the `Write` trait for use by `Garbler`.
#[derive(Debug)]
struct GarbledWriter {
    blocks: Vec<U8x16>,
}

impl GarbledWriter {
    /// Make a new [`GarbledWriter`].
    fn new(ngates: Option<usize>) -> Self {
        let blocks = if let Some(n) = ngates {
            Vec::with_capacity(2 * n)
        } else {
            Vec::new()
        };
        Self { blocks }
    }

    /// Consume the [`GarbledWriter`], outputting the resulting garbled circuit.
    fn finish(self) -> Vec<U8x16> {
        self.blocks
    }
}

impl std::io::Write for GarbledWriter {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        for item in buf.chunks(16) {
            let bytes: [u8; 16] = match item.try_into() {
                Ok(bytes) => bytes,
                Err(_) => {
                    return Err(std::io::Error::new(
                        std::io::ErrorKind::InvalidData,
                        "unable to map bytes to block",
                    ));
                }
            };
            self.blocks.push(bytes.into());
        }
        Ok(buf.len())
    }
    fn flush(&mut self) -> std::io::Result<()> {
        Ok(())
    }
}