core_utils/circuit/

ops.rs

use std::iter::repeat_n;

use ff::Field;
use num_traits::{One, Zero};
use primitives::{
    algebra::{
        elliptic_curve::{Curve, Point, Scalar},
        field::{FieldExtension, SubfieldElement},
        BoxedUint,
    },
    types::PeerNumber,
};
use serde::{Deserialize, Serialize};
use typenum::Unsigned;

use crate::{
    circuit::{
        AlgebraicType,
        BaseFieldPlaintext,
        BaseFieldPlaintextBatch,
        BitPlaintext,
        BitPlaintextBatch,
        PointPlaintext,
        PointPlaintextBatch,
        ScalarPlaintext,
        ScalarPlaintextBatch,
    },
    errors::{AbortError, FaultyPeer},
    types::Label,
};

/// Enum representing unary operations on field element plaintexts.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum FieldPlaintextUnaryOp {
    Neg,
    // Computes the multiplicative inverse. Note: for 0 we return 0.
    MulInverse,
    // Extracts a specified bit from a field element
    BitExtract {
        little_endian_bit_idx: u16,
        signed: bool,
    },
    Sqrt,
    Pow {
        exp: BoxedUint,
    },
}

impl FieldPlaintextUnaryOp {
    // TODO: see if returning CtOption could make more sense
    pub fn eval<F: FieldExtension>(
        &self,
        label: Label,
        x: SubfieldElement<F>,
    ) -> Result<SubfieldElement<F>, AbortError> {
        match self {
            FieldPlaintextUnaryOp::Neg => Ok(-x),
            FieldPlaintextUnaryOp::MulInverse => {
                if x == SubfieldElement::<F>::zero() {
                    Ok(SubfieldElement::<F>::zero())
                } else {
                    Ok(x.invert().unwrap())
                }
            }
            FieldPlaintextUnaryOp::BitExtract {
                little_endian_bit_idx: idx,
                signed,
            } => {
                let bit = if *signed && x > -x {
                    !(-SubfieldElement::<F>::one() - x)
                        .to_biguint()
                        .bit(*idx as u64)
                } else {
                    x.to_biguint().bit(*idx as u64)
                };
                Ok(SubfieldElement::<F>::from(bit))
            }
            FieldPlaintextUnaryOp::Sqrt => {
                let (choice, sqrt) =
                    SubfieldElement::<F>::sqrt_ratio(&x, &SubfieldElement::<F>::one());
                if !bool::from(choice) {
                    return Err(AbortError::quadratic_non_residue(label, FaultyPeer::Local));
                }
                Ok(sqrt)
            }
            FieldPlaintextUnaryOp::Pow { exp } => Ok(x.pow(exp)),
        }
    }
}

/// Enum representing binary operations on field element plaintexts.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum FieldPlaintextBinaryOp {
    Add,
    Mul,
    EuclDiv,
    Mod,
    Gt,
    Ge,
    Eq,
    Xor,
    Or,
}

impl FieldPlaintextBinaryOp {
    pub fn eval<F: FieldExtension>(
        &self,
        x: SubfieldElement<F>,
        y: SubfieldElement<F>,
        label: Label,
    ) -> Result<SubfieldElement<F>, AbortError> {
        match self {
            FieldPlaintextBinaryOp::Add => Ok(x + y),
            FieldPlaintextBinaryOp::Mul => Ok(x * y),
            FieldPlaintextBinaryOp::EuclDiv => euclidean_division::<F>(x, y, label),
            FieldPlaintextBinaryOp::Mod => modulo::<F>(x, y, label),
            FieldPlaintextBinaryOp::Gt => Ok(SubfieldElement::<F>::from(x > y)),
            FieldPlaintextBinaryOp::Ge => Ok(SubfieldElement::<F>::from(x >= y)),
            FieldPlaintextBinaryOp::Eq => Ok(SubfieldElement::<F>::from(x == y)),
            FieldPlaintextBinaryOp::Xor => Ok(x + y - SubfieldElement::<F>::from(2u32) * x * y),
            FieldPlaintextBinaryOp::Or => Ok(x + y - x * y),
        }
    }
}

pub(crate) fn euclidean_division<F: FieldExtension>(
    x: SubfieldElement<F>,
    y: SubfieldElement<F>,
    label: Label,
) -> Result<SubfieldElement<F>, AbortError> {
    if y == SubfieldElement::<F>::zero() {
        return Err(AbortError::division_by_zero(label, FaultyPeer::Local));
    }

    // Convert to BigUint
    let x = x.to_biguint();
    let y = y.to_biguint();

    let div = (x / y).to_bytes_be();
    // Pad with zeroes as big-endian
    let div = repeat_n(0, F::FieldBytesSize::USIZE - div.len())
        .chain(div)
        .collect::<Vec<_>>();

    Ok(SubfieldElement::<F>::from_be_bytes(&div).unwrap())
}

fn modulo<F: FieldExtension>(
    x: SubfieldElement<F>,
    y: SubfieldElement<F>,
    label: Label,
) -> Result<SubfieldElement<F>, AbortError> {
    if y == SubfieldElement::<F>::zero() {
        return Err(AbortError::division_by_zero(label, FaultyPeer::Local));
    }

    // Convert to BigUint
    let x = x.to_biguint();
    let y = y.to_biguint();

    let modulo = x.modpow(&num_bigint::BigUint::from(1u32), &y).to_bytes_be();
    // Pad with zeroes as big-endian
    let modulo = repeat_n(0, F::FieldBytesSize::USIZE - modulo.len())
        .chain(modulo)
        .collect::<Vec<_>>();

    Ok(SubfieldElement::<F>::from_be_bytes(&modulo).unwrap())
}

/// Enum representing unary operations on a field share.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum FieldShareUnaryOp {
    /// Negation of a field share.
    Neg,
    /// Multiplicative inverse of a field share.
    MulInverse,
    /// Opens a field share to reveal the underlying value.
    Open,
    /// Checks if the field share is zero, returning a plaintext value.
    IsZero,
}

/// Enum representing binary operations on field shares. This includes the case where the second
/// operand is a plaintext value.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum FieldShareBinaryOp {
    /// Addition of two field shares.
    Add,
    /// Multiplication of two field shares.
    Mul,
}

/// Enum representing unary operations on binary shares
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum BitShareUnaryOp {
    /// NOT operation
    Not,
    /// Opens a bit share to reveal the underlying value.
    Open,
}

/// Enum representing binary operations on binary shares.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum BitShareBinaryOp {
    /// Exclusive OR operation on two bit shares.
    Xor,
    /// OR operation on two bit shares.
    Or,
    /// AND operation on two bit shares.
    And,
}

/// Enum representing unary operations on point shares.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum PointShareUnaryOp {
    /// Negation of a point share.
    Neg,
    /// Opens a point share to reveal the underlying value.
    Open,
    /// Checks if the point share is zero, returning a plaintext value.
    IsZero,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound(
    serialize = "Scalar<C>: Serialize, Point<C>: Serialize",
    deserialize = "Scalar<C>: Deserialize<'de>, Point<C>: Deserialize<'de>"
))]
pub enum Input<C: Curve> {
    SecretPlaintext {
        inputer: PeerNumber,
        algebraic_type: AlgebraicType,
        batched: Batched,
    },
    Share {
        algebraic_type: AlgebraicType,
        batched: Batched,
    },
    RandomShare {
        algebraic_type: AlgebraicType,
        batched: Batched,
    },
    Scalar(ScalarPlaintext<C>),
    ScalarBatch(ScalarPlaintextBatch<C>),
    BaseField(BaseFieldPlaintext<C>),
    BaseFieldBatch(BaseFieldPlaintextBatch<C>),
    Bit(BitPlaintext),
    BitBatch(BitPlaintextBatch),
    Point(PointPlaintext<C>),
    PointBatch(PointPlaintextBatch<C>),
    ElGamalCiphertext {
        c: PointPlaintext<C>,
        r: PointPlaintext<C>,
    },
}

impl<C: Curve> Input<C> {
    pub fn batched(&self) -> Batched {
        match self {
            Input::SecretPlaintext { batched, .. } => *batched,
            Input::Share { batched, .. } => *batched,
            Input::RandomShare { batched, .. } => *batched,
            Input::ScalarBatch(input) => Batched::Yes(input.len()),
            Input::BaseFieldBatch(input) => Batched::Yes(input.len()),
            Input::BitBatch(input) => Batched::Yes(input.len()),
            Input::PointBatch(input) => Batched::Yes(input.len()),
            Input::ElGamalCiphertext { .. } => Batched::No,
            Input::Scalar { .. } => Batched::No,
            Input::BaseField { .. } => Batched::No,
            Input::Bit { .. } => Batched::No,
            Input::Point { .. } => Batched::No,
        }
    }
}

/// Enum representing binary operations on point shares.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub enum PointShareBinaryOp {
    /// Addition of two point shares.
    Add,
    /// Multiplication of a point share by a scalar.
    ScalarMul,
}

/// Enum representing whether a gate is batched or not.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum Batched {
    Yes(usize),
    No,
}

impl Batched {
    pub fn count(&self) -> usize {
        match self {
            Batched::Yes(count) => *count,
            Batched::No => 1,
        }
    }

    pub fn is_batched(&self) -> bool {
        match self {
            Batched::Yes(_) => true,
            Batched::No => false,
        }
    }
}

#[cfg(test)]
mod tests {
    use primitives::algebra::{
        elliptic_curve::{BaseField, Curve25519Ristretto as C, ScalarField},
        field::SubfieldElement,
    };

    use super::*;

    #[test]
    fn test_scalar_unary_op() {
        let mut rng = rand::thread_rng();
        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
        let label = Label::task(0);
        let neg = FieldPlaintextUnaryOp::Neg;
        let mul_inverse = FieldPlaintextUnaryOp::MulInverse;

        assert_eq!(neg.eval::<ScalarField<C>>(label, x), Ok(-x));
        assert_eq!(
            mul_inverse.eval::<ScalarField<C>>(label, x),
            Ok(x.invert().unwrap())
        );
    }

    #[test]
    fn test_scalar_binary_op() {
        let mut rng = rand::thread_rng();
        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
        let y = SubfieldElement::<ScalarField<C>>::random(&mut rng);
        let label = Label::task(0);

        let add = FieldPlaintextBinaryOp::Add;
        let mul = FieldPlaintextBinaryOp::Mul;
        let eucl_div = FieldPlaintextBinaryOp::EuclDiv;
        let modulo_op = FieldPlaintextBinaryOp::Mod;
        let gt = FieldPlaintextBinaryOp::Gt;
        let ge = FieldPlaintextBinaryOp::Ge;
        let eq = FieldPlaintextBinaryOp::Eq;

        assert_eq!(add.eval::<ScalarField<C>>(x, y, label), Ok(x + y));
        assert_eq!(mul.eval::<ScalarField<C>>(x, y, label), Ok(x * y));
        assert_eq!(
            eucl_div.eval::<ScalarField<C>>(x, y, label),
            euclidean_division::<ScalarField<C>>(x, y, label)
        );
        assert_eq!(
            modulo_op.eval::<ScalarField<C>>(x, y, label),
            modulo::<ScalarField<C>>(x, y, label)
        );
        assert_eq!(
            gt.eval::<ScalarField<C>>(x, y, label),
            Ok(SubfieldElement::<ScalarField<C>>::from(x > y))
        );
        assert_eq!(
            ge.eval::<ScalarField<C>>(x, y, label),
            Ok(SubfieldElement::<ScalarField<C>>::from(x >= y))
        );
        assert_eq!(
            eq.eval::<ScalarField<C>>(x, y, label),
            Ok(SubfieldElement::<ScalarField<C>>::from(x == y))
        );
    }

    #[test]
    fn test_boolean_binary_op() {
        let and = FieldPlaintextBinaryOp::Mul;
        let or = FieldPlaintextBinaryOp::Or;
        let xor = FieldPlaintextBinaryOp::Xor;
        let label = Label::task(0);
        for bool_x in [false, true] {
            for bool_y in [false, true] {
                let scalar_x = SubfieldElement::<ScalarField<C>>::from(bool_x);
                let scalar_y = SubfieldElement::<ScalarField<C>>::from(bool_y);
                assert_eq!(
                    and.eval::<ScalarField<C>>(scalar_x, scalar_y, label),
                    Ok((bool_x && bool_y).into())
                );
                assert_eq!(
                    or.eval::<ScalarField<C>>(scalar_x, scalar_y, label),
                    Ok((bool_x || bool_y).into())
                );
                assert_eq!(
                    xor.eval::<ScalarField<C>>(scalar_x, scalar_y, label),
                    Ok((bool_x ^ bool_y).into())
                );
            }
        }
    }

    #[test]
    fn test_euclidian_division() {
        let x = SubfieldElement::<ScalarField<C>>::from(37u32);
        let y = SubfieldElement::<ScalarField<C>>::from(12u32);
        let label = Label::task(0);

        let result = euclidean_division::<ScalarField<C>>(x, y, label).unwrap();
        assert_eq!(result, SubfieldElement::<ScalarField<C>>::from(37u32 / 12));
    }

    #[test]
    fn test_modulo() {
        let x = SubfieldElement::<ScalarField<C>>::from(37u32);
        let y = SubfieldElement::<ScalarField<C>>::from(12u32);
        let label = Label::task(0);

        let result = modulo::<ScalarField<C>>(x, y, label).unwrap();
        assert_eq!(result, SubfieldElement::<ScalarField<C>>::from(37u32 % 12));
    }

    #[test]
    fn test_signed_bit_extract() {
        let x = -Scalar::<C>::from(9u32);
        let label = Label::task(0);
        for i in 0..5 {
            let op = FieldPlaintextUnaryOp::BitExtract {
                little_endian_bit_idx: i,
                signed: true,
            };
            let result = op.eval::<ScalarField<C>>(label, x);
            assert_eq!(result.unwrap(), ((-9i32 >> i) & 1 == 1).into())
        }
    }

    #[test]
    fn test_sqrt() {
        let mut rng = rand::thread_rng();
        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
        let label = Label::task(0);
        let result = FieldPlaintextUnaryOp::Sqrt
            .eval::<ScalarField<C>>(label, x * x)
            .unwrap();

        assert_eq!(result * result, x * x)
    }

    #[test]
    fn test_pow() {
        let mut rng = rand::thread_rng();
        let x = SubfieldElement::<BaseField<C>>::random(&mut rng);
        let label = Label::task(0);
        let five = BoxedUint::from(vec![5u64]);
        let five_inv = BoxedUint::from(vec![
            14757395258967641281,
            14757395258967641292,
            14757395258967641292,
            5534023222112865484,
        ]);
        let x_pow_5 = FieldPlaintextUnaryOp::Pow { exp: five }
            .eval::<BaseField<C>>(label, x)
            .unwrap();
        let x_again = FieldPlaintextUnaryOp::Pow { exp: five_inv }
            .eval::<BaseField<C>>(label, x_pow_5)
            .unwrap();

        assert_eq!(x_again, x)
    }
}