1use crate::{
  2    convert::{ToBitsGadget, ToBytesGadget},
  3    fields::emulated_fp::EmulatedFpVar,
  4    prelude::*,
  5};
  6use ark_ff::PrimeField;
  7use ark_relations::r1cs::{Namespace, SynthesisError};
  8use core::ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign};
  9
 10use ark_ec::CurveGroup;
 11use core::{borrow::Borrow, fmt::Debug};
 12
 13/// This module contains implementations of arithmetic for various curve models.
 14pub mod curves;
 15
 16pub use self::curves::short_weierstrass::{bls12, mnt4, mnt6};
 17
 18/// A hack used to work around the lack of implied bounds.
 19pub trait GroupOpsBounds<'a, G, T: 'a>:
 20    Sized
 21    + Add<&'a T, Output = T>
 22    + Sub<&'a T, Output = T>
 23    + Add<T, Output = T>
 24    + Sub<T, Output = T>
 25    + Add<G, Output = T>
 26    + Sub<G, Output = T>
 27{
 28}
 29
 30/// A variable that represents a curve point for
 31/// the curve `C`.
 32pub trait CurveVar<C: CurveGroup, ConstraintF: PrimeField>:
 33    'static
 34    + Sized
 35    + Clone
 36    + Debug
 37    + R1CSVar<ConstraintF, Value = C>
 38    + ToBitsGadget<ConstraintF>
 39    + ToBytesGadget<ConstraintF>
 40    + EqGadget<ConstraintF>
 41    + CondSelectGadget<ConstraintF>
 42    + AllocVar<C, ConstraintF>
 43    + AllocVar<C::Affine, ConstraintF>
 44    + for<'a> GroupOpsBounds<'a, C, Self>
 45    + for<'a> AddAssign<&'a Self>
 46    + for<'a> SubAssign<&'a Self>
 47    + AddAssign<C>
 48    + SubAssign<C>
 49    + AddAssign<Self>
 50    + SubAssign<Self>
 51    + Mul<EmulatedFpVar<C::ScalarField, ConstraintF>, Output = Self>
 52    + for<'a> Mul<&'a EmulatedFpVar<C::ScalarField, ConstraintF>, Output = Self>
 53    + MulAssign<EmulatedFpVar<C::ScalarField, ConstraintF>>
 54{
 55    /// Returns the constant `F::zero()`. This is the identity
 56    /// of the group.
 57    fn zero() -> Self;
 58
 59    /// Returns a `Boolean` representing whether `self == Self::zero()`.
 60    #[tracing::instrument(target = "r1cs")]
 61    fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
 62        self.is_eq(&Self::zero())
 63    }
 64
 65    /// Returns a constant with value `v`.
 66    ///
 67    /// This *should not* allocate any variables.
 68    fn constant(other: C) -> Self;
 69
 70    /// Allocates a variable in the subgroup without checking if it's in the
 71    /// prime-order subgroup.
 72    fn new_variable_omit_prime_order_check(
 73        cs: impl Into<Namespace<ConstraintF>>,
 74        f: impl FnOnce() -> Result<C, SynthesisError>,
 75        mode: AllocationMode,
 76    ) -> Result<Self, SynthesisError>;
 77
 78    /// Enforce that `self` is in the prime-order subgroup.
 79    fn enforce_prime_order(&self) -> Result<(), SynthesisError>;
 80
 81    /// Computes `self + self`.
 82    #[tracing::instrument(target = "r1cs")]
 83    fn double(&self) -> Result<Self, SynthesisError> {
 84        let mut result = self.clone();
 85        result.double_in_place()?;
 86        Ok(result)
 87    }
 88
 89    /// Sets `self = self + self`.
 90    fn double_in_place(&mut self) -> Result<(), SynthesisError>;
 91
 92    /// Coputes `-self`.
 93    fn negate(&self) -> Result<Self, SynthesisError>;
 94
 95    /// Computes `bits * self`, where `bits` is a little-endian
 96    /// `Boolean` representation of a scalar.
 97    #[tracing::instrument(target = "r1cs", skip(bits))]
 98    fn scalar_mul_le<'a>(
 99        &self,
100        bits: impl Iterator<Item = &'a Boolean<ConstraintF>>,
101    ) -> Result<Self, SynthesisError> {
102        // TODO: in the constant case we should call precomputed_scalar_mul_le,
103        // but rn there's a bug when doing this with TE curves.
104
105        // Computes the standard little-endian double-and-add algorithm
106        // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
107        let mut res = Self::zero();
108        let mut multiple = self.clone();
109        for bit in bits {
110            let tmp = res.clone() + &multiple;
111            res = bit.select(&tmp, &res)?;
112            multiple.double_in_place()?;
113        }
114        Ok(res)
115    }
116
117    /// Computes a `I * self` in place, where `I` is a `Boolean` *little-endian*
118    /// representation of the scalar.
119    ///
120    /// The bases are precomputed power-of-two multiples of a single
121    /// base.
122    #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
123    fn precomputed_base_scalar_mul_le<'a, I, B>(
124        &mut self,
125        scalar_bits_with_bases: I,
126    ) -> Result<(), SynthesisError>
127    where
128        I: Iterator<Item = (B, &'a C)>,
129        B: Borrow<Boolean<ConstraintF>>,
130        C: 'a,
131    {
132        // Computes the standard little-endian double-and-add algorithm
133        // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
134
135        // Let `original` be the initial value of `self`.
136        let mut result = Self::zero();
137        for (bit, base) in scalar_bits_with_bases {
138            // Compute `self + 2^i * original`
139            let self_plus_base = result.clone() + *base;
140            // If `bit == 1`, set self = self + 2^i * original;
141            // else, set self = self;
142            result = bit.borrow().select(&self_plus_base, &result)?;
143        }
144        *self += result;
145        Ok(())
146    }
147
148    /// Computes `Σⱼ(scalarⱼ * baseⱼ)` for all j,
149    /// where `scalarⱼ` is a `Boolean` *little-endian*
150    /// representation of the j-th scalar.
151    #[tracing::instrument(target = "r1cs", skip(bases, scalars))]
152    fn precomputed_base_multiscalar_mul_le<'a, T, I, B>(
153        bases: &[B],
154        scalars: I,
155    ) -> Result<Self, SynthesisError>
156    where
157        T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
158        I: Iterator<Item = &'a T>,
159        B: Borrow<[C]>,
160    {
161        let mut result = Self::zero();
162        // Compute Σᵢ(bitᵢ * baseᵢ) for all i.
163        for (bits, bases) in scalars.zip(bases) {
164            let bases = bases.borrow();
165            let bits = bits.to_bits_le()?;
166            result.precomputed_base_scalar_mul_le(bits.iter().zip(bases))?;
167        }
168        Ok(result)
169    }
170}