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

core_utils/circuit/v2/
ops.rs
