core_utils/circuit/latest/
ops.rs

1use std::iter::repeat_n;
2
3use ff::Field;
4use num_traits::{One, Zero};
5use primitives::{
6    algebra::{
7        elliptic_curve::{BaseFieldElement, Curve, Point, Scalar},
8        field::{Bit, FieldExtension, SubfieldElement},
9        BoxedUint,
10    },
11    types::PeerNumber,
12};
13use serde::{Deserialize, Serialize};
14use typenum::Unsigned;
15
16use crate::{
17    circuit::{errors::BatchSizeError, AlgebraicType, BatchSize, GateIndex, ShareOrPlaintext},
18    config::{MpcConfig, MpcFieldElement},
19    errors::{AbortError, FaultyPeer},
20};
21
22/// Enum representing unary operations on field element plaintexts.
23#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
24#[repr(C)]
25pub enum FieldPlaintextUnaryOp {
26    Neg,
27    // Computes the multiplicative inverse. Note: for 0 we return 0.
28    MulInverse,
29    // Extracts a specified bit from a field element
30    BitExtract {
31        little_endian_bit_idx: u16,
32        signed: bool,
33    },
34    Sqrt,
35    Pow {
36        exp: BoxedUint,
37    },
38}
39
40impl FieldPlaintextUnaryOp {
41    // TODO: see if returning CtOption could make more sense
42    pub fn eval<F: FieldExtension>(
43        &self,
44        label: GateIndex,
45        x: &SubfieldElement<F>,
46    ) -> Result<SubfieldElement<F>, AbortError> {
47        match self {
48            FieldPlaintextUnaryOp::Neg => Ok(-x),
49            FieldPlaintextUnaryOp::MulInverse => {
50                Ok(x.invert().unwrap_or(SubfieldElement::<F>::zero()))
51            }
52            FieldPlaintextUnaryOp::BitExtract {
53                little_endian_bit_idx: idx,
54                signed,
55            } => {
56                let bit = if *signed && *x > -x {
57                    !(-SubfieldElement::<F>::one() - x)
58                        .to_biguint()
59                        .bit(*idx as u64)
60                } else {
61                    x.to_biguint().bit(*idx as u64)
62                };
63                Ok(SubfieldElement::<F>::from(bit))
64            }
65            FieldPlaintextUnaryOp::Sqrt => {
66                let (choice, sqrt) =
67                    SubfieldElement::<F>::sqrt_ratio(x, &SubfieldElement::<F>::one());
68                if !bool::from(choice) {
69                    return Err(AbortError::quadratic_non_residue(label, FaultyPeer::Local));
70                }
71                Ok(sqrt)
72            }
73            FieldPlaintextUnaryOp::Pow { exp } => Ok(x.pow(exp)),
74        }
75    }
76}
77
78/// Enum representing binary operations on field element plaintexts.
79#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
80#[repr(C)]
81pub enum FieldPlaintextBinaryOp {
82    Add,
83    Mul,
84    EuclDiv,
85    Mod,
86    Gt,
87    Ge,
88    Eq,
89    Xor,
90    Or,
91}
92
93impl FieldPlaintextBinaryOp {
94    pub fn eval<F: FieldExtension>(
95        &self,
96        x: &SubfieldElement<F>,
97        y: &SubfieldElement<F>,
98        label: GateIndex,
99    ) -> Result<SubfieldElement<F>, AbortError> {
100        match self {
101            FieldPlaintextBinaryOp::Add => Ok(x + y),
102            FieldPlaintextBinaryOp::Mul => Ok(x * y),
103            FieldPlaintextBinaryOp::EuclDiv => euclidean_division::<F>(x, y, label),
104            FieldPlaintextBinaryOp::Mod => modulo::<F>(x, y, label),
105            FieldPlaintextBinaryOp::Gt => Ok(SubfieldElement::<F>::from(x > y)),
106            FieldPlaintextBinaryOp::Ge => Ok(SubfieldElement::<F>::from(x >= y)),
107            FieldPlaintextBinaryOp::Eq => Ok(SubfieldElement::<F>::from(x == y)),
108            FieldPlaintextBinaryOp::Xor => Ok(x + y - SubfieldElement::<F>::from(2u32) * x * y),
109            FieldPlaintextBinaryOp::Or => Ok(x + y - x * y),
110        }
111    }
112}
113
114pub(crate) fn euclidean_division<F: FieldExtension>(
115    x: &SubfieldElement<F>,
116    y: &SubfieldElement<F>,
117    label: GateIndex,
118) -> Result<SubfieldElement<F>, AbortError> {
119    if *y == SubfieldElement::<F>::zero() {
120        return Err(AbortError::division_by_zero(label, FaultyPeer::Local));
121    }
122
123    // Convert to BigUint
124    let x = x.to_biguint();
125    let y = y.to_biguint();
126
127    let div = (x / y).to_bytes_be();
128    // Pad with zeroes as big-endian
129    let div = repeat_n(0, F::FieldBytesSize::USIZE - div.len())
130        .chain(div)
131        .collect::<Vec<_>>();
132
133    Ok(SubfieldElement::<F>::from_be_bytes(&div)?)
134}
135
136fn modulo<F: FieldExtension>(
137    x: &SubfieldElement<F>,
138    y: &SubfieldElement<F>,
139    label: GateIndex,
140) -> Result<SubfieldElement<F>, AbortError> {
141    if *y == SubfieldElement::<F>::zero() {
142        return Err(AbortError::division_by_zero(label, FaultyPeer::Local));
143    }
144
145    // Convert to BigUint
146    let x = x.to_biguint();
147    let y = y.to_biguint();
148
149    let modulo = x.modpow(&num_bigint::BigUint::from(1u32), &y).to_bytes_be();
150    // Pad with zeroes as big-endian
151    let modulo = repeat_n(0, F::FieldBytesSize::USIZE - modulo.len())
152        .chain(modulo)
153        .collect::<Vec<_>>();
154
155    Ok(SubfieldElement::<F>::from_be_bytes(&modulo)?)
156}
157
158/// Enum representing unary operations on a field share.
159#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
160#[repr(C)]
161pub enum FieldShareUnaryOp {
162    /// Negation of a field share.
163    Neg,
164    /// Multiplicative inverse of a field share.
165    MulInverse,
166    /// Opens a field share to reveal the underlying value.
167    Open,
168    /// Checks if the field share is zero, returning a plaintext value.
169    IsZero,
170}
171
172/// Enum representing binary operations on field shares. This includes the case where the second
173/// operand is a plaintext value.
174#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
175#[repr(C)]
176pub enum FieldShareBinaryOp {
177    /// Addition of two field shares.
178    Add,
179    /// Multiplication of two field shares.
180    Mul,
181}
182
183/// Enum representing unary operations on binary shares
184#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
185#[repr(C)]
186pub enum BitShareUnaryOp {
187    /// NOT operation
188    Not,
189    /// Opens a bit share to reveal the underlying value.
190    Open,
191}
192
193/// Enum representing binary operations on binary shares.
194#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
195#[repr(C)]
196pub enum BitShareBinaryOp {
197    /// Exclusive OR operation on two bit shares.
198    Xor,
199    /// OR operation on two bit shares.
200    Or,
201    /// AND operation on two bit shares.
202    And,
203}
204
205/// Enum representing unary operations on binary shares
206#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
207#[repr(C)]
208pub enum BitPlaintextUnaryOp {
209    /// NOT operation
210    Not,
211}
212
213impl BitPlaintextUnaryOp {
214    pub fn eval(&self, x: Bit) -> Bit {
215        match self {
216            BitPlaintextUnaryOp::Not => Bit::ONE - x,
217        }
218    }
219}
220
221/// Enum representing binary operations on binary shares.
222#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
223#[repr(C)]
224pub enum BitPlaintextBinaryOp {
225    /// Exclusive OR operation on two bits.
226    Xor,
227    /// OR operation on two bits.
228    Or,
229    /// AND operation on two bits.
230    And,
231}
232
233impl BitPlaintextBinaryOp {
234    pub fn eval(&self, x: Bit, y: Bit) -> Bit {
235        match self {
236            BitPlaintextBinaryOp::Xor => x + y,
237            BitPlaintextBinaryOp::Or => x + y - x * y,
238            BitPlaintextBinaryOp::And => x * y,
239        }
240    }
241}
242
243/// Enum representing unary operations on plaintext points.
244#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
245#[repr(C)]
246pub enum PointPlaintextUnaryOp {
247    /// Negation of a point.
248    Neg,
249}
250
251impl PointPlaintextUnaryOp {
252    pub fn eval<C: Curve>(&self, x: &Point<C>) -> Result<Point<C>, AbortError> {
253        match self {
254            PointPlaintextUnaryOp::Neg => Ok(-x),
255        }
256    }
257}
258
259/// Enum representing binary operations on plaintext points/scalars.
260#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
261#[repr(C)]
262pub enum PointPlaintextBinaryOp {
263    /// Addition of two plaintext points.
264    Add,
265    /// Multiplication of a plaintext point by a plaintext scalar.
266    ScalarMul,
267}
268
269impl PointPlaintextBinaryOp {
270    pub fn eval<C: Curve>(&self, x: &Point<C>, y: &Point<C>) -> Result<Point<C>, AbortError> {
271        match self {
272            PointPlaintextBinaryOp::Add => Ok(x + y),
273            PointPlaintextBinaryOp::ScalarMul => Err(AbortError::internal_error(
274                "PointPlaintextBinaryOp::eval not supported for PointPlaintextBinaryOp::ScalarMul.",
275            )),
276        }
277    }
278}
279
280/// Enum representing unary operations on point shares.
281#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
282#[repr(C)]
283pub enum PointShareUnaryOp {
284    /// Negation of a point share.
285    Neg,
286    /// Opens a point share to reveal the underlying value.
287    Open,
288    /// Checks if the point share is zero, returning a plaintext value.
289    IsZero,
290}
291
292/// Enum representing binary operations on point shares.
293#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
294#[repr(C)]
295pub enum PointShareBinaryOp {
296    /// Addition of two point shares.
297    Add,
298    /// Multiplication of a point share by a scalar.
299    ScalarMul,
300}
301
302/// A circuit input which can be either be a plaintext value, a secret plaintext value, or a secret
303/// share.
304#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
305#[repr(C)]
306pub enum Input {
307    Plaintext {
308        algebraic_type: AlgebraicType,
309        batch_size: BatchSize,
310    },
311    SecretPlaintext {
312        inputer: PeerNumber,
313        algebraic_type: AlgebraicType,
314        batch_size: BatchSize,
315    },
316    Share {
317        algebraic_type: AlgebraicType,
318        batch_size: BatchSize,
319    },
320}
321
322impl Input {
323    pub fn batch_size(&self) -> u32 {
324        match self {
325            Input::Plaintext { batch_size, .. }
326            | Input::SecretPlaintext { batch_size, .. }
327            | Input::Share { batch_size, .. } => *batch_size,
328        }
329    }
330
331    pub fn algebraic_type(&self) -> AlgebraicType {
332        match self {
333            Input::Plaintext { algebraic_type, .. }
334            | Input::Share { algebraic_type, .. }
335            | Input::SecretPlaintext { algebraic_type, .. } => *algebraic_type,
336        }
337    }
338
339    pub fn share_or_plaintext(&self) -> ShareOrPlaintext {
340        match self {
341            Input::SecretPlaintext { .. } | Input::Share { .. } => ShareOrPlaintext::Share,
342            Input::Plaintext { .. } => ShareOrPlaintext::Plaintext,
343        }
344    }
345}
346
347#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
348#[serde(bound(
349    serialize = "Scalar<C::Curve>: Serialize, Point<C::Curve>: Serialize",
350    deserialize = "Scalar<C::Curve>: Deserialize<'de>, Point<C::Curve>: Deserialize<'de>"
351))]
352#[repr(C)]
353pub enum Constant<C: MpcConfig> {
354    Scalar(Scalar<C::Curve>),
355    ScalarBatch(Vec<Scalar<C::Curve>>),
356    BaseField(BaseFieldElement<C::Curve>),
357    BaseFieldBatch(Vec<BaseFieldElement<C::Curve>>),
358    MpcField(MpcFieldElement<C>),
359    MpcFieldBatch(Vec<MpcFieldElement<C>>),
360    Bit(Bit),
361    BitBatch(Vec<Bit>),
362    Point(Point<C::Curve>),
363    PointBatch(Vec<Point<C::Curve>>),
364}
365
366impl<C: MpcConfig> Constant<C> {
367    pub fn batch_size(&self) -> Result<u32, BatchSizeError> {
368        let n = match self {
369            Constant::ScalarBatch(v) => v.len(),
370            Constant::BaseFieldBatch(v) => v.len(),
371            Constant::MpcFieldBatch(v) => v.len(),
372            Constant::BitBatch(v) => v.len(),
373            Constant::PointBatch(v) => v.len(),
374            Constant::Scalar(_)
375            | Constant::BaseField(_)
376            | Constant::MpcField(_)
377            | Constant::Bit(_)
378            | Constant::Point(_) => 1,
379        };
380        if let Ok(n) = u32::try_from(n) {
381            Ok(n)
382        } else {
383            Err(BatchSizeError(n))
384        }
385    }
386
387    pub fn algebraic_type(&self) -> AlgebraicType {
388        match self {
389            Constant::Scalar(_) | Constant::ScalarBatch(_) => AlgebraicType::ScalarField,
390            Constant::BaseField(_) | Constant::BaseFieldBatch(_) => AlgebraicType::BaseField,
391            Constant::MpcField(_) | Constant::MpcFieldBatch(_) => AlgebraicType::MpcField,
392            Constant::Bit(_) | Constant::BitBatch(_) => AlgebraicType::Bit,
393            Constant::Point(_) | Constant::PointBatch(_) => AlgebraicType::Point,
394        }
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use primitives::algebra::{
401        elliptic_curve::{BaseField, Curve25519Ristretto as C, ScalarField},
402        field::SubfieldElement,
403    };
404
405    use super::*;
406
407    #[test]
408    fn test_scalar_unary_op() {
409        let mut rng = rand::thread_rng();
410        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
411        let label = 0;
412        let neg = FieldPlaintextUnaryOp::Neg;
413        let mul_inverse = FieldPlaintextUnaryOp::MulInverse;
414
415        assert_eq!(neg.eval::<ScalarField<C>>(label, &x), Ok(-x));
416        assert_eq!(
417            mul_inverse.eval::<ScalarField<C>>(label, &x),
418            Ok(x.invert().unwrap())
419        );
420    }
421
422    #[test]
423    fn test_scalar_binary_op() {
424        let mut rng = rand::thread_rng();
425        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
426        let y = SubfieldElement::<ScalarField<C>>::random(&mut rng);
427        let label = 0;
428
429        let add = FieldPlaintextBinaryOp::Add;
430        let mul = FieldPlaintextBinaryOp::Mul;
431        let eucl_div = FieldPlaintextBinaryOp::EuclDiv;
432        let modulo_op = FieldPlaintextBinaryOp::Mod;
433        let gt = FieldPlaintextBinaryOp::Gt;
434        let ge = FieldPlaintextBinaryOp::Ge;
435        let eq = FieldPlaintextBinaryOp::Eq;
436
437        assert_eq!(add.eval::<ScalarField<C>>(&x, &y, label), Ok(x + y));
438        assert_eq!(mul.eval::<ScalarField<C>>(&x, &y, label), Ok(x * y));
439        assert_eq!(
440            eucl_div.eval::<ScalarField<C>>(&x, &y, label),
441            euclidean_division::<ScalarField<C>>(&x, &y, label)
442        );
443        assert_eq!(
444            modulo_op.eval::<ScalarField<C>>(&x, &y, label),
445            modulo::<ScalarField<C>>(&x, &y, label)
446        );
447        assert_eq!(
448            gt.eval::<ScalarField<C>>(&x, &y, label),
449            Ok(SubfieldElement::<ScalarField<C>>::from(x > y))
450        );
451        assert_eq!(
452            ge.eval::<ScalarField<C>>(&x, &y, label),
453            Ok(SubfieldElement::<ScalarField<C>>::from(x >= y))
454        );
455        assert_eq!(
456            eq.eval::<ScalarField<C>>(&x, &y, label),
457            Ok(SubfieldElement::<ScalarField<C>>::from(x == y))
458        );
459    }
460
461    #[test]
462    fn test_scalar_boolean_binary_op() {
463        let and = FieldPlaintextBinaryOp::Mul;
464        let or = FieldPlaintextBinaryOp::Or;
465        let xor = FieldPlaintextBinaryOp::Xor;
466        let label = 0;
467        for bool_x in [false, true] {
468            for bool_y in [false, true] {
469                let scalar_x = SubfieldElement::<ScalarField<C>>::from(bool_x);
470                let scalar_y = SubfieldElement::<ScalarField<C>>::from(bool_y);
471                assert_eq!(
472                    and.eval::<ScalarField<C>>(&scalar_x, &scalar_y, label),
473                    Ok((bool_x && bool_y).into())
474                );
475                assert_eq!(
476                    or.eval::<ScalarField<C>>(&scalar_x, &scalar_y, label),
477                    Ok((bool_x || bool_y).into())
478                );
479                assert_eq!(
480                    xor.eval::<ScalarField<C>>(&scalar_x, &scalar_y, label),
481                    Ok((bool_x ^ bool_y).into())
482                );
483            }
484        }
485    }
486
487    #[test]
488    fn test_bit_ops() {
489        let not = BitPlaintextUnaryOp::Not;
490        for bool_x in [false, true] {
491            let x = Bit::from(bool_x);
492            assert_eq!(not.eval(x), (!bool_x).into());
493        }
494
495        let and = BitPlaintextBinaryOp::And;
496        let or = BitPlaintextBinaryOp::Or;
497        let xor = BitPlaintextBinaryOp::Xor;
498        for bool_x in [false, true] {
499            for bool_y in [false, true] {
500                let x = Bit::from(bool_x);
501                let y = Bit::from(bool_y);
502                assert_eq!(and.eval(x, y), (bool_x && bool_y).into());
503                assert_eq!(or.eval(x, y), (bool_x || bool_y).into());
504                assert_eq!(xor.eval(x, y), (bool_x ^ bool_y).into());
505            }
506        }
507    }
508
509    #[test]
510    fn test_euclidian_division() {
511        let x = SubfieldElement::<ScalarField<C>>::from(37u32);
512        let y = SubfieldElement::<ScalarField<C>>::from(12u32);
513        let label = 0;
514
515        let result = euclidean_division::<ScalarField<C>>(&x, &y, label).unwrap();
516        assert_eq!(result, SubfieldElement::<ScalarField<C>>::from(37u32 / 12));
517    }
518
519    #[test]
520    fn test_modulo() {
521        let x = SubfieldElement::<ScalarField<C>>::from(37u32);
522        let y = SubfieldElement::<ScalarField<C>>::from(12u32);
523        let label = 0;
524
525        let result = modulo::<ScalarField<C>>(&x, &y, label).unwrap();
526        assert_eq!(result, SubfieldElement::<ScalarField<C>>::from(37u32 % 12));
527    }
528
529    #[test]
530    fn test_signed_bit_extract() {
531        let x = -Scalar::<C>::from(9u32);
532        let label = 0;
533        for i in 0..5 {
534            let op = FieldPlaintextUnaryOp::BitExtract {
535                little_endian_bit_idx: i,
536                signed: true,
537            };
538            let result = op.eval::<ScalarField<C>>(label, &x);
539            assert_eq!(result.unwrap(), ((-9i32 >> i) & 1 == 1).into())
540        }
541    }
542
543    #[test]
544    fn test_sqrt() {
545        let mut rng = rand::thread_rng();
546        let x = SubfieldElement::<ScalarField<C>>::random(&mut rng);
547        let label = 0;
548        let result = FieldPlaintextUnaryOp::Sqrt
549            .eval::<ScalarField<C>>(label, &(x * x))
550            .unwrap();
551
552        assert_eq!(result * result, x * x)
553    }
554
555    #[test]
556    fn test_pow() {
557        let mut rng = rand::thread_rng();
558        let x = SubfieldElement::<BaseField<C>>::random(&mut rng);
559        let label = 0;
560        let five = BoxedUint::from(vec![5u64]);
561        let five_inv = BoxedUint::from(vec![
562            14757395258967641281,
563            14757395258967641292,
564            14757395258967641292,
565            5534023222112865484,
566        ]);
567        let x_pow_5 = FieldPlaintextUnaryOp::Pow { exp: five }
568            .eval::<BaseField<C>>(label, &x)
569            .unwrap();
570        let x_again = FieldPlaintextUnaryOp::Pow { exp: five_inv }
571            .eval::<BaseField<C>>(label, &x_pow_5)
572            .unwrap();
573
574        assert_eq!(x_again, x)
575    }
576}
core_utils/circuit/latest/ops.rs

core_utils/circuit/latest/
ops.rs
