curvy_core/
babyjubjub.rs

1//! BabyJubjub twisted Edwards curve over BN254 `Fr` - a faithful port of
2//! `@zk-kit/baby-jubjub@1.0.3` (EIP-2494). Only the two operations EdDSA needs are
3//! ported: point addition and scalar multiplication. The curve lives over the same
4//! field as everything else (`Fr`), so no separate curve crate is required.
5//!
6//! Curve: `a·x² + y² = 1 + d·x²y²` with `a = 168700`, `d = 168696`.
7
8use std::{fmt, sync::LazyLock};
9
10use ark_ff::{AdditiveGroup, Field};
11use num_bigint::BigUint;
12use zeroize::Zeroize;
13
14use crate::field::{Bn254Fr, Bn254FrError, Fr, fr_from_dec};
15
16/// An affine BabyJubjub point `(x, y)`.
17pub type Point = (Fr, Fr);
18
19/// A canonical scalar in `[0, l)`. Zero is valid for arithmetic values such as a
20/// signature response, but not for a private key or nonce.
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub struct BabyJubScalar(BigUint);
23
24/// A canonical non-zero scalar in `[1, l)`, stored as fixed-width little-endian
25/// bytes so the owned key material can be cleared on drop.
26///
27/// The current prototype point multiplication still converts this value to a
28/// `BigUint` and is not constant-time. See the module-level security note in the
29/// scalar-signature proposal before using it in a hostile co-resident setting.
30pub struct BabyJubSecretScalar([u8; 32]);
31
32/// A checked affine point in the prime-order BabyJubJub subgroup.
33#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34pub struct BabyJubPoint {
35    x: Fr,
36    y: Fr,
37}
38
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub enum BabyJubError {
41    InvalidScalarDecimal,
42    NonCanonicalScalarDecimal,
43    ScalarOutOfRange,
44    ZeroSecretScalar,
45    InvalidCoordinate(Bn254FrError),
46    PointNotOnCurve,
47    PointNotInSubgroup,
48    IdentityPoint,
49}
50
51impl fmt::Display for BabyJubError {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        match self {
54            Self::InvalidScalarDecimal => f.write_str("invalid unsigned decimal BabyJubJub scalar"),
55            Self::NonCanonicalScalarDecimal => {
56                f.write_str("non-canonical decimal BabyJubJub scalar")
57            }
58            Self::ScalarOutOfRange => {
59                f.write_str("BabyJubJub scalar is greater than or equal to the subgroup order")
60            }
61            Self::ZeroSecretScalar => f.write_str("BabyJubJub secret scalar must be non-zero"),
62            Self::InvalidCoordinate(e) => write!(f, "invalid BabyJubJub coordinate: {e}"),
63            Self::PointNotOnCurve => f.write_str("point is not on BabyJubJub"),
64            Self::PointNotInSubgroup => {
65                f.write_str("point is not in the BabyJubJub prime-order subgroup")
66            }
67            Self::IdentityPoint => {
68                f.write_str("BabyJubJub identity is not a valid public or nonce point")
69            }
70        }
71    }
72}
73
74impl std::error::Error for BabyJubError {}
75
76impl From<Bn254FrError> for BabyJubError {
77    fn from(value: Bn254FrError) -> Self {
78        Self::InvalidCoordinate(value)
79    }
80}
81
82const COEFF_A_U64: u64 = 168700;
83const COEFF_D_U64: u64 = 168696;
84
85static COEFF_A: LazyLock<Fr> = LazyLock::new(|| Fr::from(COEFF_A_U64));
86static COEFF_D: LazyLock<Fr> = LazyLock::new(|| Fr::from(COEFF_D_U64));
87
88/// The BabyJubjub base point `Base8` (the order-`subOrder` subgroup generator).
89pub static BASE8: LazyLock<Point> = LazyLock::new(|| {
90    (
91        fr_from_dec("5299619240641551281634865583518297030282874472190772894086521144482721001553"),
92        fr_from_dec(
93            "16950150798460657717958625567821834550301663161624707787222815936182638968203",
94        ),
95    )
96});
97
98/// The large prime subgroup order `l` (`subOrder = order >> 3`). EdDSA scalars and
99/// the signature `S` are reduced modulo this.
100pub static SUB_ORDER: LazyLock<BigUint> = LazyLock::new(|| {
101    BigUint::parse_bytes(
102        b"2736030358979909402780800718157159386076813972158567259200215660948447373041",
103        10,
104    )
105    .unwrap()
106});
107
108fn parse_scalar_decimal(s: &str) -> Result<BigUint, BabyJubError> {
109    if s.is_empty() || !s.bytes().all(|b| b.is_ascii_digit()) {
110        return Err(BabyJubError::InvalidScalarDecimal);
111    }
112    if s.len() > 1 && s.starts_with('0') {
113        return Err(BabyJubError::NonCanonicalScalarDecimal);
114    }
115    BigUint::parse_bytes(s.as_bytes(), 10).ok_or(BabyJubError::InvalidScalarDecimal)
116}
117
118impl BabyJubScalar {
119    /// Construct a canonical scalar without reducing it.
120    pub fn try_from_biguint(value: BigUint) -> Result<Self, BabyJubError> {
121        if value >= *SUB_ORDER {
122            return Err(BabyJubError::ScalarOutOfRange);
123        }
124        Ok(Self(value))
125    }
126
127    pub fn try_from_dec(s: &str) -> Result<Self, BabyJubError> {
128        Self::try_from_biguint(parse_scalar_decimal(s)?)
129    }
130
131    pub fn try_from_le_bytes(bytes: [u8; 32]) -> Result<Self, BabyJubError> {
132        Self::try_from_biguint(BigUint::from_bytes_le(&bytes))
133    }
134
135    #[inline]
136    pub fn as_biguint(&self) -> &BigUint {
137        &self.0
138    }
139
140    pub fn to_le_32(&self) -> [u8; 32] {
141        let bytes = self.0.to_bytes_le();
142        let mut out = [0u8; 32];
143        out[..bytes.len()].copy_from_slice(&bytes);
144        out
145    }
146
147    pub fn to_dec(&self) -> String {
148        self.0.to_str_radix(10)
149    }
150}
151
152impl BabyJubSecretScalar {
153    pub fn try_from_biguint(value: BigUint) -> Result<Self, BabyJubError> {
154        let scalar = BabyJubScalar::try_from_biguint(value)?;
155        if scalar.0 == BigUint::from(0u8) {
156            return Err(BabyJubError::ZeroSecretScalar);
157        }
158        Ok(Self(scalar.to_le_32()))
159    }
160
161    pub fn try_from_dec(s: &str) -> Result<Self, BabyJubError> {
162        Self::try_from_biguint(parse_scalar_decimal(s)?)
163    }
164
165    pub fn try_from_le_bytes(bytes: [u8; 32]) -> Result<Self, BabyJubError> {
166        Self::try_from_biguint(BigUint::from_bytes_le(&bytes))
167    }
168
169    #[inline]
170    pub fn to_le_32(&self) -> [u8; 32] {
171        self.0
172    }
173
174    #[inline]
175    pub(crate) fn to_biguint(&self) -> BigUint {
176        BigUint::from_bytes_le(&self.0)
177    }
178
179    pub fn to_dec(&self) -> String {
180        self.to_biguint().to_str_radix(10)
181    }
182}
183
184impl Drop for BabyJubSecretScalar {
185    fn drop(&mut self) {
186        self.0.zeroize();
187    }
188}
189
190impl BabyJubPoint {
191    /// Check curve and subgroup membership. The identity is allowed here for
192    /// arithmetic uses; public/nonce boundaries should call [`Self::try_from_xy_non_identity`].
193    pub fn try_from_xy(x: Fr, y: Fr) -> Result<Self, BabyJubError> {
194        let point = (x, y);
195        if !is_on_curve(point) {
196            return Err(BabyJubError::PointNotOnCurve);
197        }
198        if !is_in_subgroup(point) {
199            return Err(BabyJubError::PointNotInSubgroup);
200        }
201        Ok(Self { x, y })
202    }
203
204    pub fn try_from_xy_non_identity(x: Fr, y: Fr) -> Result<Self, BabyJubError> {
205        let point = Self::try_from_xy(x, y)?;
206        if point.is_identity() {
207            return Err(BabyJubError::IdentityPoint);
208        }
209        Ok(point)
210    }
211
212    /// Parse canonical decimal coordinates, then check curve, subgroup, and
213    /// non-identity requirements.
214    pub fn try_from_dec(x: &str, y: &str) -> Result<Self, BabyJubError> {
215        let x = Bn254Fr::try_from_dec(x)?.into_inner();
216        let y = Bn254Fr::try_from_dec(y)?.into_inner();
217        Self::try_from_xy_non_identity(x, y)
218    }
219
220    #[inline]
221    pub(crate) fn from_subgroup_non_identity_unchecked(point: Point) -> Self {
222        debug_assert!(is_on_curve(point));
223        debug_assert!(is_in_subgroup(point));
224        debug_assert_ne!(point, identity());
225        Self {
226            x: point.0,
227            y: point.1,
228        }
229    }
230
231    #[inline]
232    pub fn x(&self) -> Fr {
233        self.x
234    }
235
236    #[inline]
237    pub fn y(&self) -> Fr {
238        self.y
239    }
240
241    #[inline]
242    pub fn as_tuple(&self) -> Point {
243        (self.x, self.y)
244    }
245
246    #[inline]
247    pub fn is_identity(&self) -> bool {
248        self.as_tuple() == identity()
249    }
250}
251
252/// The neutral element `(0, 1)`.
253#[inline]
254pub fn identity() -> Point {
255    (Fr::ZERO, Fr::ONE)
256}
257
258/// Whether `point` satisfies the BabyJubJub twisted-Edwards equation.
259pub fn is_on_curve(point: Point) -> bool {
260    let (x, y) = point;
261    let x2 = x * x;
262    let y2 = y * y;
263    *COEFF_A * x2 + y2 == Fr::ONE + *COEFF_D * x2 * y2
264}
265
266/// Whether an on-curve point is in the subgroup generated by [`BASE8`].
267pub fn is_in_subgroup(point: Point) -> bool {
268    is_on_curve(point) && mul_point_escalar(point, &SUB_ORDER) == identity()
269}
270
271/// Twisted Edwards point addition, mirroring `@zk-kit`'s exact formula:
272///
273/// ```text
274/// x3 = (x1·y2 + y1·x2) / (1 + d·x1·x2·y1·y2)
275/// y3 = (y1·y2 − a·x1·x2) / (1 − d·x1·x2·y1·y2)
276/// ```
277///
278/// The addition law is complete on BabyJubjub, so the denominators never vanish.
279pub fn add_point(p1: Point, p2: Point) -> Point {
280    let (x1, y1) = p1;
281    let (x2, y2) = p2;
282    let a = *COEFF_A;
283    let d = *COEFF_D;
284
285    let beta = x1 * y2;
286    let gamma = y1 * x2;
287    let delta = (y1 - a * x1) * (x2 + y2);
288    let dtau = d * (beta * gamma);
289
290    let x3 = (beta + gamma)
291        * (Fr::ONE + dtau)
292            .inverse()
293            .expect("babyjubjub: x denominator nonzero");
294    let y3 = (delta + a * beta - gamma)
295        * (Fr::ONE - dtau)
296            .inverse()
297            .expect("babyjubjub: y denominator nonzero");
298    (x3, y3)
299}
300
301/// Scalar multiplication `e · base` via LSB-first double-and-add (`mulPointEscalar`).
302/// `e` is consumed as a non-negative integer of any size (it need not be reduced
303/// modulo the subgroup order - the result is identical either way).
304pub fn mul_point_escalar(base: Point, e: &BigUint) -> Point {
305    let mut res = identity();
306    let mut exp = base;
307    for i in 0..e.bits() {
308        if e.bit(i) {
309            res = add_point(res, exp);
310        }
311        exp = add_point(exp, exp);
312    }
313    res
314}
315
316/// Direct public-key derivation from a canonical non-zero subgroup scalar.
317pub fn public_key_from_scalar(scalar: &BabyJubSecretScalar) -> BabyJubPoint {
318    BabyJubPoint::from_subgroup_non_identity_unchecked(mul_point_escalar(
319        *BASE8,
320        &scalar.to_biguint(),
321    ))
322}
323
324#[cfg(test)]
325mod tests {
326    use super::*;
327    use crate::field::FIELD_MODULUS_DEC;
328
329    #[test]
330    fn scalar_boundaries_are_strict() {
331        assert_eq!(
332            BabyJubSecretScalar::try_from_dec("0").err(),
333            Some(BabyJubError::ZeroSecretScalar)
334        );
335        assert_eq!(
336            BabyJubScalar::try_from_dec("00").unwrap_err(),
337            BabyJubError::NonCanonicalScalarDecimal
338        );
339        assert_eq!(
340            BabyJubScalar::try_from_dec(&SUB_ORDER.to_string()).unwrap_err(),
341            BabyJubError::ScalarOutOfRange
342        );
343        assert_eq!(
344            BabyJubSecretScalar::try_from_dec("1").unwrap().to_dec(),
345            "1"
346        );
347    }
348
349    #[test]
350    fn direct_public_key_is_checked() {
351        let one = BabyJubSecretScalar::try_from_dec("1").unwrap();
352        assert_eq!(public_key_from_scalar(&one).as_tuple(), *BASE8);
353        assert!(BabyJubPoint::try_from_xy(BASE8.0, BASE8.1).is_ok());
354        assert_eq!(
355            BabyJubPoint::try_from_xy_non_identity(Fr::ZERO, Fr::ONE),
356            Err(BabyJubError::IdentityPoint)
357        );
358        assert_eq!(
359            BabyJubPoint::try_from_xy(Fr::ZERO, Fr::ZERO),
360            Err(BabyJubError::PointNotOnCurve)
361        );
362        assert!(matches!(
363            BabyJubPoint::try_from_dec(FIELD_MODULUS_DEC, "1"),
364            Err(BabyJubError::InvalidCoordinate(_))
365        ));
366    }
367}
curvy_core/babyjubjub.rs

curvy_core/
babyjubjub.rs
