snarkvm_curves/templates/twisted_edwards_extended/
projective.rs

1// Copyright (c) 2019-2025 Provable Inc.
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};
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.r#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    fn double(&self) -> Self {
238        let mut result = *self;
239        result.double_in_place();
240        result
241    }
242
243    #[inline]
244    fn double_in_place(&mut self) {
245        // See "Twisted Edwards Curves Revisited"
246        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
247        // 3.3 Doubling in E^e
248        // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/doubling/dbl-2008-hwcd
249
250        // A = X1^2
251        let a = self.x.square();
252        // B = Y1^2
253        let b = self.y.square();
254        // C = 2 * Z1^2
255        let c = self.z.square().double();
256        // D = a * A
257        let d = P::mul_by_a(&a);
258        // E = (X1 + Y1)^2 - A - B
259        let e = (self.x + self.y).square() - a - b;
260        // G = D + B
261        let g = d + b;
262        // F = G - C
263        let f = g - c;
264        // H = D - B
265        let h = d - b;
266        // X3 = E * F
267        self.x = e * f;
268        // Y3 = G * H
269        self.y = g * h;
270        // T3 = E * H
271        self.t = e * h;
272        // Z3 = F * G
273        self.z = f * g;
274    }
275
276    fn to_affine(&self) -> Affine<P> {
277        (*self).into()
278    }
279}
280
281impl<P: Parameters> Neg for Projective<P> {
282    type Output = Self;
283
284    fn neg(mut self) -> Self {
285        self.x = -self.x;
286        self.t = -self.t;
287        self
288    }
289}
290
291impl_add_sub_from_field_ref!(Projective, Parameters);
292
293impl<'a, P: Parameters> Add<&'a Self> for Projective<P> {
294    type Output = Self;
295
296    fn add(self, other: &'a Self) -> Self {
297        let mut copy = self;
298        copy += other;
299        copy
300    }
301}
302
303impl<'a, P: Parameters> AddAssign<&'a Self> for Projective<P> {
304    #[allow(clippy::many_single_char_names)]
305    #[allow(clippy::suspicious_op_assign_impl)]
306    fn add_assign(&mut self, other: &'a Self) {
307        // See "Twisted Edwards Curves Revisited"
308        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
309        // 3.1 Unified Addition in E^e
310
311        // A = x1 * x2
312        let a = self.x * other.x;
313
314        // B = y1 * y2
315        let b = self.y * other.y;
316
317        // C = d * t1 * t2
318        let c = P::EDWARDS_D * self.t * other.t;
319
320        // D = z1 * z2
321        let d = self.z * other.z;
322
323        // H = B - aA
324        let h = b - P::mul_by_a(&a);
325
326        // E = (x1 + y1) * (x2 + y2) - A - B
327        let e = (self.x + self.y) * (other.x + other.y) - a - b;
328
329        // F = D - C
330        let f = d - c;
331
332        // G = D + C
333        let g = d + c;
334
335        // x3 = E * F
336        self.x = e * f;
337
338        // y3 = G * H
339        self.y = g * h;
340
341        // t3 = E * H
342        self.t = e * h;
343
344        // z3 = F * G
345        self.z = f * g;
346    }
347}
348
349impl<'a, P: Parameters> Sub<&'a Self> for Projective<P> {
350    type Output = Self;
351
352    fn sub(self, other: &'a Self) -> Self {
353        let mut copy = self;
354        copy -= other;
355        copy
356    }
357}
358
359impl<'a, P: Parameters> SubAssign<&'a Self> for Projective<P> {
360    fn sub_assign(&mut self, other: &'a Self) {
361        *self += &(-(*other));
362    }
363}
364
365impl<P: Parameters> Mul<P::ScalarField> for Projective<P> {
366    type Output = Self;
367
368    /// Performs scalar multiplication of this element.
369    #[allow(clippy::suspicious_arithmetic_impl)]
370    #[inline]
371    fn mul(self, other: P::ScalarField) -> Self {
372        let mut res = Self::zero();
373
374        let mut found_one = false;
375
376        for i in BitIteratorBE::new(other.to_bigint()) {
377            if found_one {
378                res.double_in_place();
379            } else {
380                found_one = i;
381            }
382
383            if i {
384                res += self;
385            }
386        }
387
388        res
389    }
390}
391
392impl<P: Parameters> MulAssign<P::ScalarField> for Projective<P> {
393    /// Performs scalar multiplication of this element.
394    fn mul_assign(&mut self, other: P::ScalarField) {
395        *self = *self * other
396    }
397}
398
399// The affine point (X, Y) is represented in the Extended Projective coordinates with Z = 1.
400impl<P: Parameters> From<Affine<P>> for Projective<P> {
401    fn from(p: Affine<P>) -> Projective<P> {
402        Self::new(p.x, p.y, p.x * p.y, P::BaseField::one())
403    }
404}
snarkvm_curves/templates/twisted_edwards_extended/projective.rs

snarkvm_curves/templates/twisted_edwards_extended/
projective.rs
