cyclone_msm/
preprocess.rs

1//! Point preprocessing.
2
3use core::ops::{AddAssign, Neg, SubAssign};
4
5pub use ark_bls12_377::g1::Parameters;
6use ark_bls12_377::{Fq, G1Affine};
7use ark_ec::{
8    models::twisted_edwards::{Affine, Projective, TECurveConfig},
9    AffineRepr as _,
10};
11use ark_ff::Field as _;
12use ark_std::{One as _, Zero as _};
13use derivative::Derivative;
14
15use crate::bls12_377::G1PTEAffine;
16
17/// Affine coordinates for a point on a twisted Edwards curve, over the
18/// base field `P::BaseField`.
19///
20/// Includes the coordinate `2D*x*y`.
21#[derive(Derivative)]
22#[derivative(Copy(bound = "P: TECurveConfig"), Clone(bound = "P: TECurveConfig"))]
23// #[must_use]
24#[derive(Debug, Eq, Hash, PartialEq)]
25pub struct PreprocessedAffine<P: TECurveConfig> {
26    /// X coordinate of the point represented as a field element
27    pub x: P::BaseField,
28    /// Y coordinate of the point represented as a field element
29    pub y: P::BaseField,
30    /// Precomputed product k*X*Y, k=2D - formulas for A=-1
31    pub kt: P::BaseField,
32}
33
34impl<P: TECurveConfig> PreprocessedAffine<P> {
35    pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
36        Self {
37            x,
38            y,
39            kt: (P::COEFF_D + P::COEFF_D) * x * y,
40        }
41    }
42
43    pub const fn zero() -> Self {
44        Self {
45            x: P::BaseField::ZERO,
46            y: P::BaseField::ONE,
47            kt: P::BaseField::ZERO,
48        }
49    }
50
51    pub fn is_zero(&self) -> bool {
52        self.x.is_zero() && self.y.is_one()
53    }
54}
55
56impl<P: TECurveConfig> From<Affine<P>> for PreprocessedAffine<P> {
57    fn from(affine: Affine<P>) -> PreprocessedAffine<P> {
58        Self::new(affine.x, affine.y)
59    }
60}
61
62impl<P: TECurveConfig> From<&Affine<P>> for PreprocessedAffine<P> {
63    fn from(affine: &Affine<P>) -> PreprocessedAffine<P> {
64        Self::new(affine.x, affine.y)
65    }
66}
67
68impl<P: TECurveConfig> From<PreprocessedAffine<P>> for Affine<P> {
69    fn from(pre: PreprocessedAffine<P>) -> Affine<P> {
70        Self::new(pre.x, pre.y)
71    }
72}
73
74impl<P: TECurveConfig> From<&PreprocessedAffine<P>> for Affine<P> {
75    fn from(pre: &PreprocessedAffine<P>) -> Affine<P> {
76        Self::new(pre.x, pre.y)
77    }
78}
79
80impl<'a, P: TECurveConfig> AddAssign<&'a PreprocessedAffine<P>> for Projective<P> {
81    fn add_assign(&mut self, other: &PreprocessedAffine<P>) {
82        if self.is_zero() {
83            // not checking this results is 7M vs 1M
84            self.x = other.x;
85            self.y = other.y;
86            self.t = other.x * other.y;
87            self.z = P::BaseField::one();
88            return;
89        }
90
91        /* 8M, we can do 7M
92        // See "Twisted Edwards Curves Revisited"
93        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
94        // 3.1 Unified Addition in E^e
95        // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/addition/madd-2008-hwcd
96        // A = X1*X2
97        let a = self.x * &other.x;
98        // B = Y1*Y2
99        let b = self.y * &other.y;
100        // C = T1*d*T2
101        let c = self.t * &other.kt;
102
103        // D = Z1
104        let d = self.z;
105        // E = (X1+Y1)*(X2+Y2)-A-B
106        let e = (self.x + &self.y) * &(other.x + &other.y) - &a - &b;
107        // F = D-C
108        let f = d - &c;
109        // G = D+C
110        let g = d + &c;
111        // H = B-a*A
112        // let h = b - &P::mul_by_a(&a);
113        let h = b + &a;
114        // X3 = E*F
115        self.x = e * &f;
116        // Y3 = G*H
117        self.y = g * &h;
118        // T3 = E*H
119        self.t = e * &h;
120        // Z3 = F*G
121        self.z = f * &g;
122        return;
123        */
124
125        let r1 = self.y - self.x;
126        let r2 = other.y - other.x;
127        let r3 = self.y + self.x;
128        let r4 = other.y + other.x;
129
130        // step 2: 1M (if parallel)
131        let r5 = r1 * r2;
132        let r6 = r3 * r4;
133        let r7 = self.t * other.kt;
134        let r8 = self.z.double();
135
136        // step 3: 1D
137        // R7 = P::COEFF_D * R7;
138        // R8 = R8.double();
139
140        // step 4
141        let r1b = r6 - r5;
142        let r2b = r8 - r7;
143        let r3b = r8 + r7;
144        let r4b = r6 + r5;
145
146        // step 5
147        self.x = r1b * r2b;
148        self.y = r3b * r4b;
149        self.t = r1b * r4b;
150        self.z = r2b * r3b;
151    }
152}
153
154impl<'a, P: TECurveConfig> SubAssign<&'a PreprocessedAffine<P>> for Projective<P> {
155    fn sub_assign(&mut self, other: &'a PreprocessedAffine<P>) {
156        self.add_assign(&(-*other))
157    }
158}
159
160impl<P: TECurveConfig> Neg for PreprocessedAffine<P> {
161    type Output = Self;
162
163    fn neg(self) -> Self {
164        Self {
165            x: -self.x,
166            y: self.y,
167            kt: -self.kt,
168        }
169    }
170}
171
172/// convert affine Weierstrass to affine extended Twisted Edwards in batch
173pub fn batch_preprocess(a: &[G1Affine], b: &mut [G1PTEAffine]) {
174    use crate::bls12_377::{FQ_S, FQ_SQRT_MIN_A};
175
176    debug_assert!(a.len() == b.len());
177
178    let mut x = vec![Fq::ZERO; a.len()];
179    let mut y = vec![Fq::ZERO; a.len()];
180    let mut z = vec![Fq::ZERO; a.len()];
181
182    for (i, p) in a.iter().enumerate() {
183        if p.is_zero() {
184            x[i] = Fq::ZERO;
185            y[i] = Fq::ONE;
186            z[i] = Fq::ONE;
187            continue;
188        }
189
190        let xpo = p.x + Fq::ONE;
191        let sxpo = xpo * FQ_S;
192        let axpo = xpo * FQ_SQRT_MIN_A;
193        let syxpo = sxpo * p.y;
194
195        x[i] = (sxpo + Fq::ONE) * axpo;
196        y[i] = syxpo - p.y;
197        z[i] = syxpo + p.y;
198    }
199
200    ark_ff::batch_inversion(&mut z);
201
202    for i in 0..a.len() {
203        b[i] = G1PTEAffine::new(x[i] * z[i], y[i] * z[i]);
204    }
205}
206
207// pub fn into_twisted(p: &G1Affine) -> G1TEAffine {
208//     if p.is_zero() {
209//         return G1TEAffine::new(Fq::ZERO, Fq::ONE);
210//     }
211
212//     let xpo = p.x + Fq::ONE;
213//     let sxpo = xpo * FQ_S;
214//     let axpo = xpo * FQ_SQRT_MIN_A;
215//     let syxpo = sxpo * p.y;
216
217//     let x = (sxpo + Fq::ONE) * axpo;
218//     let y = syxpo - p.y;
219//     let z = syxpo + p.y;
220//     let z_inv = Fq::ONE / z;
221
222//     G1TEAffine::new(x * z_inv, y * z_inv)
223// }
224
225// impl Into<G1Projective> for &G1TEProjective {
226//     fn into(self) -> G1Projective {
227//         into_weierstrass(self)
228//     }
229// }
230
231pub fn preprocess_points(points: &[G1Affine]) -> Vec<G1PTEAffine> {
232    let mut ppoints = vec![G1PTEAffine::zero(); points.len()];
233
234    const CHUNK: usize = 1 << 16;
235    for (chunk_in, chunk_out) in points
236        .chunks(CHUNK)
237        .zip(ppoints.as_mut_slice().chunks_mut(CHUNK))
238    {
239        crate::preprocess::batch_preprocess(chunk_in, chunk_out);
240    }
241    ppoints
242}
cyclone_msm/preprocess.rs

cyclone_msm/
preprocess.rs
