bsv/primitives/
base_point.rs

1//! Base point (generator) operations with precomputed window tables.
2//!
3//! BasePoint provides optimized scalar multiplication of the secp256k1
4//! generator point G using precomputed tables. This is significantly
5//! faster than general point multiplication for operations like key
6//! generation (privkey * G).
7
8use crate::primitives::big_number::BigNumber;
9use crate::primitives::curve::Curve;
10use crate::primitives::jacobian_point::JacobianPoint;
11use crate::primitives::point::Point;
12
13/// The secp256k1 base point (generator) with precomputed multiplication tables.
14///
15/// Uses a windowed precomputation approach: stores [1*G, 2*G, ..., 2^w * G]
16/// for a chosen window size w, enabling faster scalar multiplication via
17/// the wNAF (windowed non-adjacent form) method.
18pub struct BasePoint {
19    /// Window size for precomputation.
20    window: u32,
21    /// Precomputed odd multiples of G: [G, 3G, 5G, ..., (2^(w-1)-1)*2*G + G].
22    table: Vec<JacobianPoint>,
23    /// Pre-negated table entries for wNAF negative digits.
24    neg_table: Vec<JacobianPoint>,
25}
26
27/// Singleton BasePoint instance.
28static BASE_POINT_INIT: std::sync::OnceLock<BasePoint> = std::sync::OnceLock::new();
29
30impl BasePoint {
31    /// Get the singleton precomputed base point.
32    pub fn instance() -> &'static BasePoint {
33        BASE_POINT_INIT.get_or_init(|| {
34            let window = 5u32;
35            let curve = Curve::secp256k1();
36            let g = JacobianPoint::from_affine(&curve.g_x, &curve.g_y);
37
38            let tbl_size = 1usize << (window - 1); // 16 entries for w=5
39            let mut table = Vec::with_capacity(tbl_size);
40            table.push(g.clone());
41
42            let two_g = g.dbl();
43            for i in 1..tbl_size {
44                table.push(table[i - 1].add(&two_g));
45            }
46
47            let neg_table: Vec<JacobianPoint> = table.iter().map(|p| p.neg()).collect();
48            BasePoint {
49                window,
50                table,
51                neg_table,
52            }
53        })
54    }
55
56    /// Access the precomputed table as a slice (for Shamir's trick).
57    pub fn table(&self) -> &[JacobianPoint] {
58        &self.table
59    }
60
61    /// Multiply the base point G by scalar k.
62    /// This uses the precomputed wNAF table for efficiency.
63    pub fn mul(&self, k: &BigNumber) -> Point {
64        if k.is_zero() {
65            return Point::infinity();
66        }
67
68        let is_neg = k.is_neg();
69        let k_abs = if is_neg { k.neg() } else { k.clone() };
70
71        // Reduce k mod n
72        let curve = Curve::secp256k1();
73        let k_mod = k_abs.umod(&curve.n).unwrap_or(k_abs);
74
75        if k_mod.is_zero() {
76            return Point::infinity();
77        }
78
79        // Build wNAF representation
80        let window = self.window;
81        let mut wnaf: Vec<i32> = Vec::new();
82        let mut k_tmp = k_mod;
83        let w_val = 1i64 << window;
84        let w_half = w_val >> 1;
85
86        while !k_tmp.is_zero() {
87            if k_tmp.is_odd() {
88                let mod_val = k_tmp.andln(window + 1) as i64;
89                let z = if mod_val >= w_half {
90                    mod_val - w_val
91                } else {
92                    mod_val
93                };
94                wnaf.push(z as i32);
95                if z < 0 {
96                    k_tmp = k_tmp.addn(-z);
97                } else if z > 0 {
98                    k_tmp = k_tmp.subn(z);
99                }
100            } else {
101                wnaf.push(0);
102            }
103            k_tmp.iushrn(1);
104        }
105
106        // Accumulate from MSB to LSB using cached neg table
107        let mut q = JacobianPoint::infinity();
108        for i in (0..wnaf.len()).rev() {
109            q = q.dbl();
110            let di = wnaf[i];
111            if di != 0 {
112                let idx = (di.unsigned_abs() as usize) >> 1;
113                if di > 0 {
114                    q = q.add(&self.table[idx]);
115                } else {
116                    q = q.add(&self.neg_table[idx]);
117                }
118            }
119        }
120
121        if q.is_infinity() {
122            return Point::infinity();
123        }
124
125        let (x, y) = q.to_affine();
126        let point = Point::new(x, y);
127
128        if is_neg {
129            point.negate()
130        } else {
131            point
132        }
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use super::*;
139
140    #[test]
141    fn test_base_point_mul_1() {
142        let bp = BasePoint::instance();
143        let result = bp.mul(&BigNumber::one());
144        let curve = Curve::secp256k1();
145        assert_eq!(result.x.cmp(&curve.g_x), 0);
146        assert_eq!(result.y.cmp(&curve.g_y), 0);
147    }
148
149    #[test]
150    fn test_base_point_mul_2() {
151        let bp = BasePoint::instance();
152        let result = bp.mul(&BigNumber::from_number(2));
153        assert_eq!(
154            result.x.to_hex(),
155            "c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5"
156        );
157    }
158
159    #[test]
160    fn test_base_point_mul_n_is_infinity() {
161        let bp = BasePoint::instance();
162        let curve = Curve::secp256k1();
163        let result = bp.mul(&curve.n);
164        assert!(result.is_infinity());
165    }
166
167    #[test]
168    fn test_base_point_mul_matches_point_mul() {
169        let bp = BasePoint::instance();
170        let curve = Curve::secp256k1();
171        let g = curve.generator();
172
173        for k_val in [3, 7, 10, 42, 100] {
174            let k = BigNumber::from_number(k_val);
175            let bp_result = bp.mul(&k);
176            let p_result = g.mul(&k);
177            assert!(
178                bp_result.eq(&p_result),
179                "BasePoint.mul mismatch for k={}",
180                k_val
181            );
182        }
183    }
184
185    #[test]
186    fn test_base_point_mul_known_vectors() {
187        let bp = BasePoint::instance();
188        let expected = vec![
189            (
190                5,
191                "2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4",
192                "d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6",
193            ),
194            (
195                10,
196                "a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7",
197                "893aba425419bc27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7",
198            ),
199        ];
200
201        for (k, ex, ey) in expected {
202            let result = bp.mul(&BigNumber::from_number(k));
203            assert_eq!(result.x.to_hex(), ex, "x mismatch for k={}", k);
204            assert_eq!(result.y.to_hex(), ey, "y mismatch for k={}", k);
205        }
206    }
207
208    #[test]
209    fn test_base_point_mul_zero() {
210        let bp = BasePoint::instance();
211        let result = bp.mul(&BigNumber::zero());
212        assert!(result.is_infinity());
213    }
214
215    #[test]
216    fn test_base_point_mul_large_scalar() {
217        // Use a large random-ish scalar
218        let bp = BasePoint::instance();
219        let k =
220            BigNumber::from_hex("deadbeef0123456789abcdef0123456789abcdef0123456789abcdef01234567")
221                .unwrap();
222        let result = bp.mul(&k);
223        assert!(!result.is_infinity());
224        assert!(result.validate());
225    }
226}
bsv/primitives/base_point.rs

bsv/primitives/
base_point.rs
