aztec_core/
grumpkin.rs

1//! Minimal Grumpkin curve arithmetic for contract address derivation.
2//!
3//! Grumpkin is an embedded curve of BN254 defined by `y^2 = x^3 - 17`
4//! over BN254's scalar field (Fr). Only affine point addition and
5//! scalar multiplication are implemented — just enough for
6//! `compute_contract_address_from_instance`.
7
8use ark_bn254::Fr as ArkFr;
9use ark_ff::{AdditiveGroup, BigInteger, Field, PrimeField};
10
11use crate::{
12    types::{Fq, Fr, Point},
13    Error,
14};
15
16/// Grumpkin curve parameter: y^2 = x^3 + B, where B = -17.
17const B: i64 = -17;
18
19/// Return the Grumpkin generator point G = (1, y) where y = sqrt(1 - 17).
20pub fn generator() -> Point {
21    let one = ArkFr::from(1u64);
22    // rhs = 1^3 + B = 1 - 17 = -16
23    let rhs = one + ArkFr::from(B.unsigned_abs()) * (-ArkFr::from(1u64));
24    let y = rhs.sqrt().expect("Grumpkin generator y must exist");
25
26    // Pick the lexicographically smaller y (convention).
27    let neg_y = -y;
28    let chosen = if y.into_bigint() < neg_y.into_bigint() {
29        y
30    } else {
31        neg_y
32    };
33
34    Point {
35        x: Fr(one),
36        y: Fr(chosen),
37        is_infinite: false,
38    }
39}
40
41/// Add two Grumpkin affine points.
42pub fn point_add(p: &Point, q: &Point) -> Point {
43    if p.is_infinite {
44        return *q;
45    }
46    if q.is_infinite {
47        return *p;
48    }
49
50    let px = p.x.0;
51    let py = p.y.0;
52    let qx = q.x.0;
53    let qy = q.y.0;
54
55    // If same x but opposite y (or both zero), result is point at infinity.
56    if px == qx {
57        if py == -qy || (py == ArkFr::ZERO && qy == ArkFr::ZERO) {
58            return Point {
59                x: Fr::zero(),
60                y: Fr::zero(),
61                is_infinite: true,
62            };
63        }
64        // Same point → doubling
65        return point_double(p);
66    }
67
68    // Standard affine addition: λ = (qy - py) / (qx - px)
69    let lambda = (qy - py) * (qx - px).inverse().expect("non-zero denominator");
70    let x3 = lambda * lambda - px - qx;
71    let y3 = lambda * (px - x3) - py;
72
73    Point {
74        x: Fr(x3),
75        y: Fr(y3),
76        is_infinite: false,
77    }
78}
79
80/// Double a Grumpkin affine point.
81fn point_double(p: &Point) -> Point {
82    if p.is_infinite || p.y.0 == ArkFr::ZERO {
83        return Point {
84            x: Fr::zero(),
85            y: Fr::zero(),
86            is_infinite: true,
87        };
88    }
89
90    let px = p.x.0;
91    let py = p.y.0;
92
93    // Grumpkin has a = 0, so λ = 3x^2 / (2y)
94    let three_x_sq = ArkFr::from(3u64) * px * px;
95    let two_y = ArkFr::from(2u64) * py;
96    let lambda = three_x_sq * two_y.inverse().expect("non-zero y");
97    let x3 = lambda * lambda - px - px;
98    let y3 = lambda * (px - x3) - py;
99
100    Point {
101        x: Fr(x3),
102        y: Fr(y3),
103        is_infinite: false,
104    }
105}
106
107/// Scalar multiplication via double-and-add.
108///
109/// The scalar is an `Fq` element (BN254 base field = Grumpkin scalar field).
110pub fn scalar_mul(scalar: &Fq, point: &Point) -> Point {
111    if point.is_infinite {
112        return *point;
113    }
114    if scalar.is_zero() {
115        return Point {
116            x: Fr::zero(),
117            y: Fr::zero(),
118            is_infinite: true,
119        };
120    }
121
122    let bits = scalar.0.into_bigint().to_bits_be();
123
124    // Skip leading zeros
125    let mut result = Point {
126        x: Fr::zero(),
127        y: Fr::zero(),
128        is_infinite: true,
129    };
130
131    for bit in bits {
132        result = point_double(&result);
133        if bit {
134            result = point_add(&result, point);
135        }
136    }
137
138    result
139}
140
141/// Recover the canonical Grumpkin affine point from an x-coordinate.
142///
143/// Aztec addresses are the x-coordinate of a point whose y-coordinate is chosen
144/// to be the "positive" one, matching the upstream address derivation path.
145pub fn point_from_x(x: Fr) -> Result<Point, Error> {
146    let x_raw = x.0;
147    let rhs = x_raw * x_raw * x_raw - ArkFr::from(17u64);
148    let y = rhs
149        .sqrt()
150        .ok_or_else(|| Error::InvalidData("address x-coordinate is not on Grumpkin".into()))?;
151    let neg_y = -y;
152    let choose_positive =
153        |candidate: ArkFr| candidate.into_bigint() <= ArkFr::MODULUS_MINUS_ONE_DIV_TWO;
154    let chosen = if choose_positive(y) {
155        y
156    } else if choose_positive(neg_y) {
157        neg_y
158    } else {
159        y
160    };
161
162    Ok(Point {
163        x,
164        y: Fr(chosen),
165        is_infinite: false,
166    })
167}
168
169/// Returns whether the affine point uses Aztec's canonical "positive" y-coordinate.
170pub fn has_positive_y(point: &Point) -> bool {
171    point.y.0.into_bigint() <= ArkFr::MODULUS_MINUS_ONE_DIV_TWO
172}
173
174#[cfg(test)]
175#[allow(clippy::expect_used)]
176mod tests {
177    use super::*;
178
179    #[test]
180    fn generator_is_on_curve() {
181        let g = generator();
182        assert!(!g.is_infinite);
183        // Verify y^2 = x^3 - 17
184        let lhs = g.y.0 * g.y.0;
185        let rhs = g.x.0 * g.x.0 * g.x.0 - ArkFr::from(17u64);
186        assert_eq!(lhs, rhs, "generator must satisfy Grumpkin equation");
187    }
188
189    #[test]
190    fn identity_add() {
191        let g = generator();
192        let inf = Point {
193            x: Fr::zero(),
194            y: Fr::zero(),
195            is_infinite: true,
196        };
197        let result = point_add(&g, &inf);
198        assert_eq!(result, g);
199        let result2 = point_add(&inf, &g);
200        assert_eq!(result2, g);
201    }
202
203    #[test]
204    fn scalar_mul_one() {
205        let g = generator();
206        let result = scalar_mul(&Fq::one(), &g);
207        assert_eq!(result, g);
208    }
209
210    #[test]
211    fn scalar_mul_two_equals_double() {
212        let g = generator();
213        let doubled = point_double(&g);
214        let result = scalar_mul(&Fq::from(2u64), &g);
215        assert_eq!(result, doubled);
216    }
217
218    #[test]
219    fn scalar_mul_zero_returns_infinity() {
220        let g = generator();
221        let result = scalar_mul(&Fq::zero(), &g);
222        assert!(result.is_infinite);
223    }
224
225    #[test]
226    fn point_add_inverse_returns_infinity() {
227        let g = generator();
228        let neg_g = Point {
229            x: g.x,
230            y: Fr(-(g.y.0)),
231            is_infinite: false,
232        };
233        let result = point_add(&g, &neg_g);
234        assert!(result.is_infinite);
235    }
236
237    #[test]
238    fn scalar_mul_associative() {
239        let g = generator();
240        // 3G = G + 2G
241        let two_g = scalar_mul(&Fq::from(2u64), &g);
242        let three_g_add = point_add(&g, &two_g);
243        let three_g_mul = scalar_mul(&Fq::from(3u64), &g);
244        assert_eq!(three_g_add, three_g_mul);
245    }
246
247    #[test]
248    fn result_is_on_curve() {
249        let g = generator();
250        let p = scalar_mul(&Fq::from(12345u64), &g);
251        assert!(!p.is_infinite);
252        let lhs = p.y.0 * p.y.0;
253        let rhs = p.x.0 * p.x.0 * p.x.0 - ArkFr::from(17u64);
254        assert_eq!(lhs, rhs, "scalar_mul result must be on curve");
255    }
256}
aztec_core/grumpkin.rs

aztec_core/
grumpkin.rs
