snarkvm_curves/templates/twisted_edwards_extended/
projective.rs

1// Copyright 2024-2025 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{
17    templates::twisted_edwards_extended::Affine,
18    traits::{AffineCurve, ProjectiveCurve, TwistedEdwardsParameters as Parameters},
19};
20use snarkvm_fields::{Field, One, PrimeField, Zero, impl_add_sub_from_field_ref};
21use snarkvm_utilities::{FromBytes, ToBytes, bititerator::BitIteratorBE, rand::Uniform, serialize::*};
22
23use core::{
24    fmt::{Display, Formatter, Result as FmtResult},
25    hash::{Hash, Hasher},
26    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
27};
28use rand::{
29    Rng,
30    distributions::{Distribution, Standard},
31};
32use std::io::{Read, Result as IoResult, Write};
33
34#[derive(Copy, Clone, Debug)]
35pub struct Projective<P: Parameters> {
36    pub x: P::BaseField,
37    pub y: P::BaseField,
38    pub t: P::BaseField,
39    pub z: P::BaseField,
40}
41
42impl<P: Parameters> Projective<P> {
43    #[inline]
44    pub const fn new(x: P::BaseField, y: P::BaseField, t: P::BaseField, z: P::BaseField) -> Self {
45        Self { x, y, t, z }
46    }
47}
48
49impl<P: Parameters> Zero for Projective<P> {
50    fn zero() -> Self {
51        Self::new(P::BaseField::zero(), P::BaseField::one(), P::BaseField::zero(), P::BaseField::one())
52    }
53
54    fn is_zero(&self) -> bool {
55        self.x.is_zero() && self.y == self.z && !self.y.is_zero() && self.t.is_zero()
56    }
57}
58
59impl<P: Parameters> Default for Projective<P> {
60    #[inline]
61    fn default() -> Self {
62        Self::zero()
63    }
64}
65
66impl<P: Parameters> Display for Projective<P> {
67    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
68        write!(f, "{}", self.to_affine())
69    }
70}
71
72impl<P: Parameters> Hash for Projective<P> {
73    fn hash<H: Hasher>(&self, state: &mut H) {
74        self.to_affine().hash(state);
75    }
76}
77
78impl<P: Parameters> Eq for Projective<P> {}
79
80impl<P: Parameters> PartialEq for Projective<P> {
81    fn eq(&self, other: &Self) -> bool {
82        if self.is_zero() {
83            return other.is_zero();
84        }
85
86        if other.is_zero() {
87            return false;
88        }
89
90        // x1/z1 == x2/z2  <==> x1 * z2 == x2 * z1
91        (self.x * other.z) == (other.x * self.z) && (self.y * other.z) == (other.y * self.z)
92    }
93}
94
95impl<P: Parameters> PartialEq<Affine<P>> for Projective<P> {
96    fn eq(&self, other: &Affine<P>) -> bool {
97        if self.is_zero() {
98            return other.is_zero();
99        }
100
101        if other.is_zero() {
102            return false;
103        }
104
105        // x1/z1 == x2/z2  <==> x1 * z2 == x2 * z1
106        self.x == (other.x * self.z) && self.y == (other.y * self.z)
107    }
108}
109
110impl<P: Parameters> Distribution<Projective<P>> for Standard {
111    #[inline]
112    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Projective<P> {
113        loop {
114            let x = P::BaseField::rand(rng);
115            let greatest = rng.gen();
116
117            if let Some(p) = Affine::from_x_coordinate(x, greatest) {
118                return p.mul_by_cofactor_to_projective();
119            }
120        }
121    }
122}
123
124impl<P: Parameters> ToBytes for Projective<P> {
125    #[inline]
126    fn write_le<W: Write>(&self, mut writer: W) -> IoResult<()> {
127        self.x.write_le(&mut writer)?;
128        self.y.write_le(&mut writer)?;
129        self.t.write_le(&mut writer)?;
130        self.z.write_le(writer)
131    }
132}
133
134impl<P: Parameters> FromBytes for Projective<P> {
135    #[inline]
136    fn read_le<R: Read>(mut reader: R) -> IoResult<Self> {
137        let x = P::BaseField::read_le(&mut reader)?;
138        let y = P::BaseField::read_le(&mut reader)?;
139        let t = P::BaseField::read_le(&mut reader)?;
140        let z = P::BaseField::read_le(reader)?;
141        Ok(Self::new(x, y, t, z))
142    }
143}
144
145impl<P: Parameters> ProjectiveCurve for Projective<P> {
146    type Affine = Affine<P>;
147    type BaseField = P::BaseField;
148    type ScalarField = P::ScalarField;
149
150    fn prime_subgroup_generator() -> Self {
151        Affine::prime_subgroup_generator().into()
152    }
153
154    fn is_normalized(&self) -> bool {
155        self.z.is_one()
156    }
157
158    fn batch_normalization(v: &mut [Self]) {
159        // Montgomery’s Trick and Fast Implementation of Masked AES
160        // Genelle, Prouff and Quisquater
161        // Section 3.2
162
163        // First pass: compute [a, ab, abc, ...]
164        let mut prod = Vec::with_capacity(v.len());
165        let mut tmp = P::BaseField::one();
166        for g in v
167            .iter_mut()
168            // Ignore normalized elements
169            .filter(|g| !g.is_normalized())
170        {
171            tmp.mul_assign(&g.z);
172            prod.push(tmp);
173        }
174
175        // Invert `tmp`.
176        tmp = tmp.inverse().unwrap(); // Guaranteed to be nonzero.
177
178        // Second pass: iterate backwards to compute inverses
179        for (g, s) in v
180            .iter_mut()
181            // Backwards
182            .rev()
183            // Ignore normalized elements
184            .filter(|g| !g.is_normalized())
185            // Backwards, skip last element, fill in one for last term.
186            .zip(
187                prod.into_iter()
188                    .rev()
189                    .skip(1)
190                    .chain(Some(P::BaseField::one())),
191            )
192        {
193            // tmp := tmp * g.z; g.z := tmp * s = 1/z
194            let newtmp = tmp * g.z;
195            g.z = tmp * s;
196            tmp = newtmp;
197        }
198
199        // Perform affine transformations
200        for g in v.iter_mut().filter(|g| !g.is_normalized()) {
201            g.x *= &g.z; // x/z
202            g.y *= &g.z;
203            g.t *= &g.z;
204            g.z = P::BaseField::one(); // z = 1
205        }
206    }
207
208    #[allow(clippy::many_single_char_names)]
209    fn add_assign_mixed(&mut self, other: &Self::Affine) {
210        // A = X1*X2
211        let a = self.x * other.x;
212        // B = Y1*Y2
213        let b = self.y * other.y;
214        // C = T1*d*T2
215        let c = P::EDWARDS_D * self.t * other.t;
216        // D = Z1
217        let d = self.z;
218        // E = (X1+Y1)*(X2+Y2)-A-B
219        let e = (self.x + self.y) * (other.x + other.y) - a - b;
220        // F = D-C
221        let f = d - c;
222        // G = D+C
223        let g = d + c;
224        // H = B-a*A
225        let h = b - P::mul_by_a(&a);
226        // X3 = E*F
227        self.x = e * f;
228        // Y3 = G*H
229        self.y = g * h;
230        // T3 = E*H
231        self.t = e * h;
232        // Z3 = F*G
233        self.z = f * g;
234    }
235
236    #[inline]
237    #[must_use]
238    fn double(&self) -> Self {
239        let mut result = *self;
240        result.double_in_place();
241        result
242    }
243
244    #[inline]
245    fn double_in_place(&mut self) {
246        // See "Twisted Edwards Curves Revisited"
247        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
248        // 3.3 Doubling in E^e
249        // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/doubling/dbl-2008-hwcd
250
251        // A = X1^2
252        let a = self.x.square();
253        // B = Y1^2
254        let b = self.y.square();
255        // C = 2 * Z1^2
256        let c = self.z.square().double();
257        // D = a * A
258        let d = P::mul_by_a(&a);
259        // E = (X1 + Y1)^2 - A - B
260        let e = (self.x + self.y).square() - a - b;
261        // G = D + B
262        let g = d + b;
263        // F = G - C
264        let f = g - c;
265        // H = D - B
266        let h = d - b;
267        // X3 = E * F
268        self.x = e * f;
269        // Y3 = G * H
270        self.y = g * h;
271        // T3 = E * H
272        self.t = e * h;
273        // Z3 = F * G
274        self.z = f * g;
275    }
276
277    fn to_affine(&self) -> Affine<P> {
278        (*self).into()
279    }
280}
281
282impl<P: Parameters> Neg for Projective<P> {
283    type Output = Self;
284
285    fn neg(mut self) -> Self {
286        self.x = -self.x;
287        self.t = -self.t;
288        self
289    }
290}
291
292impl_add_sub_from_field_ref!(Projective, Parameters);
293
294impl<'a, P: Parameters> Add<&'a Self> for Projective<P> {
295    type Output = Self;
296
297    fn add(self, other: &'a Self) -> Self {
298        let mut copy = self;
299        copy += other;
300        copy
301    }
302}
303
304impl<'a, P: Parameters> AddAssign<&'a Self> for Projective<P> {
305    #[allow(clippy::many_single_char_names)]
306    #[allow(clippy::suspicious_op_assign_impl)]
307    fn add_assign(&mut self, other: &'a Self) {
308        // See "Twisted Edwards Curves Revisited"
309        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
310        // 3.1 Unified Addition in E^e
311
312        // A = x1 * x2
313        let a = self.x * other.x;
314
315        // B = y1 * y2
316        let b = self.y * other.y;
317
318        // C = d * t1 * t2
319        let c = P::EDWARDS_D * self.t * other.t;
320
321        // D = z1 * z2
322        let d = self.z * other.z;
323
324        // H = B - aA
325        let h = b - P::mul_by_a(&a);
326
327        // E = (x1 + y1) * (x2 + y2) - A - B
328        let e = (self.x + self.y) * (other.x + other.y) - a - b;
329
330        // F = D - C
331        let f = d - c;
332
333        // G = D + C
334        let g = d + c;
335
336        // x3 = E * F
337        self.x = e * f;
338
339        // y3 = G * H
340        self.y = g * h;
341
342        // t3 = E * H
343        self.t = e * h;
344
345        // z3 = F * G
346        self.z = f * g;
347    }
348}
349
350impl<'a, P: Parameters> Sub<&'a Self> for Projective<P> {
351    type Output = Self;
352
353    fn sub(self, other: &'a Self) -> Self {
354        let mut copy = self;
355        copy -= other;
356        copy
357    }
358}
359
360impl<'a, P: Parameters> SubAssign<&'a Self> for Projective<P> {
361    fn sub_assign(&mut self, other: &'a Self) {
362        *self += &(-(*other));
363    }
364}
365
366impl<P: Parameters> Mul<P::ScalarField> for Projective<P> {
367    type Output = Self;
368
369    /// Performs scalar multiplication of this element.
370    #[allow(clippy::suspicious_arithmetic_impl)]
371    #[inline]
372    fn mul(self, other: P::ScalarField) -> Self {
373        let mut res = Self::zero();
374
375        let mut found_one = false;
376
377        for i in BitIteratorBE::new(other.to_bigint()) {
378            if found_one {
379                res.double_in_place();
380            } else {
381                found_one = i;
382            }
383
384            if i {
385                res += self;
386            }
387        }
388
389        res
390    }
391}
392
393impl<P: Parameters> MulAssign<P::ScalarField> for Projective<P> {
394    /// Performs scalar multiplication of this element.
395    fn mul_assign(&mut self, other: P::ScalarField) {
396        *self = *self * other
397    }
398}
399
400// The affine point (X, Y) is represented in the Extended Projective coordinates with Z = 1.
401impl<P: Parameters> From<Affine<P>> for Projective<P> {
402    fn from(p: Affine<P>) -> Projective<P> {
403        Self::new(p.x, p.y, p.x * p.y, P::BaseField::one())
404    }
405}
snarkvm_curves/templates/twisted_edwards_extended/projective.rs

snarkvm_curves/templates/twisted_edwards_extended/
projective.rs
