ark-r1cs-std/src/groups/mod.rs
src/groups/mod.rsRaw
1use crate::prelude::*;
2use ark_ec::ProjectiveCurve;
3use ark_ff::Field;
4use ark_relations::r1cs::{Namespace, SynthesisError};
5use core::ops::{Add, AddAssign, Sub, SubAssign};
6
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, F, 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<F, Output = T>
22 + Sub<F, Output = T>
23{
24}
25
26/// A variable that represents a curve point for
27/// the curve `C`.
28pub trait CurveVar<C: ProjectiveCurve, ConstraintF: Field>:
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{
48 /// Returns the constant `F::zero()`. This is the identity
49 /// of the group.
50 fn zero() -> Self;
51
52 /// Returns a `Boolean` representing whether `self == Self::zero()`.
53 #[tracing::instrument(target = "r1cs")]
54 fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
55 self.is_eq(&Self::zero())
56 }
57
58 /// Returns a constant with value `v`.
59 ///
60 /// This *should not* allocate any variables.
61 fn constant(other: C) -> Self;
62
63 /// Allocates a variable in the subgroup without checking if it's in the
64 /// prime-order subgroup.
65 fn new_variable_omit_prime_order_check(
66 cs: impl Into<Namespace<ConstraintF>>,
67 f: impl FnOnce() -> Result<C, SynthesisError>,
68 mode: AllocationMode,
69 ) -> Result<Self, SynthesisError>;
70
71 /// Enforce that `self` is in the prime-order subgroup.
72 fn enforce_prime_order(&self) -> Result<(), SynthesisError>;
73
74 /// Computes `self + self`.
75 #[tracing::instrument(target = "r1cs")]
76 fn double(&self) -> Result<Self, SynthesisError> {
77 let mut result = self.clone();
78 result.double_in_place()?;
79 Ok(result)
80 }
81
82 /// Sets `self = self + self`.
83 fn double_in_place(&mut self) -> Result<(), SynthesisError>;
84
85 /// Coputes `-self`.
86 fn negate(&self) -> Result<Self, SynthesisError>;
87
88 /// Computes `bits * self`, where `bits` is a little-endian
89 /// `Boolean` representation of a scalar.
90 #[tracing::instrument(target = "r1cs", skip(bits))]
91 fn scalar_mul_le<'a>(
92 &self,
93 bits: impl Iterator<Item = &'a Boolean<ConstraintF>>,
94 ) -> Result<Self, SynthesisError> {
95 if self.is_constant() {
96 // Compute 2^i * self for i in 0..bits.len()
97 // (these will be used by`precomputed_base_scalar_mul_le`, to perform
98 // a conditional addition.).
99 //
100 // TODO: if `bits.len()` is small n, it might be cheaper to
101 // conditinally select between 2^n options.
102 let mut value = self.value().unwrap();
103 let bits_and_multiples = bits
104 .map(|b| {
105 let multiple = value;
106 value.double_in_place();
107 (b, multiple)
108 })
109 .collect::<ark_std::vec::Vec<_>>();
110 let mut result = self.clone();
111 result.precomputed_base_scalar_mul_le(
112 bits_and_multiples.iter().map(|&(ref b, ref c)| (*b, c)),
113 )?;
114 Ok(result)
115 } else {
116 // Computes the standard little-endian double-and-add algorithm
117 // (Algorithm 3.27, Guide to Elliptic Curve Cryptography)
118 let mut res = Self::zero();
119 let mut multiple = self.clone();
120 for bit in bits {
121 let tmp = res.clone() + &multiple;
122 res = bit.select(&tmp, &res)?;
123 multiple.double_in_place()?;
124 }
125 Ok(res)
126 }
127 }
128
129 /// Computes a `I * self` in place, where `I` is a `Boolean` *little-endian*
130 /// representation of the scalar.
131 ///
132 /// The bases are precomputed power-of-two multiples of a single
133 /// base.
134 #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
135 fn precomputed_base_scalar_mul_le<'a, I, B>(
136 &mut self,
137 scalar_bits_with_bases: I,
138 ) -> Result<(), SynthesisError>
139 where
140 I: Iterator<Item = (B, &'a C)>,
141 B: Borrow<Boolean<ConstraintF>>,
142 C: 'a,
143 {
144 // Computes the standard little-endian double-and-add algorithm
145 // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
146
147 // Let `original` be the initial value of `self`.
148 let mut result = Self::zero();
149 for (bit, base) in scalar_bits_with_bases {
150 // Compute `self + 2^i * original`
151 let self_plus_base = result.clone() + *base;
152 // If `bit == 1`, set self = self + 2^i * original;
153 // else, set self = self;
154 result = bit.borrow().select(&self_plus_base, &result)?;
155 }
156 *self = result;
157 Ok(())
158 }
159
160 /// Computes `Σⱼ(scalarⱼ * baseⱼ)` for all j,
161 /// where `scalarⱼ` is a `Boolean` *little-endian*
162 /// representation of the j-th scalar.
163 #[tracing::instrument(target = "r1cs", skip(bases, scalars))]
164 fn precomputed_base_multiscalar_mul_le<'a, T, I, B>(
165 bases: &[B],
166 scalars: I,
167 ) -> Result<Self, SynthesisError>
168 where
169 T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
170 I: Iterator<Item = &'a T>,
171 B: Borrow<[C]>,
172 {
173 let mut result = Self::zero();
174 // Compute Σᵢ(bitᵢ * baseᵢ) for all i.
175 for (bits, bases) in scalars.zip(bases) {
176 let bases = bases.borrow();
177 let bits = bits.to_bits_le()?;
178 result.precomputed_base_scalar_mul_le(bits.iter().zip(bases))?;
179 }
180 Ok(result)
181 }
182}