ark_ec/models/short_weierstrass/
bucket.rs

1use super::{Affine, Projective, SWCurveConfig};
2use crate::AffineRepr;
3use ark_ff::{fields::Field, AdditiveGroup};
4use ark_std::{
5    borrow::Borrow,
6    fmt::{Debug, Formatter, Result as FmtResult},
7    hash::{Hash, Hasher},
8    ops::{Add, AddAssign, Neg, SubAssign},
9    One, Zero,
10};
11use educe::Educe;
12use zeroize::Zeroize;
13
14/// Extended Jacobian coordinates for a point on an elliptic curve in short Weierstrass
15/// form, over the base field `P::BaseField`.
16/// This struct implements arithmetic via the extended Jacobian arithmetic outlined here:
17/// <https://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html>
18#[derive(Educe)]
19#[educe(Copy, Clone)]
20#[must_use]
21pub struct Bucket<P: SWCurveConfig> {
22    /// `X / ZZ` projection of the affine `X`
23    pub x: P::BaseField,
24    /// `Y / ZZZ` projection of the affine `Y`
25    pub y: P::BaseField,
26    /// Bucket multiplicative inverse. Will be `0` only at infinity.
27    pub zz: P::BaseField,
28    /// Bucket multiplicative inverse. Will be `0` only at infinity.
29    pub zzz: P::BaseField,
30}
31
32impl<P: SWCurveConfig> Debug for Bucket<P> {
33    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
34        match self.is_zero() {
35            true => write!(f, "infinity"),
36            false => write!(f, "({}, {}, {}, {})", self.x, self.y, self.zz, self.zzz),
37        }
38    }
39}
40
41impl<P: SWCurveConfig> Eq for Bucket<P> {}
42
43impl<P: SWCurveConfig> PartialEq for Bucket<P> {
44    fn eq(&self, other: &Self) -> bool {
45        if self.is_zero() {
46            return other.is_zero();
47        }
48
49        if other.is_zero() {
50            return false;
51        }
52
53        // The points (X, Y, Z) and (X', Y', Z')
54        // are equal when (X * Z^2) = (X' * Z'^2)
55        // and (Y * Z^3) = (Y' * Z'^3).
56        if self.x * &other.zz == other.x * &self.zz {
57            self.y * other.zzz == other.y * &self.zzz
58        } else {
59            false
60        }
61    }
62}
63
64impl<P: SWCurveConfig> Hash for Bucket<P> {
65    fn hash<H: Hasher>(&self, state: &mut H) {
66        Affine::from(*self).hash(state)
67    }
68}
69
70impl<P: SWCurveConfig> Default for Bucket<P> {
71    #[inline]
72    fn default() -> Self {
73        Self::zero()
74    }
75}
76
77impl<P: SWCurveConfig> Bucket<P> {
78    pub const ZERO: Self = Self::new_unchecked(
79        P::BaseField::ONE,
80        P::BaseField::ONE,
81        P::BaseField::ZERO,
82        P::BaseField::ZERO,
83    );
84    /// Constructs a new group element without checking whether the coordinates
85    /// specify a point in the subgroup.
86    pub const fn new_unchecked(
87        x: P::BaseField,
88        y: P::BaseField,
89        zz: P::BaseField,
90        zzz: P::BaseField,
91    ) -> Self {
92        Self { x, y, zz, zzz }
93    }
94
95    /// Returns the point at infinity, which always has Z = 0.
96    #[inline]
97    fn zero() -> Self {
98        Self::new_unchecked(
99            P::BaseField::one(),
100            P::BaseField::one(),
101            P::BaseField::zero(),
102            P::BaseField::zero(),
103        )
104    }
105
106    /// Checks whether `self.z.is_zero()`.
107    #[inline]
108    pub fn is_zero(&self) -> bool {
109        self.zz == P::BaseField::ZERO && self.zzz == P::BaseField::ZERO
110    }
111
112    pub fn double_in_place(&mut self) {
113        // From https://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html#doubling-dbl-2008-s-1
114        // U = 2*Y1
115        let mut u = self.y;
116        u.double_in_place();
117
118        // V = U^2
119        let mut v = u;
120        v.square_in_place();
121
122        // W = U*V
123        let mut w = u;
124        w *= &v;
125
126        // S = X1*V
127        let mut s = self.x;
128        s *= &v;
129
130        // M = 3*X1^2+a*ZZ1^2
131        let mut m = self.x.square();
132        m += m.double();
133        if P::COEFF_A != P::BaseField::ZERO {
134            m += P::mul_by_a(self.zz.square());
135        }
136        // X3 = M^2-2*S
137        self.x = m;
138        self.x.square_in_place();
139        self.x -= &s.double();
140        // Y3 = M*(S-X3)-W*Y1
141        self.y = P::BaseField::sum_of_products(&[m, -w], &[(s - &self.x), self.y]);
142        // ZZ3 = V*ZZ1
143        self.zz *= v;
144        // ZZZ3 = W*ZZZ1
145        self.zzz *= &w;
146    }
147}
148
149impl<P: SWCurveConfig> Zeroize for Bucket<P> {
150    fn zeroize(&mut self) {
151        self.x.zeroize();
152        self.y.zeroize();
153        self.zz.zeroize();
154        self.zzz.zeroize();
155    }
156}
157
158impl<P: SWCurveConfig> Neg for Bucket<P> {
159    type Output = Self;
160
161    #[inline]
162    fn neg(mut self) -> Self {
163        self.y = -self.y;
164        self
165    }
166}
167
168impl<P: SWCurveConfig, T: Borrow<Affine<P>>> AddAssign<T> for Bucket<P> {
169    /// Using <https://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html#addition-madd-2008-s>
170    fn add_assign(&mut self, other: T) {
171        let other = other.borrow();
172        // If the other point is not at infinity, set `self` to the other point.
173        // If the other point *is* at infinity, `other.xy()` will be `None`, and we
174        // will do nothing
175        if let Some((other_x, other_y)) = other.xy() {
176            if self.is_zero() {
177                self.x = other_x;
178                self.y = other_y;
179                self.zz = P::BaseField::one();
180                self.zzz = P::BaseField::one();
181                return;
182            }
183
184            let z1z1 = self.zz;
185
186            // U2 = X2*Z1Z1
187            let mut u2 = other_x;
188            u2 *= &z1z1;
189
190            // S2 = Y2*Z1*Z1Z1
191            let s2 = other_y * self.zzz;
192
193            if self.x == u2 {
194                if self.y == s2 {
195                    // The two points are equal, so we double.
196                    *self = other.double_to_bucket();
197                } else {
198                    // a + (-a) = 0
199                    *self = Self::zero()
200                }
201            } else {
202                // P = (U2 - X1);
203                let mut p = u2;
204                p -= &self.x;
205
206                // R = S2-Y1
207                let mut r = s2;
208                r -= &self.y;
209
210                // PP = P^2
211                let mut pp = p;
212                pp.square_in_place();
213
214                // PPP = P*PP
215                let mut ppp = pp;
216                ppp *= &p;
217
218                // Q = X1 * PP;
219                let mut q = self.x;
220                q *= &pp;
221
222                // X3 = r^2 -PPP - 2*Q
223                self.x = r.square();
224                self.x -= &ppp;
225                self.x -= &q.double();
226
227                // Y3 = R*(Q-X3)-Y1*PPP
228                q -= &self.x;
229                self.y = P::BaseField::sum_of_products(&[r, -self.y], &[q, ppp]);
230
231                // ZZ3 = ZZ1*PP
232                // ZZZ3 = ZZZ1*PPP
233                self.zz *= &pp;
234                self.zzz *= &ppp;
235            }
236        }
237    }
238}
239
240impl<P: SWCurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Bucket<P> {
241    fn sub_assign(&mut self, other: T) {
242        *self += -(*other.borrow());
243    }
244}
245
246impl<'a, P: SWCurveConfig> Add<&'a Self> for Bucket<P> {
247    type Output = Self;
248
249    #[inline]
250    fn add(mut self, other: &'a Self) -> Self {
251        self += other;
252        self
253    }
254}
255
256impl<'a, P: SWCurveConfig> AddAssign<&'a Self> for Bucket<P> {
257    fn add_assign(&mut self, other: &'a Self) {
258        if self.is_zero() {
259            *self = *other;
260            return;
261        }
262
263        if other.is_zero() {
264            return;
265        }
266
267        // https://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html#addition-add-2008-s
268        // Works for all curves.
269
270        // Z1Z1 = Z1^2
271        let z1z1 = self.zz;
272
273        // Z2Z2 = Z2^2
274        let z2z2 = other.zz;
275
276        // U1 = X1*Z2Z2
277        let mut u1 = self.x;
278        u1 *= &z2z2;
279
280        // U2 = X2*Z1Z1
281        let mut u2 = other.x;
282        u2 *= &z1z1;
283
284        // S1 = Y1*Z2*Z2Z2
285        let s1 = self.y * other.zzz;
286
287        // S2 = Y2*Z1*Z1Z1
288        let s2 = other.y * self.zzz;
289
290        if u1 == u2 {
291            if s1 == s2 {
292                // The two points are equal, so we double.
293                self.double_in_place();
294            } else {
295                // a + (-a) = 0
296                *self = Self::zero();
297            }
298        } else {
299            // P = U2-U1
300            let mut p = u2;
301            p -= &u1;
302
303            // R = S2-S1
304            let mut r = s2;
305            r -= &s1;
306
307            // PP = P^2
308            let mut pp = p;
309            pp.square_in_place();
310
311            // PPP = P*PP
312            let mut ppp = pp;
313            ppp *= &p;
314
315            // Q = U1*PP
316            let mut q = u1;
317            q *= &pp;
318
319            // X3 = R^2 - PPP - 2*Q
320            self.x = r.square();
321            self.x -= &ppp;
322            self.x -= &q.double();
323
324            // Y3 = R*(Q-X3)-S1*PPP
325            q -= &self.x;
326            self.y = P::BaseField::sum_of_products(&[r, -s1], &[q, ppp]);
327
328            // ZZ3 = ZZ1*ZZ2*PP
329            self.zz *= &pp;
330            self.zz *= &other.zz;
331
332            // ZZZ3 = ZZZ1*ZZZ2*PPP
333            self.zzz *= &ppp;
334            self.zzz *= &other.zzz;
335        }
336    }
337}
338
339impl<'a, P: SWCurveConfig> SubAssign<&'a Self> for Bucket<P> {
340    fn sub_assign(&mut self, other: &'a Self) {
341        *self += &(-(*other));
342    }
343}
344
345impl<'a, P: SWCurveConfig> AddAssign<&'a Bucket<P>> for Projective<P> {
346    fn add_assign(&mut self, other: &'a Bucket<P>) {
347        if self.is_zero() {
348            *self = (*other).into();
349            return;
350        }
351
352        if other.is_zero() {
353            return;
354        }
355
356        // TODO: optimize using an explicit formula.
357        *self += Self::from(*other);
358    }
359}
360
361// The affine point X, Y is represented in the Jacobian
362// coordinates with Z = 1.
363impl<P: SWCurveConfig> From<Affine<P>> for Bucket<P> {
364    #[inline]
365    fn from(p: Affine<P>) -> Self {
366        p.xy().map_or_else(Self::zero, |(x, y)| Self {
367            x,
368            y,
369            zz: P::BaseField::one(),
370            zzz: P::BaseField::one(),
371        })
372    }
373}
374
375// The affine point X, Y is represented in the Jacobian
376// coordinates with Z = 1.
377impl<P: SWCurveConfig> From<Bucket<P>> for Affine<P> {
378    #[inline]
379    fn from(p: Bucket<P>) -> Self {
380        p.zzz.inverse().map_or_else(Self::zero, |zzz_inv| {
381            let b = p.zz.square();
382            let x = p.x * &b;
383            let y = p.y * zzz_inv;
384            Self::new_unchecked(x, y)
385        })
386    }
387}
388
389impl<P: SWCurveConfig> From<Bucket<P>> for Projective<P> {
390    #[inline]
391    fn from(p: Bucket<P>) -> Self {
392        if p.is_zero() {
393            Self::zero()
394        } else {
395            Self::new_unchecked(p.x * &p.zz, p.y * &p.zzz, p.zz)
396        }
397    }
398}
ark_ec/models/short_weierstrass/bucket.rs

ark_ec/models/short_weierstrass/
bucket.rs
