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

core_utils/circuit/latest/
ops.rs
