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